Dans le cas d’un système d’équations linéaires, les deux principales classes de méthodes itératives sont les méthodes itératives stationnaires, et les méthodes plus générales de sous-espace de Krylov.
Méthodes itératives stationnairesEdit
IntroductionEdit
Les méthodes itératives stationnaires résolvent un système linéaire avec un opérateur approchant celui d’origine ; et sur la base d’une mesure de l’erreur dans le résultat (le résidu), forment une « équation de correction » pour laquelle ce processus est répété. Bien que ces méthodes soient simples à dériver, à mettre en œuvre et à analyser, la convergence n’est garantie que pour une classe limitée de matrices.
DéfinitionEdit
Une méthode itérative est définie par
x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}
et pour un système linéaire donné A x = b {\displaystyle A\mathbf {x} =\mathbf {b} }
avec solution exacte x ∗ {\displaystyle \mathbf {x} ^{*}}
l’erreur par e k := x k – x ∗ , k ≥ 0 . {\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.}
Une méthode itérative est dite linéaire s’il existe une matrice C ∈ R n × n {\displaystyle C\in \mathbb {R} ^{n\times n}}.
telle que e k + 1 = C e k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0}
et cette matrice est appelée la matrice d’itération.Une méthode itérative avec une matrice d’itération donnée C {\displaystyle C}
est dite convergente si ce qui suit tient lim k → ∞ C k = 0 . {\displaystyle \lim _{k\rightarrow \infty }C^{k}=0\,.}
Un théorème important stipule que pour une méthode itérative donnée et sa matrice d’itération C {\displaystyle C}.
elle est convergente si et seulement si son rayon spectral ρ ( C ) {\displaystyle \rho (C)}.
est inférieur à l’unité, c’est-à-dire que ρ ( C ) < 1 . {\displaystyle \rho (C)<1\,.}
Les méthodes itératives de base fonctionnent en divisant la matrice A {\displaystyle A}.
en A = M – N {\displaystyle A=M-N}
et ici la matrice M {\displaystyle M}
devrait être facilement inversible.Les méthodes itératives sont maintenant définies comme M x k + 1 = N x k + b , k ≥ 0 . {\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b\,,\quad k\geq 0\,.}
Il en résulte que la matrice d’itération est donnée par
C = I – M – 1 A = M – 1 N . {\displaystyle C=I-M^{-1}A=M^{-1}N\,.}
ExemplesEdit
Des exemples basiques de méthodes itératives stationnaires utilisent un fractionnement de la matrice A {\displaystyle A}.
telle que A = D + L + U , D := diag ( ( a i i ) i ) {\displaystyle A=D+L+U\,,\quad D:={\text{diag}}((a_{ii})_{i})}
où D {\displaystyle D}
est seulement la partie diagonale de A {\displaystyle A}
, et L {\displaystyle L}
est la partie triangulaire inférieure stricte de A {\displaystyle A}
. Respectivement, U {\displaystyle U}
est la partie triangulaire supérieure stricte de A {\displaystyle A}
.
- Méthode de Richardson : M := 1 ω I ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}.
- Méthode de Jacobi : M := D {\displaystyle M:=D}
- Méthode de Jacobi amortie : M := 1 ω D ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}
- Méthode de Gauss-Seidel : M := D + L {\displaystyle M:=D+L}
- Méthode de surrelaxation successive (SOR) : M := 1 ω D + L ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}.
- Surrelaxation successive symétrique (SSOR) : M := 1 ω ( 2 – ω ) ( D + ω L ) D – 1 ( D + ω U ) ( ω ≠ { 0 , 2 } ) {\displaystyle M:={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \neq \{0,2\})}
Les méthodes itératives stationnaires linéaires sont également appelées méthodes de relaxation.
Méthodes du sous-espace de KrylovModification
Les méthodes du sous-espace de Krylov fonctionnent en formant une base de la séquence des puissances successives de la matrice fois le résidu initial (la séquence de Krylov). Les approximations de la solution sont ensuite formées en minimisant le résidu sur le sous-espace formé. La méthode prototypique de cette classe est la méthode du gradient conjugué (CG) qui suppose que la matrice du système A {\displaystyle A}
est symétrique positive-définie.Pour une matrice A symétrique (et éventuellement indéfinie) {\displaystyle A}
on travaille avec la méthode du résidu minimal (MINRES).Dans le cas de matrices non symétriques, des méthodes telles que la méthode du résidu minimal généralisé (GMRES) et la méthode du gradient biconjugué (BiCG) ont été dérivées.
Convergence des méthodes du sous-espace de KrylovEdit
Puisque ces méthodes forment une base, il est évident que la méthode converge en N itérations, où N est la taille du système. Cependant, en présence d’erreurs d’arrondi, cette affirmation ne tient pas ; de plus, en pratique, N peut être très grand, et le processus itératif atteint une précision suffisante déjà bien avant. L’analyse de ces méthodes est difficile, dépendant d’une fonction compliquée du spectre de l’opérateur.
PréconditionneursEdit
L’opérateur d’approximation qui apparaît dans les méthodes itératives stationnaires peut également être incorporé dans les méthodes de sous-espace de Krylov telles que GMRES (alternativement, les méthodes de Krylov préconditionnées peuvent être considérées comme des accélérations des méthodes itératives stationnaires), où elles deviennent des transformations de l’opérateur original vers un opérateur présumé mieux conditionné. La construction de préconditionneurs est un vaste domaine de recherche.
HistoriqueEdit
Probablement, la première méthode itérative pour résoudre un système linéaire est apparue dans une lettre de Gauss à un de ses étudiants. Il proposait de résoudre un système d’équations 4 par 4 en résolvant de manière répétée la composante dans laquelle le résidu était le plus grand.
La théorie des méthodes itératives stationnaires a été solidement établie avec les travaux de D.M. Young à partir des années 1950. La méthode du gradient conjugué a également été inventée dans les années 1950, avec des développements indépendants par Cornelius Lanczos, Magnus Hestenes et Eduard Stiefel, mais sa nature et son applicabilité étaient mal comprises à l’époque. Ce n’est que dans les années 1970 que l’on s’est rendu compte que les méthodes basées sur la conjugaison fonctionnent très bien pour les équations aux dérivées partielles, notamment de type elliptique.