Iteración de punto fijo

Algoritmo de búsqueda de raíces

En el análisis numérico , la iteración de punto fijo es un método para calcular puntos fijos de una función.

Más específicamente, dada una función definida en los números reales con valores reales y dado un punto en el dominio de , la iteración de punto fijo es que da lugar a la secuencia de aplicaciones de funciones iteradas que se espera que converjan a un punto . Si es continua, entonces se puede demostrar que la obtenida es un punto fijo de , es decir, ${\displaystyle f}$ ${\displaystyle x_{0}}$ ${\displaystyle f}$ $${\displaystyle x_{n+1}=f(x_{n}),\,n=0,1,2,\dots }$$ ${\displaystyle x_{0},x_{1},x_{2},\dots }$ ${\displaystyle x_{0},f(x_{0}),f(f(x_{0})),\dots }$ ${\displaystyle x_{\text{fix}}}$ ${\displaystyle f}$ ${\displaystyle x_{\text{fix}}}$ ${\displaystyle f}$ $${\displaystyle f(x_{\text{fix}})=x_{\text{fix}}.}$$

De manera más general, la función se puede definir en cualquier espacio métrico con valores en ese mismo espacio. ${\displaystyle f}$

Ejemplos

La iteración de punto fijo x _{n + 1} = sen x _n con valor inicial x ₀ = 2 converge a 0. Este ejemplo no satisface los supuestos del teorema de punto fijo de Banach y, por lo tanto, su velocidad de convergencia es muy lenta.

• Un primer ejemplo sencillo y útil es el método babilónico para calcular la raíz cuadrada de a > 0 , que consiste en tomar , es decir, el valor medio de x y a / x , para aproximarse al límite (a partir de cualquier punto de partida ). Se trata de un caso particular del método de Newton que se cita a continuación. ${\displaystyle f(x)={\frac {1}{2}}\left({\frac {a}{x}}+x\right)}$ ${\displaystyle x={\sqrt {a}}}$ ${\displaystyle x_{0}\gg 0}$
• La iteración de punto fijo converge al único punto fijo de la función para cualquier punto de partida Este ejemplo satisface (a más tardar después del primer paso de iteración) los supuestos del teorema de punto fijo de Banach . Por lo tanto, el error después de n pasos satisface (donde podemos tomar , si comenzamos desde ). Cuando el error es menor que un múltiplo de para alguna constante q , decimos que tenemos convergencia lineal . El teorema de punto fijo de Banach permite obtener iteraciones de punto fijo con convergencia lineal. ${\displaystyle x_{n+1}=\cos x_{n}\,}$ ${\displaystyle f(x)=\cos x\,}$ ${\displaystyle x_{0}.}$ ${\displaystyle |x_{n}-x|\leq {q^{n} \over 1-q}|x_{1}-x_{0}|=Cq^{n}}$ ${\displaystyle q=0.85}$ ${\displaystyle x_{0}=1}$ ${\displaystyle q^{n}}$
• El requisito de que f sea continua es importante, como lo demuestra el siguiente ejemplo. La iteración converge a 0 para todos los valores de . Sin embargo, 0 no es un punto fijo de la función , ya que esta no es continua en , y de hecho no tiene puntos fijos. $${\displaystyle x_{n+1}={\begin{cases}{\frac {x_{n}}{2}},&x_{n}\neq 0\\1,&x_{n}=0\end{cases}}}$$ ${\displaystyle x_{0}}$ $${\displaystyle f(x)={\begin{cases}{\frac {x}{2}},&x\neq 0\\1,&x=0\end{cases}}}$$ ${\displaystyle x=0}$

Atraer puntos fijos

La iteración de punto fijo x _{n +1} = cos x _n con valor inicial x ₁ = −1 .

Un punto fijo de atracción de una función f es un punto fijo _x de f con un entorno U de _puntos "suficientemente cercanos" alrededor de x de tal manera que para cualquier valor de x en U , la secuencia de iteración _de punto fijo está contenida en U y converge a x . La cuenca de atracción de _x es el entorno U más grande de este tipo . ^[1] $${\displaystyle x,\ f(x),\ f(f(x)),\ f(f(f(x))),\dots }$$

La función coseno natural ("natural" significa en radianes , no en grados u otras unidades) tiene exactamente un punto fijo, y ese punto fijo atrae. En este caso, "suficientemente cerca" no es un criterio estricto en absoluto; para demostrarlo, comience con cualquier número real y presione repetidamente la tecla cos en una calculadora (verificando primero que la calculadora esté en modo "radianes"). Finalmente converge al número de Dottie (aproximadamente 0,739085133), que es un punto fijo. Ahí es donde el gráfico de la función coseno interseca la línea . ^[2] ${\displaystyle y=x}$

No todos los puntos fijos se atraen. Por ejemplo, 0 es un punto fijo de la función f ( x ) = 2 x , pero la iteración de esta función para cualquier valor distinto de cero diverge rápidamente. Decimos que el punto fijo de es repulsivo. ${\displaystyle f(x)=2x}$

