Sous-espace de Krylov

En algèbre linéaire, le sous-espace de Krylov d'ordre r associé à une matrice A {\displaystyle A} de taille n {\displaystyle n} 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 A 0 = I {\displaystyle A^{0}=I} )[1], c'est-à-dire

K r ( A , b ) = span { b , A b , A 2 b , … , A r − 1 b } . {\displaystyle {\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[2].

Propriétés

Les sous-espaces de Krylov ont de nombreuses propriétés utilisées en algèbre linéaire. Soit r ∈ N {\displaystyle r\in \mathbb {N} } . En considérant A {\displaystyle A} une matrice de taille n × n {\displaystyle n\times n} et le vecteur colonne b ∈ R n {\displaystyle b\in \mathbb {R} ^{n}} , on a les propriétés suivantes[3] :

  • K r ( A , b ) ⊂ K r + 1 ( A , b ) {\displaystyle {\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r+1}(A,b)} ,
  • A K r ( A , b ) ⊂ K r + 1 ( A , b ) {\displaystyle A{\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r+1}(A,b)} .

Comme K r ( A , b ) ⊂ R n {\displaystyle {\mathcal {K}}_{r}(A,b)\subset \mathbb {R} ^{n}} on a dim ⁡ ( K r ( A , b ) ) ≤ n {\displaystyle \dim({\mathcal {K}}_{r}(A,b))\leq n} et il existe un entier r 0 ≤ n {\displaystyle r_{0}\leq n} dépendant de A {\displaystyle A} et b {\displaystyle b} tel que les vecteurs { b , A b , A 2 b , … , A r − 1 b } {\displaystyle \{b,Ab,A^{2}b,\ldots ,A^{r-1}b\}} sont linéairement indépendants tant que r < r 0 {\displaystyle r<r_{0}} . De plus, on sait que K r ( A , b ) ⊂ K r 0 ( A , b ) {\displaystyle {\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r_{0}}(A,b)} d'après la première relation d'imbrication ci-dessus. La valeur r 0 {\displaystyle r_{0}} désigne la dimension maximale des sous-espaces de Krylov associés à A {\displaystyle A} et b {\displaystyle b} .

On a les relations d'imbrication suivantes :

K 1 ( A , b ) ⊂ ⋯ ⊂ K r ( A , b ) ⊂ K r + 1 ( A , b ) ⊂ ⋯ ⊂ K r 0 ( A , b ) = K r 0 + 1 ( A , b ) ⋯ {\displaystyle {\mathcal {K}}_{1}(A,b)\subset \cdots \subset {\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r+1}(A,b)\subset \cdots \subset {\mathcal {K}}_{r_{0}}(A,b)={\mathcal {K}}_{r_{0}+1}(A,b)\cdots }

On rappelle que pour tout r {\displaystyle r} on a K r ( A , b ) ⊂ R n {\displaystyle {\mathcal {K}}_{r}(A,b)\subset \mathbb {R} ^{n}} . On en déduit que r 0 ≤ n + 1 {\displaystyle r_{0}\leq n+1} . De plus, on a r 0 ≤ 1 + rank ⁡ A {\displaystyle r_{0}\leq 1+\operatorname {rank} A} . Plus précisément, r 0 {\displaystyle r_{0}} est inférieur au degré du polynôme minimal de A {\displaystyle A} . En effet, si p ( x ) ∈ R m [ x ] {\displaystyle p(x)\in \mathbb {R} _{m}[x]} est le polynôme minimal de A {\displaystyle A} alors il existe une famille de réels ( a i ) 0 ≤ i ≤ m {\displaystyle (a_{i})_{0\leq i\leq m}} tels que p ( A ) = ∑ i = 0 m a i A i {\displaystyle p(A)=\displaystyle \sum _{i=0}^{m}a_{i}A^{i}} est la matrice nulle. En particulier p ( A ) b {\displaystyle p(A)b} est le vecteur nul donc les vecteurs { b , A b , ⋯ , A m b } {\displaystyle \lbrace b,Ab,\cdots ,A^{m}b\rbrace } sont liés. Plus exactement, r 0 ≤ deg ⁡ ( p ) {\displaystyle r_{0}\leq \deg(p)} , où p ( A ) {\displaystyle p(A)} est le polynôme minimal de A {\displaystyle A} .


Les propriétés qui suivent sont aussi vérifiées par les sous-espaces de Krylov:

  • K r ( A , b ) {\displaystyle {\mathcal {K}}_{r}(A,b)} est un sous-module cyclique généré par b {\displaystyle b} de la torsion k [ x ] {\displaystyle k[x]} -module ( k n ) A {\displaystyle (k^{n})^{A}} , où k n {\displaystyle k^{n}} est l'espace linéaire sur k {\displaystyle k} .
  • k n {\displaystyle k^{n}} peut être décomposé comme la somme directe des sous-espaces de Krylov.

Applications

Les sous-espaces de Krylov sont utilisés dans de nombreux algorithmes numériques en algèbre linéaire. Par exemple, on mentionne les utilisations suivantes :

  • le calcul de f ( A ) b {\displaystyle f(A)b} où f : x ↦ f ( x ) {\displaystyle f:x\mapsto f(x)} est une fonction analytique. Comme f {\displaystyle f} est analytique, il existe des réels ( a i ) i ∈ N {\displaystyle (a_{i})_{i\in \mathbb {N} }} tels que f ( x ) = ∑ i ∈ N a i x i {\displaystyle f(x)=\displaystyle \sum _{i\in \mathbb {N} }a_{i}x^{i}} . Comme f ( A ) b ∈ R n {\displaystyle f(A)b\in \mathbb {R} ^{n}} et par construction des sous-espaces de Krylov, pour r {\displaystyle r} suffisamment grand, on a f ( A ) b ∈ K r ( A , b ) {\displaystyle f(A)b\in {\mathcal {K}}_{r}(A,b)} . Le calcul peut être effectué en se ramenant à l'espace de Krylov K r ( A , b ) {\displaystyle {\mathcal {K}}_{r}(A,b)} . Cette approche est parfois utilisée pour calculer exp ⁡ ( A ) b {\displaystyle \exp(A)b} [4] pour la résolution de systèmes d'équation différentielle linéaires.
  • la résolution du système linéaire A X = b {\displaystyle AX=b} où A {\displaystyle A} est une matrice inversible. D'après le théorème de Cayley-Hamilton, on a A − 1 b ∈ K n − 1 ( A , b ) {\displaystyle A^{-1}b\in {\mathcal {K}}_{n-1}(A,b)} donc la résolution du système peut se faire dans des sous-espaces de Krylov. Les algorithmes GMRES et FOM[5],[6] sont des algorithmes itératifs pour la résolution de système linéaires basés sur les sous-espaces de Krylov.
  • la recherche de valeurs propres. 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. La méthode de la puissance itérée et l'algorithme de Lanczos reposent sur des sous-espaces de Krylov.
  • la résolution de système mal posés de la forme A x = b {\displaystyle Ax=b} (où A {\displaystyle A} peut-être une matrice rectangulaire et/ou une matrice non-inversible). On peut par exemple citer les méthodes de type RRGMRES[7] qui reposent sur des sous-espaces de Krylov de la forme K n ( A , A b ) {\displaystyle {\mathcal {K}}_{n}(A,Ab)} . La solution d'un tel système est généralement considérée au sens des moindres carrés et n'est pas toujours unique.

Dans les algorithmes itératifs basés sur les sous-espaces de Krylov, on cherche à éviter les opérations matrice-matrice, coûteuses en calculs, au profit de produits matrice-vecteur. Étant donné le vecteur b {\displaystyle b} , on calcule A b {\displaystyle Ab} , puis on multiplie ce vecteur par A {\displaystyle A} pour trouver A 2 b {\displaystyle A^{2}b} etc. De plus, au lieu de stocker des matrices complètes de taille n × n {\displaystyle n\times n} ( f ( A ) {\displaystyle f(A)} ou A − 1 {\displaystyle A^{-1}} par exemple), on ne stocke qu'un vecteur de taille n {\displaystyle n} . Grâce à ces propriétés, les sous-espaces de Krylov sont particulièrement utiles pour les grandes valeurs de n {\displaystyle n} .

Tous les algorithmes qui fonctionnent de cette manière sont appelés méthodes de sous-espace de Krylov, ou plus simplement méthodes de Krylov. Ils font actuellement parti des méthodes les plus efficaces disponibles en algèbre linéaire numérique.

Inconvénients

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

Notes et références

Notes

  1. ↑ Valeria Simoncini (dir.), Krylov Subspaces, Princeton University Press, coll. « The Princeton Companion to Applied Mathematics », , 113–114 p.
  2. ↑ (ru) Krylov, « О численном решении уравнения, которым в технических вопросах определяются частоты малых колебаний материальных систем », Izvestiia Akademii nauk SSSR, vol. 7, no 4,‎ , p. 491–539 (lire en ligne)
  3. ↑ (en) Yousef Saad, Iterative Methods for Sparse Linear Systems (ISBN 0-89871-534-2, lire en ligne)
  4. ↑ (en) Marlis Hochbruck, « On Krylov subspace approximations to the matrix exponential operator », SIAM Journal of Numerical Analysis,‎ (lire en ligne Accès limité [PDF])
  5. ↑ (en) Yousef Saad, « GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems », SIAM Journal on scientific and statistical computing 7.3,‎ (lire en ligne Accès libre [PDF])
  6. ↑ (en) Yousef Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, , 553 p. (ISBN 978-3-030-55250-3, lire en ligne), p. 165-193
  7. ↑ (en) Aminikhah, H, « Preconditioned RRGMRES for discrete Ill-posed problems », International Journal of Computational Methods, vol. 15, no 04,‎ (lire en ligne Accès payant [PDF])

Référence

  • Olavi Nevanlinna, Convergence of iterations for linear equations, Basel, Birkhäuser Verlag, coll. « Lectures in Mathematics ETH Zürich », , viii+177 pp. (ISBN 3-7643-2865-7, MR 1217705) lien Math Reviews
  • Yousef Saad, Iterative methods for sparse linear systems, SIAM, (ISBN 0-89871-534-2, OCLC 51266114, lire en ligne) (OCLC 51266114)
  • 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), 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).
  • icône décorative Portail de l’algèbre