Ir al contenido

Usuario:Kxx/Sandbox/Derivación del método del gradiente conjugado

De Wikipedia, la enciclopedia libre

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.

References[editar]

  1. 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). 
  2. Saad, Y. (2003). «Chapter 6: Krylov Subspace Methods, Part I». Iterative methods for sparse linear systems (2nd edición). SIAM. ISBN 978-0898715347.