GMRES

En mathématique, la généralisation de la Méthode de Minimisation du Résidu (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 un approximation de la solution par un vecteur appartenant à un 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^[1].

La méthode

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

$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., ||b|| = 1 (dans cet article, ||·|| représente la norme euclidienne).

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

$K_n = \operatorname{span} \, \{ b, Ab, A^2b, \ldots, A^{n-1}b \}. \,$

GMRES donne une approximation de la solution exacte de Ax = b par le vecteur x_n ∈ K_n qui minimise la norme du résidu : ||Ax_n − b||.

Pour garantir le caractère linéairement indépendant aux vecteurs b, Ab, …, Aⁿ⁻¹b, on utilise la méthode d'Arnoldi pour trouver des vecteurs orthonormaux

$q_1, q_2, \ldots, q_n \,$

qui constituent une base de K_n. Ainsi, le vecteur x_n ∈ K_n peut s'écrire x_n = Q_ny_n avec y_n ∈ Rⁿ, 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 $\tilde{H}_n$ de taille (n+1) xn avec

$AQ_n = Q_{n+1} \tilde{H}_n. \,$

Comme Q_n est orthogonale, on a

$\| Ax_n - b \| = \| \tilde{H}_ny_n - \beta e_1 \|, \,$

où

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

est le premier vecteur de la base canonique de Rⁿ⁺¹, et

$\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

$r_n = \tilde{H}_n y_n - \beta e_1.$

C'est un problème linéaire de moindres carrés de taille n.

Voici le contenu de chaque itération de l'algorithme du GMRES :

• effectuer une étape de l'algorithme d'Arnoldi ;
• trouver y_n qui minimise ||r_n|| ;
• calculer x_n = Q_ny_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 Aq_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.

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(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).

Notes

1. ↑ Saad and Schultz

Références

• A. Meister, Numerik linearer Gleichungssysteme, 2nd édition, Vieweg 2005, (ISBN 978-3-528-13135-7).
• Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd édition, Society for Industrial and Applied Mathematics, 2003. (ISBN 978-0-89871-534-7).
• Y. Saad and M.H. Schultz, « GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems », SIAM J. Sci. Stat. Comput., 7:856-869, 1986. DOI:10.1137/0907058.
• J. Stoer and R. Bulirsch, Introduction to numerical analysis, 3rd édition, Springer, New York, 2002. (ISBN 978-0-387-95452-3).
• Lloyd N. Trefethen and David Bau, III, Numerical Linear Algebra, Society for Industrial and Applied Mathematics, 1997. (ISBN 978-0-89871-361-9).
• Dongarra et al. , Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Édition, SIAM, Philadelphia, 1994

Notes et références

• (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)