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

4.1 計算方法

4.1.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)$ (12)

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

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

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

計算の終了は,

$\displaystyle \left\vert\frac{x_{i+1}-x_i}{x_i}\right\vert\leq\varepsilon$ (14)

の条件を満たした場合とするのが一般的である 5 $ \varepsilon$は計算 精度を決める定数で,非常に小さな値である.これ以外にも計算の終了を決めることは可 能なので,状況に応じて,計算の打ち切り方法を決めればよい.実際に式 (4)を計算した結果を図4に示す.接線 との交点が解に近づく様子がわかるであろう.
図 4: $ f(x)=x^3-3x^2+9x-8$の実数解をニュートン法で計算し,解の収 束の様子を示している.初期値$ x_0=5$から始まり,接線とx軸の交点からよ り精度の高い回を求めている.
\includegraphics[keepaspectratio, scale=0.7]{figure/function_solution/NewtonMethod.eps}
ニュートン法は複素数にも適用できる .また,連立方程式にも容易に拡張できる.諸君 が学習してきた数は,自然数 $ \rightarrow$整数 $ \rightarrow$有理数 $ \rightarrow$無理 数 $ \rightarrow$複素数 $ \rightarrow$ベクトル $ \rightarrow$ 行列 $ \rightarrow\cdots$ と拡張されてきた.しかし,どのような数であれ,演算規則は非常に似通っていることは 今まで経験してきたとおりである.このことから,実数で成り立つ方法は,複素数や行列 にも成り立つことが予想できる.このように考えると,ニュートン法が連立方程式や複素 数に拡張できることも不思議ではない.

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

4.1.2 解への収束速度

ニュートン法を使う上で必要な式は,式(13)のみである.計算 に必要な式は分かったが,数列がどのように真の解$ \alpha$に収束するか考える. $ x_{i+1}$ と真値$ \alpha$の差の絶対値,ようするに誤差を計算する. $ f(\alpha)=0$を 忘れないで,右辺 $ f(x_i)/f^\prime(x_i)$$ \alpha$の周りでテイラー展開する.すると,

\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}$ の精度で近似解が得られ ているとすると,もう一回式(13)を計算するだけで, $ 10^{-6}$程度の精度で近似解が得られるということである.一次収束の二分法よりも,収 束が早いことが分かる.

4.1.3 解けない方程式

アルゴリズムから,二分法は解に必ず収束する6.ただし,収束のスピードが遅いのが欠点である. 一方,ニュートン法と解に収束するとは限らない.初期値が悪いと解に収束しない場合が ある.厳密にその条件を求めるのは大変なので,実例を示すことにする.

非線形方程式

$\displaystyle 3\tan^{-1}(x-1)+\frac{x}{4}=0$ (16)

を計算することを考える.これは,初期値が悪いと収束しない方程式の例である.例えば 初期値$ x_0=3$の場合,図5のように収束しない7.これを初期値$ x_0=2.5$にすると図6のように 収束する.

このようにニュートン法は解に収束しないで,振動する場合がある.こうなると,プログ ラムは無限ループに入り,永遠に計算し続ける.これは資源の無駄遣いなので,慎むべき である.通常は,反復回数の上限を決めて,それを防ぐ.ニュートン法を使う場合は,こ の反復回数の上限は必須である.

ニュートン法で収束する必要条件が分かればこの問題は解決する.しかし,それを探すの は大変である.というか私には分からない.一方,十分条件は簡単にわかる.閉区間 $ [a,\,b]$で, $ f(a)<0,\,f(b)>0$ のような関数を考える.このとき,

は,必ず収束する.ニュートン法の図から明らかである. $ f(a)>0,\,f(b)<0$ の場合は, $ f(x)$に-1倍すれば,先の十分条件を考えることができる.

実際には収束しない場合のほうが稀であるので,ニュートン法は非常に強力な非線形方程 式の解法である.ただ,反復回数を忘れないことが重要である.また,二分法と組み合わ せて使うことも考えられる.

図 5: ニュートン法で解が求まらない場合
\includegraphics[keepaspectratio, scale=0.4]{figure/comv_hasan/hasan.eps}
図 6: ニュートン法で解が求まる場合
\includegraphics[keepaspectratio, scale=0.4]{figure/comv_hasan/comb.eps}

4.2 フローチャート

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

ホームページ: Yamamoto's laboratory
著者: 山本昌志
Yamamoto Masashi
平成18年7月11日


no counter