¿Por qué la amortiguación promedio agiliza mágicamente la convergencia de las calculadoras de punto fijo?

Question

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

edición

Obviamente, he pensado esto a través de un tanto. No puedo entender por qué promediar una función consigo mismo acelerará la convergencia cuando se aplica repetidamente.

Answer 1

Solo acelera aquellas funciones cuyas aplicaciones repetidas "brincan" alrededor del punto fijo. Intuitivamente, es como agregar un freno a un péndulo: se detendrá antes con el freno.

Pero no todas las funciones tienen esta propiedad. Considere f(x)=x/2. Esta función convergerá más rápido sin la amortiguación promedio (base de registro 2 pasos frente a base de registro (4/3) pasos), ya que se acerca al punto fijo desde un lado.

Answer 2

Si bien no puedo responder a su pregunta sobre una base matemática, intentaré con una intuitiva: las técnicas de punto fijo necesitan un gráfico de función "plana" alrededor de su ... bien ... punto fijo. Esto significa que si visualiza su función de punto fijo en un gráfico 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 de referencia está adivinando un valor X que debe estar dentro del intervalo alrededor del punto de intersección donde la primera derivada se encuentra entre (-1 .. + 1) y toma el valor Y. La Y que tomó estará más cerca del punto de intersección porque comenzando desde la intersección es alcanzable siguiendo una ruta que tiene una pendiente más pequeña que +/- 1, en contraste con el valor de X anterior que utilizó, que tiene en este sentido, la pendiente exacta -1. Ahora está claro que cuanto menor es la pendiente, más se avanza hacia el punto de intersección (el verdadero valor de la función) cuando se usa Y como nueva X. La mejor función de interpolación es trivialmente una constante, que tiene pendiente 0, que le da el verdadero valor en el primer paso.

Disculpe a todos los matemáticos.