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.

Principe de constructionModifier

On cherche à construire, pour x(0) donné, la suite x(k + 1) = F(x(k)) avec  .

A=MNM est une matrice inversible.

 

F est une fonction affine. La matrice B = M–1N est alors appelée matrice de Jacobi.

Cependant, 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).

AlgorithmeModifier

 

Erreur et convergenceModifier

Si x est solution de Ax=b alors il vérifie

  .

Soit e(k) le vecteur erreur

 

ce qui donne

 .

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 x(0) pour les systèmes linéaires dont la matrice est à diagonale strictement dominante.

Méthode de JacobiModifier

On décompose la matrice A de la façon suivante : A=DEF 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=DE et N=F).

 
  avec


pour la ligne i de D–1(E+F) :  

 

Vecteur résiduModifier

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

 .

Test d'arrêtModifier

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 ε :

 

CoûtModifier

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 aussiModifier

Articles connexesModifier

Liens externesModifier