U.M.B.

B - Faculté - D’Hydrocarbures - 2eme Année - 2022/2023

Resolution d0 Equations Lineaires : AX = b

Responsable : Khodja

I. Préliminaire
On s’intéresse à la résolution d’équations linéaires :
8
>
> a11 x1 + a12 x2 + : : : a1n xn = b1
>
>
>
> a21 x1 + a22 x2 + : : : a2n xn = b2
>
>
>
> a31 x1 + a32 x2 + : : : a3n xn = b3
>
>
>
> :
<
:
(SL) où aij 2 R; bj 2 R; i; j = 1; :::; n:
>
> :
>
>
>
> :
>
>
>
> :
>
>
>
> :
:
an1 x1 + an2 x2 + : : : ann xn = bn

On dit que le système (SL) est un système de n équations à n inconnus.

L’écriture matricielle est la plus adaptée pour les méthodes numériques. On peut donc écrire le système
(SL) sous forme matricielle :
(SL) , AX = b

où 0 1 1 0 0 1
a11 a12 : : : : : a1n x1 b1
B a21 a22 : : : : : a2n C B x2 C B b2 C
B C B C B C
B a31 C B:C B:C
B C B C B C
B : C B:C B:C
B
A=B C; X=B C b=B C
: C B : C; B:C
B C B C B C
B : C B:C B:C
B C B C B C
@ : A @:A @:A
an1 an2 : : : : : ann xn bn
A est une matrice d’ordre (n; n), b est le vecteur colonne (n; 1) et X est le vecteur inconnu:
II. Conditions nécessaires et su¢ santes d’existance de la solution :
Le système AX = b a une solution unique si et seulement si det A 6= 0.
Si le det A = 0 alors
b 2 Im (A), le système a une in…nité de solutions.
b 2 Rn Im (A), le système n’a pas de solutions.

III. Méthodes de résolution

Pour la résolution d’un système linéaire AX = b; il existe deux méthodes de résolution suivant que
l’ordre de la matrice A est inférieur à 100 ou plus grand. Les méthodes directes et les méthodes itératives.
Les méthodes directes permettent d’obtenir la solution exacte du système en un nombre …ni d’étapes.
Les méthodes itératives consistent à générer une suite de vecteurs qui converge vers la solution du système.
III.1. Méthodes Directes
Elles permettent d’obtenir la solution exacte d’un système en un nombre …ni d’étapes.
On utilise les méthodes directes dans le cas où l’ordre de la matrice A est inférieur à 100:

III.1.1. Méthode de Cramèr

Cette méthode repose sur le calcule des déterminants.
Si det A 6= 0; le système AX = b admet une unique solution
det Ai
xi = ; i = 1; :::; n
det A
où Ai est la matrice obtenue en remplaçant dans A la ieme colonne par le second membre b:
Exemple :
Donner la solution du système suivant :
2x1 + 3x2 = 6 2 3 x1 6
(SL) , = , AX = b
x1 + 4x2 = 3 1 4 x2 3

On a det A = 8 3 = 5 6= 0 , le système admet une unique solution.

6 3 2 6
det det
det A1 3 4 15 det A2 1 3 0 x1 3
x1 = = = = 3; x2 = = = =0)X= =
det A 5 5 det A 5 5 x2 0
III.1.2 Système particulier
aii si i = j
F A matrice diagonale , aij =
0 si i 6= j
La solution d’un système diagonale est donnée par
bi
xi = ; i = 1; :::; n
aii

