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

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

  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

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 itérer les projections elles-mêmes, comme

.

Les nouvelles directions de descente et sont alors orthogonales aux résidus : et , qui satisfont aux mêmes 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'exécution de l'algorithme.

Propriétés

  • 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 ;
  • SI est un polynôme avec , alors .
  • Portail de l'analyse
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.