U:M:B:B Faculte d0Hydrocarbures M:N:A

Corrige : Resolution AX = b
Responsable : Khodja

I. Méthodes directes :
Exercice 1 : 8
< 2x + y 4z = 8
Résoudre le système linéaire (SL) 3x + 3y 5z = 14
:
4x + 5y 2z = 16
1. Ecrire le système (SL) sous forme matricille.
2. En utilisant la méthode d’élémination de Gauss, résoudre le système (SL)
Réponse :
1. 0 10 1 0 1
2 1 4 x 8
@
(SL) , 3 3 5 A @ A @
y = 14A , AX = b
4 5 2 z 16

2. Algorithme :
a11 = 2 ! 2 pivot
0 1 0 13 22 30 10 13
2 1 4 8 L1 2 1 4 8
A(1) : b(1) = 4@3 3 5A @14A5 ! 44L2 23 L1 5 @0 3 32 5 + 32 4A @14 23 8A5
4 5 2 16 L3 2L1 0 3 6 0
3
a22 = 2 ! pivot
22 3 0 1 0 13 22 30 10 13
L1 2 1 4 8 L1 2 1 4 8
A(2) : b(2) = 44L2 5 @0 32 1 A @2A5 ! 44 L2 5 @0 3
2
1 A @ 2 A5
3
L3 0 3 6 0 L3 3 L 2 0 0 6 2 0 4
2

0 1 0 1
s 2 1 4 s 8
AX = b , U X = b où U = A(3) = @0 23 1 A ; b = b(3) = @ 2 A
0 0 4 4

La solution est donnée par 8

< z= 1
y = (2 z) = 32 (2 + 1) = 2
2
3
:
x = 21 (8 y + 4z) = 12 (8 2 4) = 1
0 1 0 1
x 1
Donc @
X= y =A @ 2A
z 1

II. Méthodes Itératives :

Exercice 1 : 0 1 0 1
1 2 2 1 2 2
On considère les deux matrices A = @ 1 1 1A ; B = @ 2 1 3 A pour b 2 R3 :
2 2 1 0 2 1
1. Montrer que, pour le système AX = b; la méthode de Jacobi converge, mais que la méthode de G-S ne
converge pas.
2. Montrer que, pour le système BX = b; la méthode de G-S converge, mais que la méthode de Jacobi ne
converge pas.
Réponse :
1. Itérations de Jacobi : X (k+1) = JX k + l avec0J = D 11(E l = D01 b
0+ F ) et 1 1
1 0 0 0 2 2 0 2 2
J = @0 1 0A @ 1 0 1A = @ 1 0 1A )
2 (n+1) 3 0 1 2 (n) 3 2 (n) 0 (n) 0 31 2 2 0 2 2 0
x1 0 2 2 x1 2x2 + 2x3
6 (n+1) 7 @ A 6 (n) 7 6 (n) (n) 7
4x2 5= 1 0 1 4x2 5 + l = 4 x1 + x3 5 + l
(n+1) 2 2 0 (n) (n) (n)
x3 x3 2x2 2x1
La méthode de Jacobi converge
0 ssi (J) 1
<1
2 2
P (J) = det (J I) = @ 1 1 A = 3
) (J) = 0 < 1 ) la méthode de Jacobi converge.
2 2
Itérations de G-S 0 1 10 1 0 1
1 0 0 0 2 2 0 2 2
G = (D E) 1 F = @ 1 1 0A @0 0 1A = @0 2 3A
2 2 1 0 0 0 0 0 2
La méthode de G-S converge 0 ssi (G) < 1 1
2 2
P (G) = det (G I) = @ 0 2 3 A = 3
+5 2 6 = ( 2) ( 3) )
0 0 2
(G) = max f0; 2; 3g = 3 > 1 ) ne converge pas pour tout X (0) :

