Iteración de Richardson modificada

Método iterativo utilizado para resolver un sistema lineal de ecuaciones.

La iteración de Richardson modificada es un método iterativo para resolver un sistema de ecuaciones lineales . La iteración de Richardson fue propuesta por Lewis Fry Richardson en su trabajo de 1910. Es similar al método de Jacobi y Gauss-Seidel .

Buscamos la solución a un conjunto de ecuaciones lineales, expresadas en términos matriciales como

${\displaystyle Ax=b.\,}$

La iteración de Richardson es

${\displaystyle x^{(k+1)}=x^{(k)}+\omega \left(b-Ax^{(k)}\right),}$

donde es un parámetro escalar que debe elegirse de manera que la secuencia converja. ${\displaystyle \omega }$ ${\displaystyle x^{(k)}}$

Es fácil ver que el método tiene los puntos fijos correctos , porque si converge, entonces y tiene que aproximarse a una solución de . ${\displaystyle x^{(k+1)}\approx x^{(k)}}$ ${\displaystyle x^{(k)}}$ ${\displaystyle Ax=b}$

Convergencia

Restando la solución exacta e introduciendo la notación del error , obtenemos la igualdad de los errores. ${\displaystyle x}$ ${\displaystyle e^{(k)}=x^{(k)}-x}$

${\displaystyle e^{(k+1)}=e^{(k)}-\omega Ae^{(k)}=(I-\omega A)e^{(k)}.}$

De este modo,

${\displaystyle \|e^{(k+1)}\|=\|(I-\omega A)e^{(k)}\|\leq \|I-\omega A\|\|e^{(k)}\|,}$

para cualquier norma vectorial y la correspondiente norma matricial inducida. Por tanto, si , el método converge. ${\displaystyle \|I-\omega A\|<1}$

Supongamos que es simétrica definida positiva y que son los valores propios de . El error converge a if para todos los valores propios . Si, por ejemplo, todos los valores propios son positivos, esto se puede garantizar si se elige tal que . La opción óptima, minimizando todo , es , que da la iteración de Chebyshev más simple . Esta elección óptima produce un radio espectral de ${\displaystyle A}$ ${\displaystyle (\lambda _{j})_{j}}$ ${\displaystyle A}$ ${\displaystyle 0}$ ${\displaystyle |1-\omega \lambda _{j}|<1}$ ${\displaystyle \lambda _{j}}$ ${\displaystyle \omega }$ ${\displaystyle 0<\omega <\omega _{\text{max}}\,,\ \omega _{\text{max}}:=2/\lambda _{\text{max}}(A)}$ ${\displaystyle |1-\omega \lambda _{j}|}$ ${\displaystyle \omega _{\text{opt}}:=2/(\lambda _{\text{min}}(A)+\lambda _{\text{max}}(A))}$

${\displaystyle \min _{\omega \in (0,\omega _{\text{max}})}\rho (I-\omega A)=\rho (I-\omega _{\text{opt}}A)=1-{\frac {2}{\kappa (A)+1}}\,,}$

¿ Dónde está el número de condición ? ${\displaystyle \kappa (A)}$

Si hay valores propios positivos y negativos, el método divergirá para cualquiera si el error inicial tiene componentes distintos de cero en los vectores propios correspondientes . ${\displaystyle \omega }$ ${\displaystyle e^{(0)}}$

Equivalencia al descenso de gradiente

Considere minimizar la función . Dado que se trata de una función convexa , una condición suficiente para la optimización es que el gradiente sea cero ( ), lo que da lugar a la ecuación ${\displaystyle F(x)={\frac {1}{2}}\|{\tilde {A}}x-{\tilde {b}}\|_{2}^{2}}$ ${\displaystyle \nabla F(x)=0}$

${\displaystyle {\tilde {A}}^{T}{\tilde {A}}x={\tilde {A}}^{T}{\tilde {b}}.}$

Definir y . Debido a la forma de A , es una matriz semidefinida positiva , por lo que no tiene valores propios negativos. ${\displaystyle A={\tilde {A}}^{T}{\tilde {A}}}$ ${\displaystyle b={\tilde {A}}^{T}{\tilde {b}}}$

Un paso de descenso de gradiente es

${\displaystyle x^{(k+1)}=x^{(k)}-t\nabla F(x^{(k)})=x^{(k)}-t(Ax^{(k)}-b)}$

lo cual es equivalente a la iteración de Richardson haciendo . ${\displaystyle t=\omega }$

Ver también

• extrapolación de Richardson

Referencias

• Richardson, LF (1910). "La solución aritmética aproximada por diferencias finitas de problemas físicos que involucran ecuaciones diferenciales, con una aplicación a las tensiones en una presa de mampostería". Transacciones filosóficas de la Royal Society A. 210 : 307–357. doi :10.1098/rsta.1911.0009. JSTOR  90994.
• Lebedev, Vyacheslav Ivanovich (2001) [1994], "Método de iteración de Chebyshev", en Michiel Hazewinkel (ed.), Enciclopedia de Matemáticas , EMS Press , ISBN 1-4020-0609-8, consultado el 25 de mayo de 2010