ニュートン法
ニュートン法とは、高次方程式の根（ゼロ点）を求めるための数値計算法です。ニュートン法は、関数 $f$ が以下の場合に有効な方法です。
-
- $f$ が根の近くで十分滑らかである。
- 根を $\alpha$ とすると $f'(\alpha)\neq0$ である。
- 初期値が根に十分近い。
関数 $f(x)$ の根を $\alpha$ 、つまり $f(\alpha)=0$ とします。根の付近の適当な点 $a_1$ について、$a_2$ を計算します（①の導出）。
$$a_2=a_1-\frac{f(a_1)}{f'(a_1)} -①$$
同様に $a_2$ から次の $a_3$ を計算します。
$$a_3=a_2-\frac{f(a_2)}{f'(a_2)}$$
適切な初期値を選び、根の近くで一定の条件が満たされる場合、これを繰り返すと、$a_n$ は根 $\alpha$ に収束します。特に単根の近くでは、ニュートン法は通常二次収束（導出）します。そして、$a_n$ の変化量が許容誤差範囲 $\epsilon$ 未満、または、$|f(a_n)|$ が $\delta$ 未満になれば、
$$|a_n-a_{n-1}|\lt\epsilon$$$$|f(a_n)|\lt\delta$$
$a_n$ を根の近似と考えて計算を終了します。
①の導出
テイラー展開より、
$$f(b)=f(a)+(b-a)f'(a)+\frac{1}{2}(b-a)^2f^{(2)}(a)+\cdots$$
$b$ を根、つまり $f(b)=0$ とします。$a$ を根の付近とすると、右辺の第２項に比べ第３項以降は十分に小さいと考えられるため、
$$0=f(a)+(b-a)f'(a)$$
従って、以下の $b$ を根の近似解と考えることができます。
$$b=a-\frac{f(a)}{f'(a)}$$
における接線を考え、その接線と $x$ 軸との交点を次の近似値として考えます。つまり、 における接線は、
$$y=f(a)+f'(a)(x-a)$$
$x$ 軸との交点では $y=0$ と置くと、同じ式が得られます。
$$0=f(a)+f'(a)(x-a)$$$$x=a-\frac{f(a)}{f'(a)}$$
二次収束することの導出
解 $\alpha$ のまわりで $f(a_n)$ をテイラー展開します。ここで $\xi_n$ は $\alpha$ と $a_n$ の間にある実数です。
$$f(\alpha) = f(a_n) + (\alpha – a_n)f'(a_n) + \frac{(\alpha – a_n)^2}{2} f”(a_n)$$
$f(\alpha) = 0$ および、第 $n$ 項目における誤差を $e_n = a_n – \alpha$ と置くと、
$$0 = f(a_n) – e_n f'(a_n) + \frac{e_n^2}{2} f”(a_n) -(1)$$
①を誤差で表すと、
$$e_{n+1} = e_n – \frac{f(a_n)}{f'(a_n)}$$
ここに (1) 式の $f(a_n)$ を代入すると、
$$e_{n+1} = e_n – \frac{e_n f'(a_n) – \frac{e_n^2}{2} f”(a_n)}{f'(a_n)}= \frac{f”(a_n)}{2 f'(a_n)} e_n^2$$
$n \to \infty$ のとき $a_n \to \alpha$ の極限を取ると、
$$\lim_{n \to \infty} \frac{\vert{}e_{n+1}\vert{}}{\vert{}e_n\vert{}^2} = \left\vert{} \frac{f”(\alpha)}{2 f'(\alpha)} \right\vert{} = M \quad (\text{定数})$$
$f'(\alpha) \neq 0$ であれば $M$ は有限の値をとるため、次のステップの誤差 $e_{n+1}$ は、現在の誤差 $e_n$ の２乗に比例することが分かります。
２分法
２分法は、関数 $f(x)$ が区間 $[a_1,b_1]$ で連続で、両端で符号が異なる場合に、その区間を半分ずつに分けながら根を求める方法です。
$$f(a_1)f(b_1)\lt0$$
関数 $f(x)$ の根を $\alpha$ とし、根の付近の適当な範囲［$a_1$、$b_1$］ について、中間点 $c_1$ を計算します。
$$c_1=\frac{a_1+b_1}{2}$$
この中間点について、
-
- $f(a_1)f(c_1)\gt0$ であれば、$a_2=c_1$、$b_2=b_1$
- $f(a_1)f(c_1)\lt0$ であれば、$a_2=a_1$、$b_2=c_1$
同様に $a_2$、$b_2$ から次の $c_2$ を計算します。
$$c_2=\frac{a_2+b_2}{2}$$
これを繰り返すと、範囲［$a_n$、$b_n$］は限りなく狭められていきます。そして、範囲［$a_n$、$b_n$］が許容誤差範囲 $\epsilon$ 未満になれば、そこで計算を止め、中間点 $c_n$ を根の近似値と考えます。
$$|a_n-b_n|\lt\epsilon \text{ならば、} c_n=\frac{a_n+b_n}{2}$$
このとき２分法の誤差評価は以下になります。
$$\Big|\frac{a_n+b_n}{2}-\alpha\Big|\le\frac{b_n-a_n}{2}$$
ニュートン法と２分法の比較
| 比較項目 | ニュートン法 | ２分法 |
| 解法のアプローチ | 接線を利用して根の位置を推測する | 区間の中点を求め、範囲を半分に狭めていく |
| 収束速度 | 非常に速い（二次収束） ※誤差がステップ毎に２乗で小さくなる |
遅い（一次収束） ※誤差がステップ毎にが半分になる |
| 初期条件 | 解の近くの初期値 $a_0$ を設定 | 異符号となる初期区間 $[a, b]$ を設定 |
| 収束の確実性（安定性） | 不安定 ※初期値が悪いと発散や振動を起こす |
非常に高い（確実に収束） ※解を挟む区間が選べていれば必ず収束する |
| 破綻するケース | 途中で $f'(a_n) = 0$ になる、または極値付近で振動する | 最初にとった区間内に根が存在しない（同符号の場合） |
| 主な用途 | 高精度かつ高速な計算が必要な場合、または他の手法で十分解に近づいた後の最終仕上げ | 微分が困難な関数、またはニュートン法を適用するための確実な初期範囲を探す前処理 |
