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

テンプレート:参照方法 ニュートン＝カントロビッチの定理（ニュートン＝カントロビッチのていり）は、ニュートン法に対する半局所収束定理であり、1948年にレオニート・カントロヴィチによって示された。バナッハ空間においても成立して、楕円型PDE・非線形方程式の解に対する精度保証付き数値計算で活用されているだけでなく、線形計画問題の精度保証付き数値解法にも応用される。 ニュートン法は特定の条件で方程式f(x)=0もしくは方程式系F(x)=0の解に収束する数列を生成する。ニュートン＝カントロビッチの定理はこの数列の初期値に条件を与え、その条件が満たされたときに初期値の近くに解が存在して数列が解に収束することを主張している。

仮定

$X\subset {ℝ}^n$を開集合として、$F:{ℝ}^n\supset X\to {ℝ}^n$を微分可能関数で局所的にリプシッツ連続であるとする。つまり、いかなる開集合$U\subset X$ に対しても定数$L>0$が存在して、任意の$𝐱,𝐲\in U$に対して

$\Vert F^{\prime }(𝐱)-F^{\prime }(𝐲)\Vert \le L\Vert 𝐱-𝐲\Vert$

が成り立ち、任意の$𝐯\in {ℝ}^n$ に対して不等式：

$\Vert F^{\prime }(𝐱)(𝐯)-F^{\prime }(𝐲)(𝐯)\Vert \le L\Vert 𝐱-𝐲\Vert \Vert 𝐯\Vert$

が成立することを意味する。 いま、任意の初期値${𝐱}_0\in X$を選択し、 $F^{\prime }({𝐱}_0)$が可逆であると仮定して、ニュートン反復: ${𝐡}_0=-F^{\prime }({𝐱}_0{)}^{-1}F({𝐱}_0).$ を構成する。 次の仮定は${𝐱}_1={𝐱}_0+{𝐡}_0$だけでなく球全体$B({𝐱}_1,\Vert {𝐡}_0\Vert )$が集合Xに包含されていることを要求する。さらに、$M\le L$をこの球におけるヤコビアンに対するリプシッツ定数であるとする。 最後の準備として、数列$({𝐱}_k{)}_k$, $({𝐡}_k{)}_k$, $({\alpha }_k{)}_k$ を帰納的に以下の通りで定める：

$\begin{array}{cc}{𝐡}_k& =-F^{\prime }({𝐱}_k{)}^{-1}F({𝐱}_k)\\ {\alpha }_k& =M\Vert F^{\prime }({𝐱}_k{)}^{-1}\Vert \Vert {𝐡}_k\Vert \\ {𝐱}_{k+1}& ={𝐱}_k+{𝐡}_k.\end{array}$

主張

上記の仮定の下で${\alpha }_0\le \frac{1}{2}$のとき、

1. $F({𝐱}^{\ast })=0$の解${𝐱}^{\ast }$が球$\overline{B}({𝐱}_1,\Vert {𝐡}_0\Vert )$内に存在する。
2. ${𝐱}_0$で始まるニュートン反復が${𝐱}^{\ast }$に少なくとも線形オーダーで収束する。

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

$p(t)=(\frac{1}{2}L\Vert F^{\prime }({𝐱}_0{)}^{-1}{\Vert }^{-1})t^2-t+\Vert {𝐡}_0\Vert$,

$t^{\ast /\ast \ast }=\frac{2\Vert {𝐡}_0\Vert }{1\pm \sqrt{1-2\alpha }}$

の解（ただし$t^{\ast }\le t^{\ast \ast }$）とその比：

$\theta =\frac{t^{\ast }}{t^{\ast \ast }}=\frac{1-\sqrt{1-2\alpha }}{1+\sqrt{1-2\alpha }}.$

を用いる。このとき

1. 解${𝐱}^{\ast }$は閉球$\overline{B}({𝐱}_1,\theta \Vert {𝐡}_0\Vert )\subset \overline{B}({𝐱}_0,t^{\ast })$内に存在する。
2. より大きい球$B({𝐱}_0,t^{\ast \ast })$の中で一意存在する。
3. さらに、$F$の解への収束は多項式$p(t)$に対するニュートン反復の最も小さい根$t^{\ast }$への収束に支配される。もし$t_0=0,t_{k+1}=t_k-\frac{p(t_k)}{p^{\prime }(t_k)}$ならば

   $\Vert {𝐱}_{k+p}-{𝐱}_k\Vert \le t_{k+p}-t_k.$である。

4. 2次収束は誤差評価：

   $\Vert {𝐱}_{n+1}-{𝐱}^{\ast }\Vert \le {\theta }^{2^n}\Vert {𝐱}_{n+1}-{𝐱}_n\Vert \le \frac{{\theta }^{2^n}}{2^n}\Vert {𝐡}_0\Vert .$

から得られる。

系

山本哲朗は1986年にDoring(1969)、Ostrowski(1971, 1973)、Gragg-Tapia(1974)、Potra-Ptak(1980)、Miel(1981)、Potra(1984)等によって得られたニュートン法の誤差限界は全て全順序で優劣がつけられて、しかもそれらはニュートン＝カントロビッチの定理から導かれることを示した。

変種・一般化

ニュートン＝カントロビッチの定理についてはq-類似が知られている。また、M. Plumによって似たような定理が示されている。その他の変種・一般化についてはOrtega-Rheinboldt(1970)が詳しい。

参考文献

• 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, テンプレート:ISBN2 (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.