Se dice que un punto fijo atractor es un punto fijo estable si también es estable según el método de Lyapunov .

Se dice que un punto fijo es neutralmente estable si es estable según el método de Lyapunov pero no atrae. El centro de una ecuación diferencial homogénea lineal de segundo orden es un ejemplo de punto fijo neutralmente estable.

Se pueden agrupar múltiples puntos de atracción en un conjunto fijo de atracción .

Teorema del punto fijo de Banach

El teorema del punto fijo de Banach proporciona una condición suficiente para la existencia de puntos fijos atractivos. Una función de aplicación de contracción definida en un espacio métrico completo tiene precisamente un punto fijo, y la iteración de punto fijo es atraída hacia ese punto fijo para cualquier aproximación inicial en el dominio de la función. Los casos especiales comunes son que (1) está definida en la línea real con valores reales y es Lipschitz continua con la constante de Lipschitz , y (2) la función f es continuamente diferenciable en un entorno abierto de un punto fijo x _fix , y . ${\displaystyle f}$ ${\displaystyle x_{0}}$ ${\displaystyle f}$ ${\displaystyle L<1}$ ${\displaystyle |f'(x_{\text{fix}})|<1}$

Aunque existen otros teoremas de punto fijo , este en particular es muy útil porque no todos los puntos fijos son atractivos. Al construir una iteración de punto fijo, es muy importante asegurarse de que converge al punto fijo. Por lo general, podemos usar el teorema de punto fijo de Banach para demostrar que el punto fijo es atractivo.

Atractores

Los puntos fijos que atraen son un caso especial de un concepto matemático más amplio, el de atractores . Las iteraciones de puntos fijos son un sistema dinámico discreto sobre una variable. La teoría de la bifurcación estudia los sistemas dinámicos y clasifica diversos comportamientos, como los puntos fijos que atraen, las órbitas periódicas o los atractores extraños . Un ejemplo de sistema es el mapa logístico .

Métodos iterativos

En matemáticas computacionales, un método iterativo es un procedimiento matemático que utiliza un valor inicial para generar una secuencia de soluciones aproximadas mejoradas para una clase de problemas, en la que la aproximación n-ésima se deriva de las anteriores. Las iteraciones convergentes de punto fijo son formalizaciones matemáticamente rigurosas de los métodos iterativos.

Ejemplos de métodos iterativos

• El método de Newton es un algoritmo de búsqueda de raíces para encontrar las raíces de una función diferenciable dada . ${\displaystyle f(x)}$ La iteración es ${\textstyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.}$

  Si escribimos , podemos reescribir la iteración de Newton como la iteración de punto fijo . ${\textstyle g(x)=x-{\frac {f(x)}{f'(x)}}}$ ${\textstyle x_{n+1}=g(x_{n})}$

  Si esta iteración converge a un punto fijo de g , entonces , por lo que ${\displaystyle x_{\text{fix}}}$ ${\textstyle x_{\text{fix}}=g(x_{\text{fix}})=x_{\text{fix}}-{\frac {f(x_{\text{fix}})}{f'(x_{\text{fix}})}}}$ ${\textstyle f(x_{\text{fix}})/f'(x_{\text{fix}})=0,}$

  por lo tanto , es decir, es una raíz de . Bajo los supuestos del teorema de punto fijo de Banach , la iteración de Newton, enmarcada como un método de punto fijo, demuestra al menos convergencia lineal . Un análisis más detallado muestra convergencia cuadrática , es decir, , bajo ciertas circunstancias. ${\displaystyle f(x_{\text{fix}})=0}$ ${\displaystyle x_{\text{fix}}}$ ${\displaystyle f}$ ${\textstyle |x_{n}-x_{\text{fix}}|<Cq^{2^{n}}}$
• El método de Halley es similar al método de Newton cuando funciona correctamente, pero su error es ( convergencia cúbica ). En general, es posible diseñar métodos que converjan con velocidad para cualquier . Como regla general, cuanto mayor sea el valor de k , menos estable será y más costoso computacionalmente será. Por estas razones, los métodos de orden superior normalmente no se utilizan. ${\displaystyle |x_{n}-x_{\text{fix}}|<Cq^{3^{n}}}$ ${\displaystyle Cq^{k^{n}}}$ ${\displaystyle k\in \mathbb {N} }$
• Los métodos de Runge-Kutta y los solucionadores numéricos de ecuaciones diferenciales ordinarias en general pueden considerarse iteraciones de punto fijo. De hecho, la idea central al analizar la estabilidad A de los solucionadores de EDO es comenzar con el caso especial , donde es un número complejo , y verificar si el solucionador de EDO converge al punto fijo siempre que la parte real de sea negativa. ^[a] ${\displaystyle y'=ay}$ ${\displaystyle a}$ ${\displaystyle y_{\text{fix}}=0}$ ${\displaystyle a}$
• El teorema de Picard-Lindelöf , que demuestra que las ecuaciones diferenciales ordinarias tienen soluciones, es esencialmente una aplicación del teorema de punto fijo de Banach a una secuencia especial de funciones que forma una iteración de punto fijo, construyendo la solución de la ecuación. Resolver una EDO de esta manera se denomina iteración de Picard , método de Picard o proceso iterativo de Picard .
• La capacidad de iteración de Excel se puede utilizar para encontrar soluciones a la ecuación de Colebrook con una precisión de 15 cifras significativas. ^{[3] [4]}
• Algunos de los esquemas de "aproximación sucesiva" utilizados en programación dinámica para resolver la ecuación funcional de Bellman se basan en iteraciones de punto fijo en el espacio de la función de retorno. ^{[5] [6]}
• El modelo de telaraña de la teoría de precios corresponde a la iteración de punto fijo de la composición de la función de oferta y la función de demanda. ^[7]

Aceleración de la convergencia

La velocidad de convergencia de la secuencia de iteraciones se puede aumentar utilizando un método de aceleración de la convergencia, como la aceleración de Anderson y el proceso delta-cuadrado de Aitken . La aplicación del método de Aitken a la iteración de punto fijo se conoce como método de Steffensen y se puede demostrar que el método de Steffensen produce una tasa de convergencia que es al menos cuadrática.

Juego de caos

Triángulo de Sierpinski creado usando IFS, seleccionando todos los miembros en cada iteración

El término juego de caos se refiere a un método para generar el punto fijo de cualquier sistema de funciones iteradas (SFI). Comenzando con cualquier punto x ₀ , las iteraciones sucesivas se forman como x _{k +1} = f _r ( x _k ) , donde f _r es un miembro del SFI dado seleccionado aleatoriamente para cada iteración. Por lo tanto, el juego de caos es una iteración de punto fijo aleatoria. El juego de caos permite trazar la forma general de un fractal como el triángulo de Sierpinski repitiendo el proceso iterativo una gran cantidad de veces. Más matemáticamente, las iteraciones convergen al punto fijo del SFI. Siempre que x ₀ pertenece al atractor del SFI, todas las iteraciones x _k permanecen dentro del atractor y, con probabilidad 1, forman un conjunto denso en este último.

Véase también

• Combinador de punto fijo
• Trama de telaraña
• Cadena de Markov
• Composiciones infinitas de funciones analíticas
• Tasa de convergencia

Referencias

1. También se pueden considerar ciertas iteraciones como A-estables si las iteraciones permanecen acotadas durante un largo tiempo, lo que está más allá del alcance de este artículo.

1. Rassias, Themistocles M.; Pardalos, Panos M. (17 de septiembre de 2014). Matemáticas sin fronteras: encuestas sobre matemáticas puras. Springer. ISBN 978-1-4939-1106-6.
2. Weisstein, Eric W. "Número Dottie". Wolfram MathWorld . Wolfram Research, Inc . Consultado el 23 de julio de 2016 .
3. MA Kumar (2010), Resolver ecuaciones implícitas (Colebrook) dentro de la hoja de trabajo, Createspace, ISBN 1-4528-1619-0 
4. Brkic, Dejan (2017) Solución de la ecuación implícita de Colebrook para la fricción de flujo usando Excel, Hojas de cálculo en educación (eJSiE): vol. 10: núm. 2, artículo 2. Disponible en: https://sie.scholasticahq.com/article/4663-solution-of-the-implicit-colebrook-equation-for-flow-friction-using-excel
5. Bellman, R. (1957). Programación dinámica, Princeton University Press.
6. Sniedovich, M. (2010). Programación dinámica: fundamentos y principios, Taylor & Francis .
7. Onozaki, Tamotsu (2018). "Capítulo 2. Modelo de telaraña no lineal unidimensional". No linealidad, racionalidad limitada y heterogeneidad: algunos aspectos de las economías de mercado como sistemas complejos . Springer. ISBN 978-4-431-54971-0.

Lectura adicional

• Burden, Richard L.; Faires, J. Douglas (1985). "Fixed-Point Iteration". Análisis numérico (tercera edición). PWS Publishers. ISBN 0-87150-857-5.
• Hoffman, Joe D.; Frankel, Steven (2001). "Fixed-Point Iteration". Métodos numéricos para ingenieros y científicos (segunda edición). Nueva York: CRC Press. págs. 141–145. ISBN 0-8247-0443-6.
• Judd, Kenneth L. (1998). "Iteración de punto fijo". Métodos numéricos en economía . Cambridge: MIT Press. pp. 165–167. ISBN 0-262-10071-1.
• Sternberg, Shlomo (2010). "Iteración y puntos fijos". Sistemas dinámicos (primera edición). Dover Publications. ISBN 978-0486477053.
• Shashkin, Yuri A. (1991). "9. El método de iteración". Puntos fijos (Primera edición). American Mathematical Society. ISBN 0-8218-9000-X.
• Rosa, Alejandro (2021). "Una historia episódica del diagrama de iteración escalonada". Antiquitates Mathematicae . 15 : 3–90. doi : 10.14708/am.v15i1.7056. S2CID  247259939.

Enlaces externos

• Algoritmos de punto fijo en línea
• Calculadora en línea de iteración de punto fijo (Asistente matemático en la Web)