Exemple :
Soit le système diagonale AX
0 =b 1 0 1 021
5 0 0 0 0 2 5
B0 8 0 0 0C B1C B1C
B C B C B 81 C
A=B B0 0 6 0 0C B C B C
C ; b = B3C ) X = B 25 C
@0 0 0 7 0A @5A @ A
7
0 0 0 0 4 4 1
F A matrice triangulaire supérieure , aij = 0 8(i; j); i > j
Exemple : 0 1
5 1 2 10 3
B0 8 6 1 0 C
B C
A=B
B0 0 6 4 2 CC
@0 0 0 7 10A
0 0 0 0 4
F A matrice triangulaire inférieure , aij = 0 8(i; j); i < j
Exemple : 0 1
5 0 0 0 0
B 2 8 0 0 0C
B C
A=B 1 B 9 6 0 0C C
@0 3 4 7 0A
2 1 5 12 4
Considerons à présent un système linéaire dont la matrice A est inversible et triangulaire supérieure,
c’est à dire sous la forme :
8
>
> a11 x1 + a12 x2 + : : : a1n xn = b1
>
>
>
> 0 + a x
22 2 + : : : a2n xn = b2
>
>
>
> 0 + 0 + a33 xn : : : a3n xn = b3
>
>
>
> 0 + 0 +
<
: 0 0 +
(SLT ) , AX = b ,
>
> : 0
>
>
>
> :
>
>
>
> :
>
>
>
> : :
:
0 : : : : : 0 ann xn = bn
 0 1 0 1 01
a11 a12 : : : :
: a1n b1 x1
B 0 a22 : : : :: a2n C
: B b2 C B x2 C
B C B C B C
B0 0 a33 C B:C B:C
B C B C B C
B0 0 0 : C B:C B:C
A=B
B0
C;
C b=B C
B : C; X=B
B:C
C
B 0 0 0 : C B C B C
B0 0 0 0 0 : C B:C B:C
B C B C B C
@0 0 0 0 0 0 : A @:A @:A
0 0 0 0 0 0 0 ann bn xn
la matrice étant inversible, ses tremes diagonaux aii ; i = 1; :::; n sont tous non nuls et la résolution du
système est alors simple. On calcule xn que l’on substitue ensuite dans la (n 1)eme équation pour obtenir
xn 1 ; et ainsi de suite, cette méthode est dite de remontée
La solution d’un système triangulaire supérieure est donnée par
8
>
< xn = ab!n
nn

1 P
n
>
: x k = b k akj xj ; k = n 1; :::; 1
akk j=k+1

Soit le système
0 triangulaire
1 AX0= 1b 8 0 1
3
1 3 4 1 1 >
> x4 = 1 2
B0 2 C B C < 1 B 1C
1 1C 0C x3 = 3 (1 x4 ) = 0
A=B @0 0 ; b=B @1A , > )X=B 2C
3 1A > x 2 = 1
2
(0 x3 x4 ) = 1
2
@ 0 A
: 3 3
0 0 0 2 2 x1 = (1 3x2 4x2 x4 ) = 1 + 2
1 = 2
1
i

III.1.3 Méthode de Gauss ( cas de matrice quelconque)

On dit méthode d’élimination de Gauss.
Principe :
La méthode de Gauss consiste à transformer le système AX = b à matrice quelconque en un système
v
équivalent U X = b; où U est une matrice triangulaire supérieure.
La triangularisation d’un système est e¤ectuée par les transformations élémentaires suivantes :
Permutation de deux lignes Li ! Lj
Multiplication d’une ligne Li par un scalaire réel non nul Li ! Li
Addition de deux lignes Li + Lj ! Li
Remarque
Il faut appliquer les transformations à la fois à la matrice A et au vecteur b: On travaille donc sur la
matrice (A; b) qui a n lignes et (n + 1) colonnes, appelée matrice complitée ou augmontée du système
AX = b.
Algorithme :
•L’algorithme d’élimination de Gauss
On considère le système AX = b; où A = (aij )1 i;j n ; et b est un vecteur colonne dans Rn :
Elimination : v
Par des transformations élémentaires en passe du système (A; b) à un système équivalent (U; b); où U est
une matrice triangulaire supérieure

uij si i j
U = (uij )1 i;j n =
0 si non

