Méthode de Jacobi

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche à compléter concernant l'algèbre, vous pouvez partager vos connaissances en le modifiant.

La méthode de Jacobi est une méthode iterative de résolution d'un système matriciel 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.

Sommaire

1 Principe de construction
2 Méthode de Jacobi
- 2.1 Vecteur résidu
- 2.2 Test d'arrêt
3 Conclusion
4 Voir aussi

[modifier] Principe de construction

On cherche à construire l'algorithme pour $x (0)$ donné, la suite $x (k + 1) = F (x (k))$ avec $k \in \N$ .

$A = M - N$ où M est une matrice inversible. $\begin{matrix} Ax=b \Leftrightarrow Mx=Nx+b \Leftrightarrow & x &=& M^{-1}Nx+M^{-1}b \\ & &=& F(x)\end{matrix}$
où F est une fonction affine.

[modifier] Algorithme

$\left\{ \begin{array}{l} x^{(0)} \; \mbox{connu}\\ x^{(k+1)} = M^{-1}Nx^{(k)}+M^{-1}b \end{array} \right.$
Si x est solution de $A x = b$ alors $x = M - 1 N x + M - 1 b$ .

[modifier] Vecteur 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 N e (k)$
On pose $B = M - 1 N$ , ce qui donne $e (k + 1) = B e (k) = B (k + 1) e (0)$ .

[modifier] Convergence

L'algorithme converge si $\lim_{k \to \infty} \| e^{(k)} \| = 0 \Longleftrightarrow \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 (plus grande valeur propre en module) de B soit strictement inférieur à 1.
Théorème : La méthode converge quel que soit $x (0)$ pour les systèmes linéaires dont la matrice est à diagonale strictement dominante.

[modifier] 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 et -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$ $x^{(k+1)}_i=\cdots x^{(k)}_i+\frac{b_i}{a_{ii}}$ avec
pour la ligne i de $D - 1 (E + F)$ : $-\left(\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}}\right)$

$x^{(k+1)}_i= -\frac{1}{a_{ii}} \sum_{j=1 \atop j \ne i}^n a_{ij}x^{(k)}_j + \frac{b_i}{a_{ii}}$

[modifier] Vecteur résidu

Soit $r (k) = D e (k)$ le vecteur résidu. On peut écrire $x_i^{(k+1)}=\frac{r_i^{(k)}}{a_{i,i}} + x_i^{(k)}$ avec $r_i^{(k)}$ que l'on calcule de la manière suivante : $r_l^{(k+1)}=-\sum_{j=1 \atop j \ne l}^n a_{l,j} \frac{r_l^{(k)}}{a_{j,j}}$ .

[modifier] 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 $ε$ : $\frac{\|r^{(k)} \|}{\|b\|} < \varepsilon$

[modifier] Conclusion

Cette méthode a un coût de l'ordre de 3n²+2n par itération, elle est très facilement parallélisable contrairement à la méthode de Gauss-Seidel, mais qui converge plus vite.