ニュートン法の収束速度

ニュートン法の収束速度

§１　ニュートン法の計算法

x=αを解にもつ次の方程式があるとする。

f(x)が何回でも微分可能な関数であるとき、x=x₀でf(α)をテーラー展開すると

となるので、２次の項を無視すると、f(x)を次のように近似できる。

x=αは（１）の解なのでf(α)=0であり、f(α)=0と（３）式より

と、（４）式を用いて方程式（１）の解を推測することができる。

（４）式の右辺で推測されたαの推測値をx₁とすると、

（５）式から得られた推測値x₁を用いて

と推測値x₂を求め、さらに、この推測値x₂をもとに・・・

と、逐次的に、方程式（１）の解の近似解を求める方法をニュートン法またはニュートン・ラプソン法という。

§２　ニュートン法の収束速度

f(α)をでテーラー展開すると

ここで、ξはαとの間にある実数。

f(α)=0だから、のとき、

ここで、

とおくと、

となる。

ここで、適当なδ>0をとり、となるようにすると、仮定よりf'(x)とf''(x)は、連続なので、Iで有界。

したがって、

となるA>0（仮定よりf'(x)>0）、B>0が存在する。

したがって、

となり、ニュートン法は２次の収束速度をもつことがわかる。

このため、ニュートン法は４、５回程度の反復計算で収束解を得ることができる。

上の表は、方程式

に対し、計算の初期値x₀=−5を与え、ニュートン法を用いて表計算ソフトで計算した結果である。５回の反復回数で、この方程式の解の１つであるx=−3が得られることがわかる。

また、反復計算の４、５回目の誤差の指数を見ると、−6と−12となっているとから、ニュートン法の収束速度が２次であることを確認できるだろう。

なのですが、

計算の初期値にx₀=5を与えると、事情は一変する。

表計算ソフトの誤差の列を見ると、反復計算の回数を１回増やすたびに誤差は約1/2にしかなっておらず、２次の収束速度を持っているはずのニュートン法が１次の収束速度に落ちてしまっていることがわかる。

このとき、ニュートン法は、２分法に限りなく近いものになってしまうのであった。

多重解x=αを持つ方程式

の解x=αをニュートン法で求めようとすると、一般に、非場に収束が遅い。

興味のあるヒトは、さらに、

の解x=3をニュートン法で求めてみるといいと思う。