next up previous
Next: 3.3 二分法 vs. Newton Up: 3 非線形方程式を計算機で解く Previous: 3.1 二分法

3.2 Newton 法

非線形方程式を解くためのもう一つの代表的な方法が Newton 法 です。

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

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

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

\begin{displaymath}
\lim_{n\to+\infty} x_n = x_{*}
\end{displaymath}

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

\begin{displaymath}
f(x_{*}) = 0
\end{displaymath}

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

[
l]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.3 二分法 vs. Newton Up: 3 非線形方程式を計算機で解く Previous: 3.1 二分法
Masashi Katsurada
平成20年10月18日