Méthode de Jacobi

Les méthodes itératives

Les méthodes itératives pour la résolution d'un système de Cramer AX = b de n équations à n inconnus
(k )
consistent à construire une suite ( X ) k ≥ 0 qui converge vers la solution du système. Plus
précisément, on prouve que A peut être écrite sous la forme A = M − N , avec M ∈ ℳ n ( R) inversible et

N ∈ ℳ n ( R) . Les suites générant les deux méthodes sont définies par

⎧⎪ (0)
⎪⎪ X ∈ ℳ n , 1 ( \R) ,
⎪⎪
⎨⎪
⎪⎪ M X (k + 1) = N X (k ) + b
⎪⎪
⎩

Les suites ainsi considérées, si elles sont covergentes, convergent nécessairement vers la solution du
système.

La Méthode de Jacobi

La méthode itérative de Jacobi pour résoudre ( S) :AX = b , consiste en premier lieu à décomposer A 
sous la forme: A = D − E − F , o\`u D est une matrice diagonale, E est une matrice triangulaire
inférieure et F est une matrice triangulaire supérieure.

⎛⎜ a1, 1 0 ⋯ 0 ⎞⎟ ⎛⎜ 0 ⋯ ⋯ 0 ⎞⎟ ⎛⎜ 0 −a1, 2 ⋯ −a1, n ⎞⎟

⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟
⎜⎜ 0 ⋱ ⋱ 0 ⎟⎟ ⎜⎜ −a2, 1 ⋱ 0 ⎟⎟ ⎜⎜ ⋮ ⋱ ⋱ ⋮ ⎟⎟
A = ⎜⎜⎜
⎜ ⎟⎟ − ⎜⎜ ⎟⎟ − ⎜⎜ ⎟⎟ 
⎜⎜ ⋮ ⋱ ⋱ 0
⎟⎟ ⎜⎜
⎟⎟ ⎜⎜ ⋮ ⋱ ⋱ 0
⎟⎟ ⎜⎜ ⋮
⎟⎟ ⎜⎜ ⋱ − a n − 1, n ⎟⎟⎟
⎟
⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟
⎝ 0 ⋯ 0 a n, n − a n, 1 ⋯ − a n , n − 1 0 0 ⋯ ⋯ 0
⎠ ⎝⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎠ ⎝⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎠
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
D E F

Considérons, par exemple, le cas où n = 3. On a

 ⎛⎜ a1, 1 a1, 2 a1, 3 ⎞⎟
⎜⎜ ⎟⎟
A = ⎜⎜⎜⎜ a2, 1 a2, 2 a2, 3 ⎟⎟⎟⎟
⎜⎜ ⎟⎟
⎝ a 3, 1 a 3, 2 a 3, 3 ⎠
 
⎛⎜ a1, 1 0 0 ⎞⎟ ⎛⎜ 0 0 0 ⎞
⎟ ⎛
⎜ 0 −a1, 2 −a1, 3 ⎞⎟
⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟
= ⎜⎜ 0 a2, 2 0 ⎟⎟ − ⎜⎜⎜ −a2, 1 0 0 ⎟⎟⎟ − ⎜⎜⎜ 0 0 −a2, 3 ⎟⎟⎟
⎜ ⎟
⎜⎜ ⎟
⎜ 0 0 a ⎟⎟ ⎜⎜ −a3, 1 −a3, 2 0 ⎟⎟ ⎜⎜ 0 0 0
⎟⎟
⎝⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎠ ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎠
3, 3 ⎝ ⎠ ⎝
D E F

Le système ( S) :AX = b est équivalent alors à

DX − ( E + F) X = b ⇔ DX = ( E + F) X + b 

⎛⎜ X k ⎞⎟
⎜⎜ 1 ⎟⎟
⎜⎜ ⎟
(k ) (k )
⎜⎜ k ⎟⎟⎟
Soit ( X ) k ≥ 0 la suite de vecteurs dans R 3 définie par X = ⎜⎜⎜ X 2 ⎟⎟⎟ , vérifiant
⎜⎜ ⎟⎟
⎜⎜ ⎟
⎜⎜ k ⎟⎟⎟
⎜ X3 ⎟
⎝ ⎠
(k + 1)
D X = ( E + F) X (k ) + b 
 ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
M N

Si A est à diagonale strictement dominante, alors les coefficients diagonaux de A sont non nuls. Par
conséquent, M
 est inversible.

(k + 1)
Dans ce cas, X = M −1NX (k ) + M −1b . 

Remarque:

Si la suite ( X ) est convergente, alors

k k ≥0

(k )
 lim X =X,
k→ + ∞

avec X l'unique solution du système ( S) .

(k + 1) (k )
Les composantes du vecteur X s'écrivent en fonction des composantes du vecteur X comme
suit:
 ⎛⎜ a ⎞⎟ ⎛⎜⎜ x (k + 1) ⎞⎟ ⎛ 0 ⎞⎟ ⎛⎜⎜ x (k ) ⎞⎟ ⎛ b ⎞
⎜⎜ 1, 1 0 0 ⎟⎟ ⎜⎜ 1 ⎟⎟ ⎜⎜
⎟⎟ ⎜⎜
−a
1, 2
−a
1, 3 ⎟⎟ ⎜⎜ 1 ⎟⎟ ⎜⎜ 1 ⎟⎟
⎟⎟ ⎜⎜ ⎟⎟
⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟
⎟⎟ ⎜⎜ (k + 1) ⎟⎟ ⎜⎜ (k )
⎜⎜⎜ 0 a 2, 2 0 ⎟⎟ ⎜⎜ x ⎟⎟ = ⎜⎜ − a 0 −a ⎟⎟ ⎜⎜ x ⎟⎟ + ⎜⎜ b ⎟⎟⎟ 
⎜
⎜⎜ ⎟⎟ ⎜⎜ 2 ⎟⎟ ⎜⎜ 2, 1 2, 3 ⎟⎟ ⎜⎜ 2 ⎟⎟ ⎜ 2 ⎟⎟
⎜
⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟
⎜⎜ 0 0 a ⎟⎟ ⎜⎜ (k + 1) ⎟⎟ ⎜⎜ − a −a 0 ⎟⎟ ⎜⎜ (k ) ⎟⎟ ⎜⎜ b ⎟⎟⎟
3, 3 x ⎟⎟ ⎜ 3, 1 3, 2 x ⎟⎟ ⎜ 3 ⎟
⎝ ⎠ ⎜⎝ 3 ⎠ ⎝ ⎠ ⎜⎝ 3 ⎠ ⎝ ⎠

Ainsi, on en déduit que

⎧⎪ ⎧⎪
⎪⎪ ⎪⎪ b − a x (k ) − a x (k )
⎪⎪ x (k + 1) = 1 1, 2 2 1, 3 3
⎪⎪ ⎪⎪
⎪⎪
a
⎪⎪ ⎪⎪ 1
⎪⎪ ⎪⎪
⎪⎪ a x (k + 1) + a x (k ) + a x (k ) = b ⎪⎪ 1, 1
⎪⎪ 1, 1 1 1, 2 2 1, 3 3 1 ⎪
b − a x (k ) − a x (k )
⎪⎪ ⎪
⎪⎪
⎪⎪ ⎪⎪
⎪⎨ a x (k ) + a x (k + 1) + a x (k ) = b ⇔ ⎪⎨ (k + 1) 2 2, 1 1 2, 3 3
⎪⎪ 2, 1 1 2, 2 2 2, 3 3 2 ⎪⎪ x 2 =
⎪⎪ ⎪⎪ a
⎪⎪ ⎪⎪ 2, 2
⎪⎪ a x (k ) + a x (k ) + a x (k + 1) = b ⎪⎪
⎪⎪ 3, 1 1 3, 2 2 3, 3 3 3 (k ) (k )
⎪⎪ (k + 1) b 3 − a 3, 1x 1 − a 3, 2x 2
⎪
⎪⎪
⎪⎪
⎪⎪
⎪⎪ ⎪⎪ x =
a
⎪⎪ ⎪⎪ 3
⎪
⎪⎪ ⎪⎪ 3, 3
⎩ ⎩

n (k + 1)
Dans R , les composantes x
 (i ∈ {0, 1, ⋯ , n} ) du vecteur X (k + 1) s'écrivent en fonction des
i
(k ) (k )
composantes x du vecteur X comme suit:
i

1 ⎛⎜ n ⎞⎟
x i( k + 1 ) =
aii
⎜⎜ b −
⎜ i ∑ ij j ⎟ a x ( k ) ⎟⎟ ,∀ i ∈ { 1 ,⋯, n }
⎝ j = 1, j ≠ i ⎠

Convergence de la méthode de Jacobi

(k )
Question: Existe-il une condition sur la matrice A assurant la convergence de la suite ( X ) k ≥ 0 est
convergente?

Théorème:

Soit A une matrice à diagonale strictement dominante alors la méthode de Jacobi appliquée au système
( S) :AX = b est convergente vers la solution de ( S) pour tout X (0) ∈ ℳ n , 1 ( R) .

Remarque:

On peut considérer le critère d’arrêt suivant pour la méthode de Jacobi:

(k )
| |AX − b| | ≤ ε avec ε très petit.
On dit que ε est une tolérance.

Étude d'un exemple

On considère un système d'équations linéaires ( S) , telle que ( S) ⇔ AX = b avec

⎛⎜ X ⎞⎟
⎛⎜ 5 2 − 1 ⎞⎟ ⎜⎜ 1 ⎟⎟ ⎛⎜ 6 ⎞⎟
⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟
A = ⎜⎜ 1 6 − 3 ⎟⎟ , X = ⎜⎜ X 2 ⎟⎟ et b = ⎜⎜⎜ 4 ⎟⎟⎟ 
⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜ ⎟
⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟
2 1 4 2
⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟
⎜⎜ X ⎟⎟
⎝ ⎠ ⎝ ⎠
⎝ 3⎠

1- Montrer qu’il existe une unique solution de ( S) dans R 3.

2- Etudier la convergence de la méthode de Jacobi pour la résolution de ( S) .

3- Donner le schéma itératif de la méthode de Jacobi associé à ( S) .

4- Calculer les quatres premiers itérés par la méthode de Jacobi.

1- Existence d'une unique solution de ( S) dans R 3:

On a det( A) = 126 ≠ 0⇒ ∃ ! X ∈ R 3/ AX = b .

2- Etude de la convergence de la méthode de Jacobi pour la résolution de ( S) :

On a:
⎧⎪
⎪⎪ |a | > |a | + |a | ( car |5| > |2| + | − 1| )
⎪⎪ 1, 1 1, 2 1, 3
⎪⎪
⎨⎪ |a 2, 2| > |a 2, 1| + |a 2, 3| ( car |6| > |1| + | − 3| ) 
⎪⎪
⎪⎪
⎪⎪
⎪⎪⎪ |a 3, 3| > |a 3, 1| + |a 3, 2| car |4| > |2| + |1| )
⎪⎩

⇒ A est une matrice à diagonale strictement dominante.

⇒ La méthode de Jacobi est convergente.

3- Schéma itératif associé à ( S) avec la méthode de Jacobi:

4- Application de la méthode de Jacobi avec 4 itérations:

⎛⎜ 0 ⎞⎟
⎜⎜ ⎟⎟
(0) ⎜ ⎟
Considérons par exemple un vecteur initial X = ⎜⎜⎜⎜ 0 ⎟⎟⎟⎟ .
⎜⎜ ⎟⎟
⎜0⎟
⎝ ⎠
⎛⎜ 6/ 5 ⎞⎟⎟
⎜⎜ ⎟⎟
(1) ⎜
• Itération 1 : X = ⎜⎜⎜⎜ 2/ 3 ⎟⎟⎟⎟ 
⎜⎜ ⎟⎟
⎜ 7/ 4 ⎟
⎝ ⎠
⎛⎜ 1, 2833 ⎞⎟⎟
⎜⎜ ⎟⎟
(2) ⎜
• Itération 2 : X = ⎜⎜⎜⎜ 1, 3417 ⎟⎟⎟⎟ 
⎜⎜ ⎟⎟
⎜ 0, 9833 ⎟
⎝ ⎠
⎛⎜ 0, 86 ⎞⎟⎟
⎜⎜ ⎟⎟
• Itération 3 : X (3) = ⎜⎜⎜⎜
⎜
0, 9444 ⎟⎟⎟⎟ 
⎜⎜ ⎟⎟
⎜ 0.7729 ⎟
⎝ ⎠
⎛⎜ 0, 9768 ⎞⎟⎟
⎜⎜ ⎟⎟
(4)
⎜
• Itération 4 : X = ⎜⎜⎜⎜ 0, 9098 ⎟⎟⎟⎟ 
⎜⎜ ⎟⎟
⎜ 1, 0839 ⎟
⎝ ⎠