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

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

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

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

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

計算の終了は，

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

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

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

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

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

4.1.2 解への収束速度

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

$$\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}$$

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

4.1.3 解けない方程式

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

非線形方程式

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

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

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

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

• 常に $f^\prime(x)>0,\,f^{\prime\prime}(x)>0$で，初期値が$x_0=b$ の場合
• 常に $f^\prime(x)>0,\,f^{\prime\prime}(x)<0$で，初期値が$x_0=b$ の場合

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

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

図 5: ニュートン法で解が求まらない場合

図 6: ニュートン法で解が求まる場合

4.2 フローチャート

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

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

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