Exercice 8 : 0 1 0 1
1 2 2 1
1. Soit @
A= 1 1 1 ; A b = 0A
@
2 2 1 0
i) Ecrire les itérations de Jacobi et de G-S et montrer que (J) < 1 < (G) :
(0) t (3)
ii) En partant0 de X = 1 0 0 0 ,0 calculer
1 X ; et donner une éstimation d’erreur.
2 1 1 0
2. Soit A = @ 2 2 2A ; b = @1A
1 1 2 0
i) Ecrire les itérations de Jacobi et de G-S et calculer (J) et (G) : Qu’en déduit-on ?
t
ii) En partant de X (0) = 0 0 0 , calculer X (3) ; et donner une éstimation d’erreur.
Exercice 9 : 0 1
1
Soit la matrice A = @ 1 A; 2 R
1
1. Pour quel valeurs de la matrice A est à DDS.
2. Pour quel valeurs de la matrice A est SDP.
3. Que peut-on conclure de la convergence des deux méthodes, celle de Jacobi et de Gauss-Seidel.
4. Ecrire les itérations de Jacobi.
5. Pour quel valeurs de la méthode de Jacobi converge ?
6. Etudier la convergence de la méthode de Gauss-Seidel pour = 31 et = 23
Réponse 0: 1
1
A=@ 1 A
1 8 8
P3 < 1 > j j + j j < 1 > 2j j
1. A est DDS , jaii j > jaij j ; i = 1; :::; 3 , 1>j j+j j , 1 > 2 j j , j j < 12
j=1;j6=i : :
1>j j+j j 1 > 2j j
2. A est SDP , k > 0; k valeurs propres de A:
 0 1
1
P (A) = det (A I) = @ 1 A =2 3
+3 2
3 2 3
+3 2
3 +1
1
= (2 + 1) ( + 1)2
) 1 = 1 + 2 ; et 2 = 3 = 1
A est SDP , 1 = 1 + 2 > 0; 2 = 3 = 1 > 0 , > 21 et < 1:
3. D’aprés 1) la méthode de Jacobi converge si 21 < < 12 et la méthode de Gauss-Seidel converge si
1
2
< < 12 (théorème 1 (CS)) :
D’aprés 2) la méthode de Gauss-Seidel converge si 21 < < 1 (théorème 2 (CS)) :
Conclusion :
la méthode de Jacobi converge si 12 < < 21 .
la méthode de Gauss-Seidel converge si 21 < < 1:
4. Les itérations
0 de Jacobi
1 0 1 2 (n+1) 3 0 1 2 (n) 3 0 1
0 b1 x 1 0 x1 b1
6 7 6
A 4x(n) 7
J =@ 0 A et l = @b2 A , 4x (n+1)
2 5 = @ 0 2 5 + @b2 A ,
0 b3 (n+1) 0 (n) b3
x3 x3
8
(n+1) (n) (n)
>
< x1 = b1 x2 x3
(n+1) (n) (n)
x2 = b2 x1 x3
>
: x(n+1) = b (n) (n)
2 3 x1 x2

La méthode de
0 Jacobi converge
1 ssi (J) < 1

P (J) = det @ A= 2 3
+3 2 3
= (2 + ) ( )2 ) 1 = 2 ; 2 = 3 =

Donc (J) = max f2 j j ; j jg = 2 j j ) (J) < 1 , j j < 12

6. = 13 2 1
2
; 1 ) G S converge question3.
3 1
=22 = 2
; 1 ; la condition su¢ sante non satisfaite, donc on peut rien dire. On utilise alors la CN S :
(G) < 1:
Les itérations de G-S :
0 3 31 0 1 10 3 3
1 0 3 3
1
1 2 2 1 0 0 0 2 2
0 2 2
A = @ 32 1 32 A ) G = (D E) 1 F = @ 32 1 0A @0 0 3A
2
= @0 94 3 A
4
3 3 3 3 9 9
2 2
1 2 2
1 0 0 0 0 8 8
0 1 10 1 0 1
1 0 0 b1 b1
g = @ 32 1 0A @b2 A = @ b2 23 b1 A
3 3 3 3
1 b3 b
4 1
b + b3
2 2
2 2 (n+1)
2
3 0 1 2 (n)
3 0 1 0 1
3 3 3 (n) 3 (n)
x1 0 2 2
x 1 b 1 b 1 x
2 2
x
2 3
6 7 @ 3 A 6 (n) 7 @ b2 3 b1 A = B C
) 4x(n+1)
2 5 = 0 9
4 4 4x 2 5 + 2 @ b 2
3
b
2 1
+ 9 (n)
x
4 2
(n)
+ 34 x3 A
(n+1) 9 9 (n) 3 3 (n) (n)
x3 0 8 8 x3 b
4 1
b + b3
2 2
3
b 3 9
b + b3 8 x 2 + 8 x 3 9
4 1 2 2

La convergence ?0
calculons (G S)1
<1
3 3
2 2
P (G) = det @ 0 9
4
3
4
A= 3
+ 27
8
2 27
8
= 1
8
( 27 + 8 2
+ 27)
9 9
0 8 8 p p
1 27+3 15i 27 3 15i
= 8 16 16
r
p 2
27 2 3 15
j j= 16
+ 16
= 1: 837 1 ) (G) = 1:8371 > 1 ) G S ne converge pas pour tout X (0) :