GMRES

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].

Sommaire

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 xnKn qui minimise la norme du résidu : ||Axnb||.

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

 q_1, q_2, \ldots, q_n \,

qui constituent une base de Kn. Ainsi, le vecteur xnKn peut s'écrire xn = Qnyn avec ynRn, et Qn une matrice de taille (m x n) formée des q1, …, qn.

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 Qn est orthogonale, on a

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

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

est le premier vecteur de la base canonique de Rn+1, et

 \beta = \|b-Ax_0\| \, ,

avec x0 vecteur d'initialisation (pour simplifier, on peut prendre zéro). Ainsi, xn 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 yn qui minimise ||rn|| ;
  • calculer xn = Qnyn ;
  • 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 Aqn doit être effectué. Cela génère un coût en calcul de 2m2 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(n2), 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 xk comme vecteur initial. Cette méthode est appelée GMRES(k).

Notes

  1. Saad and Schultz

Références

Notes et références


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article GMRES de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • GMRES — Das GMRES Verfahren (für Generalized minimal residual method) ist ein iteratives numerisches Verfahren zur Lösung großer, dünnbesetzter linearer Gleichungssysteme. Das Verfahren ist aus der Klasse der Krylow Unterraum Verfahren und insbesondere… …   Deutsch Wikipedia

  • GMRES-Verfahren — Das GMRES Verfahren (für Generalized minimal residual method) ist ein iteratives numerisches Verfahren zur Lösung großer, dünnbesetzter linearer Gleichungssysteme. Das Verfahren ist aus der Klasse der Krylow Unterraum Verfahren und insbesondere… …   Deutsch Wikipedia

  • Generalized minimal residual method — In mathematics, the generalized minimal residual method (usually abbreviated GMRES) is an iterative method for the numerical solution of a system of linear equations. The method approximates the solution by the vector in a Krylov subspace with… …   Wikipedia

  • Arnoldi-Verfahren — In der numerischen Mathematik ist das Arnoldi Verfahren wie das Lanczos Verfahren ein iteratives Verfahren zur Bestimmung einiger Eigenwerte und zugehöriger Eigenvektoren. Im Arnoldi Verfahren wird zu einer gegebenen Matrix und einem gegebenen… …   Deutsch Wikipedia

  • Krylov-Unterraum-Verfahren — Krylow Unterraum Verfahren sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach… …   Deutsch Wikipedia

  • Krylov-Unterraumverfahren — Krylow Unterraum Verfahren sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach… …   Deutsch Wikipedia

  • Método del gradiente biconjugado estabilizado — En álgebra lineal numérica, el método del gradiente biconjugado estabilizado, generalmente abreviado como BiCGSTAB (del inglés «biconjugate gradient stabilized method»), es un método iterativo propuesto por H. A. van der Vorst para la resolución… …   Wikipedia Español

  • Iterative method — In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination… …   Wikipedia

  • Arnoldi iteration — In numerical linear algebra, the Arnoldi iteration is an eigenvalue algorithm and an important example of iterative methods. Arnoldi finds the eigenvalues of general (possibly non Hermitian) matrices; an analogous method for Hermitian matrices is …   Wikipedia

  • Finite-Elemente-Analyse — Die Finite Elemente Methode (FEM) ist ein numerisches Verfahren zur näherungsweisen Lösung, insbesondere elliptischer partieller Differentialgleichungen mit Randbedingungen. Sie ist auch ein weit verbreitetes modernes Berechnungsverfahren im… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”