ニュートン法

数値解析の分野において、ニュートン法（ニュートンほう、Newton's method）またはニュートン・ラフソン法（Newton-Raphson method）は、方程式系を数値計算によって解くための反復法による求根アルゴリズムの1つである。対象とする方程式系に対する条件は、領域における微分可能性と2次微分に関する符号だけであり、線型性などは特に要求しない。収束の速さも2次収束なので古くから数値計算で使用されていた。名称はアイザック・ニュートンとジョゼフ・ラフソン（英語版）に由来する。 この方法の考え方は以下のようである：まず初めに、予想される真の解に近いと思われる値をひとつとる。次に、そこでグラフの接線を考え、その x 切片を計算する。このx切片の値は、予想される真の解により近いものとなるのが一般である。以後、この値に対してそこでグラフの接線を考え、同じ操作を繰り返していく。 上の考え方は次のように定式化される。 ここでは、考える問題を f: R → R, x ∈ Rとして f ( x ) = 0 {\displaystyle f(x)=0\,} となる x を求めることに限定する。このとき、x の付近に適当な値 x0 をとり、次の漸化式によって、x に収束する数列を得ることができる場合が多い。 x n + 1 = x n − f ( x n ) f ′ ( x n ) ⋯ ( 1 ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\quad \cdots (1)} 例として、√2 を計算で求める場合に、 f ( x ) = x 2 − 2 {\displaystyle f(x)=x^{2}-2\,} とおき、f(x) = 0 の解を求めることを考える。 f ′ ( x ) = 2 x {\displaystyle f'(x)=2x\,} であるので、(1) の式は x n + 1 = x n − x n 2 − 2 2 x n = 1 2 ( x n + 2 x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {x_{n}^{2}-2}{2x_{n}}}={\frac {1}{2}}\left(x_{n}+{\frac {2}{x_{n}}}\right)} と書き表せる。たとえば x0 = 1 とおくと、この数列は √2 に収束し、x0 = -1 とおくと、この数列は -√2 に収束する。 初期値 x 0 {\displaystyle x_{0}} を解の十分近くに選ぶことを要求した上で、 f ( x ) = 0 {\displaystyle f(x)=0\,} の解を考える（解の存在を仮定する）。 f ( x ) {\displaystyle f(x)} の x = x 0 {\displaystyle x=x_{0}} でのテーラー展開をすると f ( x ) = f ( x 0 ) + f ′ ( x 0 ) ( x − x 0 ) + O ( ( x − x 0 ) 2 ) {\displaystyle f(x)=f(x_{0})+f^{\prime }(x_{0})(x-x_{0})+O((x-x_{0})^{2})} このとき、(右辺)=0の解は、(左辺)=0の根の x 0 {\displaystyle x_{0}} での多項式次数一次の近似となっている。 右辺の解は x = x 0 − f ( x 0 ) f ′ ( x 0 ) {\displaystyle x=x_{0}-{\frac {f(x_{0})}{f^{\prime }(x_{0})}}} 次に、この近似値が、 x 0 {\displaystyle x_{0}} より根に近づいている ということに関する意味を考える。 上式を、次のような離散力学系として考える。 x n + 1 = g ( x n ) {\displaystyle x_{n+1}=g(x_{n})} , ただし g ( x ) = x − f ( x ) f ′ ( x ) {\displaystyle g(x)=x-{\frac {f(x)}{f'(x)}}} この力学系において、 f ( x ∗ ) = 0 {\displaystyle f(x^{*})=0} となる x ∗ {\displaystyle x^{*}} は明らかに固定点である。 したがって | g ′ ( x ∗ ) | < 1 {\displaystyle |g'(x^{*})|<1} 、つまり x ∗ {\displaystyle x^{*}} が沈点(アトラクター、安定固定点)であり、 与えられた初期条件 x 0 {\displaystyle x_{0}} が、このアトラクターの吸引領域に属していれば x n {\displaystyle x_{n}} の ω {\displaystyle \omega } -極限( n → ∞ {\displaystyle n\rightarrow \infty } )は f ( x ∗ ) = 0 {\displaystyle f(x^{*})=0} となる x ∗ {\displaystyle x^{*}} に収束する。 x ∗ {\displaystyle x^{*}} が沈点である保証は、常に担保されてはいない。 例えばx軸の漸近線や関数 f ( x ) {\displaystyle f(x)} の極値近傍では固定点が不安定になる事が知られている。 たとえば f ( x ∗ ) {\displaystyle f(x^{*})} を、適当な近傍の点 x n {\displaystyle x_{n}} で展開すると f ′ ( x ∗ ) ≠ 0 {\displaystyle f'(x^{*})\neq 0} なら、二次の余剰項 R 2 = f ″ ( ξ n ) 2 ( x n − x ∗ ) 2 {\displaystyle R_{2}={\frac {f''(\xi _{n})}{2}}(x_{n}-x^{*})^{2}} として x n + 1 − x ∗ = − f ″ ( ξ n ) 2 f ′ ( x n ) ( x n − x ∗ ) 2 {\displaystyle x_{n+1}-x^{*}=-{\frac {f''(\xi _{n})}{2f'(x_{n})}}(x_{n}-x^{*})^{2}} よって２次で収束する。 前節では解の存在を仮定した上で初期値 x 0 {\displaystyle x_{0}} を解の十分近くに選ぶことを要求した。これに対して、解の存在を仮定せず、初期値 x 0 {\displaystyle x_{0}} がある条件を満たすときに解の存在と反復の収束を示す定理を半局所収束定理（Semi-Local Convergence Theorem）という。1次元の場合での半局所収束定理はコーシーによって1829年に示され、 n {\displaystyle n} 次元ユークリッド空間での場合はファイン（Fine）によって1916年に示された。その後、バナッハ空間での半局所収束定理がカントロビッチ（Kantorovich）によって1948年に示され、現代ではニュートン-カントロビッチの定理と呼ばれている。この定理にはいくつかの変種が知られており、にまとめられている。 ニュートン法は、接線を一次近似式、接線のx切片を一次近似式の零点と考えることにより、より高次元の関数の場合に一般化できる。 対象となる関数を f: Rm → Rm, x ∈ Rm とし、 f ( x ) = 0 {\displaystyle f(\mathbf {x} )=\mathbf {0} } なる点 x を求めるには次のようにする。（f が同じ次元の空間の間の関数であることに注意せよ。） まず、今 x0 ∈ Rm が既知であるとする。x0における f(x) の一次近似式 f ( x 0 ) + ∂ f ( x 0 ) ( x − x 0 ) {\displaystyle f(\mathbf {x} _{0})+\partial f(\mathbf {x} _{0})(\mathbf {x} -\mathbf {x} _{0})} を考える。ただし、∂f(x0) は、m × m のヤコビ行列である。 この一次近似式の零点を求める。ヤコビ行列∂f(x0) が正則行列であるとして、 f ( x 0 ) + ∂ f ( x 0 ) ( x − x 0 ) = 0 {\displaystyle f(\mathbf {x} _{0})+\partial f(\mathbf {x} _{0})(\mathbf {x} -\mathbf {x} _{0})=\mathbf {0} } を解いて、 x = x 0 − ∂ f ( x 0 ) − 1 f ( x 0 ) {\displaystyle \mathbf {x} =\mathbf {x} _{0}-\partial f(\mathbf {x} _{0})^{-1}f(\mathbf {x} _{0})} となる。 コンピュータで計算を行う場合 ∂f(x0)-1f(x0) を直接求めることは困難なので、 ∂ f ( x 0 ) r = f ( x 0 ) {\displaystyle \partial f(\mathbf {x} _{0})\mathbf {r} =f(\mathbf {x} _{0})} という方程式をガウスの消去法などの解法によって線形方程式系を解き r を求め、x = x0 - r によって x を求める。 ここで求めた x はx0よりも f(x) = 0 の解に近いことが見込まれる。そこで、今求めた x を x1 として、再び同様の計算を繰り返す。計算を繰り返すことによって xn は f(x) = 0 の解に近づいていく。 逆行列を求めることを避けるために共役勾配法を用いることがある。 ニュートン法により近似値を求めようとする場合にはヤコビ行列が陽に分からなければ計算できない。しかし、関数 f によってはヤコビ行列が陽に分からない場合もある。この場合にはヤコビ行列を必要としない準ニュートン法を用いる。 また、f (x*) = 0 を満たす真の解 x* において導関数が f '(x*) = 0 であった場合、収束の速さは1次に退化する。 ニュートン法の考え方を少し改良することにより、(1) の代わりに次の式を用いる方法を得る。 x k + 1 = x k − [ f ( x k ) ] 2 f ′ ( x k ) [ f ( x k ) − f ( x k − f ( x k ) f ′ ( x k ) ) ] {\displaystyle x_{k+1}=x_{k}-{\frac {{\Bigl [}f(x_{k}){\Bigr ]}^{2}}{\;f^{\boldsymbol {\prime }}(x_{k}){\Bigl [}f(x_{k})-f{\Bigl (}x_{k}-{\dfrac {f(x_{k})}{f^{\boldsymbol {\prime }}(x_{k})}}{\Bigr )}{\Bigr ]}\;}}} この方法は、場合によっては従来の方法より速い。 ニュートン法の局所的な２次収束性を保ちつつ、不安定な振る舞いを抑えるように工夫した方法として平野の変形ニュートン法が知られている。 ニュートン法における導関数の計算を簡略化したものが簡易ニュートン法である: x n + 1 = x n − f ( x n ) f ′ ( x 0 ) . {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{0})}}.} 簡易ニュートン法に対する半局所収束定理は占部の定理として知られる。占部の定理は元々数学的帰納法を使って示されたが、その後、バナッハの不動点定理を使った別証明が与えられた。 簡易ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発された簡易ニュートン法の変種がクラフチック（Krawczyk）法である。 ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発されたニュートン法の変種が区間ニュートン法である。 ニュートン法において微分の代わりに微分のq-類似（ q {\displaystyle q} -微分）を使う反復を q {\displaystyle q} -ニュートン法という: x n + 1 = x n − f ( x n ) D q ( x n ) . {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{D_{q}(x_{n})}}.} q {\displaystyle q} -ニュートン法に対する半局所収束定理が q {\displaystyle q} -ニュートン-カントロビッチの定理である。 ^ Newton's Method(Wolfram Math World), http://mathworld.wolfram.com/NewtonsMethod.html 2010年6月8日閲覧。  ^ 数値解析入門（増訂版）、山本哲郎、サイエンス社、2003年。 ^ J. Ortega & W. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press (1970). ^ 小澤一文 『Cで学ぶ数値計算アルゴリズム』 共立出版、2008年、49頁。ISBN 978-4-320-12221-5。  ^ 長島隆廣「ニュートン近似の改良」数学セミナー1980年5月号 p.112、日本評論社 ^ 室田一雄「平野の変形Newton法の大域的収束性」数理解析研究所講究録 (1981), 422: 104-118 ^ 非線形解析入門、大石進一、コロナ社、1997年。 ^ 精度保証付き数値計算、大石進一、コロナ社、2000年。 ^ Interval Newton Method ^ Rajković, P., Stanković, M., & Marinković D, S. (2002). Mean value theorems in g-calculus. Matematički vesnik, 54(3-4), 171-178. ^ 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. 除算 (デジタル) ガウス・ニュートン法 Newton法とその周辺