Método iterativo

Ajustar Compartir Imprimir Citar

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

En matemática computacional, 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 n-ésima aproximación se deriva de las anteriores. Una implementación específica de un método iterativo, incluidos los criterios de terminación, es un algoritmo del método iterativo. Un método iterativo se llama convergente si la secuencia correspondiente converge para las aproximaciones iniciales dadas. Por lo general, se realiza un análisis de convergencia matemáticamente riguroso de un método iterativo; sin embargo, los métodos iterativos basados en heurística también son comunes.

En cambio, métodos directos tratar de resolver el problema por una secuencia finita de operaciones. En ausencia de errores de redondeo, los métodos directos darían una solución exacta (por ejemplo, resolver un sistema lineal de ecuaciones) $Amathbf {x} =mathbf {b}$ por eliminación gaussiana). Los métodos iterativos son a menudo la única opción para las ecuaciones no lineales. Sin embargo, los métodos iterativos son a menudo útiles incluso para problemas lineales que implican muchas variables (a veces en el orden de millones), donde los métodos directos serían prohibitivamente costosos (y en algunos casos imposibles) incluso con el mejor poder de cálculo disponible.

Atractivos puntos fijos

Si una ecuación se puede poner 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 a menudo se usan en métodos numéricos, para no interferir con los subíndices con otros significados. (Por ejemplo, x⁽ⁿ⁺¹⁾ = f(x⁽ⁿ⁾).) 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 del punto fijo. Si esta condición se cumple en el punto fijo, entonces debe existir una vecindad suficientemente pequeña (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 más generales del subespacio de Krylov.

Métodos iterativos estacionarios

Introducción

Los métodos iterativos estacionarios resuelven un sistema lineal con un operador que se aproxima al original; y en base a una medición del error en el resultado (el residuo), forme una "ecuación de corrección" por lo 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 kgeq 0}

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

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

Un método iterativo se llama lineal si existe una matriz ${displaystyle Cin mathbb {R} ^{ntimes n}}$ tales que

{displaystyle mathbf {e} ^{k+1}=Cmathbf {e} ^{k}quad forall ,kgeq 0}

y esta matriz se llama matriz de iteración. Un método iterativo con una matriz de iteración dada $C$ se llama convergente si los siguientes sostienen

{displaystyle lim _{krightarrow infty }C^{k}=0,.}

Un teorema importante establece que para un método iterante dado y su matriz de iteración $C$ es convergente si y sólo si su radio espectral ${displaystyle rho (C)}$ es más pequeño que la unidad, es decir,

<math alttext="{displaystyle rho (C)*** *** ()C).1.{displaystyle rho (C)traducido1,} <img alt="{displaystyle rho (C)

Los métodos iterativos básicos funcionan dividiendo la matriz $A$ en

{displaystyle A=M-N}

y aquí la matriz $M$ debe ser fácilmente invertible. Los métodos iterativos se definen ahora como

{displaystyle Mmathbf {x} ^{k+1}=Nmathbf {x} ^{k}+b,,quad kgeq 0,.}

De esto se deduce que la matriz de iteraciones viene dada por

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

Ejemplos

Ejemplos básicos de métodos iterativos estacionarios utilizan una división de la matriz $A$ tales como

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

Donde $D$ es sólo la parte diagonal de $A$ , y $L$ es la parte triangular inferior estricta $A$ . Respetuosamente, $U$ es la parte superior estricta triangular $A$ .

método Richardson: ${displaystyle M:={frac {1}{omega }}Iquad (omega neq 0)}$
Método Jacobi: ${displaystyle M:=D}$
Método Jacobi dañado: ${displaystyle M:={frac {1}{omega }}Dquad (omega neq 0)}$
Método Gauss-Seidel: ${displaystyle M:=D+L}$
Método de sobre-relajación (SOR): ${displaystyle M:={frac {1}{omega }}D+Lquad (omega neq 0)}$
Sobre-relaxació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 subespaciales de Krylov funcionan formando una base de la secuencia de sucesivos poderes matrices tiempos el residual inicial (el Secuencia de Krylov). Las aproximaciones a la solución se forman entonces minimizando el residual sobre el subespacio formado. El método prototípico en esta clase es el método de gradiente conjugado (CG) que asume que la matriz del sistema $A$ es simétrico positivo-definido. Para simétrica (y posiblemente indefinida) $A$ uno trabaja con el método residual mínimo (MINRES). En el caso de las matrices no simétricas, se han derivado métodos como el método residual mínimo generalizado (GMRES) y el método gradiente biconyugado (BiCG).

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 la precisión suficiente mucho antes. El análisis de estos métodos es difícil, dependiendo de una función complicada del espectro del operador.

Preacondicionadores

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

Historia

Jamshīd al-Kāshī usó métodos iterativos para calcular el seno de 1° y $π$ en The Treatise of Chord y Seno de alta 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.

La teoría de los métodos iterativos estacionarios quedó sólidamente establecida con el trabajo de D.M. Joven 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 se malinterpretaron en ese momento. Solo en la década de 1970 se dio cuenta de que los métodos basados en la conjugación funcionan muy bien para ecuaciones diferenciales parciales, especialmente del tipo elíptico.