Knowledge base dedicated to Linux and applied mathematics.
Accueil > Mathématiques > Résolution de systèmes linéaires > Méthode de Jacobi
Toutes les versions de cet article : <English> <français>
Nous allons étudier une méthode itérative de résolution de système linéaire : la méthode de Jacobi. L’objectif est de construire une suite vectorielle convergente vers la solution du système linéaire.
La méthode de Jacobi est une méthode itérative de résolution de système linéaire de la forme
$$Ax=b$$
Pour cela, on utilise une suite $x^{(k)}$ qui converge vers un point fixe $x$, solution du système d’équations linéaires.
On cherche à construire l’algorithme pour $x^{(0)}$ donné, la suite $x^{(k+1)}=F(x^{(k)})$ avec $k \in \mathbf{N}$.
$A=M-N$ o๠$M$ est une matrice inversible.
$$
\begin{array}{cccc}
Ax=b \Leftrightarrow
Mx=Nx+b \Leftrightarrow & x &=& M^{-1}Nx+M^{-1}b \\
& &=& F(x)
\end{array} $$
o๠$F$ est une fonction affine.
$$ \left\{ \begin{array}{cc} x^{(0)} \textrm{ donne}& ,\\ x^{(k+1)} = M^{-1}Nx^{(k)}+M^{-1}b& \textrm{sinon}. \end{array} \right. $$
Si $x$ est solution de $Ax=b$ alors $x = M^{-1}Nx+M^{-1}b$
Soit $e^{(k)}$ le vecteur erreur
$e^{(k+1)}=x^{(k+1)}-x^{(k)}=M^{-1}N(x^{(k)}-x^{(k-1)})=M^{-1}Ne^{(k)}$
On pose $B = M^{-1}N$, ce qui donne
$$e^{(k+1)}=Be^{(k)}=B^{(k+1)}e^{(0)}.$$
L’algorithme converge si $\lim_{k \to \infty} \| e^{(k)} \| = 0 \Leftrightarrow \lim_{k \to \infty} \| B^k \| = 0$ (matrice nulle).
Théorème : Une condition nécessaire et suffisante pour que $\lim_{k \to \infty} \| B^k \| = 0$ est que le rayon spectral de $B$ vérifie
$$\rho(B)<1,$$
on rappelle que $\rho(B) = \max_{i =
1,\ldots,n} |\lambda_i|$ o๠$ \lambda_1,\ldots,\lambda_n$ sont les valeurs propres de
$B$.
Théorème : si $A$ est à diagonale strictement dominante
$$\left | a_{ii} \right | > \sum_{i \ne j} {\left | a_{ij} \right |},\forall i=1,\ldots,n$$
alors pour tout $x_0$ la méthode de Jacobi converge vers la solution $x$ du système $Ax=b.$
On décompose la matrice $A$ de la façon suivante :
$$A=D-E-F$$
avec
– $D$ la diagonale
– $-E$ la partie en dessous de la diagonale
– $-F$ la partie au dessus.
Dans la méthode de Jacobi, on choisit $M = D$ et $N = E+F$ (dans la méthode de Gauss-Seidel, $M = D-E$ et $N = F$).
$$x^{(k+1)}=D^{-1}(E+F) x^{(k)}+D^{-1}b$$
avec pour la ligne $i$ de $D^{-1}(E+F)$ : $-(\frac{a_{i,1}}{a_{i,i}},\cdots, \frac{a_{i,i-1}}{a_{i,i}},0,\frac{a_{i,i+1}}{a_{i,i}},\cdots, \frac{a_{i,n}}{a_{i,i}})$
on a alors :
$$x^{(k+1)}_i= -\frac{1}{a_{ii}} \sum_{j=1,j \ne i}^n a_{ij}x^{(k)}_j + \frac{b_i}{a_{ii}}$$
Soit $r^{(k)}=b-Ax^{(k)}$ le vecteur résidu. On peut écrire $x_i^{(k+1)}=\frac{r_i^{(k)}}{a_{ii}} + x_i^{(k)}$ avec $r_i^{(k)}$ que l’on calcule de la manière suivante :
$$r_i^{(k+1)}=-\sum_{j=1,j \ne i}^n a_{ij} \frac{r_i^{(k)}}{a_{jj}}$$
Pour le test d’arràªt, on utilise le vecteur résidu, ce qui donne, pour une précision donnée $\epsilon$ :
$$\frac{\|r^{(k)} \|}{\|b\|}=\frac{\|b-Ax^{(k)} \|}{\|b\|} < \epsilon$$