Método iterativo

Algoritmo en el que cada aproximación de la solución se deriva de aproximaciones anteriores.

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 i -ésima aproximación (llamada "iterar") se deriva de las anteriores.

Una implementación específica con criterios de terminación para un método iterativo dado como descenso de gradiente , escalada de colinas , método de Newton o métodos cuasi-Newton como BFGS , es un algoritmo de un método iterativo o un método de aproximación sucesiva . Un método iterativo se denomina convergente si la secuencia correspondiente converge para aproximaciones iniciales dadas. Generalmente se realiza un análisis de convergencia matemáticamente riguroso de un método iterativo; sin embargo, los métodos iterativos basados ​​en heurísticas también son comunes.

Por el contrario, los métodos directos intentan resolver el problema mediante una secuencia finita de operaciones. En ausencia de errores de redondeo , los métodos directos proporcionarían una solución exacta (por ejemplo, resolver un sistema lineal de ecuaciones mediante eliminación gaussiana ). Los métodos iterativos suelen ser la única opción para ecuaciones no lineales . Sin embargo, los métodos iterativos suelen ser útiles incluso para problemas lineales que involucran muchas variables (a veces del orden de millones), donde los métodos directos serían prohibitivamente costosos (y en algunos casos imposibles) incluso con la mejor potencia de cálculo disponible. ^[1] ${\displaystyle A\mathbf {x} =\mathbf {b} }$

Puntos fijos atractivos

Si una ecuación puede ser puesta en la forma f ( x ) = x , y una solución x es un punto fijo atractivo de la función f , entonces uno puede comenzar con un punto x ₁ en la cuenca de atracción de x , y sea x _{n + 1} = f ( x _n ) para n  ≥ 1, y la secuencia { x _n } _{n  ≥ 1} convergerá a la solución x . Aquí x _n es la n ésima aproximación o iteración de x y x _{n + 1} es la siguiente o n + 1 iteración de x . Alternativamente, los superíndices entre paréntesis se usan a menudo en métodos numéricos, para no interferir con subíndices con otros significados. (Por ejemplo, x ^{( n + 1)} = f ( x ^{( n )} ).) Si la función f es continuamente diferenciable , una condición suficiente para la convergencia es que el radio espectral de la derivada esté estrictamente acotado por uno en un entorno del punto fijo. Si esta condición se cumple en el punto fijo, entonces debe existir un vecindario suficientemente pequeño (cuenca de atracción).

Sistemas lineales

En el caso de un sistema de ecuaciones lineales , las dos clases principales de métodos iterativos son los métodos iterativos estacionarios y los métodos del subespacio de Krylov más generales .

Métodos iterativos estacionarios

Introducción

Los métodos iterativos estacionarios resuelven un sistema lineal con un operador que se aproxima al original y, basándose en una medición del error en el resultado ( el residuo ), forman una "ecuación de corrección" para la que se repite este proceso. Si bien estos métodos son simples de derivar, implementar y analizar, la convergencia solo está garantizada para una clase limitada de matrices.

Definición

Un método iterativo se define por

${\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}$

y para un sistema lineal dado con solución exacta el error por ${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle \mathbf {x} ^{*}}$

${\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.}$

Un método iterativo se denomina lineal si existe una matriz tal que ${\displaystyle C\in \mathbb {R} ^{n\times n}}$

${\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0}$

y esta matriz se llama matriz de iteración . Un método iterativo con una matriz de iteración dada se llama convergente si se cumple lo siguiente ${\displaystyle C}$

${\displaystyle \lim _{k\rightarrow \infty }C^{k}=0\,.}$

Un teorema importante establece que para un método iterativo dado y su matriz de iteración es convergente si y solo si su radio espectral es menor que la unidad, es decir, ${\displaystyle C}$ ${\displaystyle \rho (C)}$

${\displaystyle \rho (C)<1\,.}$

Los métodos iterativos básicos funcionan dividiendo la matriz en ${\displaystyle A}$

${\displaystyle A=M-N}$

y aquí la matriz debería ser fácilmente invertible . Los métodos iterativos ahora se definen como ${\displaystyle M}$

${\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b\,,\quad k\geq 0\,.}$

De esto se deduce que la matriz de iteración está dada por

${\displaystyle C=I-M^{-1}A=M^{-1}N\,.}$

Ejemplos

Los ejemplos básicos de métodos iterativos estacionarios utilizan una división de la matriz como ${\displaystyle A}$

${\displaystyle A=D+L+U\,,\quad D:={\text{diag}}((a_{ii})_{i})}$

donde es solo la parte diagonal de , y es la parte triangular inferior estricta de . Respectivamente, es la parte triangular superior estricta de . ${\displaystyle D}$ ${\displaystyle A}$ ${\displaystyle L}$ ${\displaystyle A}$ ${\displaystyle U}$ ${\displaystyle A}$

