ニュートン法

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

導入

ファイル:Newton iteration.svg

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

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

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

<math>f(x) = 0\,</math>

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

<math>x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \quad \cdots (1) </math>

例として、√2 を計算で求める場合に、

<math>f(x) = x^2 - 2\,</math>

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

<math>f'(x) = 2x\,</math>

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

<math>x_{n+1} = x_n - \frac{x_n^2-2}{2x_n} </math>

と書き表せる。たとえば x₀ = 1 とおくと、この数列は √2 に収束し、x₀ = -1 とおくと、この数列は -√2 に収束する。

理論

<math>f(x) = 0\,</math>

の解を考える。 <math>f(x)</math> の <math>x=x_0</math> でのテーラー展開をすると

<math>f(x) =f(x_0)+f^{\prime}(x_0)(x-x_0)+o((x-x_0))</math>

このとき、(右辺)=0の解は、(左辺)=0の根の <math>x_0</math>での多項式次数一次の近似となっている。 右辺の解は

<math>x=x_0-\frac{f(x_0)}{f^{\prime}(x_0)}</math>

次に、この近似値が、<math>x_0</math>より根に近づいている ということに関する意味を考える。 上式を、次のような離散力学系として考える。

<math>g(x) = x - \frac{f(x)}{f'(x)}</math>

<math>x_{n+1} = g(x_n)</math>

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

したがって、<math>x^*</math>が沈点(アトラクター)であり、 与えられた初期条件<math>x_0</math>が、このアトラクターの吸引領域に属していれば <math>x_n</math>の<math>\omega</math>-極限(<math>n \rightarrow \infty</math>)は <math>f(x^*)=0</math>となる<math>x^*</math>に収束する。

この様な収束性は、常に担保されてはいない。 例えばx軸の漸近線や関数<math>f(x)</math>の極値近傍では固定点が不安定になる事が知られている。

高次元の場合

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

<math>f(\mathbf{x}) = \mathbf{0}</math>

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

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

<math> f(\mathbf{x}_0) + \partial f(\mathbf{x}_0)(\mathbf{x} - \mathbf{x}_0)</math>

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

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

<math> f(\mathbf{x}_0) + \partial f(\mathbf{x}_0)(\mathbf{x} - \mathbf{x}_0)=\mathbf{0} </math>

を解いて、

<math> \mathbf{x} = \mathbf{x}_0 - \partial f(\mathbf{x}_0)^{-1} f(\mathbf{x}_0)</math>

となる。

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

<math>

\partial f(\mathbf{x}_0) \mathbf{r} = f(\mathbf{x}_0) </math> という方程式をガウスの消去法などの解法によって線形方程式系を解き r を求め、x = x₀ - r によって x を求める。

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

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

注意

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

改良

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

<math>

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

</math> この方法は、場合によっては従来の方法より速い。

関連項目

• 除算 (デジタル)
• ガウス・ニュートン法テンプレート:Link GA