- 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 A soit auto-adjointe, en revanche, la méthode requiert des multiplications par la matrice adjointe A * .
L'algorithme
- Choisir x0, y0, un préconditionneur régulier M (on utilise fréquemment M − 1 = 1) et c;
;
;
- for
do
;
;
,
(rk = b − Axk et sk = c − A * yk sont le résidus);
;
,
.
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
(j < k) 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
(i,j < k).
La méthode du gradient biconjugué propose alors le choix suivant :
- uk: = M − 1rk et vk: = M − * sk.
Ce choix particulier permet alors d'éviter une évaluation directe de Pk et A − 1, et donc augmenter la vitesse d'execution de l'algorithme.
Propriétés
- Si A = A * est auto-adjointe, y0 = x0 et c = b, donc rk = sk, dk = fk, et la méthode du gradient conjugué produit la même suite xk = yk.
- En dimensions finies xn = A − 1b, au plus tard quand Pn = 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 biorthogonale (en) :
et
pour
.
- SI pj' est un polynôme avec
, alors
. L'algorithme est donc composé de projections sur des sous-espaces de Krylov (en) ;
- SI pi' est un polynôme avec
, alors
.
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Biconjugate gradient method » (voir la liste des auteurs)
Catégories :- Optimisation
- Analyse numérique matricielle
Wikimedia Foundation. 2010.