[1] Etape :
Si a11 = 0 alors
s’il existe un i > 1; tel que ai1 6= 0; on fait permutation des lignes 1 et i.
si non, la matrice est singulière
terminer
Le pivot a11 6= 0
 On fait des transformations élémentaires pour faire apparaitre des zero dans la première colonne à
partir de la deuxième lignes, ainsi on obtient une matrice équivalente :
8
> (2) ai1
>
> aij = aij a1j ; i; j = 2; :::; n
< a11
(2)
ai1 = 0; i = 2; :::; n
>
> a
>
:
(2)
bi = bi
i1
b1 ; i = 2; :::; n
a11

[2] Etape :
(2)
Si a22 = 0 alors
(2)
s’il existe un i > 2; tel que ai2 6= 0; on fait permutation des lignes 2 et i.
si non, la matrice est singulière
terminer.
(2)
Le pivot a22 6= 0
On itère le procédé
.
.
.
[k] Etape :
(k)
Si akk = 0 alors
(k)
s’il existe un i > k; tel que aik 6= 0; on fait permutation des lignes k et i.
si non, la matrice est singulière
terminer
(k)
Le pivot akk 6= 0
Par le même procédé, on obtient une matrice équivalente
8 (k)
>
> (k+1) (k) aik (k)
>
> aij = aij a ; i; j = k + 1; :::; n
>
> a
(k) kj
>
> kk
< (k+1)
aik = 0; i = k + 1; :::; n
(k+1) (k)
>
> aij = aij ; i = 1; :::; k ; j = 1; :::; n
>
>
>
>
(k)
aik (k)
>
> (k+1)
bi = bi
(k)
b ; i = k + 1; ::; n
: (k) i
akk
.
.
.
[n] Etape :
(n)
Si ann = 0; alors la matrice est singulière, donc le système n’admet pas de solution ou admet une
in…nité de solutions
(n)
Si non ann 6= 0; le système admet une unique solution.
On obtient une matrice triangulaire supérieure :
0 1 0 1
a11 a12 : : : a1n b1
B 0 a(2) : (2) C
B b2 C
(2)
B 22 : : a2n C B C
B (3) C v B : C
B0 0 a33 C
U =B C; b = B C B
C
B0 0 0 : C B : C
B C @ : A
@0 0 0 0 : A
(n) (n)
0 0 0 0 0 ann bn

• Résolution :
8 (n)
>
> xn = bn
v < (n)
unn!
AX = b , U X = b , P
n
>
> 1 (k) (k)
: xk = (k)
ukk
bk ukj xj ; k=n 1; :::; 1
j=k+1
Exemple : 0 1 0 1
2 1 4 1
1) Soit le système A = @4 2 7A ; b = @0A
2 1 1 0
Résoudre le système AX = b; en utilisant la méthode de Gauss.
On a :
a11 =2206= 0; pivot 13 2 3 20 13
2 1 4 1 L1 2 1 4 1
(A; b) = 4@4 2 7 0A5 ! 4L2 24 L1 5 4@0 0 1 2A5
2
2 1 1 0 L3 2 L1 0 0 3 1
(2) (2)
a22 = 0; et a32 = 0 ) que la matrice est singulière.
8
s < 2x1 +x2 4x3 = 1
On a donc le système équivalent U X = b , x3 = 2 ) le système n’admet pas de
:
3x3 = 1
solution. 0 1 0 1
2 1 4 1
@
2) Soit A = 4 2 A
7 ; b = 0A@
2 2 1 0
Résoudre le système AX = b; en utilisant la méthode de Gauss.
On a :
a11 =2206= 0; pivot 13 2 3 20 13
2 1 4 1 L1 2 1 4 1
(A; b) = 4@4 2 7 0A5 ! 4L2 42 L1 5 4@0 0 1 2A5
2
2 2 1 0 L3 2 L1 0 1 3 1
(2) (2)
0et a32 = 1 6= 0;1on
2a22 3=20; 3 permute
2 3 2la0ligne 2 et 3: 13
L1 2 1 4 1 L1 2 1 4 1
! 4L2 5 4@0 0 1 2A5 ! 4L3 5 4@0 1 3 1A5
L3 0 1 3 1 L2 0 0 81 2
s < 2x1 +x2 4x3 = 1
On a donc le système équivalent U X = b , x2 +3x3 = 1 ) le système admet une
:
x3 = 2
solution unique. 0 1
x3 = 2 6
La solution est donnée par : x2 = 1 3x3 = 1 + 6 = 5 )X=@ 5 A
x1 = 12 (1 x2 + 4x3 ) = 21 (1 5 8) = 6 2
III.2. Méthodes Itératives
Elles consistent à générer une suite de vecteurs qui converge (sous conditions) vers la solution du
système.
III.2.1 Quelques rappels d’Algèbre Linéaire :
• Matrices
On note par Mn (R) ensemble des matrices carrées d’ordres n:
La transposee d’une matrice A = (aij )i;j=1;:::;n est une matrice notée At = (aji )j;i=1;:::;n :
On a les propriétés :
1 1 t
(At )t = A; (A + B)t = At + B t ; (AB)t = B t At ; det At = det (A) ; At = A

