En la álgebra lineal numérica, el método del gradiente conjugado es un método iterativo para la resolución numérica del sistema lineal
donde es simétrica definida positiva. El método del gradiente conjugado se puede derivar de varias perspectivas diferentes, incluidas la especialización del método de las direcciones conjugadas para la optimización, y la variación de la iteración de Arnoldi/Lanczos para los problemas de los valores propios.
El intento de este artículo es documentar los paso importantes en estas derivaciones.
Derivación del método de las direcciones conjugadas
[editar]
Hestenes y Stiefel, los inventores del método del gradiente conjugado, derivaron el método del más general método de las direcciones conjugadas en el contexto de la minimización de la función cuadrática
En el método de las direcciones conjugadas se elige una serie de direcciones que son conjugadas mutuamente, en otras palabras,
para . La iteración se inicia con una solución aproximada y el correspondiente residuo y procede con los siguientes pasos para :
Derivación de la iteración de Arnoldi/Lanczos
[editar]
El método del gradiente conjugado también se puede ver como una variante de la iteración de Arnoldi/Lanczos aplicada a la solución de los sistemas lineales.
El método de Arnoldi general
[editar]
En la iteración de Arnoldi, se comienza con un vector y construye gradualmente una base ortonormal del subespacio de Krylov
mediante la definición de donde
En otras palabras, para , se obtiene a través de la ortogonalización de Gram-Schmidt de contra seguida por la normalización.
Expresada en la forma matricial, la iteración se capta por la ecuación
donde
with
Cuando se aplica la iteración de Arnoldi a la solución de los sistemas lineals, se comienza con , el residuo correspondiente a la aproximación inicial . Después de cada paso de la iteración, se computa y la nueva aproximación .
El método de Lanczos directo
[editar]
Para el resto de la discusión, se supone que es simétrica definida positiva. Con la simetría de , la matriz superior de Hessenberg se hace simétrica y por lo tanto tridiagonal. Entonces se puede representar más claramente por
Esto permite una corta recurrencia de tres términos para en la iteración, y así la iteración de Arnoldi se reduce a la iteración de Lanczos.
Ya que es simétrica definida positiva, también lo es. Por lo tanto, se puede factorizar LU sin pivoteo parcial en
con las recurrencias convenientes para y :
Se varía en
con
Ahora es crucial observar que
De hecho, también existen recurrencias cortas para y :
Con esta formulación, llegamos a una recurrencia simple para :
Las anteriores relaciones resultan sencillamente en el método de Lanczos directo, que es un poco más complejo.
El método del gradiente conjugado de imponer la ortogonalidad y la conjugación
[editar]
Si se permite que se escale y compensa el escalamiento en el factor constante, potencialmente se puede obtener recurrencias más simples de la forma:
Como las premisas de la simplificación, ahora se deriva la ortogonalidad of y la conjugación de , es decir, para ,
Los residuos son mutuamente ortogonales porque es esencialmente un múltiplo de , dado que para , , y para ,
Para ver la conjugación de , basta mostrar que es diagonal:
es simétria y triangular inferior simultáneamente y por lo tanto debe ser diagonal.
Ahora se puede derivar los factores constantes and con respecto al escalado mediante imponer solamente la ortogonalidad de y la conjugación de .
Debido a la ortogonalidad de , es necesario que . Como resultante de eso,
De manera similar, debido a la conjugación de , es necesario que . Como resultante de eso,
Esto completa la derivación.
- Hestenes, M. R.; Stiefel, E. (December de 1952). «Methods of conjugate gradients for solving linear systems» (PDF). Journal of Research of the National Bureau of Standards 49 (6).
- Saad, Y. (2003). «Chapter 6: Krylov Subspace Methods, Part I». Iterative methods for sparse linear systems (2nd edición). SIAM. ISBN 978-0898715347.