ニュートン法

ニュートン法は、一つのステップを繰り返してfの根、つまり$f(r) = 0$を満たす数rを近似します。現在の近似値$x_n$に対して、グラフ上の点$(x_n, f(x_n))$での接線$L(x) = f(x_n) + f'(x_n)(x - x_n)$を考えます。$x_n$の近くでは接線が曲線に近いため、接線とx軸の交点は、曲線と軸の交点のよりよい近似になります。$L(x) = 0$を解くと次の近似値が得られます。図の各ステップでは、$x_n$から薄い破線に沿って曲線まで進み、次に接線に沿って軸まで進みます。

誤差を$e_n = x_n - r$とします。rが単根（$f'(r) \ne 0$）で、fの二階導関数が連続なら、$x_n$がrに近いとき、ステップのテイラー展開から$e_{n+1} \approx \frac{f''(r)}{2f'(r)}\,e_n^2$を得ます。誤差を二乗すると、正しい桁数はおよそ2倍になります。x² − 2をx₀ = 1から始めた誤差は0.086、0.0025、2.1 × 10⁻⁶、1.6 × 10⁻¹²で、表示では$e_n/e_{n-1}^2$が$1/(2\sqrt2) \approx 0.354$に近づきます。根から遠い場所では保証されません。$f''(r) = 0$なら二乗の項が消えてさらに速くなります。arctan xでは次の誤差は約$-\tfrac23 e_n^3$で、毎回三乗になります。

このステップには$f'(x_n) \ne 0$が必要です。水平な接線は軸と交わらず、ほぼ水平な接線は遠くで交わります。x² − 2を0.1から始めると、最初の着地点は10.05です。遠くへ逃げなくても失敗することがあります。x³ − 2x + 2では、0での接線は1へ、1での接線は0へ戻り、0の近くの初期値もこの周期に引き込まれます。数列は有界ですが極限を持ちません。arctan xには、$2\alpha = (1 + \alpha^2)\arctan\alpha$を満たすα ≈ 1.3917という境界があります。|x₀| < αなら収束し、それを超えると毎回反対側のさらに遠くに着地します。「すべての初期値」は行き着く先に応じてx軸を色分けします。x³ − 2x + 2では[−3, 3]の約5分の1が周期に入り、接線が水平になる$\pm\sqrt{2/3}$へ集まる細い帯も含まれます。初期値を複素数にすると、これらの帯はニュートンフラクタルになります。

重根では$f'(r) = 0$も成り立ち、誤差が二乗で減る性質が失われます。$(x - 1)^2$ではステップが厳密に$x_{n+1} = (x_n + 1)/2$となるため、誤差は毎回半分になります。これは一次収束で、小数が新たに1桁正しくなるまで約3.3ステップかかります。重複度mの根の近くでは、比$e_{n+1}/e_n$が$(m - 1)/m$に近づきます。