3.7 参考: Newton 法の原理

(情報処理教室で実習中にここを読む時間はほとんどないでしょうから、 余裕のあるときに読んで下さい。)

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

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

$$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$ よりも良い近似解になっているだろう (実際に適当な条件下でこれは正当化できます)、 という考えから導かれるものです。

すなわち、漸化式

$$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}$ を定めると、適当な条件 ⁹の下で

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

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

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

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

Newton法のアルゴリズム

(1)

適当な初期値 $x_0$ を選ぶ。

(2)

$x\leftarrow x_0$

(3)

$x \leftarrow x - f(x)/f'(x)$ とする。

(4)

まだ近似の程度が十分でないと判断されたら (3) に戻る。 そうでなければ $x$ を解として出力する。