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
Choisir , , un préconditionneur régulier (on utilise fréquemment ) et ;
for do
, ( et sont le résidus); ; , .
Discussion La méthode est numériquement instable, mais on y remédie par la , 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 : 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 .
Catégorie:Optimisation Catégorie:Analyse numérique matricielle