Método del gradiente biconjugado

En matemáticas , más específicamente en álgebra lineal numérica , el método del gradiente biconjugado es un algoritmo para resolver sistemas de ecuaciones lineales.

${\displaystyle Ax=b.\,}$

A diferencia del método del gradiente conjugado , este algoritmo no requiere la matriz.${\displaystyle A}$para ser autoadjunto , pero en su lugar es necesario realizar multiplicaciones por la transpuesta conjugada A ^* .

1. Elige tu primera suposición${\displaystyle x_{0}\,}$, otros dos vectores${\displaystyle x_{0}^{*}}$y${\displaystyle b^{*}\,}$y un preacondicionador${\displaystyle M\,}$
2. ${\displaystyle r_{0}\leftarrow bA\,x_{0}\,}$
3. ${\displaystyle r_{0}^{*}\leftarrow b^{*}-x_{0}^{*}\,A^{*}}$
4. ${\displaystyle p_{0}\leftarrow M^{-1}r_{0}\,}$
5. ${\displaystyle p_{0}^{*}\leftarrow r_{0}^{*}M^{-1}\,}$
6. para${\displaystyle k=0,1,\ldots }$hacer
   1. ${\displaystyle \alpha _{k}\leftarrow {r_{k}^{*}M^{-1}r_{k} \over p_{k}^{*}Ap_{k}}\,}$
   2. ${\displaystyle x_{k+1}\leftarrow x_{k}+\alpha _{k}\cdot p_{k}\,}$
   3. ${\displaystyle x_{k+1}^{*}\leftarrow x_{k}^{*}+{\overline {\alpha _{k}}}\cdot p_{k}^{*}\,}$
   4. ${\displaystyle r_{k+1}\leftarrow r_{k}-\alpha _{k}\cdot Ap_{k}\,}$
   5. ${\displaystyle r_{k+1}^{*}\leftarrow r_{k}^{*}-{\overline {\alpha _{k}}}\cdot p_{k}^{*}\,A^{*}}$
   6. ${\displaystyle \beta _{k}\leftarrow {r_{k+1}^{*}M^{-1}r_{k+1} \over r_{k}^{*}M^{-1}r_{k}}\,}$
   7. ${\displaystyle p_{k+1}\leftarrow M^{-1}r_{k+1}+\beta _{k}\cdot p_{k}\,}$
   8. ${\displaystyle p_{k+1}^{*}\leftarrow r_{k+1}^{*}M^{-1}+{\overline {\beta _{k}}}\cdot p_{k}^{*}\,}$

En la formulación anterior, el calculado${\displaystyle r_{k}\,}$y${\displaystyle r_{k}^{*}}$satisfacer

${\displaystyle r_{k}=b-Ax_{k},\,}$

${\displaystyle r_{k}^{*}=b^{*}-x_{k}^{*}\,A^{*}}$

y por lo tanto son los residuos respectivos correspondientes a${\displaystyle x_{k}\,}$y${\displaystyle x_{k}^{*}}$como soluciones aproximadas a los sistemas

${\displaystyle Ax=b,\,}$

${\displaystyle x^{*}\,A^{*}=b^{*}\,;}$

${\displaystyle x^{*}}$es el adjunto y${\displaystyle {\overline {\alpha }}}$es el conjugado complejo .

El método del gradiente biconjugado es numéricamente inestable (compárese con el método del gradiente biconjugado estabilizado ), pero muy importante desde un punto de vista teórico. Defina los pasos de iteración mediante

${\displaystyle x_{k}:=x_{j}+P_{k}A^{-1}\left(b-Ax_{j}\right),}$

${\displaystyle x_{k}^{*}:=x_{j}^{*}+\left(b^{*}-x_{j}^{*}A\right)P_{k}A^{-1},}$

dónde${\displaystyle j<k}$utilizando la proyección relacionada

${\displaystyle P_{k}:=\mathbf {u} _{k}\left(\mathbf {v} _{k}^{*}A\mathbf {u} _{k}\right)^{-1}\mathbf {v} _{k}^{*}A,}$

con

${\displaystyle \mathbf {u} _{k}=\left[u_{0},u_{1},\dots ,u_{k-1}\right],}$

