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

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

仮定

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

‖ F ′ ( x ) − F ′ ( y ) ‖ ≤ L ‖ x − y ‖ {\displaystyle \|F'(\mathbf {x} )-F'(\mathbf {y} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|}

が成り立ち、任意の v ∈ R n {\displaystyle \mathbf {v} \in \mathbb {R} ^{n}} に対して不等式：

‖ F ′ ( x ) ( v ) − F ′ ( y ) ( v ) ‖ ≤ L ‖ x − y ‖ ‖ v ‖ {\displaystyle \|F'(\mathbf {x} )(\mathbf {v} )-F'(\mathbf {y} )(\mathbf {v} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|\,\|\mathbf {v} \|}

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

h k = − F ′ ( x k ) − 1 F ( x k ) α k = M ‖ F ′ ( x k ) − 1 ‖ ‖ h k ‖ x k + 1 = x k + h k . {\displaystyle {\begin{alignedat}{2}\mathbf {h} _{k}&=-F'(\mathbf {x} _{k})^{-1}F(\mathbf {x} _{k})\\[0.4em]\alpha _{k}&=M\,\|F'(\mathbf {x} _{k})^{-1}\|\,\|\mathbf {h} _{k}\|\\[0.4em]\mathbf {x} _{k+1}&=\mathbf {x} _{k}+\mathbf {h} _{k}.\end{alignedat}}}

主張

上記の仮定の下で α 0 ≤ 1 2 {\displaystyle \alpha _{0}\leq {\tfrac {1}{2}}} のとき、

  1. F ( x ∗ ) = 0 {\displaystyle F(\mathbf {x} ^{*})=0} の解 x ∗ {\displaystyle \mathbf {x} ^{*}} が球 B ¯ ( x 1 , ‖ h 0 ‖ ) {\displaystyle {\bar {B}}(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)} 内に存在する。
  2. x 0 {\displaystyle \mathbf {x} _{0}} で始まるニュートン反復が x ∗ {\displaystyle \mathbf {x} ^{*}} に少なくとも線形オーダーで収束する。

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

p ( t ) = ( 1 2 L ‖ F ′ ( x 0 ) − 1 ‖ − 1 ) t 2 − t + ‖ h 0 ‖ {\displaystyle p(t)=\left({\tfrac {1}{2}}L\|F'(\mathbf {x} _{0})^{-1}\|^{-1}\right)t^{2}-t+\|\mathbf {h} _{0}\|} ,
t ∗ / ∗ ∗ = 2 ‖ h 0 ‖ 1 ± 1 − 2 α {\displaystyle t^{\ast /**}={\frac {2\|\mathbf {h} _{0}\|}{1\pm {\sqrt {1-2\alpha }}}}}

の解（ただし t ∗ ≤ t ∗ ∗ {\displaystyle t^{\ast }\leq t^{**}} ）とその比：

θ = t ∗ t ∗ ∗ = 1 − 1 − 2 α 1 + 1 − 2 α . {\displaystyle \theta ={\frac {t^{*}}{t^{**}}}={\frac {1-{\sqrt {1-2\alpha }}}{1+{\sqrt {1-2\alpha }}}}.}

を用いる。このとき

  1. 解 x ∗ {\displaystyle \mathbf {x} ^{*}} は閉球 B ¯ ( x 1 , θ ‖ h 0 ‖ ) ⊂ B ¯ ( x 0 , t ∗ ) {\displaystyle {\bar {B}}(\mathbf {x} _{1},\theta \|\mathbf {h} _{0}\|)\subset {\bar {B}}(\mathbf {x} _{0},t^{*})} 内に存在する。
  2. より大きい球 B ( x 0 , t ∗ ∗ ) {\displaystyle B(\mathbf {x} _{0},t^{*\ast })} の中で一意存在する。
  3. さらに、 F {\displaystyle F} の解への収束は多項式 p ( t ) {\displaystyle p(t)} に対するニュートン反復の最も小さい根 t ∗ {\displaystyle t^{\ast }} への収束に支配される[6]。もし t 0 = 0 , t k + 1 = t k − p ( t k ) p ′ ( t k ) {\displaystyle t_{0}=0,\,t_{k+1}=t_{k}-{\tfrac {p(t_{k})}{p'(t_{k})}}} ならば
    ‖ x k + p − x k ‖ ≤ t k + p − t k . {\displaystyle \|\mathbf {x} _{k+p}-\mathbf {x} _{k}\|\leq t_{k+p}-t_{k}.} である。
  4. 2次収束は誤差評価[7]：
    ‖ x n + 1 − x ∗ ‖ ≤ θ 2 n ‖ x n + 1 − x n ‖ ≤ θ 2 n 2 n ‖ h 0 ‖ . {\displaystyle \|\mathbf {x} _{n+1}-\mathbf {x} ^{*}\|\leq \theta ^{2^{n}}\|\mathbf {x} _{n+1}-\mathbf {x} _{n}\|\leq {\frac {\theta ^{2^{n}}}{2^{n}}}\|\mathbf {h} _{0}\|.}

から得られる。

系

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

変種・一般化

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

脚注

[脚注の使い方]
  1. ^ a b c d e 大石進一（編著）『精度保証付き数値計算の基礎』コロナ社、2018年7月。ISBN 978-4-339-02887-4。 
  2. ^ a b c d 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ 現代数学への入門 14〉、2003年6月。ISBN 4-7819-1038-6。 
  3. ^ a b c 山本哲朗「Newton法とその周辺」『数学』第37巻第1号、1985年、1-15頁、doi:10.11429/sugaku1947.37.1。 
  4. ^ a b c 杉原正顯, & 室田一雄. (1994). 数値計算法の数理. 岩波書店.
  5. ^ Oishi, S., & Tanabe, K. (2009). Numerical Inclusion of Optimum Point for Linear Programming. JSIAM Letters, 1, 5-8.
  6. ^ Ortega, J. M. (1968). “The Newton-Kantorovich Theorem”. Amer. Math. Monthly 75 (6): 658–660. doi:10.2307/2313800. JSTOR 2313800. 
  7. ^ Gragg, W. B.; Tapia, R. A. (1974). “Optimal Error Bounds for the Newton-Kantorovich Theorem”. SIAM Journal on Numerical Analysis 11 (1): 10–13. doi:10.1137/0711002. JSTOR 2156425. 
  8. ^ A. M. Ostrowski, “La method de Newton dans les espaces de Banach,” C. R. Acad. Sei. Paris, 27 (A) (1971), 1251–1253.
  9. ^ A. M. Ostrowski, Solution of Equations in Euclidean and Banach Spaces, Academic Press, New York, 1973.
  10. ^ F. A. Potra and V. Ptak, “Sharp error bounds for Newton’s process,” Numer. Math., 34 (1980), 63–72.
  11. ^ G. J. Miel, “An updated version of the Kantorovich theorem for Newton’s method,” Computing, 27 (1981), 237–244.
  12. ^ F. A. Potra, “On the a posteriori error estimates for Newton’s method,” Beiträge zur Numerische Mathematik, 12 (1984), 125–138.
  13. ^ 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.
  14. ^ 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.
  15. ^ 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.
  16. ^ 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, ISBN 3-540-21099-7 (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.