• Método Richardson : ${\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}$
• Método Jacobi : ${\displaystyle M:=D}$
• Método de Jacobi amortiguado : ${\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}$
• Método de Gauss-Seidel : ${\displaystyle M:=D+L}$
• Método de relajación sucesiva (SOR): ${\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}$
• Sobre-relajación sucesiva simétrica (SSOR): ${\displaystyle M:={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \not \in \{0,2\})}$

Los métodos iterativos estacionarios lineales también se denominan métodos de relajación .

Métodos del subespacio de Krylov

Los métodos de subespacio de Krylov funcionan formando una base de la secuencia de potencias de matriz sucesivas multiplicadas por el residuo inicial (la secuencia de Krylov ). Las aproximaciones a la solución se forman luego minimizando el residuo sobre el subespacio formado. El método prototípico en esta clase es el método del gradiente conjugado (CG) que supone que la matriz del sistema es simétrica positiva-definida . Para matrices simétricas (y posiblemente indefinidas) se trabaja con el método del residuo mínimo (MINRES). En el caso de matrices no simétricas, se han derivado métodos como el método del residuo mínimo generalizado (GMRES) y el método del gradiente biconjugado (BiCG). ${\displaystyle A}$ ${\displaystyle A}$

Convergencia de los métodos del subespacio de Krylov

Dado que estos métodos forman una base, es evidente que el método converge en N iteraciones, donde N es el tamaño del sistema. Sin embargo, en presencia de errores de redondeo, esta afirmación no se cumple; además, en la práctica, N puede ser muy grande y el proceso iterativo alcanza una precisión suficiente mucho antes. El análisis de estos métodos es difícil, ya que depende de una función compleja del espectro del operador.

Preacondicionadores

El operador de aproximación que aparece en los métodos iterativos estacionarios también se puede incorporar en métodos de subespacios de Krylov como GMRES (alternativamente, los métodos de Krylov preacondicionados se pueden considerar como aceleraciones de métodos iterativos estacionarios), donde se convierten en transformaciones del operador original en uno presumiblemente mejor condicionado. La construcción de preacondicionadores es un área de investigación amplia.

Métodos de aproximación sucesiva

Los métodos matemáticos relacionados con la aproximación sucesiva incluyen:

• Método babilónico para hallar raíces cuadradas de números ^[2]
• Iteración de punto fijo ^[3]
• Medios para encontrar ceros de funciones:
  • El método Halley
  • El método de Newton
• Las ecuaciones diferenciales son importantes:
  • Teorema de Picard-Lindelöf sobre la existencia de soluciones de ecuaciones diferenciales
  • Métodos de Runge-Kutta para la solución numérica de ecuaciones diferenciales

Historia

Jamshīd al-Kāshī utilizó métodos iterativos para calcular el seno de 1° y π en el Tratado de la cuerda y el seno con gran precisión. Un método iterativo temprano para resolver un sistema lineal apareció en una carta de Gauss a un estudiante suyo. Propuso resolver un sistema de ecuaciones de 4 por 4 resolviendo repetidamente el componente en el que el residuo era el más grande ^{[ cita requerida ]} .

La teoría de los métodos iterativos estacionarios se estableció sólidamente con el trabajo de DM Young a partir de la década de 1950. El método del gradiente conjugado también se inventó en la década de 1950, con desarrollos independientes de Cornelius Lanczos , Magnus Hestenes y Eduard Stiefel , pero su naturaleza y aplicabilidad fueron mal entendidas en ese momento. Solo en la década de 1970 se comprendió que los métodos basados ​​en la conjugación funcionan muy bien para ecuaciones diferenciales parciales , especialmente el tipo elíptico.

Véase también

• Portal de matemáticas

• Expresión de forma cerrada
• Refinamiento iterativo
• Método Kaczmarz
• Mínimos cuadrados no lineales
• Análisis numérico
• Algoritmo de búsqueda de raíces

Referencias

1. Amritkar, Amit; de Sturler, Eric; Świrydowicz, Katarzyna; Tafti, Danesh; Ahuja, Kapil (2015). "Reciclaje de subespacios de Krylov para aplicaciones de CFD y un nuevo solucionador de reciclaje híbrido". Journal of Computational Physics . 303 : 222. arXiv : 1501.03358 . Código Bibliográfico :2015JCoPh.303..222A. doi :10.1016/j.jcp.2015.09.040.
2. "Matemáticas babilónicas". Matemáticas babilónicas . 1 de diciembre de 2000.
3. Day, Mahlon (2 de noviembre de 1960). Teoremas de punto fijo para conjuntos convexos compactos . Mahlon M Day.

Enlaces externos

• Plantillas para la solución de sistemas lineales
• Y. Saad: Métodos iterativos para sistemas lineales dispersos, 1.ª edición, PWS 1996