Méthode de Jacobi

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 qui converge vers un point fixe x, solution du système d'équations linéaires.

Principe de construction[modifier | modifier le code]

On cherche à construire, pour donné, la suite avec .

A=M-NM est une matrice inversible.


où F est une fonction affine. est alors appelée matrice de Jacobi.

Attention, l'algorithme qui suit n'est valable que si la matrice A est à diagonale strictement dominante sur les lignes (si la matrice M est diagonale, sinon se référer à la section convergence)

Algorithme[modifier | modifier le code]


Si x est solution de Ax=b alors .

Vecteur erreur[modifier | modifier le code]

Soit le vecteur erreur

On pose , ce qui donne .

Convergence[modifier | modifier le code]

L'algorithme converge si (c-à-d. Bk tend vers la matrice nulle).

Théorème — Une condition nécessaire et suffisante pour que 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 pour les systèmes linéaires dont la matrice est à diagonale strictement dominante.

Méthode de Jacobi[modifier | modifier le code]

On décompose la matrice A de la façon suivante : A=D-E-F avec D la matrice diagonale de A, -E la matrice triangulaire inférieure de A de diagonale nulle et -F la matrice triangulaire supérieure de diagonale nulle. 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).

avec
pour la ligne i de  :


Vecteur résidu[modifier | modifier le code]

Soit le vecteur résidu. On peut écrire avec que l'on calcule de la manière suivante :

.

Test d'arrêt[modifier | modifier le code]

Pour le test d'arrêt, on utilise l'erreur relative sur le vecteur résidu, ce qui donne, pour une précision donnée  :

Conclusion[modifier | modifier le code]

Cette méthode a un coût de l'ordre de 3n2+2n par itération. Elle converge moins vite que la méthode de Gauss-Seidel, mais est très facilement parallélisable.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]