Análisis numérico básico, iteración de punto fijo

Question

Acabo de empezar con el análisis numérico, así que esta pregunta probablemente parezca trivial.

Digamos que tengo una función $f(x) = x^2 - x - 3$

Dejo que $g(x) = x^2 - 3$

Entonces quiero encontrar las raíces de $f(x)$ por lo que tengo $f(x) = g(x) - x = 0$

Así que puedo encontrar las raíces encontrando los puntos fijos de $x = g(x)$

Hasta aquí todo bien, ¿no?

Ahora uso la fórmula de iteración de punto fijo - $x_{n+1} = g(x_{n}) = x_{n}^2 - 3$

Digamos que elijo 3 para $x_{1}$ , entonces obtengo $x_{2} = 6$ y $x_{3} = 33$ ...por lo que es divergente

Luego traté de elegir 1 para $x_{1}$ , entonces obtengo $x_{2} = -2$ y $x_{3} = 1$ ...así que va a alternar infinitamente...

Así que el método de iteración de punto fijo no funciona. ¿Por qué no funciona en esta situación y cuáles son las condiciones que necesita para funcionar?

Answer 1

Pistas:

1. Traza la función: http://www.wolframalpha.com/input/?i=Solve%5Bx%5E2-x-3%3D0%2Cx%5D&t=crmtb01

2. Mira la sección 2.1 y 2.2 en: http://pages.cs.wisc.edu/~amos/412/lecture-notes/lecture03.pdf

¿Puedes averiguar qué es lo que está mal a partir de eso?

HTH

Answer 2

Una cosa a considerar es si la iteración es un mapa de contracción en una vecindad de la raíz deseada. Aquí la derivada de la función de iteración es $2x$ y esto tiene un valor absoluto mayor que 1 cerca de cualquier raíz.

En este caso, una iteración inversa suele funcionar como una contracción, es decir, aquí asignaríamos $\sqrt{x+3}$ a $x$ repetidamente para aproximar la raíz positiva.

La propiedad del mapa de contracción es que $|f(x)-f(y)|$ es menor que $|x-y|$ pero esta es una condición suficiente y no necesaria para la convergencia de una iteración al punto fijo. Sin embargo, si la desigualdad va en sentido contrario, los iterados no pueden converger al punto fijo.