Método del gradiente conjugado al cuadrado

En álgebra lineal numérica , el método del gradiente conjugado al cuadrado (CGS) es un algoritmo iterativo para resolver sistemas de ecuaciones lineales de la forma${\displaystyle A{\mathbf {x}}={\mathbf {b}}}$, particularmente en casos donde se calcula la transpuesta${\displaystyle A^{T}}$es poco práctico. ^{[ 1 ]} El método CGS se desarrolló como una mejora del método del gradiente biconjugado . ^{[ 2 ] [ 3 ] [ 4 ]}

Un sistema de ecuaciones lineales${\displaystyle A{\mathbf {x}}={\mathbf {b}}}$consta de una matriz conocida${\displaystyle A}$y un vector conocido${\displaystyle {\mathbf {b}}}$Resolver el sistema consiste en encontrar el valor del vector desconocido.${\displaystyle {\mathbf {x}}}$. ^{[ 3 ] [ 5 ]} Un método directo para resolver un sistema de ecuaciones lineales es tomar la inversa de la matriz${\displaystyle A}$, luego calcular${\displaystyle {\mathbf {x}}=A^{-1}{\mathbf {b}}}$Sin embargo, calcular la inversa es computacionalmente costoso. Por lo tanto, se suelen utilizar métodos iterativos. Los métodos iterativos comienzan con una suposición.${\displaystyle {\mathbf {x}}^{(0)}}$y en cada iteración la estimación mejora. Una vez que la diferencia entre estimaciones sucesivas es suficientemente pequeña, el método ha convergido a una solución. ^{[ 6 ] [ 7 ]}

Al igual que el método del gradiente conjugado , el método del gradiente biconjugado y otros métodos iterativos similares para resolver sistemas de ecuaciones lineales, el método CGS puede utilizarse para encontrar soluciones a problemas de optimización multivariable , como el análisis de flujo de potencia , la optimización de hiperparámetros y el reconocimiento facial . ^{[ 8 ]}

El algoritmo es el siguiente: ^{[ 9 ]}

1. Elige una suposición inicial${\displaystyle {\mathbf {x}}^{(0)}}$
2. Calcular el residuo${\displaystyle {\mathbf {r}}^{(0)}={\mathbf {b}}-A{\mathbf {x}}^{(0)}}$
3. Elegir${\displaystyle {\tilde {\mathbf {r}}}={\mathbf {r}}^{(0)}}$
4. Para${\displaystyle i=1,2,3,\dots }$hacer:
   1. ${\displaystyle \rho ^{(i-1)}={\tilde {\mathbf {r}}}^{T}{\mathbf {r}}^{(i-1)}}$
   2. Si${\displaystyle \rho ^{(i-1)}=0}$El método falla.
   3. Si${\displaystyle i=1}$:
      1. ${\displaystyle {\mathbf {p}}^{(1)}={\mathbf {u}}^{(1)}={\mathbf {r}}^{(0)}}$
   4. Demás:
      1. ${\displaystyle \beta ^{(i-1)}=\rho ^{(i-1)}/\rho ^{(i-2)}}$
      2. ${\displaystyle {\mathbf {u}}^{(i)}={\mathbf {r}}^{(i-1)}+\beta _{i-1}{\mathbf {q}}^{(i-1)}}$
      3. ${\displaystyle {\mathbf {p}}^{(i)}={\mathbf {u}}^{(i)}+\beta ^{(i-1)}({\mathbf {q}}^{(i-1)}+\beta ^{(i-1)}{\mathbf {p}}^{(i-1)})}$
   5. Resolver${\displaystyle M{\hat {\mathbf {p}}}={\mathbf {p}}^{(i)}}$, dónde${\displaystyle M}$es un preacondicionador.
   6. ${\displaystyle {\hat {\mathbf {v}}}=A{\hat {\mathbf {p}}}}$
   7. ${\displaystyle \alpha ^{(i)}=\rho ^{(i-1)}/{\tilde {\mathbf {r}}}^{T}{\hat {\mathbf {v}}}}$
   8. ${\displaystyle {\mathbf {q}}^{(i)}={\mathbf {u}}^{(i)}-\alpha ^{(i)}{\hat {\mathbf {v}}}}$
   9. Resolver${\displaystyle M{\hat {\mathbf {u}}}={\mathbf {u}}^{(i)}+{\mathbf {q}}^{(i)}}$
   10. ${\displaystyle {\mathbf {x}}^{(i)}={\mathbf {x}}^{(i-1)}+\alpha ^{(i)}{\hat {\mathbf {u}}}}$
   11. ${\displaystyle {\hat {\mathbf {q}}}=A{\hat {\mathbf {u}}}}$
   12. ${\displaystyle {\mathbf {r}}^{(i)}={\mathbf {r}}^{(i-1)}-\alpha ^{(i)}{\hat {\mathbf {q}}}}$
   13. Comprueba la convergencia: si hay convergencia, finaliza el bucle y devuelve el resultado.

• Método del gradiente biconjugado
• Método estabilizado por gradiente biconjugado
• Método generalizado de residuos mínimos