A est symétrique , A = At
Normes vectorielle

Une application k:k : E ! R+ ( E est un éspace vectoriel reel), est dite une norme vectorielle si elle
véri…e les proprietés suivantes :
i) kXk = 0 , X = 0Rn ; 8X 2 E:
ii) kX + Y k kXk + kY k ; 8X; Y 2 E
iii) k Xk = j j kXk ; 8 2 R; 8X 2 E:
 Normes vectoreilles Usuelles r
Pn P
n
kXk1 = jxi j ; kXk1 = max (jxi j) ; kXk2 = x2i
i=1 1 i n i=1
Exemple : 0 1
2
B 0 C
Calculer les normes k:k1 ; k:k1 et k:k2 du vecteur X = B
@ 1 A
C

5
P
n
kXk1 = jxi j = j2j + j0j + j 1j + j 5j = 8
i=1
kXk1 = max (jxi j) = max(j2j ; j0j ; j 1j ; j 5j) = 5
1 i n
r
P
n p p
kXk2 = x2i = 4 + 0 + 2 + 25 = 31
i=1
Normes matricielles
L’application k:k : Mn ! R+ ; (Mn (R) ensemble des matrices carrées d’ordres n) est une norme matricielle
si elle véri…e les proprietés suivantes :
i) kAk = 0 , A = 0Rn Rn ; 8A 2 Mn :
ii) kA + Bk kAk + kBk ; 8A; B 2 Mn :
iii) k Ak = j j kAk ; 8 2 R; 8A 2 Mn :
Normes Usuelles !
Pn Pn p p
kAk1 = max jaij j ; kAk1 = max jaij j ; kAk2 = (AAt ) = (At A)
1 j n i=1 1 i n j=1

Remarque :
Si A est symétrique alors kAk1 = kAk1 et kAk2 = (A)
Exemple
0 : 1
1 0 1
A=@ 0 1 0A ) kAk1 = max (1 + 0 + j 2j ; 0 + j 1j + 0; 1 + 0 + 1) = 3;
2 0 1
kAk1 = (1 + 0 + 1; 0 + j 1j + 0; j 2j + 0 + 1) = 3:
On calcule kAk2 ultérieurement
• Rayon spéctral
Dé…nition :
Soit A 2 Mn (R) et 2 C:
On dit que est une valeur propre de A; s’il existe un vecteur u 2 Rn ; u 6= 0Rn tel que Au = u:
On dit alors que u est un vecteur propre de A associé à la valeur propre :
On a donc Au = u , (A I) u = 0 , det (A I) = 0:
Proposition :
Les valeurs propres de A sont donc les racines du polynôme caractéristique PA ( ) = det (A I) = 0:
C’est un polynôme de degré n; il a donc n racines dans C. La matrice A a donc n valeurs propres dans
C
Rayon spectral de A :
(A) = max fj j ; 2 C= p est la valeurppropre de Ag
Revenons au calcul de kAk = (AA t) = (A t
0 1 2 0 1 A)
1 0 1 1 0 2
On a A = @ 0 A
1 0 ,A = 0 t @ 1 0 A)
0 2 0 11 0 1 10 01 1
1 0 1 1 0 2 2 0 1
AAt = @ 0 1 0A @0 1 0 A=@ 0 1 0 A=
2 0 1 001 0 1 1 0 1 0 1 51
2 0 1 0 0
det (AA t
I) = det @ @ 0 1 0 A @ 0 0 AA
1 0 5 0 0
 0 1
