平均減衰が魔法のように固定点計算機の収束をスピードアップするのはなぜですか？

Question

私はSICPを読んでおり、著者は、機能の固定点を計算する際に平均減衰の手法をブラッシングしています。私はそれが特定の場合、つまり関数の振動を抑えるために正方形の根が必要であることを理解しています y = x/y しかし、なぜそれが固定点計算関数の収束を魔法のように助けるのか理解していません。ヘルプ？

編集

明らかに、私はこれを多少考えました。関数を平均することで、それ自体を平均することで、繰り返し適用すると収束がスピードアップされる理由が頭を包むことができないようです。

Answer 1

繰り返しアプリケーションがFixpointを「ホップ」する機能を高速化するだけです。直感的には、振り子にブレーキを追加するようなものです。ブレーキでより早く停止します。

しかし、すべての関数にこのプロパティがあるわけではありません。検討 f(x)=x/2. 。この関数は、平均減衰（ログベース2ステップ対ログベース（4/3）ステップ）なしでより早く収束します。これは、片側からフィックスポイントに近づくためです。

Answer 2

数学的にあなたの質問に答えることはできませんが、直感的なものを試してみてください。FixPointテクニックには、..Well .. FixPointの周りに「フラット」関数グラフが必要です。これは、XYチャートにFixPoint関数を想像すると、この関数が真の結果で斜め（+x、+y）を正確に越えていることがわかります。 FixPointアルゴリズムの1つのステップでは、最初の導関数が（-1 ..+1）の間にある交差点の周りの間隔内にある必要があるx値を推測しており、Y値を取得します。あなたが取ったyは、交差点に近いものになります。 交差点から始めて、+/- 1よりも勾配が小さいパスに従うことで到達できます。 、あなたが利用した以前のx値とは対照的に、この意味で正確な勾配-1があります。勾配が小さいほど、Yを新しいXとして使用するときに交差点（真の関数値）に向かってより多くの方法を作る方法がすぐに明らかになります。最初のステップの真の値。

すべての数学者に申し訳ありません。