4 ニュートン法(Newton's method)
関数
![$ f(x)$](img69.png)
のゼロ点
![$ \alpha$](img70.png)
に近い近似値
![$ x_0$](img71.png)
から出発する。そして、関数
![$ f(x)$](img72.png)
上の
点
![$ (x_0,f(x_0))$](img73.png)
での接線が、x軸と交わる点を次の近似解
![$ x_1$](img74.png)
とする。そして、次の
接線がx軸と交わる点を次の近似解
![$ x_2$](img75.png)
とする。同じことを繰り返して
![$ x_3,\,x_4,\cdots$](img76.png)
を求める(図
4)。この計算結果の数列
![$ (x_0,\,x_2,\,x_3,\,x_4,\cdots)$](img77.png)
は初期値
![$ x_0$](img78.png)
が適当であれば、真の解
![$ \alpha$](img79.png)
に収
束することは図より明らかであろう。
実際にこの数列を計算するためには、漸化式が必要である。図の用にすると、関数
上の点
の接線を引き、それとx軸と交点
になる。まずは、
を求めることにする。点
を通り、傾きが
の
直線の方程式は、
![$\displaystyle y-f(x_i)=f^\prime(x_i)(x-x_i)$](img86.png) |
(8) |
である。図
4より、
![$ y=0$](img87.png)
の時の
![$ x$](img88.png)
の値が
![$ x_{i+1}$](img89.png)
になることが
分かる。したがって、
![$ x_{i+1}$](img90.png)
は、
となる。これで、
![$ x_i$](img92.png)
から
![$ x_{i+1}$](img93.png)
が計算できる。これをニュートン法の漸化式と言う。この漸化
式を用いれば、次々とより精度の良い近似解を求めることができる。
計算の終了は、
![$\displaystyle \left\vert\frac{x_{i+1}-x_i}{x_i}\right\vert<\varepsilon$](img94.png) |
(10) |
の条件を満たした場合とするのが一般的である。
![$ \varepsilon$](img95.png)
は計算精度を決める定数
で、非常に小さな値である。これ以外にも計算の終了を決めることは可能なので、状況に
応じて、計算の打ち切り方法を決めればよい。実際に式(
2)を
計算した結果を図
4に示す。接線との交点が解に近づく様子がわか
るであろう。
ニュートン法を使う上で必要な式は、式(9)のみである。計算
に必要な式は分かったが、数列がどのように真の解
に収束するか考える。
と真値
の差の絶対値、ようするに誤差を計算する。
を
忘れないで、テイラー展開を用いて、計算を進めると
となる。
![$ i+1$](img101.png)
番目の近似値は、
![$ i$](img102.png)
番目に比べて2乗で精度が良くなるのである。これを、
二次収束と言い、非常に早く解に収束する。例えば、
![$ 10^{-3}$](img103.png)
の精度で近似解が得られ
ているとすると、もう一回式(
9)を計算するだけで、
![$ 10^{-6}$](img104.png)
程度の精度で近似解が得られるということである。一次収束の二分法よりも、収
束が早いことが分かる。
ニュートン法の特徴をまとめると次のようになる。
- 長所
- 初期値が適当ならば、収束が非常に早い(図
8)。
- 短所
- 初期値が悪いと、収束しない(図9)。収束
しない場合があるので、反復回数の上限を決めておく必要がある。
ニュートン法は複素数にも適用できる 。また、連立方程式にも容易に拡張できる。諸君
が学習してきた数は、自然数
整数
有理数
無理
数
複素数
ベクトル
行列
と拡張されてきた。しかし、どのような数であれ、演算規則は非常に似通っていることは
今まで経験してきたとおりである。このことから、実数で成り立つ方法は、複素数や行列
にも成り立つことが予想できる。このように考えると、ニュートン法が連立方程式や複素
数に拡張できることも不思議ではない。
これは少し高度な内容なので、8節におまけで載せておく。た
ぶん、諸君の中の何人かは一瞬にして実数の近似解を求めるニュートン法を理解したと思
う。これまでの話が理解できた者は、8節を勉強することを勧
める。
図 4:
の実数解をニュートン法で計算し、解の収
束の様子を示している。初期値
から始まり、接線とx軸の交点からよ
り精度の高い回を求めている。
|
二分法同様、関数と計算を打ち切る条件はプログラム中に書くものとする。そうすると、
図
5のようなニュートン法のフローチャートが考えられる。
ホームページ:
Yamamoto's laboratory著者:
山本昌志
Yamamoto Masashi
平成19年6月24日