2 0 1
= det @ 0 1 0 A=
3
+ 8 2 16 + 9
1 0 5
3 2
On a alors PA ( ) = 0 +8 161 + 9 = 0
1 = 1p
les racines sont : @ 2 = 27 p 21 13A )
1 7
3 = 2 13 + 2
p p
(AAt ) = max fj i jg = 3 = 5: 302 8 ) kAk2 = (AAt ) = 5: 302 8 = 2: 302 8:
1 i 3

III.2.2 Principe des méthodes itératives :

Considérons A 2 Mn (R) ; inversible et b un vecteur de Rn :
On cherche à approcher la solution X du système linéaire AX = b: Donc les méthodes itératives
engendrent une suite …nie / in…nie de vecteurs qui tend (sous certaines conditions) vers la solution exacte.
L’idée d’une méthode itérative de résolution du système AX = b est d’écrire ce système sous forme d’un
point …xe (f (x) = 0 , ' (x) = x) :
On décompose alors la matrice A sous la forme A = M N; où M 2 Mn (R) est facile à inverser et
N 2 Mn (R) :
Ceci implique que AX = b , (M N )X = b , M X = N X + b , X = M 1 N X + M 1 b , X = CX + l
X = F (X) :
Etant donné un vecteur X (0) 2 Rn ; on construit la suite X (k) k2N par :

X (k+1) = CX (k) + l
avec C = M 1 N; l = M 1
b

C = M 1 N est appelée matrice de la méthode itérative.

La forme générale des méthodes itératives à étudier :

X (0) 2 Rn
( ) (k+1)
X = CX (k) + l; k = 0; ::::

Dé…nition :
On dit que la méthode itérative ( ) converge si lim X (k) = X ; pour tout X (0) 2 Rn ; avec X est la
k!1
solution exacte de système AX = b:
Ceci est équivalent à lim X (k) X =0
k!1
III.2.3 Conditions Nécessaires et Su¢ santes de convergence :
Théorème1 : (C.N.S)
La méthode itérative ( ) converge, pour tout X (0) 2 Rn si et seulement si (C) < 1:
La convergence est d’autant plus rapide que (C) est petit.
Théorème2 : (C.N.S)
S’il existe une norme matricielle (k:k) telque kCk < 1 alors La méthode itérative ( ) converge, pour
tout X (0) 2 Rn :
Majoration d’erreur :

kCkk
X (k) X X (1) X (0) ; où k:k est une norme telle que kCk < 1:
1 kCk
III.2.4 Méthodes usuelles :
Principe : 0 1
F
On décompose A sous la forme A = D E F =@ D A
E
où
D est la partie diagonale de la matrice A:
E est la partie triangulaire inférieure de la matrice A:
 F est la partie triangulaire supérieure de la matrice A:
Exemple : 0 1 0 1 0 1 0 1
1 2 3 1 1 0 0 0 0 0 0 0 0 2 3 1
B4 3 7 2C B0 3 0 0C B 4 0 0 0C B0 0 7 2C
Soit A = B
@ 1
C)D=B C;E = B C;F = B C
5 3 0A @0 0 3 0A @1 5 0 0A @0 0 0 0A
6 1 2 1 0 0 0 1 6 1 2 0 0 0 0 0

