Méthode du gradient biconjugué

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

A x= 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[modifier | modifier le code]

  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^* 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^* A d_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 A d_k \,, s_{k+1} \leftarrow s_k- \overline{\alpha_k} A^* f_k \, (r_k=b-A x_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[modifier | modifier le code]

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 - A x_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 iré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ême 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'execution de l'algorithme.

Propriétés[modifier | modifier le code]

  • 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.
  • SI p_{i'} est un polynôme avec i+deg\left( p_{i'} \right) <k , alors v_i^* p_{i'}\left(A M^{-1} \right) r_k=0.