Méthode de Jacobi

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l'algèbre.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

La méthode de Jacobi, due au mathématicien allemand Karl Jacobi, est une méthode itérative 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

[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. Attention, l'algorithme qui suit n'est valable que si la matrice A est à diagonale strictement dominante sur les lignes.

[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 Ax = b alors x = M − 1Nx + M − 1b .

[modifier] Vecteur erreur

Soit e(k) le vecteur erreur

e(k + 1) = x(k + 1) − x(k) = M − 1N(x(k) − x(k − 1)) = M − 1Ne(k)
On pose B = M − 1N, ce qui donne e(k + 1) = Be(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 − 1b

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) = De(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.

[modifier] Voir aussi