1. Méthode de Jacobi :
1.1 Itérations de la méthode de Jacobi
On a donc AX = (D (E + F ))X = b
On soppose que aii 6= 0; 8i = 1; :::; n donc la matrice D est inversible. On choisit alors M = D et
N =E+F
X (0) 2 Rn
On dé…nit ainsi la méthode itérative de Jacobi où J = D 1 (E + F ) la matrice
X (k+1) = JX (k) + l
de Jacobi et l = D 1 b:
Remarque : (
0 si i = j bi
J = D 1 (E + F ) = D 1 (D A) = I D 1 A ceci donne Jij = aij
si i 6= j et li = aii
aii
Algorithme de Jacobi :
(0)
xi donnée !
(k+1) 1 Pn
(k)
xi = bi aij xj , i = 1; :::; n
aii j=1;j6=i
Exemple :
Ecrire les itérations
0 de1Jacobi pour0 1 le système AX = b
2 1 1 1
A = @1 2 1A ; b = @0A
1 1 2 0
Méthode 1 : 0 1 0 1
2 0 0 0 1 1
J = D 1 (E + F ) ; D = @0 2 0A ; E + F = @ 1 0 1A )
01 10 0 0 1 2 0 1
1 1 0 01 1 0 1 011
1 1
2
0 0 0 1 1 0 2 2 2
0 0 1 2
@
J= 0 2 0 1 A @ 1 0 A
1 = @ 1
0 1A
l = D 1
b = @ 0 1
0 A @ 0A = @0A
2 2 2
0 0 12 1 1 0 1
2
1
2
0 0 0 1
2
0 0
D’où les itérations de Jacobi 0 (k+1) 1 0 1 0 1 011
1 1 (k)
x1 0 2 2
x 1 2
B C @ 1 1 A B (k) C
X (k+1) = JX (k) + l ) @x(k+1) 2 A= 2
0 2 @x 2 A + @ 0 A ,
(k+1) 1 1 (k)
x3 2 2
0 x3 0
0 (k+1) 1 0 1 8
1 (k) 1 (k) > (k+1) 1 (k) 1 (k)
x1 x2 x3 + 1 < x1 = x
2 2
x
2 3
+ 21
B (k+1) C B 2 1 (k) 2 1 (k) 2 C (k+1) 1 (k) 1 (k)
@x 2 A=@ x
2 1
x
2 3 A, x2 = x
2 1
x
2 3
(k+1) 1 (k) 1 (k)
>
: (k+1) 1 (k) 1 (k)
x3 x
2 1
x
2 2
x3 = x
2 1
x
2 2

Méthode2 : ( 0 1 011
1 1
0 si i = j 0
bij 2 2 2
On a Jij = aij
si i =6 j , lij = ) J = @ 21 0 1A
2
; l = @0A
aii a ii 1 1
2 2
0 0
La méthode de Jacobi associée au système AX = b est-elle convergente ?
C.N.S , (J) < 1:
(J) = max fj i jg
1 i n
00 1 1
1 0 11
0 2 2
1 0 0
P (J) = det (J I) = det @@ 12 0 1A
2
@0 1 0AA =
1 1
2 2
0 0 0 1
 0 1 1
1
2 2
det @ 1
2
1A
2
= 3
+ 3
4
1
4
= 1
4
( + 1) (2 1)2 ) 1 = 1; 2 = 1
2
1 1
2 2
1
et 3 = 2
ceci implique que (J) = max fj i jg = max 1; 12 = 1 , la méthode de Jacobi associée au système
1 i 3
AX = b ne converge pas pour tout X (0) 2 R3 :

1.2. Condition su¢ sante de convergence

