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

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

L'algorithme[modifier | modifier le code]

  1. Choisir , , un préconditionneur régulier (on utilise fréquemment ) et ;
  2. ;
  3. ;
  4. for do
  5. ;
  6. ;
  7. , ( et sont le résidus);
  8. ;
  9. , .

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 et () en utilisant les projections suivantes :

,

Avec et . On peut irérer les projections elles-mêmes, comme

.

Les nouvelles directions de descente et sont alors orthogonales aux résidus : et , qui satisfont aux-même et ().

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

et .

Ce choix particulier permet alors d'éviter une évaluation directe de et , et donc augmenter la vitesse d'execution de l'algorithme.

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

  • Si est auto-adjointe, et , donc , , et la méthode du gradient conjugué produit la même suite .
  • En dimensions finies , au plus tard quand  : 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) : et pour .
  • SI est un polynôme avec , alors . L'algorithme est donc composé de projections sur des sous-espaces de Krylov (en) ;
  • SI est un polynôme avec , alors .