Newton法の概要

次のスカラー方程式を考える．

$$f(x) = 0, \quad x \in \bm{R},\quad f \in \bm{R}$$ (2)

この解 $x$ について，何らかの方法で近似解 $x_k$ が得られたとしよう． するとこの$x_k$まわりに$f(x)$をTaylor展開すると，

$$f(x) = f(x_k) + \frac{df}{dx}(x_k)(x-x_k) + \frac{1}{2}\frac{d^2 f}{dx^2} (x_k)(x-x_k)^2 + \cdots$$ (3)

となる． $$\frac{df}{dx}(x_k)$$は$f$の$x$に関する導関数に $x_k$を代入したことを表す． この式の第2項までを取って式(2)に代入すると(線形化)，

$$f(x_k) + \frac{df}{dx}(x_k)(x-x_k) = 0$$ (4)

となる．これを$x$について解き，それを次の近似値$x_{k+1}$とする:

$$x_{k+1} = x_k - \frac{f(x_k)}{\displaystyle\frac{df}{dx}(x_k)}$$ (5)

この繰り返しアルゴリズムをNewton法と言う． 真の解を$\alpha$とすると，$f(\alpha)=0$だから，近似解との差は

$$x_{k+1}-\alpha = x_k - \alpha - \frac{\displaystyle f(x_k)-f(\alpha)}{\displaystyle \frac{df}{dx}(x_k)}$$ (6)

である． この式に

$$f(\alpha) = f(x_k) + \frac{df(x_k)}{dx}(\alpha- x_k) + \frac... ...{d^2f}{dx^2}(x_k)(\alpha - x_k)^2 + {\cal O}((\alpha - x_k)^3)$$ (7)

を代入すると，

$$x_{k+1} -\alpha = \frac12(\alpha-x_k)^2 \frac{ \displaystyl... ...{\displaystyle\frac{df}{dx}(x_k)} + {\cal O}((\alpha - x_k)^3)$$ (8)

を得る．したがって，

$$\lim_{k\rightarrow\infty}\frac{x_{k+1}-\alpha}{(x_k-\alpha)^... ...(\alpha)} {\displaystyle\frac{df}{dx}(\alpha)} = \mbox{const.}$$ (9)

となる．この式より， $k\rightarrow\infty$で$\alpha$に収束するとき， 第$k+1$次近似値の誤差 $x_{k+1}-\alpha$は，第$k$次の誤差$x_k - \alpha$の 2乗に比例して小さくなることが分かる．このような収束を2次収束といい， アルゴリズムを繰り返す度に正しい解の桁数が倍々に増えて行く． $10^{-8}$程度の精度であれば，数回の反復で求まるはずである． このようにNewton法を用いて非線形方程式の解がうまく求まるのは， ``非線形と言えども，局所的には線形である''という原理に基づいている．

さて，これを$n$次元に拡張した方程式(1)を再掲する．

$$\bm{f}(\bm{x})={\bf0}, \quad \bm{x}, \bm{f} \in \bm{R}^n$$ (10)

ここで$\bm{x}$は$x_i$を第$i$要素としたベクトル， $\bm{f}$は$f_i$を第$i$要素としたベクトルである．

解法原理はスカラーの場合と同じである．すなわち，$\bm{x}$の第$k$近似値を $\bm{x}_k \in \bm{R}^n$ とする．ただし$\bm{x}_k$は$x_i^k$を第$i$要素に持つベクトルになる． この$\bm{x}_k$まわりで式(10)のTaylor展開は，

$$\bm{f}(\bm{x}) = \bm{f}(\bm{x}_k) + \frac{d\bm{f}}{d\bm{x}} (\bm{x}_k)(\bm{x} - \bm{x}_k) + \cdots$$ (11)

となる．ここで $$\frac{d\bm{f}}{d\bm{x}}(\bm{x}_k)$$は

$$\frac{d\bm{f}}{d\bm{x}} (\bm{x}_k) = \left( \begin{array}{c... ...e \frac{\partial f_n}{\partial x_n}(x_n^k) \end{array}\right)$$ (12)

となる，$(n\times n)$の Jocobi行列である． ここで $$\frac{\partial f_i}{\partial x_j}(x_i^k)$$は， 関数$f_i$を$x_j$で偏微分し，それに $x_i^k$を代入することを意味する．

スカラーの場合の議論と同様，線形化をはかり，

$$\bm{f}(\bm{x}_k) + \frac{d\bm{f}}{d\bm{x}}(\bm{x}_k) (\bm{x} - \bm{x}_k) = {\bf0}$$ (13)

とする．解$\bm{x}$を第$k+1$近似とすると，

$$\frac{d\bm{f}}{d\bm{x}}(\bm{x}_k)(\bm{x}_{k+1} - \bm{x}_k) = - \bm{f}(\bm{x}_k)$$ (14)

となる．これを $\bm{x}_{k+1} - \bm{x}_k$について解き， 前の近似値$\bm{x}_k$を加えて，新しい近似値$\bm{x}_{k+1}$を求める．

ところが，ここで問題に直面する．すなわち， いま解きたい$\bm{x}_{k+1}$について， $$\frac{d\bm{f}}{d\bm{x}}(\bm{x}_k)$$という邪魔な 行列が かかっていて，これを簡単に右辺に払うことができないのである．

この式(14)は，良く見ると次の形をしている:

$$\bm{A}\bm{x} = \bm{b}$$ (15)

ただし， $$\frac{d\bm{f}}{d\bm{x}}(\bm{x}_k) = \bm{A}, \bm{x}_{k+1} - \bm{x}_k = \bm{x}, - \bm{f}(\bm{x}_k) = \bm{b}$$とおいた． すなわち行列で表現された連立一次方程式である．Gauss-Jordanの掃き出し法や， LU 分解などの手法が適用できて，$\bm{x}$について 解くことができる．それら解法の説明は適宜参考書を読んでみてほしい．