$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Algèbre > Algèbre linéaire > Matrices >
Dictionnaire de mathématiques > Analyse > Analyse numérique >

Méthodes itératives pour résoudre un système linéaire

Soit $A\in\mathcal M_n(\mathbb K)$ inversible. On souhaite résoudre $AX=b$, avec $b\in \mathbb K^n.$ Alors la résolution du système par la méthode de Gauss nécessite de l'ordre de $n^3$ opérations. Les méthodes itératives se proposent de trouver une solution approchée du système en effectuant moins de $O(n^3)$ opérations. Pour cela, on appelle décomposition régulière de $A$ un couple $(M,N)\in GL_n(\mathbb K)\times \mathcal M_n(\mathbb K)$ tel que $A=M-N$ (en pratique, on choisira toujours une telle décomposition de sorte que la matrice $M$ soit facilement inversible). Une méthode itérative basée sur cette décomposition est définie comme une suite récurrente $(X_k)$ de vecteurs de $\mathbb K^n$ telle que $X_0\in\mathbb K^n$ et $MX_{k+1}=N X_k+b.$ Si la suite $(X_k)$ converge vers $X$, alors par passage à la limite on a $MX=NX+b$ et donc $AX=b.$

Théorème : La méthode itérative converge pour tout choix de $X_0$ si et seulement si $\rho(M^{-1}N)<1$ où $\rho(B)$ désigne le rayon spectral de la matrice $B.$

En pratique, ces méthodes itératives fonctionnent très bien si on part d'une matrice hermitienne positive :

Théorème : Soit $A\in H_n^{++}(\mathbb C)$ et $(M,N)$ une décomposition régulière de $A.$ Alors $M^*+N\in H_n(\mathbb C)$ et si $M^*+N\in H_n^{++}(\mathbb C)$, alors $\rho(M^{-1}N)<1.$

On fait alors les choix possibles suivants : on écrit $A=D-E-F$, où $D$ est la partie diagonale de $A,$ $-E$ est sa partie inférieure et $-F$ sa partie supérieure : $$M=\begin{pmatrix} &\\ &&&&-F\\ &&D&&\\ -E&&&&\\ &&&&\\ \end{pmatrix} $$

  • Méthode de Jacobi : $M=D$, $N=E+F.$
  • Méthode de Gauss-Seidel : $M=D-E$, $N=F.$
  • Méthode de relaxation : pour $\omega>0,$ $M=\frac{D}\omega-E$, $N=\frac{1-\omega}{\omega}D+F.$

Dans chacun des cas, la matrice $M$ est triangulaire inférieure (ou même diagonale), et il faut de l'ordre de $O(n^2)$ opérations pour trouver son inverse (ce qu'on ne fait qu'une fois bien sûr). Puis, à chaque étape, pour calculer $X_{k+1}$ connaissant $X_k,$ il faut $O(n^2)$ calculs. Si on calcule moins de $n$ valeurs de la suite $(X_k),$ alors cette méthode est intéressante par rapport à la méthode directe de recherche de l'inverse. Comme la convergence est gouvernée par le théorème du point fixe et est donc géométrique, on peut espérer effectivement obtenir une bonne approximation en calculant moins de $n$ valeurs de la suite.

Consulter aussi
Recherche alphabétique
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Recherche thématique
  • Algèbre
  • Analyse
  • Applications
  • Arithmétique
  • Probabilité et statistiques
  • Géométrie
  • Fondements
  • Histoire
  • Mathématiques discrètes
  • Mathématiques interactives