Méthode de Jacobi

Principe de construction

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.

Algorithme

$$ \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$

Erreur

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)}.$$

Convergence

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

Méthode de Jacobi

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}}$$

Résidu

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}}$$

Test d’arràªt

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$$