${\displaystyle \mathbf {v} _{k}=\left[v_{0},v_{1},\dots ,v_{k-1}\right].}$

Estas proyecciones relacionadas pueden ser iteradas a su vez como

${\displaystyle P_{k+1}=P_{k}+\left(1-P_{k}\right)u_{k}\otimes {v_{k}^{*}A\left(1-P_{k}\right) \over v_{k}^{*}A\left(1-P_{k}\right)u_{k}}.}$

Una relación con los métodos cuasi-Newton viene dada por${\displaystyle P_{k}=A_{k}^{-1}A}$y${\displaystyle x_{k+1}=x_{k}-A_{k+1}^{-1}\left(Ax_{k}-b\right)}$, dónde

${\displaystyle A_{k+1}^{-1}=A_{k}^{-1}+\left(1-A_{k}^{-1}A\right)u_{k}\otimes {v_{k}^{*}\left(1-AA_{k}^{-1}\right) \over v_{k}^{*}A\left(1-A_{k}^{-1}A\right)u_{k}}.}$

Las nuevas direcciones

${\displaystyle p_{k}=\left(1-P_{k}\right)u_{k},}$

${\displaystyle p_{k}^{*}=v_{k}^{*}A\left(1-P_{k}\right)A^{-1}}$

son entonces ortogonales a los residuos:

${\displaystyle v_{i}^{*}r_{k}=p_{i}^{*}r_{k}=0,}$

${\displaystyle r_{k}^{*}u_{j}=r_{k}^{*}p_{j}=0,}$

que en sí mismas satisfacen

${\displaystyle r_{k}=A\left(1-P_{k}\right)A^{-1}r_{j},}$

${\displaystyle r_{k}^{*}=r_{j}^{*}\left(1-P_{k}\right)}$

dónde${\displaystyle i,j<k}$.

El método del gradiente biconjugado ahora hace una elección especial y utiliza la configuración

${\displaystyle u_{k}=M^{-1}r_{k},\,}$

${\displaystyle v_{k}^{*}=r_{k}^{*}\,M^{-1}.\,}$

Con esta elección en particular, evaluaciones explícitas de${\displaystyle P_{k}}$y A ^{− 1} se evitan, y el algoritmo toma la forma indicada anteriormente.

• Si${\displaystyle A=A^{*}\,}$es autoadjunto ,${\displaystyle x_{0}^{*}=x_{0}}$y${\displaystyle b^{*}=b}$, entonces${\displaystyle r_{k}=r_{k}^{*}}$,${\displaystyle p_{k}=p_{k}^{*}}$y el método del gradiente conjugado produce la misma secuencia${\displaystyle x_{k}=x_{k}^{*}}$con la mitad del coste computacional.
• Las secuencias producidas por el algoritmo son biorthogonales , es decir,${\displaystyle p_{i}^{*}Ap_{j}=r_{i}^{*}M^{-1}r_{j}=0}$para${\displaystyle i\neq j}$.
• si${\displaystyle P_{j'}\,}$es un polinomio con${\displaystyle \deg \left(P_{j'}\right)+j<k}$, entonces${\displaystyle r_{k}^{*}P_{j'}\left(M^{-1}A\right)u_{j}=0}$. El algoritmo produce así proyecciones sobre el subespacio de Krylov .
• si${\displaystyle P_{i'}\,}$es un polinomio con${\displaystyle i+\deg \left(P_{i'}\right)<k}$, entonces${\displaystyle v_{i}^{*}P_{i'}\left(AM^{-1}\right)r_{k}=0}$.

• Método de gradiente biconjugado estabilizado (BiCG-Stab)
• Método del gradiente conjugado (CG)
• Método del gradiente conjugado al cuadrado (CGS)

• Fletcher, R. (1976). «Métodos de gradiente conjugado para sistemas indefinidos». En Watson, G. Alistair (ed.). Análisis numérico  : actas de la Conferencia de Dundee sobre Análisis Numérico . Lecture Notes in Mathematics. Vol.  506. Springer. pp. 73–89 . doi : 10.1007/BFb0080116 . ISBN  978-3-540-07610-0.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). «Sección 2.7.6» . Numerical Recipes: The Art of Scientific Computing (3.ª  ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.