En mathématique, la généralisation de la méthode de minimisation du résidu (ou GMRES, pour Generalized minimal residual) 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 .
La méthode GMRES fut développée par Yousef Saad et Martin H. Schultz en 1986.
On cherche à résoudre le système d'équations linéaires suivant :
La matrice A est supposée inversible et de taille (m x m). De plus, on suppose que b est normé, i.e., (dans cet article, représente la norme euclidienne).
Le n-ième espace de Krylov pour ce problème est défini ainsi :
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 qui minimise la norme du résidu : .
Pour garantir le caractère linéairement indépendant des vecteurs b, Ab, ..., Ab, on utilise la méthode d'Arnoldi pour trouver des vecteurs orthonormaux
qui constituent une base de . Ainsi, le vecteur peut s'écrire x = Q y avec , et Q une matrice de taille (m x n) formée des q, ..., q.
La méthode d'Arnoldi produit aussi une matrice de Hessenberg supérieure de taille (n+1) x n avec
Comme Q est orthogonale, on a
où
est le premier vecteur de la base canonique de , et
avec x vecteur d'initialisation (pour simplifier, on peut prendre zéro). Ainsi, x peut être trouvé en minimisant la norme du résidu
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 qui minimise r ;
calculer x = Q y ;
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 doit être effectué.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
En mathématique, la généralisation de la méthode de minimisation du résidu (ou GMRES, pour Generalized minimal residual) 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 . La méthode GMRES fut développée par Yousef Saad et Martin H. Schultz en 1986.
Numerical linear algebra, sometimes called applied linear algebra, is the study of how matrix operations can be used to create computer algorithms which efficiently and accurately provide approximate answers to questions in continuous mathematics. It is a subfield of numerical analysis, and a type of linear algebra. Computers use floating-point arithmetic and cannot exactly represent irrational data, so when a computer algorithm is applied to a matrix of data, it can sometimes increase the difference between a number stored in the computer and the true number that it is an approximation of.
En algèbre linéaire, le sous-espace de Krylov d'ordre r associé à une matrice de taille et un vecteur b de dimension n est le sous-espace vectoriel linéaire engendré par les vecteurs images de b par les r premières puissances de A (à partir de ), c'est-à-dire Le concept porte le nom du mathématicien appliqué et ingénieur naval russe Alexei Krylov, qui a publié un article à ce sujet en 1931. Les vecteurs sont linéairement indépendants tant que , et . Ainsi, désigne la dimension maximale d'un sous-espace de Krylov.
The student will learn state-of-the-art algorithms for solving differential equations. The analysis and implementation of these algorithms will be discussed in some detail.
Couvre le système logiciel Canalflow pour l'analyse numérique du flux de fluide incompressible dans les géométries des canaux, y compris les méthodes spectrales et les solutions invariantes.
We present a multi-level algorithm to approximate the inverse of the fluid block in a Navier-Stokes saddle-point matrix where the coarse level is defined as a restriction of the degrees of freedom to
2013
We analyze an expansion of the generalized block Krylov subspace framework of [Electron.\ Trans.\ Numer.\ Anal., 47 (2017), pp. 100-126]. This expansion allows the use of low-rank modifications of the