ニュートン法ビジュアライザー

ニュートン法は局所的な傾きの情報を利用するため強力で、良い初期値を選べば1ステップごとに正しい桁数がほぼ倍になることもあります。同じ仕組みが、傾きがほぼゼロの場所や吸引域の境界付近では失敗の原因にもなります。x0のわずかな違いが、別の根、周期的な振る舞い、あるいは発散につながることがあります。

曲線がゼロを横切る点を探すため、ニュートン法は現在の推定値における接線で曲線を置き換え、その直線がx軸と交わる点へ跳びます。滑らかな曲線は近くで見るとほぼ直線に見えるので、この交点はたいてい真の根にずっと近づきます。これを繰り返すと素早く収束します。公式は x_{n+1} = x_n − f(x_n)/f'(x_n) です。

現代のCPUは a/b を計算するとき、まず 1/b を求めることが多く、ニュートン法はこれを割り算をいっさい使わずに実現します。f(x) = 1/x − a に適用すると反復式 x_{n+1} = x_n(2 − a·x_n) が得られ、乗算と減算だけで構成されます。これらはハードウェアが安価に行える演算です。同じ技法は高速な逆数平方根ルーチン、Quake III の有名な例の裏にもあります。