Pourquoi la vitesse moyenne amortissement par magie la convergence des calculatrices à point fixe?

Question

Je lis à travers SICP, et les auteurs badigeonner la technique d'amortissement moyenne dans le calcul des points fixes de fonctions. Je comprends qu'il est nécessaire dans certains cas, soit des racines carrées pour amortir l'oscillation de la fonction y = x/y cependant, je ne comprends pas pourquoi il aide comme par magie la convergence de la fonction de calcul de point fixe. Aide?

modifier

De toute évidence, je l'ai réfléchi à cela un peu. Je ne peux pas sembler envelopper la tête autour de laquelle la moyenne d'une fonction avec elle-même permettrait d'accélérer la convergence lorsqu'elle est appliquée de façon répétée.

Answer 1

Il ne fait qu'accélérer les fonctions dont les demandes répétées « hop autour » du point fixe. Intuitivement, il est comme l'ajout d'un frein à un pendule -. Ça va arrêter plus tôt avec le frein

Mais pas toutes les fonctions a cette propriété. Tenez compte f(x)=x/2. Cette fonction converge plus tôt sans l'amortissement moyen (log base 2 étapes vs log base (4/3) étapes), car il se rapproche du point fixe d'un côté.

Answer 2

Alors que je ne peux pas répondre à votre question sur une base mathématique, je vais essayer sur un intuitif: techniques dénotationnelle ont besoin d'un graphe de fonction « plat » autour de leur ..well .. fixpoint. Cela signifie: si vous décrivez votre fonction fixpoint sur un graphique X-Y, vous verrez que la fonction traverse la diagonale (+ x, + y) exactement au vrai résultat. Dans une étape de votre algorithme fixpoint vous deviner une valeur X qui doit être dans l'intervalle autour du point d'intersection où la première dérivée est comprise entre (-1 .. + 1) et prendre la valeur Y. Y que vous avez pris sera plus proche du point d'intersection parce que à partir de l'intersection, il est accessible en suivant un chemin qui a une pente inférieure à +/- 1 , contrairement à la valeur précédente X qui vous avez utilisé, qui a dans ce sens, la pente exacte -1. Il est immédiatement clair maintenant que plus la pente, la manière plus que vous faites vers le point d'intersection (la vraie valeur de la fonction) lorsque vous utilisez Y comme nouveau X. La meilleure fonction d'interpolation est trivialement une constante qui a une pente de 0, vous donnant la valeur réelle dans la première étape.

Désolé à tous les mathématiciens.