CHAPITRE 1

RAPPELS SUR QUELQUES MÉTHODES

NUMÉRIQUES

1
 1. Résolution des systèmes d’équations linéaires par les méthodes itératives

1 Résolution des systèmes d’équations linéaires

par les méthodes itératives

Soit un système d’équations linéaires

AX = b (1.1)

où A = (aij ) 2 Mn (R) est une matrice carrée d’ordre n et inversible (det A 6= 0), b
un vecteur de Rn : Les méthodes itératives pour la résolution des systèmes d’équations
linéaires consistent à construire une suites de vecteurs (Xk ); k 2 N et Xk 2 Rn
laquelle converge vers la solution (le vecteur ) X 2 Rn de AX = b. On décompose la
matrice A sous la forme de la soustraction de deux matrices carrées d’ordre n

1.1 Méthode de Jacobi

La méthode de Jacobi repose sur la décomposition de la matrice A du système

(1:1) comme suit
A=D N

où D = Diag(aii) est la matrice diagonale formée des éléments diagonaux de A ; S’ils

sont tous non nuls la matrice D est inversible. La méthode de Jacobi s’écrit alors
(
X0 le vecteur initial
(1.3)
Xk+1 = D 1 N Xk + D 1 b; k 0

La matrice
J = D 1N

2
1. Résolution des systèmes d’équations linéaires par les méthodes itératives

est dite la matrice de Jacobi. On peut formuler la méthode de Jacobi de la manière

équivalente suivante ; sachant que Xk = (X1;k ; :::Xn;k ) 2 Rn
0 1
1 B X
n
C
Xi;k+1 = @ bi aij Xj;k A ; k 0 et i = 1; :::; n
aii j=1
j6=i

Dé…nition 1.2 On dit qu’une matrice A est à diagonale dominante stricte si quelque
soit i = 1; :::; n
X
n
jaii j > jaij j
j=1
j6=i

Proposition 1.2 Si la matrice A du système (1:1) est à diagonale dominante stricte

alors (D 1 N ) < 1 et la méthode de Jacobi converge.

Exemple 1.1 On considère un exemple dans R3 : Soit respectivement la matrice

A d’ordre 3 et le vecteur b dans R3

0 1 0 1
4 1 0 1
B C B C
A=@ 1 4 1 A; b = @ 1 A
0 1 4 1

Le vecteur initial 01
0:5
B C
X0 = @ 0:5 A
0:5
et la précision = 10 2 . On é¤ectue la décomposition de la matrice A
0 1 0 1
4 0 0 0 1 0
B C B C
A = D N =@ 0 4 0 A @ 1 0 1 A
0 0 4 0 1 0
1 1
D = ID
4

3
1. Résolution des systèmes d’équations linéaires par les méthodes itératives

où ID est la matrice identité. La matrice J de Jacobi est alors

01
0 1 0
1B C
J = D 1N = @ 1 0 1 A
4
0 1 0

et 0
1
1
1B C
D 1b = @ 1 A
4
1
La méthode de Jacobi s’écrit alors

X0 le vecteur initial
0 1 0 1
0 1 0 1
1B C 1B C
Xk+1 = @ 1 0 1 A Xk @ 1 A; k 0
4 4
0 1 0 1

Ainsi
0 1 0 1 0 10 1 0 1 0 1
0 1 0 1 0 1 0 0:5 1 1
1B C 1B C 1B CB C 1B C 1B C
k = 0 : X1 = @ 1 0 1 A X0 @ 1 A = @ 1 0 1 A @ 0:5 A @ 1 A= @ 0 A
4 4 4 4 8
0 1 0 1 0 1 0 0:5 1 1

0 1 0 1 0 10 1 1 0 1 0 1
1
0 1 0 1 0 1 0 8
1 4
1B C 1B C 1B CB C 1B C B 5 C
k = 1 : X2 = @ 1 0 1 A X1 @ 1 A = @ 1 0 1 A@ 0 A @ 1 A=@ 16 A
4 4 4 1
4 1
0 1 0 1 0 1 0 8
1 4

0 1 0 1 0 10 1
1 0 1 0 21
1
0 1 0 1 0 1 0 4
1 64
1B C 1B C 1B CB 5 C 1B C B 3 C
k = 2 : X3 = @ 1 0 1 A X2 @ 1 A = @ 1 0 1 A@ 16 A @ 1 A=@ 8 A
4 4 4 1
4 21
0 1 0 1 0 1 0 4
1 64

5
 1. Résolution des systèmes d’équations linéaires par les méthodes itératives

On regroupe les résultats dans le tableau qui suit

k Xk kXk+1 Xk k
T
0 X0 = (0:5; 0:5; 0:5) .
1 1 T
1 X1 = 8
; 0:5; 8
kX1 X0 k = 0:883883 >
T
2 X2 = ( 0:25; 0:3125; 0:25) kX2 X1 k = 0:359035 >
T
3 X3 = ( 0:328125; 0:375; 328125) kX3 X2 k = 0:126938 >
11 53 T
4 X4 = 32
; 128
; 1132
kX4 X3 k = 0:044879 >
181 27 181 T
5 X5 = 512
; 64
; 512 kX5 X4 k = 0:015867 >
91 437 91 T
6 X6 = 256
; 1024
; 256 kX6 X5 k = 0:005609 >
1461 219 1461 T
7 X7 = 4096
; 512
; 4096 kX7 X6 k = 0:001983 >
731 3509 731 T
8 X8 = 2048
; 8192
; 2048 kX8 X7 k =0.000701=0.0701 <10 2
(Tableau 1.1)
Ainsi X8 = ( 0:35693; 0:42834; 0:35693)T est la solution approchée de X par
la méthode itérative de Jacobi avec la précision =10 2 : On calcule le rayon spectral
de la matrice J. Les valeurs propres de la matrice J sont solution de l’équation

det (J ID ) = 0

Donc
1
4
0
1 1 3
4 4
= =0
0
Par conséquent

i (J) = 0 ce qui implique (J) = 0 < 1; la méthode de Jacobi converge.

1.2 Méthode de Gauss-Seidel

La méthode de Gauss-Seidel repose sur la décomposition de la matrice A du
système (1:1) comme suit
A=M N

6
1. Résolution des systèmes d’équations linéaires par les méthodes itératives

où la matrice M est la matrice triangulaire inférieure

0 1
a11 0 ::: 0 ::: 0
B C
B ::: ::: ::: ::: ::: ::: C
B C
M =B
B ai1 ai2 ::: aii ::: 0 C
C
B C
@ ::: ::: ::: ::: ::: ::: A
an1 an2 ::: ani ::: ann

La méthode de Gauss-Seidel s’écrit alors

(
X0 le vecteur initial
(1.4)
Xk+1 = M 1 N Xk + M 1 b; k 0

La matrice
1
G=M N

est dite la matrice de Gauss-Seidel. L’écriture explicite de la méthode de Gauss-Seidel

!
1 X
i 1 X
n
Xi;k+1 = bi aij Xj;k+1 aij Xj;k ; k 0 et i = 1; :::; n:
aii j=1 j=i+1

Proposition 1.3 Si la matrice A du système (1:1) est à diagonale dominante stricte

alors (M 1 N ) < 1 et la méthode de Gauss-Seidel converge.

Exemple 1.2 On reprend le même exemple traité pour la méthode de Jacobi et

on résout le système par la méthode de Gauss-Seidel, les matrices
0 1 0 1
4 0 0 0 1 0
B C B C
M =@ 1 4 0 A et N = @ 0 0 1 A
0 1 4 0 0 0

7
 1. Résolution des systèmes d’équations linéaires par les méthodes itératives

La matrice G de la méthode de Gauss-Seidel pour cet exemple est

0 10 1 0 1
16 0 0 0 1 0 0 16 0
1 1 B CB C 1 B C
G=M N= @ 4 16 0 A @ 0 0 1 A= @ 0 4 16 A
64 64
1 4 16 0 0 0 0 1 4

Le vecteur 0 1
16
1 1 B C
M b= @ 20 A :
64
21
On trouve le tableau suivant

k Xk kXk+1 Xk k
T
0 X0 = (0:5; 0:5; 0:5) .
T
1 5 18:5
1 X1 = ; ; kX1 X0 k = 19:021600 >
8 32 64
T
37 101 357
2 X2 = ; ; kX2 X1 k = 0:295369 >
128 256 1024
T
357 869 2917
3 X3 = ; ; kX3 X2 k = 0:067016 >
1024 2048 8192
T
2917 7013 23397
4 X4 = ; ; kX4 X3 k = 0:008377 >
8192 16384 65536
T
23397 56165 187237
5 X5 = ; ; kX5 X4 k = 0:001047 >
65536 131072 524288
T
187237 449381 1497957 3
6 X6 = ; ; kX6 X5 k = 0:000130 = 0:13 10 <
524288 1048576 4194304
(Tableau 1.2)
T
Ainsi X6 = ( 0:357126; 0:428563; 0:357140) est la solution approchée de X par
la méthode itérative de Gauss-Seidel avec la précision = 10 3 . On peut rajouter la
remarque que X6 est la solution approchée de X avec trois chi¤res signi…catifs exacts
après la virgule.