Dé…nition :
P
n
On dit que la matrice A = (aij )1 i;j n est à diagonale dominante stricte (DDS) si jaii j > jaij j ; 8i =
j=1;j6=i
1; :::; n:
Théorème : ( C:S Jacobi)
Si A est une matrice à DDS alors la méthode de Jacobi converge pour tout X (0) donné.
Exemple :
Les
0 matrices1 suivantes 0
sont-elles1DDS ? 0 1
2 1 1 2 0 1 5 1 1
A = @1 2 1A ; B = @1 4 1A ; C=@ 1 3 1 A
1 1 2 1 1 2 1 1 4
Pour A : 2 1 + 1 ) A n’est pas à DDS.
Pour B : 2 > 0 + 1; 4 > 1 + 1; 2 = 1 + 1 ) B n’est pas à DDS.
Pour C : j 5j > 1 + j 1j ; 3 > 1 + 1; j 4j > 1 + 1 ) C est à DDS.
Exercice :
Sans faire les calcules, que peut-on dire de la convergence de la méthode de Jacobi associéee aux
systèmes BX = b1 et CX = b2 :
On a : la matrice B n’est pas à DDS, la Condition Su¢ sante n’est pas satisfaite donc on peut rien
conclure.
la matrice C est à DDS, la Condition Su¢ sante est satisfaite alors la méthode de Jacobi appliquée
au système CX = b2 est convergente.

2. Méthode de Gauss - Seidel

2.1. Itérations de la méthode de Gauss - Seidel :
A partir de la décompostion A = D E F:
Si aii 6= 0; i = 1; :::; n alors la matrice M = D E est inversible (matrice triangulaire inférieure à diagonale
D)
X (0) 2 Rn
Pour M = D E donc N = F; la méthode de Gauss-Seidel est dé…nie par
X (k+1) = GX (k) + g
où G = (D E) 1 F dite matrice de Gauss-Seidel, g = (D E) 1 b:
Algorithme de G-S :
(0)
xi donnée !
1 iP1 P
n
(k+1) (k+1) (k)
xi = bi aij xj aij xj ; i = 1; :::; n
aii j=1 j=i+1

Exemple :
0Ecrire les itérations
1 de la méthode
0 1de Gauss-Seidel associéee au système AX = b
1
1 3
0 1
A= @ 1
1 1A
; b = 1A
@
3 3
1
0 3
1 1 0 1 0 1 1
1 0 0 0 3 0
1
La matrice de Gauss-Seidel G = (D E) F; on a D E = @ 1
1 0 ; F = 0 0 31 A
A @
3
1
0 3
1 0 0 0
1
Calculons (D E) en utilisant la méthode d’élimination de Gauss Jordan.
 0 10 1 0 10 1
1 0 0 1 0 0 L1 1 0 0 1 0 0
@ 1 1 0A @0 1 0A ! L2 + 31 L1 @0 1 0A @ 31 1 0A
3
1 1
0 3
1 00 0 1 1 0 L3 1 0 3
1 00 0 1 1
L1 1 0 0 1 0 0 1 0 0
! L2 @ 0 1 0 A @ 1 A
1 0 ) (D E) 1
= 13 1 0A
@
3
1 1 1 1 1
3 + 3 L2
L0 100 0 11 19 30 1 1 1 0 9 3 110 1 0 1
1 0 0 0 3 0 0 3 0 1 0 0 1 1
@
Donc G = 3 1 0 1 A @ 1A @ 1
0 0 3 = 0 9 3 ; g= 3 1 0 1A @ 1 A @ 1 = 43 A
A @
1 1 1 1 1 1 13
9 3
1 0 0 0 0 27 9 9 3
1 1 9
On déduit alors les itérations
0 de Gauss-Seidel
1 0 1 0 1 0 1 0 1
(k+1) (k)
x1 0 13 0 x1 1 1 k
3
x 2 + 1
B C @ B (k) C
X (k+1) = GX (k) + g , @x(k+1)
2 A = 0 19 13 A @x2 A + @ 34 A = @ 91 xk2 + 31 xk3 + 43 A
1 1 13 1 k
(k+1)
x3 0 27 9
(k)
x3 9
x + 19 xk3 + 13
27 2 9
8
(k+1)
>
< x1
1 k
= 3 x2 + 1
(k+1)
D’où les itérations : x2 = 19 xk2 + 13 xk3 + 43
>
: x(k+1) = 1 xk + 1 xk + 13
3 27 2 9 3 9
Etudions la convergence.
La C.N.S de convergence : (G) < 1:
Calculons (G) : 00 1 0 11 0 1
0 31 0 1 0 0 1
3
0
P (G) = det (G I) = det @@0 19 13 A @0 1 0AA = det @ 0 1
9
1 A
3
1 1 1 1
0 27 9
0 0 1 0 27 9
2 2 3 1 2
=9 = 9 (9 2) =
P (G) = det (G I) = 0 , 1 = 2 = 0; et 3 = 29
ce qui donne (G) = max fj i jg = 92 < 1 , la méthode de gauss-Seidel converge pour tout X (0) 2 R3 :
1 i 3

