Newton 法

$y = f(x)$ が微分可能であるとする. $x_n$ を $f(x)=0$ の解のある近似値と する. $(x_n,f(x_n))$ における接線の方程式は $y-f(x_n) = f'(x_n)(x-x_n)$. $f'(x_n) \neq 0$のとき, この接線と $x$ 軸との交点は $x=x_n-f(x_n)/f'(x_n)$. この値を新たな近似値 $x_{n+1}$ とする. このようにして次々と近似値を求めていく方法を Newton 法とよぶ.

Newton 法の収束の様子を調べてみよう. $f(x)=0$ の根 $\alpha$ が 存在するとし, $x_n = \alpha + \epsilon_n$ とする. $f(x)$ が $C^2$ 級とし, $f(x)$, $f'(x)$ を $x=\alpha$ の周りで Taylor 展開すると

$$f(x_n) = \epsilon_n f'(\alpha) + {\epsilon_n^2 \over 2} f''(\xi) \quad (\vert\xi-\alpha\vert \le \vert\epsilon_n\vert)$$

$$f'(x_n) = f'(\alpha) + \epsilon_n f''(\zeta) \quad (\vert\zeta-\alpha\vert \le \vert\epsilon_n\vert)$$

$$\epsilon_{n+1} = x_{n+1}-\alpha = \epsilon_n-{f(x_n)\over f'... ...n^2 f''(\zeta)- {\epsilon_n^2 \over 2} f''(\xi)}\over f'(x_n)}$$

もし, $\epsilon_n$ が十分小なら $f''(\xi), f''(\zeta) \simeq f''(\alpha)$, $f'(x_n) \simeq f'(\alpha)$ より

$$\epsilon_{n+1} \simeq {f''(\alpha) \over {2f'(\alpha)}} \epsilon_n^2$$

すなわち, Newton 法では, $x_n$ が解 $\alpha$ に十分近くなると誤差は 2 乗, 4 乗, 8 乗と減る. これを二次収束するという. しかし, 解から遠いと何が起こるかわからない. (不安定)

例 13.1   $a > 0$ とし $f(x) = x^2-a$ とする. $f(x)=0$ の根 $\sqrt{a}$ を Newton 法で求めるプログラムを書く. $x_{n+1} = 1/2(x_n+a/x_n)$ より 次のプログラムを得る. 収束判定は, $\vert x_{n+1}-x_n\vert < \epsilon$ で 行う.

def sqrt(A,Eps) {
    X = deval(A); /* 倍精度浮動小数に変換 */
    while ( 1 ) {
        Y = (X+A/X)/2;
        if ( abs(X-Y) < Eps )
            return Y;
        else
            X = Y;
    }
}

/* if ( X > 0 ) return X; else return -X と同じ */

def abs(X) { return X > 0 ? X : -X; }

倍精度浮動小数に変換するのは, 有理数で計算しても時間がかかるだけで あまり意味がないから.

演習 13.1   平方根を二分法で計算するプログラムを書き, 収束の様子(回数) を比較せよ. 真の値は eval(A^(1/2),N) で見ればよい. N は十進での桁数で, 十分大きくとっておく.

演習 13.2   3 次方程式 $x^3+Ax^2+Bx+C=0$ の実根を Newton 法で求めるプログラムを書け.

1. レベル 1

   とりあえず一根を求める. 反復が停止しないなどという失敗も有り得る.

2. レベル 2

   失敗を検知して, 初期値をとり直しをする.

3. レベル 3

   実根の個数をあらかじめ調べ, 場合分けして初期値を適切に設定し, 全実根を求める.