ニュートン法

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

導入

ニュートン法の一手順の概念図 (青い線が関数 f のグラフで、その接線を赤で示した). x_n よりも x_n+1 のほうが、 f(x)=0 の解 x についてのよりよい近似を与えている.

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

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

${\displaystyle f(x)=0\,}$

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

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

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

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

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

${\displaystyle f'(x)=2x\,}$

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

${\displaystyle 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 とおくと、この数列は ${\displaystyle {\sqrt {2}}}$ に収束するが、その収束の仕方は

x₀ = 2

x₁ = 1.5

x₂ = 1.416666…

x₃ = 1.4142156862745…

x₄ = 1.4142135623746899… (下線部は${\displaystyle {\sqrt {2}}}$と一致する部分)

となる。

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

理論

局所収束定理

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

${\displaystyle f(x)=0\,}$

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

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

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

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

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

${\displaystyle x_{n+1}=g(x_{n})}$, ただし ${\displaystyle g(x)=x-{\frac {f(x)}{f'(x)}}}$

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

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

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

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

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

よって２次で収束する。

半局所収束定理

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

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

高次元の場合

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

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

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

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

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

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

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

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

を解いて、

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

となる。

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

${\displaystyle \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次に退化する^[7]。

改良

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

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

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

平野の変形ニュートン法

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

簡易ニュートン法

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

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

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

クラフチック法

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

区間ニュートン法

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

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

q-ニュートン法

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

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

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