Exercice 1

´Enonc´e

On considere le systeme d’´equations lin´eaires (S), dont l’´ecriture matricielle est donn´ee par :

AX = b avec :

A =







 , X =







 et b =









Partie I :

1 Montrer que (S) admet une unique solution.

2 Montrer que A admet une d´ecomposition LU.

3 Justiﬁer la convergence de la m´ethode it´eratif de Jacobi pour la r´esolution du (S)

Partie II :

1 R´esoudre (S) par la m´ethode de Gauss.

2 Donner le sch´ema it´eratif de la m´ethode de Jacobi associ´e au syst`eme (S).

3 Pour le vecteur X (0) =







, donner les r´esultats des deux premi`eres it´erations de la

m´ethodes de Jacobi pour r´esolution du (S).

1 / 6

1 On a det(A) =

= 4(16 − 1) − 4 = 56 (cid:54)= 0.

(cid:12)

= 4

(cid:12)

− 1

(cid:12)

Donc, (S) admet une unique solution.

Rappel

A admet une d´ecomposition LU ssi tous les mineurs principaux de A sont inversibles.

2 A(1) = (4); det(A(1)) = |4| (cid:54)= 0,

A(2) =

(cid:18)4

(cid:19)

; det(A(2)) =

= 15 (cid:54)= 0,

(cid:12)

A(3) = A; det(A(3)) = 56 (cid:54)= 0,

Ainsi tous les mineurs principaux de A sont inversibles et par suite A admet une

d´ecomposition LU.

Exercice 1

Partie I

Solution

Rappel

(S) admet une unique solution ⇔ det(A) (cid:54)= 0.

2 / 6

Rappel

A admet une d´ecomposition LU ssi tous les mineurs principaux de A sont inversibles.

2 A(1) = (4); det(A(1)) = |4| (cid:54)= 0,

A(2) =

(cid:18)4

(cid:19)

; det(A(2)) =

= 15 (cid:54)= 0,

(cid:12)

A(3) = A; det(A(3)) = 56 (cid:54)= 0,

Ainsi tous les mineurs principaux de A sont inversibles et par suite A admet une

d´ecomposition LU.

Exercice 1

Partie I

Solution

Rappel

(S) admet une unique solution ⇔ det(A) (cid:54)= 0.

1 On a det(A) =

(cid:12)

= 4

(cid:12)

− 1

(cid:12)

Donc, (S) admet une unique solution.

= 4(16 − 1) − 4 = 56 (cid:54)= 0.

2 / 6

2 A(1) = (4); det(A(1)) = |4| (cid:54)= 0,

A(2) =

(cid:18)4

(cid:19)

; det(A(2)) =

= 15 (cid:54)= 0,

(cid:12)

A(3) = A; det(A(3)) = 56 (cid:54)= 0,

Ainsi tous les mineurs principaux de A sont inversibles et par suite A admet une

d´ecomposition LU.

Exercice 1

Partie I

Solution

Rappel

(S) admet une unique solution ⇔ det(A) (cid:54)= 0.

1 On a det(A) =

(cid:12)

= 4

(cid:12)

− 1

(cid:12)

Donc, (S) admet une unique solution.

= 4(16 − 1) − 4 = 56 (cid:54)= 0.

Rappel

A admet une d´ecomposition LU ssi tous les mineurs principaux de A sont inversibles.

2 / 6

Exercice 1

Partie I

Solution

Rappel

(S) admet une unique solution ⇔ det(A) (cid:54)= 0.

1 On a det(A) =

(cid:12)

= 4

(cid:12)

− 1

(cid:12)

Donc, (S) admet une unique solution.

= 4(16 − 1) − 4 = 56 (cid:54)= 0.

Rappel

A admet une d´ecomposition LU ssi tous les mineurs principaux de A sont inversibles.

2 A(1) = (4); det(A(1)) = |4| (cid:54)= 0,

(cid:12)

(cid:19)

(cid:12)

; det(A(2)) =

(cid:18)4

A(2) =

(cid:12)

= 15 (cid:54)= 0,

A(3) = A; det(A(3)) = 56 (cid:54)= 0,

