Méthode du gradient biconjugué

En mathématiques, plus spécifiquement en analyse numérique, la méthode du gradient biconjugué est un algorithme permettant de résoudre un système d'équations linéaires

$Ax=b.\,$

Contrairement à la méthode du gradient conjugué, cet algorithme ne nécessite pas que la matrice $A$ soit auto-adjointe, en revanche, la méthode requiert des multiplications par la matrice adjointe $A^{*}$.

L'algorithme

1. Choisir $x_{0}$, $y_{0}$, un préconditionneur régulier $M$ (on utilise fréquemment $M^{-1}=1$) et $c$;
2. $r_{0}\leftarrow b-Ax_{0},s_{0}\leftarrow c-A^{*}y_{0}\,$;
3. $d_{0}\leftarrow M^{-1}r_{0},f_{0}\leftarrow M^{-*}s_{0}\,$;
4. for $k=0,1,\dots \,$ do
5. $\alpha _{k}\leftarrow {s_{k}^{*}M^{-1}r_{k} \over f_{k}^{*}Ad_{k}}\,$;
6. $x_{k+1}\leftarrow x_{k}+\alpha _{k}d_{k}\,$ $\left(y_{k+1}\leftarrow y_{k}+{\overline {\alpha _{k}}}f_{k}\right)\,$;
7. $r_{k+1}\leftarrow r_{k}-\alpha _{k}Ad_{k}\,$, $s_{k+1}\leftarrow s_{k}-{\overline {\alpha _{k}}}A^{*}f_{k}\,$ ($r_{k}=b-Ax_{k}$ et $s_{k}=c-A^{*}y_{k}$ sont le résidus);
8. $\beta _{k}\leftarrow {s_{k+1}^{*}M^{-1}r_{k+1} \over s_{k}^{*}M^{-1}r_{k}}\,$;
9. $d_{k+1}\leftarrow M^{-1}r_{k+1}+\beta _{k}d_{k}\,$, $f_{k+1}\leftarrow M^{-*}s_{k+1}+{\overline {\beta _{k}}}f_{k}\,$.

Discussion

La méthode est numériquement instable, mais on y remédie par la méthode stabilisée du gradient biconjugué (en), et elle reste très importante du point de vue théorique : on définit l'itération par $x_{k}:=x_{j}+P_{k}A^{-1}\left(b-Ax_{j}\right)$ et $y_{k}:=y_{j}+A^{-*}P_{k}^{*}\left(c-A^{*}y_{j}\right)$ ($j<k$) en utilisant les projections suivantes :

$P_{k}:=\mathbf {u_{k}} \left(\mathbf {v_{k}} ^{*}A\mathbf {u_{k}} \right)^{-1}\mathbf {v_{k}} ^{*}A$,

Avec $\mathbf {u_{k}} =\left(u_{0},u_{1},\dots u_{k-1}\right)$ et $\mathbf {v_{k}} =\left(v_{0},v_{1},\dots v_{k-1}\right)$. On peut itérer les projections elles-mêmes, comme

$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}}$.

Les nouvelles directions de descente $d_{k}:=\left(1-P_{k}\right)u_{k}$ et $f_{k}:=\left(A\left(1-P_{k}\right)A^{-1}\right)^{*}v_{k}$ sont alors orthogonales aux résidus : $v_{i}^{*}r_{k}=f_{i}^{*}r_{k}=0$ et $s_{k}^{*}u_{j}=s_{k}^{*}d_{j}=0$, qui satisfont aux mêmes $r_{k}=A\left(1-P_{k}\right)A^{-1}r_{j}$ et $s_{k}=\left(1-P_{k}\right)^{*}s_{j}$($i,j<k$).

La méthode du gradient biconjugué propose alors le choix suivant :

$u_{k}:=M^{-1}r_{k}$ et $v_{k}:=M^{-*}s_{k}$.

Ce choix particulier permet alors d'éviter une évaluation directe de $P_{k}$ et $A^{-1}$, et donc augmenter la vitesse d'exécution de l'algorithme.

Propriétés

• Si $A=A^{*}$ est auto-adjointe, $y_{0}=x_{0}$ et $c=b$, donc $r_{k}=s_{k}$, $d_{k}=f_{k}$, et la méthode du gradient conjugué produit la même suite $x_{k}=y_{k}$.

• En dimensions finies $x_{n}=A^{-1}b$, au plus tard quand $P_{n}=1$ : La méthode du gradient biconjugué rend la solution exacte après avoir parcouru tout l'espace et est donc une méthode directe.

• La suite produite par l'algorithme est biorthogonale (en) : $f_{i}^{*}Ad_{j}=0$ et $s_{i}^{*}M^{-1}r_{j}=0$ pour $i\neq j$.

• SI $p_{j'}$ est un polynôme avec $deg\left(p_{j'}\right)+j<k$, alors $s_{k}^{*}p_{j'}\left(M^{-1}A\right)u_{j}=0$. L'algorithme est donc composé de projections sur des sous-espaces de Krylov ;

• SI $p_{i'}$ est un polynôme avec $i+deg\left(p_{i'}\right)<k$, alors $v_{i}^{*}p_{i'}\left(AM^{-1}\right)r_{k}=0$.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Biconjugate gradient method » (voir la liste des auteurs).