ニュートン法

数値解析の分野において、ニュートン法（ニュートンほう、英: Newton's method）またはニュートン・ラフソン法（英: Newton–Raphson method）は、方程式系を数値計算によって解くための反復法による求根アルゴリズムの1つである。対象とする方程式系に対する条件は、領域における微分可能性と2次微分に関する符号だけであり、線型性などは特に要求しない。収束の速さも2次収束なので古くから数値計算で使用されていた。名称はアイザック・ニュートンとジョゼフ・ラフソンに由来する。

導入

この方法の考え方は以下のようである：まず初めに、予想される真の解に近いと思われる値をひとつとる。次に、そこでグラフの接線を考え、その x 切片を計算する。このx切片の値は、予想される真の解により近いものとなるのが一般である。以後、この値に対してそこでグラフの接線を考え、同じ操作を繰り返していく。

上の考え方は次のように定式化される。ここでは、考える問題を f: R → R, x ∈ Rとして

f(x)=0\,

となる x を求めることに限定する。このとき、x の付近に適当な値 x₀ をとり、次の漸化式によって、x に収束する数列を得ることができる場合が多い。

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\quad \cdots (1)

例として、 ${\sqrt {2}}$ を計算で求める場合に、

f(x)=x^{2}-2\,

とおき、f(x) = 0 の解を求めることを考える。

f'(x)=2x\,

であるので、(1) の式は

x_{n+1}=x_{n}-{\frac {x_{n}^{2}-2}{2x_{n}}}={\frac {1}{2}}\left(x_{n}+{\frac {2}{x_{n}}}\right)

と書き表せる。たとえば x₀ = 2 とおくと、この数列は ${\sqrt {2}}$ に収束するが、その収束の仕方は

x₀ = 2

x₁ = 1.5

x₂ = 1.416666…

x₃ = 1.4142156862745…

x₄ = 1.4142135623746899… (下線部は

{\sqrt {2}}

と一致する部分)

となる。

また、x₀ = −1 とおくと、この数列は $-{\sqrt {2}}$ に収束する。

理論

局所収束定理

初期値 $x_{0}$ を解の十分近くに選ぶことを要求した上で、

f(x)=0\,

の解を考える（解の存在を仮定する）。 $f(x)$ の $x=x_{0}$ でのテーラー展開をすると

f(x)=f(x_{0})+f^{\prime }(x_{0})(x-x_{0})+O((x-x_{0})^{2})

このとき、(右辺)=0の解は、(左辺)=0の根の $x_{0}$ での多項式次数一次の近似となっている。右辺の解は

x=x_{0}-{\frac {f(x_{0})}{f^{\prime }(x_{0})}}

次に、この近似値が、 $x_{0}$ より根に近づいているということに関する意味を考える。上式を、次のような離散力学系として考える。

x_{n+1}=g(x_{n})

, ただし

g(x)=x-{\frac {f(x)}{f'(x)}}

この力学系において、 $f(x^{*})=0$ となる $x^{*}$ は明らかに固定点である。

したがって $|g'(x^{*})|<1$ 、つまり $x^{*}$ が沈点(アトラクター、安定固定点)であり、与えられた初期条件 $x_{0}$ が、このアトラクターの吸引領域に属していれば $x_{n}$ の $\omega$ -極限( $n\rightarrow \infty$ )は $f(x^{*})=0$ となる $x^{*}$ に収束する。

$x^{*}$ が沈点である保証は、常に担保されてはいない。例えばx軸の漸近線や関数 $f(x)$ の極値近傍では固定点が不安定になる事が知られている。 ^[1]

たとえば $f(x^{*})$ を、適当な近傍の点 $x_{n}$ で展開すると $f'(x^{*})\neq 0$ なら、二次の余剰項 $R_{2}={\frac {f''(\xi _{n})}{2}}(x_{n}-x^{*})^{2}$ として

$x_{n+1}-x^{*}=-{\frac {f''(\xi _{n})}{2f'(x_{n})}}(x_{n}-x^{*})^{2}$

よって２次で収束する。

半局所収束定理

→「ニュートン＝カントロビッチの定理」も参照

前節では解の存在を仮定した上で初期値 $x_{0}$ を解の十分近くに選ぶことを要求した。これに対して、解の存在を仮定せず、初期値 $x_{0}$ がある条件を満たすときに解の存在と反復の収束を示す定理を半局所収束定理（semi-local convergence theorem）という。1次元の場合での半局所収束定理はコーシーによって1829年に示され、 $n$ 次元ユークリッド空間での場合はファイン^[2]によって1916年に示された。その後、バナッハ空間での半局所収束定理がカントロヴィチによって1948年に示され、現代ではニュートン＝カントロヴィチの定理と呼ばれている^[3]。この定理にはいくつかの変種が知られており、(Ortega & Rheinboldt 1970)^[4]にまとめられている。

高次元の場合

ニュートン法は、接線を一次近似式、接線のx切片を一次近似式の零点と考えることにより、より高次元の関数の場合に一般化できる。対象となる関数を f: R^m → R^m, x ∈ R^m とし、

f(\mathbf {x} )=\mathbf {0}

なる点 x を求めるには次のようにする。（f が同じ次元の空間の間の関数であることに注意せよ。）

まず、今 x₀ ∈ R^m が既知であるとする。x₀における f(x) の一次近似式

f(\mathbf {x} _{0})+\partial f(\mathbf {x} _{0})(\mathbf {x} -\mathbf {x} _{0})

を考える。ただし、∂f(x₀) は、m × m のヤコビ行列である。

この一次近似式の零点を求める。ヤコビ行列∂f(x₀) が正則行列であるとして、

f(\mathbf {x} _{0})+\partial f(\mathbf {x} _{0})(\mathbf {x} -\mathbf {x} _{0})=\mathbf {0}

を解いて、

\mathbf {x} =\mathbf {x} _{0}-\partial f(\mathbf {x} _{0})^{-1}f(\mathbf {x} _{0})

となる。

コンピュータで計算を行う場合 ∂f(x₀)^-1f(x₀) を直接求めることは困難なので、

\partial f(\mathbf {x} _{0})\mathbf {r} =f(\mathbf {x} _{0})

という方程式をガウスの消去法などの解法によって線形方程式系を解き r を求め、x = x₀ - r によって x を求める。

ここで求めた x はx₀よりも f(x) = 0 の解に近いことが見込まれる。そこで、今求めた x を x₁ として、再び同様の計算を繰り返す。計算を繰り返すことによって x_n は f(x) = 0 の解に近づいていく。

逆行列を求めることを避けるために共役勾配法を用いることがある。

注意

ニュートン法により近似値を求めようとする場合にはヤコビ行列が陽に分からなければ計算できない。しかし、関数 f によってはヤコビ行列が陽に分からない場合もある。この場合にはヤコビ行列を必要としない準ニュートン法を用いる。

また、 $f (x *) = 0$ を満たす真の解 $x *$ において導関数が $f'(x *) = 0$ であった場合、収束の速さは1次に退化する^[5]。

改良

ニュートン法の考え方を少し改良することにより、(1) の代わりに次の式を用いる方法を得る。

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 ]}\;}}