2:2 Condition su¢ sante de convergence :

Théorème 1 : (C:S Gauss-Seidel)
Si A est une matrice à DDS alors la méthode de Gauss-Seidel appliquée au systhème AX = b est
convergente pour tout X (0) donné.
Dé…nition : (Mineurs principaux diagonaux d’une matrice) :
Le mineur principal diagonal d’ordre k (noté k ) de la matrice A est le déterminant de la sous-matrice
de A obtenue en supprimant les (n k) dernières lignes et (n k) dernières colonnes de A:
Une matrice carrée d’ordre n admet n mineurs principaux digonaux.
Exemple :
Soit A une matrice d’ordre 3.
Le mineur principal diagonal d’ordre 1 de A est 1 = (a11 ) :
a11 a12
Le mineur principal diagonal d’ordre 2 de A est 2 =
a21 a22
a11 a12 a13
Le mineur principal diagonal d’ordre 3 de A est 3 = a21 a22 a23
a31 a32 a33
A est une matrice symétrique dé…nie positive (SDP ) si et seulement si les mineurs principaux diago-
naux sont strictement positifs.
A est une matrice symétrique dé…nie positive (SDP ) si et seulement si les valeurs propres de A sont
strictement positives.
Théorème 2 : ( C.S Gauss-Seidel)
Si A est une matrice symétrique dé…nie positive (SDP) alors la méthode de Gauss-Seidel appliquée au
système AX = b est convergente pour tout X (0) donné.
Exemple :
Reprendre les mêmes matrices de l’exercice précédent.
A n’est pas DDS alors on peut rien conclure d’aprés le théorème1 (C.S).
Mais A est 0 SDP, en
1e¤et : 0 1
2 1 1 2 1 1
2 1
A = @1 2 1A ; on a A = At et 1 = 2; 2 = det = 3; 3 = det @1 2 1A = 4
1 2
1 1 2 1 1 2
(0)
on a la matrice A est SDP ) la méthode de G-S converge, pour tout X donné.
B n’est0pas DDS1alors on peut rien conclure d’aprés le théorème1 (C.S). 0 1
2 0 1 2 0 1
2 0
B = @1 4 1A ; on a B = B t et 1 = 2; 2 = det = 6; 3 = det @1 4 1A = 11 ) sont
1 4
1 1 2 1 1 2
strictement positifs alors la méthode de G-S associée au système BX = b2 converge pour tout X (0) :
C n’est pas SDP0 1
5 1 1
en e¤et C = @ 1 3 1 A ; C 6= C t ) C n’est pas symétrique.
1 1 4
Mais C est à DDS alors la méthode de G-S associée au système CX = b3 converge pour tout X (0) :
Remarque :
La matrice A qui doit satisfaire la C.S
La matrice de la méthode itérative C (J : la matrice de Jacobi, G : la matrice de G-S) qui doit sa-
tisfaire la C.N.S