iteración de punto fijo

Algoritmo de búsqueda de raíces

En 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 sobre números reales con valores reales y dado un punto en el dominio de , la iteración de punto fijo es ${\displaystyle f}$ ${\displaystyle x_{0}}$ ${\displaystyle f}$

$${\displaystyle x_{n+1}=f(x_{n}),\,n=0,1,2,\dots }$$

secuenciade funciones iteradasconverjan ${\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 del punto fijo de Banach y por eso 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 aproximarnos al límite (desde cualquier punto de partida ). Este es un caso especial 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 del 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 del 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 del 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 muestra el siguiente ejemplo. la iteración
  $${\displaystyle x_{n+1}={\begin{cases}{\frac {x_{n}}{2}},&x_{n}\neq 0\\1,&x_{n}=0\end{cases}}}$$
  converge a 0 para todos los valores de . Sin embargo, 0 no es un punto fijo de la función. ${\displaystyle x_{0}}$
  $${\displaystyle f(x)={\begin{cases}{\frac {x}{2}},&x\neq 0\\1,&x=0\end{cases}}}$$
  ya que esta función no es continua en y de hecho no tiene puntos fijos. ${\displaystyle x=0}$

Atrayendo puntos fijos

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

Un punto fijo atractivo de una función f es un punto fijo x _fix de f con una vecindad U de puntos "lo suficientemente cercanos" alrededor de x _fix tal que para cualquier valor de x en U , la secuencia de iteración de punto fijo

$${\displaystyle x,\ f(x),\ f(f(x)),\ f(f(f(x))),\dots }$$

Uconvergex _fixx _fixU^[1]

La función coseno natural ("natural" significa en radianes , no en grados u otras unidades) tiene exactamente un punto fijo, y ese punto fijo es la atracción. En este caso, "lo 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 la gráfica de la función coseno intersecta la recta . ^[2] ${\displaystyle y=x}$

No todos los puntos fijos 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 repelente. ${\displaystyle f(x)=2x}$

Un punto fijo atractivo se dice que es un punto fijo estable si también es estable de Lyapunov .

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

Se pueden reunir 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 da una condición suficiente para la existencia de puntos fijos atractivos. Una función de mapeo de contracción definida en un espacio métrico completo tiene precisamente un punto fijo, y la iteración del punto fijo es atraída hacia ese punto fijo para cualquier suposición inicial en el dominio de la función. Los casos especiales comunes son que (1) se define en la recta real con valores reales y es continua de Lipschitz con constante de Lipschitz _, y (2) la función f es continuamente diferenciable en una vecindad abierta de un punto fijo xfix , y . ${\displaystyle f}$ ${\displaystyle x_{0}}$ ${\displaystyle f}$ ${\displaystyle L<1}$ ${\displaystyle |f'(x_{\text{fix}})|<1}$

Aunque existen otros teoremas de puntos fijos , éste 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 converja al punto fijo. Generalmente podemos utilizar el teorema del punto fijo de Banach para demostrar que el punto fijo es atractivo.

Atractores

Atraer puntos fijos es un caso especial de un concepto matemático más amplio de atractores . Las iteraciones de punto fijo son un sistema dinámico discreto en una variable. La teoría de la bifurcación estudia sistemas dinámicos y clasifica diversos comportamientos como la atracción de puntos fijos, órbitas periódicas o atractores extraños . Un sistema de ejemplo 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 el que la enésima aproximación se deriva de las anteriores. Las iteraciones convergentes de punto fijo son formalizaciones matemáticamente rigurosas de métodos iterativos.

Ejemplos de métodos iterativos

• El método de Newton es un algoritmo de búsqueda de raíces para encontrar raíces de una función diferenciable dada . La iteración es ${\displaystyle f(x)}$ ${\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 , entonces ${\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 raíz de . Bajo los supuestos del teorema del punto fijo de Banach , la iteración de Newton, enmarcada como el método del punto fijo, demuestra convergencia lineal . Sin embargo, 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 es k , menos estable es y más costoso computacionalmente. Por estos motivos, normalmente no se utilizan métodos de orden superior. ${\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 verse como 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 muestra que las ecuaciones diferenciales ordinarias tienen soluciones, es esencialmente una aplicación del teorema del 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 convergencia

La velocidad de convergencia de la secuencia de iteración se puede aumentar utilizando un método de aceleración de 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 del caos

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

El término juego del caos se refiere a un método para generar el punto fijo de cualquier sistema de funciones iteradas (IFS). 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 IFS dado seleccionado aleatoriamente para cada iteración. Por tanto, el juego del caos es una iteración aleatoria de punto fijo. El juego del caos permite trazar la forma general de un fractal como el triángulo de Sierpinski repitiendo el proceso iterativo un gran número de veces. Más matemáticamente, las iteraciones convergen al punto fijo del IFS. Siempre que x ₀ pertenece al atractor del IFS, todas las iteraciones x _k permanecen dentro del atractor y, con probabilidad 1, forman un conjunto denso en este último.

Ver 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 A-estables si las iteraciones permanecen limitadas durante mucho tiempo, lo que está más allá del alcance de este artículo.

1. Rassias, Temístocles M.; Pardalos, Panos M. (17 de septiembre de 2014). Matemáticas sin límites: encuestas en matemáticas puras. Saltador. 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 utilizando Excel, Hojas de cálculo en educación (eJSiE): vol. 10: Edición. 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 y 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 . Saltador. ISBN 978-4-431-54971-0.

Otras lecturas

• Carga, Richard L.; Ferias, J. Douglas (1985). "Iteración de punto fijo". Análisis numérico (Tercera ed.). Editores de PWS. ISBN 0-87150-857-5.
• Hoffman, Joe D.; Frankel, Steven (2001). "Iteración de punto fijo". Métodos numéricos para ingenieros y científicos (Segunda ed.). 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: Prensa del MIT. págs. 165-167. ISBN 0-262-10071-1.
• Sternberg, Shlomo (2010). "Iteración y puntos fijos". Sistemas dinámicos (Primera ed.). Publicaciones de Dover. ISBN 978-0486477053.
• Shashkin, Yuri A. (1991). "9. El método de iteración". Puntos fijos (Primera ed.). Sociedad Matemática Estadounidense. 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)