この方法は、場合によっては従来の方法より速い^[6]。

平野の変形ニュートン法

ニュートン法の局所的な２次収束性を保ちつつ、不安定な振る舞いを抑えるように工夫した方法として平野の変形ニュートン法が知られている^[7]。

簡易ニュートン法

ニュートン法における導関数の計算を簡略化したものが簡易ニュートン法である:

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{0})}}.

簡易ニュートン法に対する半局所収束定理は占部の定理として知られる。占部の定理は元々数学的帰納法を使って示されたが、その後、バナッハの不動点定理を使った別証明が与えられた^[8]。

クラフチック法

簡易ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発された簡易ニュートン法の変種がクラフチック（Krawczyk）法である^[9]^[10]。

区間ニュートン法

→詳細は「区間ニュートン法」を参照

ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発されたニュートン法の変種が区間ニュートン法である^[11]。

$q$ -ニュートン法

ニュートン法において微分の代わりに微分のq-類似（ $q$ -微分）を使う反復を $q$ -ニュートン法という^[12]:

x_{n+1}=x_{n}-{\frac {f(x_{n})}{D_{q}(x_{n})}}.

$q$ -ニュートン法に対する半局所収束定理が $q$ -ニュートン-カントロビッチの定理である^[13]。

脚注

[脚注の使い方]

出典

^ Newton's Method(Wolfram Math World) 2010年6月8日閲覧。
^ Fine, Henry B. (1916-09-15). “On Newton’s Method of Approximation”. Proceedings of the National Academy of Sciences of the United States of America 2 (9): 546–552. JSTOR 83815.
^ 数値解析入門（増訂版）、山本哲朗、サイエンス社、2003年。
^ Ortega, J.; Rheinboldt, W. (1970). Iterative Solution of Nonlinear Equations in Several Variables. Academic Press
^ 小澤一文『Cで学ぶ数値計算アルゴリズム』共立出版、2008年、49頁。ISBN 978-4-320-12221-5。
^ 長島, 隆廣「ニュートン近似の改良」『数学セミナー』第19巻第5号、日本評論社、1980年5月、112頁。
^ 室田一雄「平野の変形Newton法の大域的収束性」『情報処理学会論文誌』第21巻第6号、情報処理学会、1980年11月、469-474頁、CRID 1050282812867143936、ISSN 1882-7764。
^ 非線形解析入門、大石進一、コロナ社、1997年。
^ 精度保証付き数値計算、大石進一、コロナ社、2000年。
^ 大石進一 et. al. (2018), 精度保証付き数値計算の基礎, コロナ社.
^ Interval Newton Method
^ Rajković, P.; Stanković, M.; Marinković, D, S. (2002-01), “Mean value theorems in g-calculus”, Matematički vesnik (Mathematical Society of Serbia, Belgrade) 54 (3-4): 171-178
^ Rajković, P. M.; Marinković, S. D.; Stanković, M. S. (2005-09-15), “On q-Newton–Kantorovich method for solving systems of equations”, Applied Mathematics and Computation (Elsevier) 168 (2): 1432-1448, doi:10.1016/j.amc.2004.10.035

