Método de gradiente conjugado (para solución SLAE)

El método del gradiente conjugado es un método numérico para resolver sistemas de ecuaciones algebraicas lineales , es un método iterativo del tipo Krylov .

Planteamiento del problema

Sea dado el sistema de ecuaciones lineales: . Además, la matriz del sistema es una matriz real , que tiene las siguientes propiedades: es decir, es una matriz definida positiva simétrica . Entonces el proceso de resolución de la SLAE se puede representar como una minimización del siguiente funcional: $hacha = b$ $A = A^T > 0$

$(Ax,x)-2(b,x)\rightarrow min$

Detrás está el producto escalar . Minimizando este funcional usando los subespacios de Krylov , obtenemos el algoritmo del método del gradiente conjugado. $(\cdot, \cdot)$

Algoritmo

Preparación antes del proceso iterativo

Elegimos una aproximación inicial $x^0$
$r^0 = b - Ax^0$
$z^0 = r^0$

k

-ésima iteración del método [1]

$\alpha_k = \frac{(r^{k-1}, r^{k-1})}{(Az^{k-1}, z^{k-1})}$
$x^k = x^{k-1} + \alpha_k z^{k-1}$
$r^k = r^{k-1} - \alpha_k A z^{k-1}$
$\beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})}$
$z^k = r^k + \beta_k z^{k-1}$

Criterios de parada

Como el funcional a minimizar es cuadrático, el proceso debe dar una respuesta en la tercera iteración, sin embargo, al implementar el método en una computadora , se presenta un error en la representación de los números reales, por lo que se pueden requerir más iteraciones. requerido. También puede evaluar la precisión por la discrepancia relativa y detener el proceso iterativo cuando la discrepancia sea menor que un número dado. $norte$ $\frac{||r^k||}{||b||}$

Algoritmo para un sistema precondicionado

Si el sistema precondicionado tiene la forma: , entonces el algoritmo del método para dicho sistema se puede escribir de la siguiente manera: $SAQx=Sb$

Preparación antes del proceso iterativo

Elegimos una aproximación inicial $x^0$
$r^0 = Q(b - SAx^0)$
$z^0 = r^0$
$\widetilde{x}^0 = Qx^0$

k

-ésima iteración del método

$\alpha_k = \frac{(r^{k-1}, r^{k-1})}{(SAQz^{k-1}, z^{k-1})}$
$\widetilde{x}^k = \widetilde{x}^{k-1} + \alpha_k z^{k-1}$
$r^k = r^{k-1} - \alpha_k SAQ z^{k-1}$
$\beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})}$
$z^k = r^k + \beta_k z^{k-1}$

Después del proceso iterativo

$x^* = Q^{-1} \widetilde{x}^m$ , donde es la solución aproximada del sistema, es el número total de iteraciones del método. $x^{*}$ $metro$

Criterios de parada

En este caso, puede utilizar los mismos criterios de parada que para un sistema convencional, pero teniendo en cuenta el preacondicionamiento. Por ejemplo, la discrepancia relativa se calculará como: , sin embargo, también puede utilizar la discrepancia del sistema original, que se calcula de la siguiente manera: $\frac{||\widetilde{r}^k||}{||Sb||}$ $\frac{||r^k||}{||b||} = \frac{||Q^{-1}\widetilde{r}^k||}{||b||}$

Características y generalizaciones

Como todos los métodos en los subespacios de Krylov, el método de gradiente conjugado de una matriz requiere solo la capacidad de multiplicarlo por un vector, lo que lleva a la capacidad de usar formatos de almacenamiento de matriz especiales (como dispersos) y ahorrar memoria para el almacenamiento de matriz.
El método se usa a menudo para resolver SLAE de elementos finitos.
El método tiene generalizaciones: el método de gradientes biconjugados , para trabajar con matrices no simétricas. Y el método del gradiente complejo conjugado, donde la matriz puede contener números complejos, pero debe cumplir la condición: , es decir, ser una matriz definida positiva autoadjunta. $A$ $A = A^* > 0$

Notas

↑ Henk A. van der Vorst. Métodos iterativos de Krylov para sistemas lineales grandes. - Prensa de la Universidad de Cambridge, 2003. - 221 p. — ISBN 9780521818285 .

Métodos para resolver SLAE
Métodos directos	método matricial método de Gauss Método de Gauss-Jordan método Cramer descomposición LU Descomposición de Cholesky método de barrido
Métodos iterativos	método jacobi Método de Gauss-Seidel Método de iteración método de relajación método de gradiente conjugado Método de gradiente biconjugado Método de gradiente biconjugado estabilizado
General	matriz inversa Métodos de proyección para resolver SLAE preacondicionamiento