4 ニュートン法(Newton's method)

4.1 計算方法

関数$f(x)$のゼロ点$\alpha$に近い近似値$x_0$から出発する。そして、関数 $f(x)$上の点 $(x_0,f(x_0))$での接線が、x軸と交わる点を次の近似解$x_1$ とする。そして、次の接線がx軸と交わる点を次の近似解$x_2$とする。同じこ とを繰り返して $x_3, x_4,\cdots$を求める(図4)。こ の計算結果の数列 $(x_0, x_2, x_3, x_4,\cdots)$は初期値$x_0$が適当で あれば、真の解$\alpha$に収束する。

まずは、この数列の漸化式を求める。関数$f(x)$上の点 $(x_i, f(x_i))$の接 線を引き、それとx軸と交点$x_{i+1}$ である。まずは、$x_{i+1}$ を求める ことにする。点 $(x_i, f(x_i))$を通り、傾きが $f^\prime(x_i)$の直線の方 程式は、

$$y-f(x_i)=f^\prime(x_i)(x-x_i)$$ (8)

である。$y=0$の時の$x$の値が$x_{i+1}$にである。$x_{i+1}$は、

$$x_{i+1}=x_i-\frac{f(x_i)}{f^\prime(x_i)}$$ (9)

となる。$x_i$から$x_{i+1}$計算できる。これをニュートン法の漸化式と言う。 この漸化式を用いれば、次々と近似解を求めることができる。

計算の終了は、

$$\left\vert\frac{x_{i+1}-x_i}{x_i}\right\vert<\varepsilon$$ (10)

の条件を満たした場合とするのが一般的である。 $\varepsilon$は計算精度を 決める定数で、非常に小さな値である。これ以外にも計算の終了を決めること は可能である。必要に応じて、決めればよい。実際に式 (2)を計算した結果を図4に 示す。接線との交点が解に近づく様子がわかるであろう。

ニュートン法を使う上で必要な式は、式(9)のみで ある。計算に必要な式は分かったが、数列がどのように真の解$\alpha$に収束 するか考える。$x_{i+1}$ と真値$\alpha$の差の絶対値、ようするに誤差を 計算する。 $f(\alpha)=0$を忘れないで、テイラー展開を用いて、計算を進める と

$$\begin{aligned} \vert\alpha-x_{i+1}\vert &=\left\vert\alpha-x... ...\left\vert O\left((\alpha-x_i)^2\right)\right\vert \end{aligned}$$

となる。$i+1$番目の近似値は、$i$番目に比べて2乗で精度が良くなるのであ る。これを、二次収束と言い、非常に早く解に収束する。例えば、$10^{-3}$ の精度で近似解が得られているとすると、もう一回式 (9)を計算するだけで、$10^{-6}$程度の精度で近似 解が得られるということである。一次収束の2分法よりも、収束が早いことが 分かる。

ニュートン法の特徴をまとめると次のようになる。

長所

初期値が適当ならば、収束が非常に早い(図 8)。

短所

初期値が悪いと、収束しない(図9)。収束 しない場合があるので、反復回数の上限を決めておく必要がある。

ニュートン法は複素数にも適用できる 。また、連立方程式にも容易に拡張で きる。皆さんが学習してきた数は、整数 $\rightarrow$自然数 $\rightarrow$有理 数 $\rightarrow$無理数 $\rightarrow$複素数 $\rightarrow$ベクトル $\rightarrow$ 行列 $\rightarrow\cdots$と拡張されてきた。しかし、どのような数であれ 演算規則は、非常に似ている。そのことから、実数で成り立つ方法は、複素 数や行列にも成り立つことが予想できる。このことからも、ニュートン法が 連立方程式や複素数に拡張できるような気にる。ここでの学習は、これ 以上踏み込まないことにするが、興味のある人は、各自、学習すべし。

図 4: $f(x)=x^3-3x^2+9x-8$の実数解をニュートン法で計算し、解の収 束の様子を示している。初期値$x_0=5$から始まり、接線とx軸の交点からよ り精度の高い回を求めている。

4.2 アルゴリズム

2分法同様、関数と計算を打ち切る条件はプログラム中に書くものとする。そ うすると、図5のようなニュートン法のフローチャー トが考えられる。

図 5: ニュートン法のフローチャート

ホームページ: Yamamoto's laboratory
著者: 山本昌志