ニュートン法とは? ~定義と性質~

定義
  ニュートン法とは、方程式
の解を数値的に求める方法の一つである。 ある適当な値 $x_{0}$ から計算を開始し、
ニュートン法
という計算を反復することによって、 真の解 $\alpha$ の近似値を与える方法である。
解説
  ニュートン法の反復計算式
$$ \tag{1} $$ は、次のように求められる。 まず、 反復計算を開始する値を $x_{0}$ とし、 点
を通る $f(x)$ の接線 $L_{0}$ と $x$ 軸の交点の $x$ 座標を $x_{1}$ とする (下図)。
ニュートン法の図
$L_{0}$ は $(x_{0}, f(x_{0}))$ を通過し、 傾きが $f'(x_{0})$の 直線なので、
と表される。 この接線と $x$ 軸との交点が $x_{1}$ であるので、 $x_{1}$ は、
を満たす。 これより、
を得る。これは反復計算式 $(1)$ の $n=1$ の場合である。 同じ様に、$x_{n}$ は $f(x)$ の $x=x_{n-1}$ における接線 $L_{n-1}$ が $x$ 軸と交差する点がであり、
と表される。これは $(1)$ そのものである。
  この反復計算を実行し、 決められた条件が満たされたとき (例えばワンステップの差 $|x_{n}-x_{n-1}|$ が許容値よりも小さくなったとき) に計算を停止し、 そのときの値 $x_{n}$ を真の解 $\alpha$ の近似解 とする。 これをニュートン法という。


具体例: 平方根
  ニュートン法を使って、 $\sqrt{3}$ の近似値を計算すると、 5回の反復計算によって、
の値が得られる。
  この値は真の値と10桁まで一致する。
速度: 二次収束
  関数 $f(x)=0$ の真の解を $\alpha$ とすると、 ニュートン法の反復結果 $x_{n}$ には
が成り立つ。ここで $K_{n}$ は $n$ に依存する数である。
  この式は、真の解との差
が一回の反復を繰り返すごとに二乗になり、 $d_{n}$ が十分に小さいのであれば、 $d_{n+1}$ はさらに小さくなることを表している。
  このように、ニュートン法は(条件が良ければ)真の解に二乗の速度で近づいていく。 これをニュートン法が二次収束するという。
証明
  ニュートン法の定義から
であるが、両辺から $\alpha$ を引くと、
$$ \tag{1} $$ と表される。 ここで、テイラーの定理から、
を満たす $c$ が $x_{n}$ と $\alpha$ の間に存在し、 $\alpha$ は $f(x) = 0$ の解である ($f(\alpha) = 0$) ので、
が成り立つ。 これと $(1)$ から
を得るが、絶対値をとることにより、
となるなので、ニュートン法は二次収束する。 ここで
とした。

収束条件
  $2$ 階微分可能な関数 $f(x)$ がある点 $x_{0}$ において
$$ \tag{1} $$ であり、 $x_{0}$ より小さな点 $a$ において、
$$ \tag{2} $$ であるとする。 また区間 $[a, x_{0}]$ において $f$ が単調増加であり、 すなわち、
$$ \tag{3} $$ を満たし、 下に凸な関数であるとする。 すなわち、
$$ \tag{4} $$ を満たすとする。
  このとき
$$ \tag{5} $$ によって定義される数列 $\{x_{n}\}$ は、区間 $(a, x_{0})$ にある $f(x)=0$ の解に収束する。
ニュートン法の図

証明
  $(4)$ から、任意の $x\in [a, x_{0})$ に対し、
が成り立つが、積分して表すと、
である。 これより、
が成り立つが、積分して表すと、
$$ \tag{6} $$ である。
  ところで $f$ が微分可能なので連続であり、 $(1)$ と $(2)$ から
が成り立つので、 中間値の定理を適用すると、
$$ \tag{7} $$ を満たす $\alpha$ が区間 $(a, x_{0})$ に存在することが分かる。 また、$f$ は単調増加関数であるので、 逆関数が存在する。よって、$\alpha$ は
$$ \tag{8} $$ と表せる。
  さて $x=\alpha$ の場合、 $(6) $は
であるが、これと $(7)$ および $(1)$ $(3)$ $(5)$ により、
が成り立つ。すなわち、 $x_{1}$ は $\alpha$ より大きく $x_{0}$ より小さい。
  同様の論法により $x_{2}$ が $\alpha$ より大きく $x_{1}$ より小さいことが示される。 すなわち、
が成り立つ。 これらより、
を得る。
  このような論法を繰り返すことにより、 数列 $\{ x_{n} \}$ が
を満たすことが示される。
  この不等式は、数列 $\{x_{n}\}$ が下に有界な単調減少数列であることを表している よって、$\{x_{n}\}$ は収束する (有界な単調数列は収束する:実数の公理)。 そこで $\{x_{n}\}$ の極限値を $\beta$ とする。すなわち、
$$ \tag{10} $$ とする。
  $(5)$ の両辺に対し、$n\rightarrow \infty$ の極限をとると、
となるので、 $(10)$ から
が成り立つ。 これより $ f(\beta) = 0 $ であるので、 $f$ が逆関数を持つことから、
である。 従って、 $(8)$ から
が成立する。 $(10)$ より、この式は数列 $\{x_{n}\}$ が $\alpha$ 収束することを表している。 すなわち、
が成立する。
  $\alpha$ は $f(x)=0$ の解であったので、次の結論を得る。すなわち、 ニュートン法の数列 $\{ x_{n} \}$ は、 条件 $(1) (2) (3) (4)$ のもとでは、 $f(x)=0$ の解 $\alpha \in (a, x_{0})$ に収束する。