Método del gradiente biconjugado estabilizado

En álgebra lineal numérica, el método del gradiente biconjugado estabilizado, generalmente abreviado como BiCGSTAB (del inglés «biconjugate gradient stabilized method»), es un método iterativo propuesto por H. A. van der Vorst para la resolución numérica de los sistemas de ecuaciones lineales no simétricos. Es una variante del método del gradiente biconjugado (BiCG) y ofrece convergencia más rápida y suave que el original BiCG así como otras variantes como el método del gradiente conjugado cuadrado (CGS). Es un método del subespacio de Krylov.

Pasos algorítmicos

BiCGSTAB sin precondicionamiento

Para resolver el sistema ${\displaystyle {\boldsymbol {Ax}}={\boldsymbol {b}}}$, el BiCGSTAB comienza con una aproximación inicial ${\displaystyle {\boldsymbol {x}}_{0}}$ y procede como sigue:

1. ${\displaystyle {\boldsymbol {r}}_{0}={\boldsymbol {b}}-{\boldsymbol {Ax_{0}}}}$
2. Elige un vector arbitrario ${\displaystyle {\boldsymbol {\hat {r}}}_{0}}$ tal que ${\displaystyle ({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {r}}_{0})\neq 0}$, por ejemplo, ${\displaystyle {\boldsymbol {\hat {r}}}_{0}={\boldsymbol {r}}_{0}}$
3. ${\displaystyle {\boldsymbol {p}}_{0}={\boldsymbol {r}}_{0}}$
4. Para ${\displaystyle i=0,1,2,\ldots \;}$
   1. ${\displaystyle \alpha _{i}=({\boldsymbol {r}}_{i},{\boldsymbol {\hat {r}}}_{0})/({\boldsymbol {Ap}}_{i},{\boldsymbol {\hat {r}}}_{0})}$
   2. ${\displaystyle {\boldsymbol {s}}_{i}={\boldsymbol {r}}_{i}-\alpha _{i}{\boldsymbol {Ap_{i}}}}$
   3. ${\displaystyle \omega _{i}=({\boldsymbol {As}}_{i},{\boldsymbol {s}}_{i})/({\boldsymbol {As}}_{i},{\boldsymbol {As}}_{i})}$
   4. ${\displaystyle {\boldsymbol {x}}_{i+1}={\boldsymbol {x}}_{i}+\alpha _{i}{\boldsymbol {p}}_{i}+\omega _{i}{\boldsymbol {s}}_{i}}$
   5. Termina si ${\displaystyle {\boldsymbol {x}}_{i+1}}$ cumple el criterio de convergencia
   6. ${\displaystyle {\boldsymbol {r}}_{i+1}={\boldsymbol {s}}_{i}-\omega _{i}{\boldsymbol {As}}_{i}}$
   7. ${\displaystyle \beta _{i}=(\alpha _{i}/\omega _{i})({\boldsymbol {r}}_{i+1},{\boldsymbol {\hat {r}}}_{0})/({\boldsymbol {r}}_{i},{\boldsymbol {\hat {r}}}_{0})\;}$
   8. ${\displaystyle {\boldsymbol {p}}_{i+1}={\boldsymbol {r}}_{i+1}+\beta _{i}({\boldsymbol {p}}_{i}-\omega _{i}{\boldsymbol {Ap}}_{i})}$

BiCGSTAB precondicionado

Generalmente se utiliza los precondicionadores para acelerar la convergencia de los métodos iterativos. Para resolver el sistema ${\displaystyle {\boldsymbol {Ax}}={\boldsymbol {b}}}$ con un precondicionador ${\displaystyle {\boldsymbol {K}}={\boldsymbol {K}}_{1}{\boldsymbol {K}}_{2}\approx {\boldsymbol {A}}}$, el BiCGSTAB precondicionado comienza con una aproximación inicial ${\displaystyle {\boldsymbol {x}}_{0}}$ y procede como sigue:

