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)$の 直線の方程式は、

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

である。図4より、$ y=0$の時の$ x$の値が$ x_{i+1}$になることが 分かる。したがって、$ x_{i+1}$は、

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

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

計算の終了は、

$\displaystyle \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{equation*}\begin{aligned}\vert\alpha-x_{i+1}\vert &=\left\vert\alpha-x_i+...
...=\left\vert O\left((\alpha-x_i)^2\right)\right\vert \end{aligned}\end{equation*}

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

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

長所
初期値が適当ならば、収束が非常に早い(図 8)。
短所
初期値が悪いと、収束しない(図9)。収束 しない場合があるので、反復回数の上限を決めておく必要がある。

ニュートン法は複素数にも適用できる 。また、連立方程式にも容易に拡張できる。諸君 が学習してきた数は、自然数 $ \rightarrow$整数 $ \rightarrow$有理数 $ \rightarrow$無理 数 $ \rightarrow$複素数 $ \rightarrow$ベクトル $ \rightarrow$ 行列 $ \rightarrow\cdots$ と拡張されてきた。しかし、どのような数であれ、演算規則は非常に似通っていることは 今まで経験してきたとおりである。このことから、実数で成り立つ方法は、複素数や行列 にも成り立つことが予想できる。このように考えると、ニュートン法が連立方程式や複素 数に拡張できることも不思議ではない。

これは少し高度な内容なので、8節におまけで載せておく。た ぶん、諸君の中の何人かは一瞬にして実数の近似解を求めるニュートン法を理解したと思 う。これまでの話が理解できた者は、8節を勉強することを勧 める。

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

4.2 フローチャート

二分法同様、関数と計算を打ち切る条件はプログラム中に書くものとする。そうすると、 図5のようなニュートン法のフローチャートが考えられる。
図 5: ニュートン法のフローチャート
\includegraphics[keepaspectratio, scale=0.8]{figure/flow_chart/flow_newton.eps}

ホームページ: Yamamoto's laboratory
著者: 山本昌志
Yamamoto Masashi
平成19年6月24日