¿Por qué amortiguación media mágicamente a acelerar la convergencia de las calculadoras de punto fijo?

Question

Estoy leyendo a través SICP, y los autores pincel sobre la técnica de amortiguación promedio en el cálculo de los puntos fijos de funciones. Yo entiendo que es necesario en ciertos casos, es decir, raíces cuadradas con el fin de amortiguar la oscilación de la función y = x/y sin embargo, no entiendo por qué mágicamente ayuda a la convergencia de la función de cálculo de punto fijo. Ayuda?

editar

Obviamente, he pensado esto a través de un tanto. Parece que no puedo envolver mi cabeza alrededor de un promedio de por qué una función consigo misma sería acelerar la convergencia cuando se aplica repetidamente.

Answer 1

Es sólo acelera las funciones cuyas repetidas aplicaciones de "saltar de un lado" el punto fijo. Intuitivamente, es como la adición de un freno a un péndulo -. Que va a parar más pronto con el freno

Sin embargo, no todas las funciones tiene esta propiedad. Considere f(x)=x/2. Esta función convergerá más pronto sin el medio de amortiguación (logaritmo en base 2 pasos vs log base (4/3) pasos), ya que se acerca al punto fijo de un lado.

Answer 2

Aunque no puedo responder a su pregunta sobre una base matemática, voy a tratar en una intuitivo: técnicas de punto fijo necesitan un gráfico de la función "plana" en torno a su ..well .. punto fijo. Esto significa que: si usted representa su función de punto fijo en un gráfico de X-Y, verá que la función cruza la diagonal (x, + y) exactamente en el resultado verdadero. En un paso de su algoritmo de punto fijo que está adivinando un valor de X que tiene que estar dentro del intervalo de alrededor del punto de intersección donde la primera derivada es entre (-1 .. + 1) y tomar el valor de Y. The Y que tomó estará más cerca al punto de intersección porque a partir de la intersección es alcanzable siguiendo un camino que tiene una pendiente menor que +/- 1 , en contraste con el valor X anterior que que se utilizan, que tiene en este sentido, la pendiente exacta -1. Es claro ahora que cuanto menor sea la pendiente, la forma de hacer más hacia el punto de intersección (el verdadero valor de la función) cuando se utiliza la Y como nueva X. La mejor función de interpolación es trivialmente una constante, que tiene pendiente 0, dándole el valor verdadero en el primer paso.

Lo siento por todos los matemáticos.