next up previous
Next: 3.6 二分法 vs. Newton Up: 3 方程式の数値解法 Previous: 3.4 Newton 法

3.5 参考: Newton 法の原理

Newton 法は非線形方程式を解くための代表的な方法である。

これは $ f$ が微分可能な関数で、 方程式 $ f(x)=0$ の近似解 $ x_0$ が得られているとき、線形化写像

$\displaystyle x\mapsto f(x_0)+f'(x_0)(x-x_0)
$

の零点 $ x=x_0-\left[f'(x_0)\right]^{-1}f(x_0)$ は、 $ x_0$ よりも良い近似解になっているであろう (実際に適当な条件下でこれは正当化できる)、という考えから導かれるものである。

すなわち、漸化式

$\displaystyle x_{n+1} = x_{n} - \frac{f(x_n)}{f'(x_n)}
\quad\hbox{($n=0, 1, 2, \cdots$)}
$

で数列 $ \{x_n\}_{n=0,1,2,\cdots}$ を定めると、適当な条件 9の下で

$\displaystyle \lim_{n\to+\infty} x_n = x_{*}
$

と収束し、極限 $ x_*$ は方程式の解になっている:

$\displaystyle f(x_{*}) = 0
$

ということを利用したもので、実際のアルゴリズムは次のようになる。

Newton法のアルゴリズム
(1)
適当な初期値 $ x_0$ を選ぶ。
(2)
$ x\leftarrow x_0$
(3)
$ x \leftarrow x - f(x)/f'(x)$ とする。
(4)
まだ近似の程度が十分でないと判断されたら (3) に戻る。そうでなけ れば $ x$ を解として出力する。


next up previous
Next: 3.6 二分法 vs. Newton Up: 3 方程式の数値解法 Previous: 3.4 Newton 法
Masashi Katsurada
平成22年6月16日