GMRES

Modèle:Ébauche Modèle:À vérifier En mathématique, la généralisation de la méthode de minimisation du résidu (Modèle:En anglais ou GMRES) est une méthode itérative pour déterminer une solution numérique d'un système d'équations linéaires. La méthode donne une approximation de la solution par un vecteur appartenant à un sous-espace de Krylov avec un résidu minimal. Pour déterminer ce vecteur, on utilise la méthode itérative d'Arnoldi.

La méthode GMRES fut développée par Yousef Saad et Martin H. Schultz en 1986.

Principe de la méthode

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

$Ax=b.$

La matrice Modèle:Mvar est supposée inversible et de taille (m x m). De plus, on suppose que Modèle:Mvar est normé, i.e., $\Vert b\Vert =1$ (dans cet article, $\Vert \cdot \Vert$ représente la norme euclidienne).

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

${𝕂}_n=\mathrm{Vect}\{b,Ab,A^{2}b,\dots ,A^{n-1}b\}$

où Modèle:Math 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 $x_n\in {𝕂}_n$ qui minimise la norme du résidu : $\Vert A{x}_n-b\Vert$.

Pour garantir le caractère linéairement indépendant des vecteurs Modèle:Math, on utilise la méthode d'Arnoldi pour trouver des vecteurs orthonormaux

$q_1,q_2,\dots ,q_n$

qui constituent une base de ${𝕂}_n$. Ainsi, le vecteur $x_n\in {𝕂}_n$ peut s'écrire Modèle:Math avec $y_n\in {ℝ}^n$, et Modèle:Mvar une matrice de taille (m x n) formée des Modèle:Math.

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

$A{Q}_n=Q_{n+1}{\tilde{H}}_n.$

Comme Modèle:Mvar est orthogonale, on a

$\Vert A{x}_n-b\Vert =\Vert {\tilde{H}}_n{y}_n-\beta e_1\Vert ,$

où

$e_1=(1,0,0,\dots ,0)$

est le premier vecteur de la base canonique de ${ℝ}^{n+1}$, et

$\beta =\Vert b-A{x}_0\Vert ,$

avec Modèle:Math vecteur d'initialisation (pour simplifier, on peut prendre zéro). Ainsi, Modèle:Mvar peut être trouvé en minimisant la norme du résidu

$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 Modèle:Mvar qui minimise Modèle:Math ;
• calculer Modèle:Math ;
• 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).

Coûts

À chaque itération, un produit matrice-vecteur Modèle:Mvar doit être effectué. Cela génère un coût en calcul de 2mModèle:Exp 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.

Extensions de la méthode

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(nModèle:Exp), 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 Modèle:Mvar comme vecteur initial. Cette méthode est appelée GMRES(k).

Bibliographie

• Modèle:Article

• Modèle:En A. Meister, Numerik linearer Gleichungssysteme, Modèle:2e éd., Vieweg 2005, Modèle:ISBN.
• Modèle:En Y. Saad, Iterative Methods for Sparse Linear Systems, Modèle:2e éd., Society for Industrial and Applied Mathematics, 2003. Modèle:ISBN.
• Modèle:En J. Stoer et R. Bulirsch, Introduction to numerical analysis, Modèle:3e éd., Springer, New York, 2002. Modèle:ISBN.
• Modèle:En Lloyd N. Trefethen et David Bau, III, Numerical Linear Algebra, Society for Industrial and Applied Mathematics, 1997. Modèle:ISBN.
• Modèle:En J. Dongarra Modèle:Et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, Modèle:2e éd., SIAM, Philadelphia, 1994