Résolution numérique de systèmes d’équations linéaires
Méthode de Jacobi
AN
-
4
année
-
A.U. 2020/2021
Matrice à diagonale strictement dominante
2
2
Définition
Une matrice A est à diagonale strictement dominante si la valeur absolue de
chaque coefficient diagonal ai,i (i ∈ {1, · · · , n}) de A est strictement supérieure à la
somme des valeurs absolues des autres coefficients de A situés à la i ème ligne. En
d’autre terme,
|ai,i| >
n
(cid:88)
j=1
j(cid:54)=i
|ai,j|, ∀i ∈ {1, ..., n}.
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
Exemple: Soit
On a:
3
3
5 2 −1
1 6 −3
2 1
4
A =
|a1,1| > |a1,2| + |a1,3| (car |5| > |2| + | − 1|)
|a2,2| > |a2,1| + |a2,3| (car |6| > |1| + | − 3|)
|a3,3| > |a3,1| + |a3,2| (car |4| > |2| + |1|)
⇒ A est une matrice à diagonale strictement dominante.
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
Les méthodes itératives
4
4
Les méthodes itératives pour la résolution d’un système de Cramer AX = b de n
équations à n inconnus consistent à construire une suite (cid:0)X
solution du système. Plus précisément, on prouve que A peut être écrite sous la
forme A = M − N , avec M ∈ Mn(R) inversible et N ∈ Mn(R). Les suites générant
les deux méthodes sont définies par
(k)(cid:1)
k≥0 qui converge vers la
(cid:40)
X (0) ∈ Mn,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.
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
0
. . .
. . .
· · ·
. . .
. . .
0
0
0
0
...
−a2,1
−
· · ·
. . .
. . .
· · ·
. . .
A =
a1,1
0
...
0
(cid:124)
· · ·
0
an,n
−an,1
· · · −an,n−1 0
· · ·
(cid:123)(cid:122)
D
(cid:125)
(cid:124)
(cid:123)(cid:122)
E
0
0
0
−
...
...
0
(cid:125)
(cid:124)
0 −a1,2
· · · −a1,n
. . .
. . .
. . . −an−1,n
...
0
· · ·
(cid:123)(cid:122)
F
(cid:125)
La Méthode de Jacobi
5
5
La méthode itérative de Jacobi pour résoudre (S) : AX = b, consiste en premier lieu
à décomposer A sous la forme:
où D est une matrice diagonale, E est une matrice triangulaire inférieure et F est
une matrice triangulaire supérieure.
A = D − E − F,
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
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:
où D est une matrice diagonale, E est une matrice triangulaire inférieure et F est
une matrice triangulaire supérieure.
A = D − E − F,
A =
a1,1
0
...
0
(cid:124)
0
. . .
. . .
· · ·
. . .
. . .
0
0
0
· · ·
0
an,n
(cid:123)(cid:122)
D
−
0
−a2,1
...
−an,1
(cid:125)
(cid:124)
· · ·
. . .
. . .
· · ·
. . .
0
0
0
0 −a1,2
...
Publicité
. . .
...
0
· · ·
−
...
· · · −a1,n
. . .
. . . −an−1,n
· · ·
(cid:123)(cid:122)
F
0
· · · −an,n−1 0
(cid:123)(cid:122)
E
(cid:125)
(cid:124)
5
5
(cid:125)
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
Considérons, par exemple, le cas où n = 3. On a
A =
=
(cid:124)
a1,1 a1,2 a1,3
a2,1 a2,2 a2,3
a3,1 a3,2 a3,3
0
0
a3,3
a1,1
0
0
0
a2,2
0
(cid:123)(cid:122)
D
−
0
−a2,1
0
0
−a3,1 −a3,2 0
(cid:123)(cid:122)
E
(cid:125)
(cid:124)
0
0
−
0
0
(cid:125)
(cid:124)
0 −a1,2 −a1,3
−a2,3
0
0
0
(cid:123)(cid:122)
F
6
6
(cid:125)
Le système (S) : AX = b est équivalent alors à
DX − (E + F )X = b
⇐⇒ DX = (E + F )X + b
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
Remarque
Si la suite (Xk)k≥0 est convergente, alors
avec X l’unique solution du système (S).
lim
k→+∞
X (k) = X,
7
7
, vérifiant
Soit (X (k))k≥0 la suite de vecteurs dans R3 définie par X (k) =
x(k)
1
x(k)
2
x(k)
3
D
(cid:124)(cid:123)(cid:122)(cid:125)
M
X (k+1) = (E + F )
(cid:124) (cid:123)(cid:122) (cid:125)
N
X (k) + b
Si A est à diagonale strictement dominante, alors les coefficients diagonaux de A
sont non nuls. Par conséquent, M est inversible.
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
Soit (X (k))k≥0 la suite de vecteurs dans R3 définie par X (k) =
7
7
, vérifiant
x(k)
1
x(k)
2
x(k)
3
D
(cid:124)(cid:123)(cid:122)(cid:125)
M
X (k+1) = (E + F )
(cid:124) (cid:123)(cid:122) (cid:125)
N
X (k) + b
Si A est à diagonale strictement dominante, alors les coefficients diagonaux de A
sont non nuls. Par conséquent, M est inversible.
Remarque
Si la suite (Xk)k≥0 est convergente, alors
avec X l’unique solution du système (S).
lim
k→+∞
X (k) = X,
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
8
8
Les composantes du vecteur X (k+1) s’écrivent en fonction des composantes du
vecteur X (k) comme suit:
x(k+1)
1
x(k+1)
2
x(k+1)
3
0
−a1,2 −a1,3
=
−a2,1
0
−a2,3
−a3,1 −a3,2
0
x(k)
1
x(k)
2
x(k)
3
+
b1
b2
b3
a1,1
0
Publicité
0
0
0
a2,2
0
0
a3,3
Ainsi, on en déduit que
a1,1x(k+1)
1
a2,1x(k)
a3,1x(k)
+ a1,2x(k)
1 + a2,2x(k+1)
1 + a3,2x(k)
2 + a1,3x(k)
+ a2,3x(k)
2 + a3,3x(k+1)
3 = b1
3 = b2
= b3
3
2
⇐⇒
x(k+1)
1
x(k+1)
2
x(k+1)
3
3
2 −a1,3x(k)
= b1−a1,2x(k)
a1,1
= b2−a2,1x(k)
1 −a2,3x(k)
a2,2
1 −a3,2x(k)
= b3−a3,1x(k)
a3,3
3
2
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
t
9
9
Dans Rn, les composantes x(k+1)
X (k+1) s’écrivent en fonction des composantes x(k)
comme suit:
i
(i ∈ {0, 1, · · · , n}) du vecteur
i du vecteur X (k)
x(k+1)
i
=
bi −
1
aii
n
(cid:88)
j=1,j(cid:54)=i
aijx(k)
j
, ∀i ∈ {1, · · · , n}
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
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
Théorème
X (0) ∈ Mn,1(R).
Remarque
On peut considérer le critère d’arrêt suivant pour la méthode de Jacobi:
||AX (k) − b|| ≤ ε, avec ε très petit .
On dit que ε est une tolérance.
Convergence de la méthode de Jacobi
Question: Existe-il une condition sur la matrice A assurant la convergence de la
suite (X (k))k≥0 est convergente?
10
10
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
Remarque
On peut considérer le critère d’arrêt suivant pour la méthode de Jacobi:
||AX (k) − b|| ≤ ε, avec ε très petit .
On dit que ε est une tolérance.
10
10
Convergence de la méthode de Jacobi
Question: Existe-il une condition sur la matrice A assurant la convergence de la
suite (X (k))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) ∈ Mn,1(R).
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
10
10
Convergence de la méthode de Jacobi
Question: Existe-il une condition sur la matrice A assurant la convergence de la
suite (X (k))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) ∈ Mn,1(R).
Remarque
On peut considérer le critère d’arrêt suivant pour la méthode de Jacobi:
||AX (k) − b|| ≤ ε, avec ε très petit .
On dit que ε est une tolérance.
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
Étude d’un exemple
On considère un système d’équations linéaires (S), telle que;
(S) ⇔ AX = b
11
11
avec :
5 2 −1
A =
1 6 −3
2 1
4
, X =
x1
x2
x3
et b =
6
4
7
1 Montrer qu’il existe une unique solution de (S) dans R3.
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.
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
12
12
• Existence d’une unique solution de (S) dans R3:
On a det(A) = 126 (cid:54)= 0 ⇒ ∃! X ∈ R3/ AX = b.
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
13
13
• Etude de la convergence de la méthode de Jacobi pour la résolution de (S):
On a:
|a1,1| > |a1,2| + |a1,3| (car |5| > |2| + | − 1|)
|a2,2| > |a2,1| + |a2,3| (car |6| > |1| + | − 3|)
|a3,3| > |a3,1| + |a3,2| (car |4| > |2| + |1|)
⇒ A est une matrice à diagonale strictement dominante.
⇒ La méthode de Jacobi est convergente.
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
x(k+1)
1
x(k+1)
2
x(k+1)
3
⇒
= b1−a1,2x(k)
2 −a1,3x(k)
3
= 6−2x(k)
2 +x(k)
3
= b2−a2,1x(k)
1 −a2,3x(k)
3
= 4−x(k)
1 +3x(k)
3
= b3−a3,1x(k)
1 −a3,2x(k)
2
= 7−2x(k)
1 −x(k)
2
a1,1
a2,2
a3,3
5
6
4
14
14
+
Publicité
6
4
7
• Schéma itératif associé à (S) avec la méthode de Jacobi:
5 0 0
0 6 0
0 0 4
x(k+1)
1
x(k+1)
2
x(k+1)
3
=
0 −2 1
−1
0
3
−2 −1 0
x(k)
1
x(k)
2
x(k)
3
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
14
14
+
6
4
7
• Schéma itératif associé à (S) avec la méthode de Jacobi:
5 0 0
0 6 0
0 0 4
x(k+1)
1
x(k+1)
2
x(k+1)
3
⇒
x(k+1)
1
x(k+1)
2
x(k+1)
3
=
0 −2 1
−1
0
3
−2 −1 0
x(k)
1
x(k)
2
x(k)
3
3
= b1−a1,2x(k)
2 −a1,3x(k)
a1,1
1 −a2,3x(k)
= b2−a2,1x(k)
a2,2
1 −a3,2x(k)
= b3−a3,1x(k)
a3,3
2
3
2 +x(k)
5
3
1 +3x(k)
3
= 6−2x(k)
= 4−x(k)
= 7−2x(k)
6
1 −x(k)
4
2
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
(cid:73) Itération 1 : X (1) =
(cid:73) Itération 3 : X (3) =
(cid:73) Itération 2 : X (2) =
(cid:73) Itération 4 : X (4) =
6/5
2/3
7/4
1, 2833
1, 3417
0, 9833
0, 86
0, 9444
0.7729
0, 9768
0, 9098
1, 0839
15
15
• Application de la méthode de Jacobi avec 4 itérations:
0
0
0
Considérons par exemple un vecteur initial X (0) =
.
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
(cid:73) Itération 2 : X (2) =
(cid:73) Itération 4 : X (4) =
1, 2833
1, 3417
0, 9833
(cid:73) Itération 3 : X (3) =
Publicité
0, 86
0, 9444
0.7729
0, 9768
0, 9098
1, 0839
15
15
• Application de la méthode de Jacobi avec 4 itérations:
0
0
0
Considérons par exemple un vecteur initial X (0) =
.
(cid:73) Itération 1 : X (1) =
6/5
2/3
7/4
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
(cid:73) Itération 3 : X (3) =
(cid:73) Itération 4 : X (4) =
0, 86
0, 9444
0.7729
0, 9768
0, 9098
1, 0839
15
15
• Application de la méthode de Jacobi avec 4 itérations:
0
0
0
Considérons par exemple un vecteur initial X (0) =
.
(cid:73) Itération 1 : X (1) =
(cid:73) Itération 2 : X (2) =
6/5
2/3
7/4
1, 2833
1, 3417
0, 9833
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
(cid:73) Itération 4 : X (4) =
0, 9768
0, 9098
1, 0839
15
15
• Application de la méthode de Jacobi avec 4 itérations:
0
0
0
Considérons par exemple un vecteur initial X (0) =
.
(cid:73) Itération 1 : X (1) =
(cid:73) Itération 2 : X (2) =
6/5
2/3
7/4
1, 2833
1, 3417
0, 9833
(cid:73) Itération 3 : X (3) =
0, 86
0, 9444
0.7729
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN
15
15
• Application de la méthode de Jacobi avec 4 itérations:
0
0
0
Considérons par exemple un vecteur initial X (0) =
.
(cid:73) Itération 1 : X (1) =
(cid:73) Itération 2 : X (2) =
6/5
2/3
7/4
1, 2833
1, 3417
0, 9833
(cid:73) Itération 3 : X (3) =
(cid:73) Itération 4 : X (4) =
0, 86
0, 9444
0.7729
0, 9768
0, 9098
1, 0839
@UP-Maths
Résolution numérique des systèmes d’équations linéaires
AN