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 los que la enésima aproximación 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 del método iterativo. Un método iterativo se llama 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, también son comunes los métodos iterativos basados ​​en heurísticas .

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 informática disponible. ^[1] ${\displaystyle A\mathbf {x} =\mathbf {b} }$

Puntos fijos atractivos

Si una ecuación se puede expresar en la forma f ( x ) = x , y una solución x es un punto fijo atractivo de la función f , entonces se puede comenzar con un punto x ₁ en la cuenca de atracción de x , y dejar 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 ené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 utilizan a menudo en métodos numéricos, para no interferir con los 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 una vecindad de el punto fijo. Si esta condición se cumple en el punto fijo, entonces debe existir una vecindad (cuenca de atracción) suficientemente pequeña.

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 subespaciales 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 con base en una medición del error en el resultado ( el residual ), formar una "ecuación de corrección" para lo cual se repite este proceso. Si bien estos métodos son sencillos de derivar, implementar y analizar, la convergencia sólo 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 llama 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 sólo 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 estricta parte triangular superior 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 Jacobi amortiguado : ${\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}$
• Método de Gauss-Seidel : ${\displaystyle M:=D+L}$
• Método de sobrerelajación sucesiva (SOR): ${\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}$
• Sobrerelajació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 lineales estacionarios también se denominan métodos de relajación .

Métodos subespaciales de Krylov

Los métodos del subespacio de Krylov funcionan formando una base de la secuencia de potencias matriciales sucesivas multiplicadas por el residual 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 de esta clase es el método del gradiente conjugado (CG), que supone que la matriz del sistema es simétrica positiva-definida . Para simétricos (y posiblemente indefinidos) se trabaja con el método residual mínimo (MINRES). En el caso de matrices no simétricas se han derivado métodos como el método residual mínimo generalizado (GMRES) y el método del gradiente biconjugado (BiCG). ${\displaystyle A}$ ${\displaystyle A}$

Convergencia de los métodos subespaciales 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, dependiendo de una complicada función del espectro del operador.

Preacondicionadores

El operador de aproximación que aparece en los métodos iterativos estacionarios también puede incorporarse en métodos subespaciales de Krylov como GMRES (alternativamente, los métodos de Krylov precondicionados pueden considerarse como aceleraciones de métodos iterativos estacionarios), donde se convierten en transformaciones del operador original a un operador presumiblemente mejor condicionado. uno. La construcción de precondicionadores es un área de investigación importante.

Historia

Jamshīd al-Kāshī utilizó métodos iterativos para calcular el seno de 1° y π en El Tratado de cuerda y seno con gran precisión. Uno de los primeros métodos iterativos para resolver un sistema lineal apareció en una carta de Gauss a un alumno suyo. Propuso resolver un sistema de ecuaciones de 4 por 4 resolviendo repetidamente el componente en el que el residuo era mayor ^{[ cita necesaria ]} .

La teoría de los métodos iterativos estacionarios quedó sólidamente establecida 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. Recién 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 las de tipo elíptica.

Ver 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, danés; Ahuja, Kapil (2015). "Reciclaje de subespacios de Krylov para aplicaciones CFD y un nuevo solucionador de reciclaje híbrido". Revista de Física Computacional . 303 : 222. arXiv : 1501.03358 . Código Bib : 2015JCoPh.303..222A. doi :10.1016/j.jcp.2015.09.040.

enlaces externos

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