ニュートン法とは? ~定義と性質~
定義
ニュートン法とは、方程式
の解を数値的に求める方法の一つである。
ある適当な値 $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})$ に収束する。