Ainsi tous les mineurs principaux de A sont inversibles et par suite A admet une

d´ecomposition LU.

2 / 6

3 On a ,







|4| > |1| + |0|

|4| > |1| + |1|

|4| > |0| + |1|

Ainsi A `a diagonale strictement dominante et par suite la m´ethode de Jacobi est

convergente.

Solution

Rappel

Soit A une matrice `a diagonale strictement dominante alors les m´ethodes de Jacobi et

Gauss Seidel appliqu´ees au syst`eme (S) : AX = b sont convergentes pour tous X (0).

Une matrice A est `a diagonale strictement dominante si la valeur absolue de chaque

coeﬃcient diagonal ai,i (i ∈ {1, · · · , n}) de A est strictement sup´erieure `a la somme des

valeurs absolues des autres coeﬃcients de A situ´es a la i eme ligne. En d’autre terme,

|ai,i | >

(cid:88)

j=1

j(cid:54)=i

|ai,j |, ∀i ∈ {1, ..., n}.

3 / 6

Solution

Rappel

Soit A une matrice `a diagonale strictement dominante alors les m´ethodes de Jacobi et

Gauss Seidel appliqu´ees au syst`eme (S) : AX = b sont convergentes pour tous X (0).

Une matrice A est `a diagonale strictement dominante si la valeur absolue de chaque

coeﬃcient diagonal ai,i (i ∈ {1, · · · , n}) de A est strictement sup´erieure `a la somme des

valeurs absolues des autres coeﬃcients de A situ´es a la i eme ligne. En d’autre terme,

|ai,i | >

(cid:88)

j=1

j(cid:54)=i

|ai,j |, ∀i ∈ {1, ..., n}.

3 On a ,







|4| > |1| + |0|

|4| > |1| + |1|

|4| > |0| + |1|

Ainsi A `a diagonale strictement dominante et par suite la m´ethode de Jacobi est

convergente.

3 / 6

´Etape 2 : Annuler tous les coeﬃcients situant en dessous du premier pivot.

L2 ←− L2 −

(cid:18) 1

(cid:19)

(A|b)(2) =





15/4





23/4

Exercice 1

Partie II

Solution

´Etape 1 : ´Ecrire la matrice ´elargie relative `a (S), not´ee par (A|b), et d´eterminer un

premier pivot non nul.

(A|b)(1) =









On a11 (cid:54)= 0.

4 / 6

Exercice 1

Partie II

Solution

´Etape 1 : ´Ecrire la matrice ´elargie relative `a (S), not´ee par (A|b), et d´eterminer un

premier pivot non nul.

(A|b)(1) =









On a11 (cid:54)= 0.

´Etape 2 : Annuler tous les coeﬃcients situant en dessous du premier pivot.

L2 ←− L2 −

(cid:19)

(cid:18) 1

(A|b)(2) =





15/4





23/4

4 / 6

Ainsi on obtient un systeme triangulaire sup´erieur ´equivalent au systeme (S) :







4x1 + x2

= 1

4 x2 + x3 = 23

15 x3 = 112/15

Le nouveau systeme triangulaire sup´erieur est tres simple `a r´esoudre :

(L3) donne : x3 =

= 112

56 = 2.

Puis dans (L2) : 15

4 x2 + x3 = 23

4 donc x2 = 1.

Enﬁn dans (L1) : 4x1 + x2 = 1 donc x1 = 0 .

Conclusion : La solution du syst`eme (S) est (x1, x2, x3) = (0, 1, 2).

Solution

´Etape 3: Passer au pivot suivant, vitriﬁer qu’il est non nul et annuler tous les

coeﬃcients situant en dessous du deuxi`eme pivot.

L3 ←− L3 −

(cid:32)

(cid:33)

L2 = L3 −

(cid:19)

(cid:18) 4

(A|b)(3) =







15/4

23/4







56/15

112/15

5 / 6

Le nouveau systeme triangulaire sup´erieur est tres simple `a r´esoudre :

(L3) donne : x3 =

= 112

56 = 2.

Puis dans (L2) : 15

4 x2 + x3 = 23

4 donc x2 = 1.

