GMRES

On cherche à résoudre le système d'équations linéaires suivant :

${\displaystyle Ax=b.\,}$

La matrice A est supposée inversible et de taille (m x m). De plus, on suppose que b est normé, i.e., ${\displaystyle \|b\|=1}$ (dans cet article, ${\displaystyle \|\cdot \|}$ représente la norme euclidienne).

Le n-ième espace de Krylov pour ce problème est défini ainsi :

${\displaystyle \mathbb {K} _{n}=\operatorname {Vect} \,\{b,Ab,A^{2}b,\dotsc ,A^{n-1}b\}}$

où Vect signifie le sous-espace vectoriel engendré par les vecteurs.

La méthode GMRES donne une approximation de la solution exacte du système de départ par un vecteur ${\displaystyle x_{n}\in \mathbb {K} _{n}}$ qui minimise la norme du résidu : ${\displaystyle \|Ax_{n}-b\|}$.

Pour garantir le caractère linéairement indépendant des vecteurs b, Ab, ..., A^n–1b, on utilise la méthode d'Arnoldi pour trouver des vecteurs orthonormaux

${\displaystyle q_{1},q_{2},\dotsc ,q_{n}}$

qui constituent une base de ${\displaystyle \mathbb {K} _{n}}$. Ainsi, le vecteur ${\displaystyle x_{n}\in \mathbb {K} _{n}}$ peut s'écrire x_n = Q_n y_n avec ${\displaystyle y_{n}\in \mathbb {R} ^{n}}$, et Q_n une matrice de taille (m x n) formée des q₁, ..., q_n.

La méthode d'Arnoldi produit aussi une matrice de Hessenberg supérieure ${\displaystyle {\tilde {H}}_{n}}$ de taille (n+1) x n avec

${\displaystyle AQ_{n}=Q_{n+1}{\tilde {H}}_{n}.}$

Comme Q_n est orthogonale, on a

${\displaystyle \|Ax_{n}-b\|=\|{\tilde {H}}_{n}y_{n}-\beta e_{1}\|,}$

où

${\displaystyle e_{1}=(1,0,0,\dotsc ,0)}$

est le premier vecteur de la base canonique de ${\displaystyle \mathbb {R} ^{n+1}}$, et

${\displaystyle \beta =\|b-Ax_{0}\|\,,}$

avec x₀ vecteur d'initialisation (pour simplifier, on peut prendre zéro). Ainsi, x_n peut être trouvé en minimisant la norme du résidu

${\displaystyle r_{n}={\tilde {H}}_{n}y_{n}-\beta e_{1}.}$

On reconnait un problème linéaire de moindres carrés de taille n.

L'algorithme se résume donc en :

• effectuer une étape de l'algorithme d'Arnoldi ;
• trouver y_n qui minimise |r_n| ;
• calculer x_n = Q_n y_n ;
• recommencer tant que le résidu est plus grand qu'une quantité choisie arbitrairement au début de l'algorithme (on appelle cette quantité tolérance).

À chaque itération, un produit matrice-vecteur A q_n doit être effectué. Cela génère un coût en calcul de 2m² opérations pour les matrices non creuses de taille m, mais le coût peut être ramené à O(m) pour les matrices creuses. En plus du produit matrice-vecteur, O(n m) opérations doivent être effectuées à la n-ième itération.

Comme d'autres méthodes itératives, GMRES est souvent combiné avec des méthodes de préconditionnement pour accroître la vitesse de convergence.

Le coût des itérations croît en O(n²), où n est le numéro de l'itération. De ce fait, la méthode est parfois relancée après un nombre k d'itérations, avec x_k comme vecteur initial. Cette méthode est appelée GMRES(k).

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Generalized minimal residual method » (voir la liste des auteurs).

• (en) A. Meister, Numerik linearer Gleichungssysteme, 2^e éd., Vieweg 2005, (ISBN 978-3-528-13135-7).
• (en) Y. Saad, Iterative Methods for Sparse Linear Systems, 2^e éd., Society for Industrial and Applied Mathematics, 2003. (ISBN 978-0-89871-534-7).
• (en) J. Stoer et R. Bulirsch, Introduction to numerical analysis, 3^e éd., Springer, New York, 2002. (ISBN 978-0-387-95452-3).
• (en) Lloyd N. Trefethen et David Bau, III, Numerical Linear Algebra, Society for Industrial and Applied Mathematics, 1997. (ISBN 978-0-89871-361-9).
• (en) J. Dongarra et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2^e éd., SIAM, Philadelphia, 1994

• Portail des mathématiques