ニュートン＝カントロビッチの定理

ニュートン＝カントロビッチの定理（ニュートン＝カントロビッチのていり）は、ニュートン法に対する半局所収束定理であり、1948年にレオニート・カントロヴィチによって示された杉原正顯, & 室田一雄. (1994). 数値計算法の数理. 岩波書店.。バナッハ空間においても成立して、楕円型PDE・非線形方程式の解に対する精度保証付き数値計算で活用されているだけでなく、線形計画問題の精度保証付き数値解法にも応用されるOishi, S., & Tanabe, K. (2009). Numerical Inclusion of Optimum Point for Linear Programming. JSIAM Letters, 1, 5-8.。
ニュートン法は特定の条件で方程式  もしくは方程式系  の解に収束する数列を生成する。ニュートン＝カントロビッチの定理はこの数列の初期値に条件を与え、その条件が満たされたときに初期値の近くに解が存在して数列が解に収束することを主張している。

 仮定 
を開集合として、を微分可能関数で局所的にリプシッツ連続であるとする。つまり、いかなる開集合 に対しても定数が存在して、任意のに対して

が成り立ち、任意の
に対して不等式：

が成立することを意味する。
いま、任意の初期値を選択し、
が可逆であると仮定して、ニュートン反復:

を構成する。
次の仮定はだけでなく球全体が集合Xに包含されていることを要求する。さらに、をこの球におけるヤコビアンに対するリプシッツ定数であるとする。
最後の準備として、数列, ,  を帰納的に以下の通りで定める：

 主張 
上記の仮定の下でのとき、
の解が球内に存在する。
で始まるニュートン反復がに少なくとも線形オーダーで収束する。

より精密だが証明が難しい主張は多項式：
,

の解（ただし）とその比：

を用いる。このとき
解は閉球内に存在する。
より大きい球の中で一意存在する。
さらに、の解への収束は多項式に対するニュートン反復の最も小さい根への収束に支配される。もしならば
である。
2次収束は誤差評価：

から得られる。

 系 
山本哲朗は1986年にDoring(1969)、Ostrowski(1971, 1973)A. M. Ostrowski, “La method de Newton dans les espaces de Banach,” C. R. Acad. Sei. Paris, 27 (A) (1971), 1251–1253.A. M. Ostrowski, Solution of Equations in Euclidean and Banach Spaces, Academic Press, New York, 1973.、Gragg-Tapia(1974)、Potra-Ptak(1980)F. A. Potra and V. Ptak, “Sharp error bounds for Newton’s process,” Numer. Math., 34 (1980), 63–72.、Miel(1981)G. J. Miel, “An updated version of the Kantorovich theorem for Newton’s method,” Computing, 27 (1981), 237–244.、Potra(1984)F. A. Potra, “On the a posteriori error estimates for Newton’s method,” Beiträge zur Numerische Mathematik, 12 (1984), 125–138.等によって得られたニュートン法の誤差限界は全て全順序で優劣がつけられて、しかもそれらはニュートン＝カントロビッチの定理から導かれることを示したYamamoto, T. (1986). A method for finding sharp error bounds for Newton's method under the Kantorovich assumptions. Numerische Mathematik, 49(2-3), 203-220.。

 変種・一般化 
ニュートン＝カントロビッチの定理についてはq-類似が知られているRajkovic, P. M., Stankovic, M. S., & Marinkovic, S. D. (2003). On q-iterative methods for solving equations and systems. Novi Sad J. Math, 33(2), 127-137.Rajković, P. M., Marinković, S. D., & Stanković, M. S. (2005). On q-Newton–Kantorovich method for solving systems of equations. Applied Mathematics and Computation, 168(2), 1432-1448.。また、M. Plumによって似たような定理が示されている。その他の変種・一般化についてはOrtega-Rheinboldt(1970)Ortega, J. M., & Rheinboldt, W. C. (1970). Iterative Solution of Nonlinear Equations in Several Variables. SIAM.が詳しい。

 脚注 

 参考文献 
 Kantorovich, L. W.; Akilov, G. P. (1964): Functional Analysis in Normed Spaces.
 Deuflhard, P.: Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms., Springer, Berlin 2004,  (Springer Series in Computational Mathematics, Vol. 35)
 Deuflhard, P., & Heindl, G. (1979). Affine invariant convergence theorems for Newton’s method and extensions to related methods. :en:SIAM Journal on Numerical Analysis, 16(1), 1-10.
 Rall, L. B. (1969). Computational solution of nonlinear operator equations. Wiley.

Category:アルゴリズム
Category:応用数学
Category:数値解析
Category:数学に関する記事
Category:関数解析学の定理
Category:数学のエポニム