反復は一点へ吸い込まれる
電卓に好きな数を入れて cos ボタンを押し続けてください。結果はある値の近く、約 0.7391 で変わらなくなります。関数に自分の出力を何度も食わせるこの単純な操作が、不動点反復です。x の次に g(x)、その次に g(g(x))。g(x)=x となる点、つまり入れたものがそのまま出てくる点に達すると止まります。それが不動点です。驚くのは、ほとんどどこから出発しても同じ点へ吸い込まれること。ただし条件があります。不動点の近くで傾き |g'| が1より小さくなければなりません。そうして初めて毎歩、距離が縮む収縮になるのです。この考えは方程式の解法からコンピュータグラフィックス、経済の均衡、グーグルのページランクまで至る所に潜んでいます。そしてニュートン法も、その正体は非常に速い不動点反復です。
青い曲線が g(x)=cos x、破線が y=x です。二つが交わる緑の点が不動点です。一歩を押すと蜘蛛の巣（cobweb）が描かれます。今の x から垂直に曲線まで上がって次の値を読み、そこから水平に y=x 線まで進んでそれを新しい x にします。開始 x0 をどこに動かしても、蜘蛛の巣が交点へぐるぐると吸い込まれるのが見えます。この一枚の図が不動点反復のすべてです。
なぜある反復は集まり、別の反復は散るのでしょうか。答えは傾き一つです。ここでの g は直線で、不動点は1です。スライダー a がまさに g' です。|a| を1より小さくすると、緑の蜘蛛の巣が不動点へきれいに収まります。これが収縮です。|a| を1より大きくすると赤に変わり、不動点から押し出されて発散します。さらに |a| が0に近いほど、わずか数歩で終わります。小さな傾きこそ速い収束です。
同じ直線 g ですが、今度は a の符号に注目します。傾きの大きさは収束するかを決め、符号は形を決めます。a が正なら、不動点へ片側から単調に近づく階段になります。a が負なら、不動点をはさんで上下に行き来する螺旋になり、毎歩、符号が反転して振動します。スライダーを0をまたいで動かすと、階段が螺旋に、螺旋が階段に変わる瞬間が見えます。
収束は保証されても、速さは大きく変わります。許容誤差 1e-6 に達するまでの歩数はおよそ n ≈ log(tol)/log|g'| です。曲線がその数を |g'| に対して示します。スライダーを0.5あたりにすると二十歩ほどで終わりますが、0.95へ寄せると数百歩に跳ね上がります。1に近い収縮は収束はしますが、じれったいほど遅い。だからこそ、より賢い方法が欲しくなるのです。
ここにその賢い方法があります。普通の不動点反復は線形収束で、誤差は毎歩、一定の割合（例えば半分）でしか減りません。棒はゆるやかに下がります。ニュートン法は2次収束で、誤差が毎歩、自乗されます。正しい桁が2倍ずつ増え、棒が崖のように落ちます。トグルで切り替えると、同じ 1e-10 の精度に、線形は数十歩、2次はわずか四、五歩です。ニュートンが、根で g'=0 となるよう g を巧みに設計した、最速の不動点反復である理由です。