外部リンク

『ニュートン法の解説とそれを背景とする入試問題』 - 高校数学の美しい物語
山本哲朗、「Newton法とその周辺」『数学』 1985年 37巻 1号 p.1-15, doi:10.11429/sugaku1947.37.1, 日本数学会

[1] Newton's Method(Wolfram Math World) 2010年6月8日閲覧。

[2] Fine, Henry B. (1916-09-15). “On Newton’s Method of Approximation”. Proceedings of the National Academy of Sciences of the United States of America 2 (9): 546–552. JSTOR 83815.

[3] 数値解析入門（増訂版）、山本哲朗、サイエンス社、2003年。

[4] Ortega, J.; Rheinboldt, W. (1970). Iterative Solution of Nonlinear Equations in Several Variables. Academic Press

[5] 小澤一文『Cで学ぶ数値計算アルゴリズム』共立出版、2008年、49頁。ISBN 978-4-320-12221-5。

[6] 長島, 隆廣「ニュートン近似の改良」『数学セミナー』第19巻第5号、日本評論社、1980年5月、112頁。

[7] 室田一雄「平野の変形Newton法の大域的収束性」『情報処理学会論文誌』第21巻第6号、情報処理学会、1980年11月、469-474頁、CRID 1050282812867143936、ISSN 1882-7764。

[8] 非線形解析入門、大石進一、コロナ社、1997年。

[9] 精度保証付き数値計算、大石進一、コロナ社、2000年。

[10] 大石進一 et. al. (2018), 精度保証付き数値計算の基礎, コロナ社.

[11] Interval Newton Method

[12] Rajković, P.; Stanković, M.; Marinković, D, S. (2002-01), “Mean value theorems in g-calculus”, Matematički vesnik (Mathematical Society of Serbia, Belgrade) 54 (3-4): 171-178

[13] Rajković, P. M.; Marinković, S. D.; Stanković, M. S. (2005-09-15), “On q-Newton–Kantorovich method for solving systems of equations”, Applied Mathematics and Computation (Elsevier) 168 (2): 1432-1448, doi:10.1016/j.amc.2004.10.035

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

表話編歴微分積分学
Precalculus	二項定理凹関数連続関数階乗有限差分自由変数と束縛変数基本定理関数のグラフ線型関数平均値の定理ラジアンロルの定理割線傾き接線
極限	不定形（英語版）関数の極限片側極限数列の極限数列の加速法近似のオーダー（英語版） ε-δ論法
微分法	連鎖律導関数微分微分方程式微分作用素陰関数微分逆関数の微分（英語版）ロピタルの定理ライプニッツ則対数微分平均値の定理ニュートン法記法ライプニッツの記法ニュートンの記法レギオモンタヌスの問題相対変化率（英語版）基本法則線型性（英語版）積商冪函数（英語版）停留点極値の判定（英語版）最大値の定理極値テイラーの定理
積分法	逆微分弧長積分定数積分記号下の微分（英語版）微分積分学の基本定理正割の立方の積分（英語版）正割関数の積分（英語版）半角正接置換法（英語版）積分における部分分数（英語版）二次有理式の積分（英語版）円周率が22/7より小さいことの証明基本法則線型性（英語版）部分積分置換積分台形公式三角函数置換法（英語版）
ベクトル解析	回転方向微分発散発散定理勾配勾配定理（英語版）グリーンの定理ラプラシアンストークスの定理
多変数微分積分学	曲率 Disc integration（英語版）発散定理外微分ガブリエルのホルン幾何解析（英語版）ヘッセ行列ヤコビ行列と行列式線積分 Matrix calculus 多重積分偏微分バウムクーヘン積分面積分テンソル解析体積分
級数	アーベルの判定法（英語版）交代交代級数判定法（英語版）算術幾何数列二項コーシーの凝集判定法比較判定法ディリクレの判定法オイラー–マクローリンの公式フーリエ幾何超幾何 q超幾何調和無限積分判定法極限比較判定法（英語版）マクローリン冪比判定法冪根判定法テイラー項判定法（英語版）
特殊関数と数学定数	ベルヌーイ数ネイピア数オイラー定数指数関数自然対数ガンマ関数スターリングの近似楕円関数
歴史（英語版）	擬等式（英語版）ブルック・テイラーコリン・マクローリン代数の一般性（英語版）ゴットフリート・ヴィルヘルム・ライプニッツ無限小無限小解析（英語版）アイザック・ニュートン連続の法則（英語版）レオンハルト・オイラー『流率法』 (流率（英語版）) 『方法（英語版）』
一覧	微分法則（英語版）指数関数の原始関数双曲線関数の原始関数逆双曲線関数の原始関数逆三角関数の原始関数無理関数の原始関数対数関数の原始関数有理関数の原始関数三角関数の原始関数ガウス関数の原始関数極限数学記号原始関数
カテゴリ

導入

理論