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^{\ast }$.

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-A{x}_0,s_0\leftarrow c-A^{\ast }{y}_0$;
3. $d_0\leftarrow M^{-1}{r}_0,f_0\leftarrow M^{-\ast }{s}_0$;
4. for $k=0,1,\dots$ do
5. ${\alpha }_k\leftarrow \frac{s_k^{\ast }{M}^{-1}{r}_k}{f_k^{\ast }A{d}_k}$;
6. $x_{k+1}\leftarrow x_k+{\alpha }_k{d}_k$ $(y_{k+1}\leftarrow y_k+\overline{{\alpha }_k}{f}_k)$;
7. $r_{k+1}\leftarrow r_k-{\alpha }_{k}A{d}_k$, $s_{k+1}\leftarrow s_k-\overline{{\alpha }_k}{A}^{\ast }{f}_k$ ($r_k=b-A{x}_k$ et $s_k=c-A^{\ast }{y}_k$ sont le résidus);
8. ${\beta }_k\leftarrow \frac{s_{k+1}^{\ast }{M}^{-1}{r}_{k+1}}{s_k^{\ast }{M}^{-1}{r}_k}$;
9. $d_{k+1}\leftarrow M^{-1}{r}_{k+1}+{\beta }_k{d}_k$, $f_{k+1}\leftarrow M^{-\ast }{s}_{k+1}+\overline{{\beta }_k}{f}_k$.

Discussion

La méthode est numériquement instable, mais on y remédie par la Modèle:Lien, 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}(b-A{x}_j)$ et $y_k:=y_j+A^{-\ast }{P}_k^{\ast }(c-A^{\ast }{y}_j)$ ($j<k$) en utilisant les projections suivantes :

$P_k:={𝐮}_{𝐤}{\left({{𝐯}_{𝐤}}^{\ast }A{𝐮}_{𝐤}\right)}^{-1}{{𝐯}_{𝐤}}^{\ast }A$,

Avec ${𝐮}_{𝐤}=(u_0,u_1,\dots u_{k-1})$ et ${𝐯}_{𝐤}=(v_0,v_1,\dots v_{k-1})$. On peut itérer les projections elles-mêmes, comme

$P_{k+1}=P_k+(1-P_k)u_k\otimes \frac{v_k^{\ast }A(1-P_k)}{v_k^{\ast }A(1-P_k)u_k}$.

Les nouvelles directions de descente $d_k:=(1-P_k)u_k$ et $f_k:={\left(A(1-P_k)A^{-1}\right)}^{\ast }{v}_k$ sont alors orthogonales aux résidus : $v_i^{\ast }{r}_k=f_i^{\ast }{r}_k=0$ et $s_k^{\ast }{u}_j=s_k^{\ast }{d}_j=0$, qui satisfont aux mêmes $r_k=A(1-P_k)A^{-1}{r}_j$ et $s_k={(1-P_k)}^{\ast }{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^{-\ast }{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^{\ast }$ 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 Modèle:Lien : $f_i^{\ast }A{d}_j=0$ et $s_i^{\ast }{M}^{-1}{r}_j=0$ pour $i\ne j$.

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

• SI $p_{i^{\prime }}$ est un polynôme avec $i+deg\left(p_{i^{\prime }}\right)<k$, alors $v_i^{\ast }{p}_{i^{\prime }}\left(A{M}^{-1}\right)r_k=0$.