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 estacionariosEditar
IntroducciónEditar
Los métodos iterativos estacionarios resuelven un sistema lineal con un operador que se aproxima al original; y basándose en una medida del error en el resultado (el residuo), forman una «ecuación de corrección» para la que se repite este proceso. Aunque estos métodos son sencillos de derivar, implementar y analizar, la convergencia sólo está garantizada para una clase limitada de matrices.
DefiniciónEditar
Un método iterativo se define por
x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}
y para un sistema lineal dado A x = b {\displaystyle A\mathbf {x} =\mathbf {b} }
con solución exacta x ∗ {\displaystyle \mathbf {x} ^{*}}
el error por e k := x k – x ∗ , k ≥ 0 . {\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\Nmathbf {x} ^{*},,\Ncuadra k\geq 0,.}
Un método iterativo se llama lineal si existe una matriz C ∈ R n × n {\displaystyle C\in \mathbb {R} ^{n\times n}}.
tal que e k + 1 = C e k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\Nmathbf {e} ^{k}\cuadro \para todos los \Nk+1}
y esta matriz se llama matriz de iteración.Un método iterativo con una matriz de iteración dada C {\displaystyle C}
se llama convergente si se cumple lo siguiente lim k → ∞ C k = 0 . {\displaystyle \lim _{k\rightarrow \infty }C^{k}=0,.}
Un importante teorema establece que para un método iterativo dado y su matriz de iteración C {\displaystyle C}
es convergente si y sólo si su radio espectral ρ ( C ) {\displaystyle \rho (C)}
es menor que la unidad, es decir, ρ ( C ) < 1 . {\displaystyle \rho (C)<1,.}
Los métodos iterativos básicos funcionan dividiendo la matriz A {\displaystyle A}
en A = M – N {\displaystyle A=M-N}
y aquí la matriz M {\displaystyle M}
debe ser fácilmente invertible.Los métodos iterativos se definen ahora como M x k + 1 = N x k + b , k ≥ 0 . {\displaystyle M\mathbf {x} ^{k+1}=N\Nmathbf {x} ^{k}+b,,\Ncuadro k\geq 0,.}
De aquí se deduce que la matriz de iteración viene dada por
C = I – M – 1 A = M – 1 N . {\displaystyle C=I-M^{-1}A=M^{-1}N,.}
EjemplosEditar
Los ejemplos básicos de métodos iterativos estacionarios utilizan un desdoblamiento de la matriz A {\displaystyle A}
como A = D + L + U , D := diag ( ( a i i ) i ) {\displaystyle A=D+L+U,,\quad D:={text{diag}((a_{ii})_{i})}
donde D {{displaystyle D}}
es sólo la parte diagonal de A {\displaystyle A}
, y L {\displaystyle L}
es la parte triangular inferior estricta de A {\displaystyle A}
.
- Método de Richardson: M := 1 ω I ( ω ≠ 0 ) {\displaystyle M:={frac {1}{\omega }}I\quad (\omega \neq 0)}
- Método de Jacobi: M := D {\\Ndice M:=D}
- Método de Jacobi amortiguado: M := 1 ω D ( ω ≠ 0 ) {\displaystyle M:={frac {1}{\omega }}D\quad (\omega \neq 0)}
- Método de Gauss-Seidel: M := D + L {\displaystyle M:=D+L}
- Método de sobrerrelajación sucesiva (SOR): M := 1 ω D + L ( ω ≠ 0 ) {\displaystyle M:={frac {1}{\omega }}D+L\quad (\omega \neq 0)}
- Sobre-relajación sucesiva simétrica (SSOR): M := 1 ω ( 2 – ω ) ( D + ω L ) D – 1 ( D + ω U ) ( ω ≠ { 0 , 2 } ) {\displaystyle M:={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \neq {0,2\})}
Los métodos iterativos estacionarios lineales también se llaman métodos de relajación.
Métodos del subespacio de KrylovEditar
Los métodos del subespacio de Krylov funcionan formando una base de la secuencia de potencias matriciales sucesivas por el residuo inicial (la secuencia de Krylov). Las aproximaciones a la solución se forman entonces 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 A
es simétrica positiva-definida.Para A simétrica (y posiblemente indefinida)
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).
Convergencia de los métodos del subespacio de KrylovEditar
Como 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 ya mucho antes. El análisis de estos métodos es difícil, ya que depende de una complicada función del espectro del operador.
PrecondicionadoresEditar
El operador de aproximación que aparece en los métodos iterativos estacionarios también puede incorporarse a los métodos del subespacio de Krylov, como el GMRES (alternativamente, los métodos de Krylov precondicionados pueden considerarse como aceleraciones de los métodos iterativos estacionarios), donde se convierten en transformaciones del operador original a uno presumiblemente mejor condicionado. La construcción de precondicionadores es una gran área de investigación.
HistoriaEditar
Probablemente el primer método iterativo 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 la componente en la que el residuo era el mayor.
La teoría de los métodos iterativos estacionarios se estableció sólidamente con el trabajo de D.M. 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 no fueron comprendidas en su momento. Sólo en la década de 1970 se comprendió que los métodos basados en la conjugación funcionan muy bien para las ecuaciones diferenciales parciales, especialmente las de tipo elíptico.