Enﬁn dans (L1) : 4x1 + x2 = 1 donc x1 = 0 .

Conclusion : La solution du syst`eme (S) est (x1, x2, x3) = (0, 1, 2).

Solution

´Etape 3: Passer au pivot suivant, vitriﬁer qu’il est non nul et annuler tous les

coeﬃcients situant en dessous du deuxi`eme pivot.

L3 ←− L3 −

(cid:32)

(cid:33)

L2 = L3 −

(cid:19)

(cid:18) 4

(A|b)(3) =







15/4

23/4







56/15

112/15

Ainsi on obtient un systeme triangulaire sup´erieur ´equivalent au systeme (S) :

4x1 + x2

= 1

4 x2 + x3 = 23

15 x3 = 112/15







5 / 6

Solution

´Etape 3: Passer au pivot suivant, vitriﬁer qu’il est non nul et annuler tous les

coeﬃcients situant en dessous du deuxi`eme pivot.

L3 ←− L3 −

(cid:32)

(cid:33)

L2 = L3 −

(cid:19)

(cid:18) 4

(A|b)(3) =







15/4

23/4







56/15

112/15

Ainsi on obtient un systeme triangulaire sup´erieur ´equivalent au systeme (S) :







4x1 + x2

= 1

4 x2 + x3 = 23

15 x3 = 112/15

Le nouveau systeme triangulaire sup´erieur est tres simple `a r´esoudre :

(L3) donne : x3 =

= 112

56 = 2.

Puis dans (L2) : 15

4 donc x2 = 1.

Enﬁn dans (L1) : 4x1 + x2 = 1 donc x1 = 0 .

Conclusion : La solution du syst`eme (S) est (x1, x2, x3) = (0, 1, 2).

4 x2 + x3 = 23

5 / 6

Le sch´ema it´eratif de la m´ethode de Jacobi est donn´e par:







x (k+1)

b1−a1,2x

b2−a2,1x

b3−a3,1x

(k)

−a1,3x

(k)

−a2,3x

(k)

−a3,2x

(k)

a1,1

(k)

a2,2

(k)

a3,3

(k)

1−x

6−x

(k)

9−x

(k)

−x

3- Pour le vecteur initial X (0) =



, les deux premiers it´eration de Jacobi sont :







1/4

3/2

9/4













−0.125

0.875

1.875

It´eration 1 : X (1) =

It´eration 2 : X (2) =

Solution

2- D´ecomposition de Jacobi: A = D − E − F













x k+1



 =





−1





−1













x (k)









6 / 6

3- Pour le vecteur initial X (0) =



, les deux premiers it´eration de Jacobi sont :







1/4

3/2

9/4













−0.125

0.875

1.875

It´eration 1 : X (1) =

It´eration 2 : X (2) =

Solution

2- D´ecomposition de Jacobi: A = D − E − F













x k+1



 =





−1





−1













x (k)

Le sch´ema it´eratif de la m´ethode de Jacobi est donn´e par:









b1−a1,2x

−a1,3x

b2−a2,1x

−a2,3x

b3−a3,1x

−a3,2x

(k)

a1,1

(k)

a2,2

(k)

a3,3

(k)

1−x

6−x

(k)

9−x

−x

(k)







x (k+1)

6 / 6

Solution

2- D´ecomposition de Jacobi: A = D − E − F













x k+1



 =





−1





−1













x (k)

Le sch´ema it´eratif de la m´ethode de Jacobi est donn´e par:















x (k+1)

3- Pour le vecteur initial X (0) =

b1−a1,2x

−a1,3x

b2−a2,1x

−a2,3x

b3−a3,1x

−a3,2x

(k)

a1,1

(k)

a2,2

(k)

a3,3

(k)

1−x

6−x

(k)

9−x

−x

(k)







, les deux premiers it´eration de Jacobi sont :



It´eration 1 : X (1) =

It´eration 2 : X (2) =

6 / 6











1/4

3/2

9/4

−0.125

0.875

1.875





Analysis of Linear System Solving Using LU Decomposition and Jacobi Method

Analysis of Linear System Solving Using LU Decomposition and Jacobi Method