Sous-espace de Krylov

En algèbre linéaire, le sous-espace de Krylov d'ordre r associé à une matrice $A$ de taille $n$ et un vecteur b de dimension n est le sous-espace vectoriel linéaire engendré par les vecteurs images de bpar les r premières puissances de A (à partir de $A^{0}=I$ ), c'est-à-dire

${\mathcal {K}}_{r}(A,b)=\operatorname {span} \,\{b,Ab,A^{2}b,\ldots ,A^{r-1}b\}.$

Introduction

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.

Propriétés

• ${\mathcal {K}}_{r}(A,b),A{\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r+1}(A,b)$ .
• Les vecteurs $\{b,Ab,A^{2}b,\ldots ,A^{r-1}b\}$ sont linéairement indépendants tant que $r<r_{0}$, et ${\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r_{0}}(A,b)$ . Ainsi, $r_{0}$ désigne la dimension maximale d'un sous-espace de Krylov.
• La dimension maximale satisfait $r_{0}\leq 1+\operatorname {rank} A$ et $r_{0}\leq n+1$ .
• Plus exactement, $r_{0}\leq \deg[p(A)]$, où $p(A)$ est le polynôme minimal de $A$ . De plus, il existe une $b$ tel que $r_{0}=\deg[p(A)]$ .
• ${\mathcal {K}}_{r}(A,b)$ est un sous-module cyclique généré par $b$ de la torsion $k[x]$ -module $(k^{n})^{A}$, où $k^{n}$ est l'espace linéaire sur $k$ .
• $k^{n}$ peut être décomposé comme la somme directe des sous-espaces de Krylov.

Utilisation

Les sous-espaces de Krylov sont utilisés dans de nombreux algorithmes numériques en algèbre linéaire pour trouver des solutions approchées à des problèmes de vecteurs propres avec des matrices de grande dimension.

Les méthodes itératives modernes, telles que l' algorithme d'Arnoldi, peuvent être utilisées pour trouver une (ou plusieurs) valeurs propres de grandes matrices creuses ou pour résoudre de grands systèmes d'équations linéaires. Ils essaient d'éviter les opérations matrice-matrice, mais utilisent plutôt les produits matrice-vecteur et travaillent avec les vecteurs résultants. Étant donné le vecteur $b$, on calcule $Ab$, puis on multiplie ce vecteur par $A$ pour trouver $A^{2}b$ etc. Tous les algorithmes qui fonctionnent de cette manière sont appelés méthodes de sous-espace de Krylov ; ce sont actuellement les méthodes les plus efficaces disponibles en algèbre linéaire numérique.

Problèmes

Étant donné que les vecteurs deviennent généralement rapidement presque linéairement dépendants en raison des propriétés de la méthode de la puissance itérée, les méthodes reposant sur le sous-espace de Krylov impliquent fréquemment un schéma d'orthonormalisation, comme l'algorithme de Lanczos pour les matrices hermitiennes ou l'algorithme d'Arnoldi pour les matrices plus générales.

Méthodes existantes

Les méthodes de sous-espace de Krylov les plus connues sont Arnoldi, Lanczos, Conjugate gradient, IDR(s) (Induced dimension reduction), GMRES (généralisation de la méthode de minimisation du résidu), BiCGSTAB (méthode du gradient biconjugué stabilisé), QMR (quasi minimal résiduel), TFQMR ( QMR sans transposition) et les méthodes de résidus minimaux.

 

Lectures complémentaires

• Olavi Nevanlinna, Convergence of iterations for linear equations, Basel, Birkhäuser Verlag, coll. « Lectures in Mathematics ETH Zürich », 1993, viii+177 pp. (ISBN 3-7643-2865-7, MR 1217705)3-7643-2865-7
• Yousef Saad, Iterative methods for sparse linear systems, SIAM, 2003 (ISBN 0-89871-534-2, OCLC 51266114, lire en ligne)0-89871-534-2
• Gerard Meurant et Jurjen Duintjer Tebbens : "Méthodes de Krylov pour les systèmes linéaires non symétriques - De la théorie aux calculs", Springer Series in Computational Mathematics, vol.57, (oct. 2020). (ISBN 978-3-030-55250-3)ISBN 978-3-030-55250-3, url= https://doi.org/10.1007/978-3-030-55251-0 .
• Iman Farahbakhsh : "Méthodes du sous-espace de Krylov avec application dans les solveurs d'écoulement de fluide incompressible", Wiley, (ISBN 978-1119618683) (septembre 2020).