不動点反復 わかりやすく
電卓に数を入れて 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 次収束で、誤差が一歩ごとに二乗され、正しい桁が二倍ずつ増えて棒が崖のように落ちます。二つを切り替えると、同じ 1e-10 の精度に線形は数十歩、2 次は数歩です。ニュートンが g'=0 になるように g を設計した、いちばん速い不動点反復である理由です。