1. ${\displaystyle {\boldsymbol {r}}_{0}={\boldsymbol {b}}-{\boldsymbol {Ax_{0}}}}$
2. Elige un vector arbitrario ${\displaystyle {\boldsymbol {\hat {r}}}_{0}}$ tal que ${\displaystyle ({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {r}}_{0})\neq 0}$, por ejemplo, ${\displaystyle {\boldsymbol {\hat {r}}}_{0}={\boldsymbol {r}}_{0}}$
3. ${\displaystyle \rho _{0}=\alpha =\omega _{0}=1\;}$
4. ${\displaystyle {\boldsymbol {v}}_{0}={\boldsymbol {p}}_{0}={\boldsymbol {0}}}$
5. Para ${\displaystyle i=1,2,3,\ldots \;}$
   1. ${\displaystyle \rho _{i}=({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {r}}_{i-1})}$
   2. ${\displaystyle \beta =(\rho _{i}/\rho _{i-1})(\alpha /\omega _{i-1})\;}$
   3. ${\displaystyle {\boldsymbol {p}}_{i}={\boldsymbol {r}}_{i-1}+\beta ({\boldsymbol {p}}_{i-1}-\omega _{i-1}{\boldsymbol {v}}_{i-1})}$
   4. ${\displaystyle {\boldsymbol {y}}={\boldsymbol {K}}^{-1}{\boldsymbol {p}}_{i}}$
   5. ${\displaystyle {\boldsymbol {v}}_{i}={\boldsymbol {Ay}}}$
   6. ${\displaystyle \alpha =\rho _{i}/({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {v}}_{i})}$
   7. ${\displaystyle {\boldsymbol {s}}={\boldsymbol {r}}_{i}-\alpha {\boldsymbol {v}}_{i}}$
   8. ${\displaystyle {\boldsymbol {z}}={\boldsymbol {As}}}$
   9. ${\displaystyle {\boldsymbol {t}}={\boldsymbol {K}}^{-1}{\boldsymbol {z}}}$
   10. ${\displaystyle \omega _{i}=({\boldsymbol {K}}_{1}^{-1}{\boldsymbol {t}},{\boldsymbol {K}}_{1}^{-1}{\boldsymbol {s}})/({\boldsymbol {K}}_{1}^{-1}{\boldsymbol {s}},{\boldsymbol {K}}_{1}^{-1}{\boldsymbol {s}})}$
   11. ${\displaystyle {\boldsymbol {x}}_{i}={\boldsymbol {x}}_{i-1}+\alpha {\boldsymbol {y}}+\omega _{i}{\boldsymbol {z}}}$
   12. Termina si ${\displaystyle {\boldsymbol {x}}_{i}}$ es lo suficientemente preciso
   13. ${\displaystyle {\boldsymbol {r}}_{i}={\boldsymbol {s}}-\omega _{i}{\boldsymbol {t}}}$

Esta formulación es equivalente a aplicar el BiCGSTAB sin precondicionamiento al sistema explícitamente precondicionado

${\displaystyle {\boldsymbol {{\tilde {A}}{\tilde {x}}}}={\boldsymbol {\tilde {b}}}}$

con ${\displaystyle {\boldsymbol {\tilde {A}}}={\boldsymbol {K}}_{1}^{-1}{\boldsymbol {AK}}_{2}^{-1}}$, ${\displaystyle {\boldsymbol {\tilde {x}}}={\boldsymbol {K}}_{2}{\boldsymbol {x}}}$, ${\displaystyle {\boldsymbol {\tilde {b}}}={\boldsymbol {K}}_{1}^{-1}{\boldsymbol {b}}}$. En otras palabras, precondicionamiento a ambas la izquierda y la derecha es posible en esta formulación.

Generalización

BiCGSTAB puede ser visto como una combinación de BiCG y GMRES en que cada paso de BiCG se sigue por un paso de GMRES(${\displaystyle 1}$) (GMRES reiniciado en cada paso) para reparar el comportamiento irregular de convergencia de CGS, de lo cual BiCGSTAB fue desarrollado como una mejora. No obstante, debido al uso de los polinomios del residuo mínimo de grado uno, la dicha reparación puede no ser eficaz si la matriz ${\displaystyle {\boldsymbol {A}}}$ tiene pares propios complejos grandes. En tales casos, es probable que BiCGSTAB se estanca como lo confirman los experimentos numéricos.

Se puede esparar que los polinomios del residuo mínimo de grado más alto pueda mejor manejar esta situación. Esto da lugar a los métodos que incluyen BiCGSTAB2^[1] y el más general BiCGSTAB(${\displaystyle l}$).^[2] En BiCGSTAB(${\displaystyle l}$), un paso de GMRES(${\displaystyle l}$) sigue cada ${\displaystyle l}$ pasos de BiCG. BiCGSTAB2 es equivalente a BiCGSTAB(${\displaystyle l}$) con ${\displaystyle l=2}$.

Véase también

• Método del gradiente biconjugado
• Método del gradiente conjugado cuadrado
• Método del gradiente conjugado

Referencias

1. Gutknecht, M. H. (1993). «Variants of BICGSTAB for Matrices with Complex Spectrum». SIAM Journal on Scientific Computing (en inglés) 14 (5): 1020-1033. doi:10.1137/0914062.
2. Sleijpen, G. L. G.; Fokkema, D. R. (1993). «BiCGstab(l) for linear equations involving unsymmetric matrices with complex spectrum» (PDF). Electronic Transactions on Numerical Analysis (en inglés) (Kent, OH, EEUU: Kent State University) 1: 11-32. ISSN 1068-9613. Archivado desde el original el 6 de junio de 2011. Consultado el 8 de febrero de 2010.

Bibliografía

• Van der Vorst, H. A. (1992). «Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems». SIAM Journal on Scientific and Statistical Computing (en inglés) 13: 631-644. doi:10.1137/0913035.

• Datos: Q4903720