Université d’Alger 1, Module : analyse Num.

Matricielle
Faculté des sciences Dépt. Mathématiques 3 année Math Appl

TP 2 : Décomposition (Factorisation) d’une Matrice

1. Introduction : Dans la littérature, il existe différents types de factorisation : LU ,

QR, SV D, Cholesky, etc. Parmi les applications de la décomposition LU on trouve :
résolution de systèmes linéaires Ax = b, inverse d’une matrice A, calcul du déterminant
d’une matrice A, etc. Dans ce T P nous intéressons principalement a la Factorisation
LU et ses applications.
2. Objectifs : Réaliser la décomposition LU d’une matrice A. Utiliser cette décomposition
pour : résoudre un système linéaire, calculer le déterminant de A, calculer l’inverse de
A.
3. Principe de cette décomposition : On décompose la matrice A en un produit
de deux matrices L et U . La matrice L est triangulaire inférieure dans laquelle les
éléments de la diagonale sont tous égaux à un et U est triangulaire supérieure.
    
1 2 3 4 1 0 0 0 1 2 3 4
    
 2 3 4 1   2 1 0 0   0 −1 −2 −7
  
(a) Exemple : A =  =
   
 
  0 0 −4 4
 3 4 1 2   3 2 1 0   
   
4 1 2 3 4 7 −1 1 0 0 0 40
(b) Algorithme : Décomposition LU par identification des coeffficients
  i−1
P 
u = a − l u si 1 ≤ i ≤ n, i ≤ j ≤ n ;



 ij ij ik kj

 k=1
1 i−1
P 
lji = a ji − l u
jk ki si 1 ≤ i ≤ n, i + 1 ≤ j ≤ n ;



 uii k=1
 l = 1 si 1 ≤ i ≤ n.

ii

Question 1 : écrire une fonction DecLU qui réalise la décomposition LU .

4. Quelques applications de la décomposition LU :

(a) Application pour résoudre un système linéaire : En trouve la solution

du système intermédiaire Ly = b par descente triangulaire ensuite on calcule la
solution de système U x = y par remontée triangulaire.

1
   
10 

 x1 + 2x2 + 3x3 + 4x4 = 10
  

 10   2x + 3x + 4x + x = 10
1 2 3 4
(b) Exemple : Soit b =  , Ax = b ⇒
 
 10  
 3x1 + 4x2 + x3 + 2x4 = 10
  


10  4x + x + 2x + 3x
1 2 3 4 = 10
  


 y1 = 10 10

  
 2y + y = 10  −10 
1 2
Ly = b ⇒ ⇒y=  et
 


 3y1 + 2y2 + y3 = 10 
 0  

 4y + 7y − y + y = 10

40
 1 2 3 4
 


 x1 + 2x2 + 3x3 + 4x4 = 10 1

  
 −x − 2x − 7x = −10  1 
2 3 4
Ux = y ⇒ ⇒x= 
 


 −4x3 + 4x4 = 0  1 
 


 40x = 40 1
4
Algorithme :
a) Descente triangulaire :
i−1
1 X 
yi = bi − lij yj , i = 1, ..., n.
lii i=1

b) Remontée triangulaire :
 n
X 
xi = y i − uij xj , i = n, ...1.
j=i+1

Question 2 : écrire une fonction RTri qui permet de résoudre le système Ly = b

par la remontée triangulaire.
Question 3 : écrire une fonction DTri qui permet de résoudre le système U x = y
par la décente triangulaire.
Question 4 : écrire une fonction ResolDecoLU qui permet de résoudre le
système linéaire Ax = b par la décomposition LU .
(c) Application pour le calcul de déterminant : La décomposition LU permet
n
Q
de calculer le déterminant de A. det(A) = det(U ) = ukk .
k=1
Exemple : det(A) = det(U ) = (1)(−1)(−4)(40) = 160.
Question 5 : écrire une fonction detLU qui permet de calculer le déterminant
d’une matrice A.
(d) Application pour le calcul de l’inverse d’une matrice : Le calcul ex-
plicite de l’inverse d’une matrice, noté A−1 , peut être effectué en utilisant la

2
 décomposition LU comme suit : Les vecteurs colonnes sont les solutions des
systèmes linéaires : Axi 
= ei , i = 1, ..., n.    
2 2 −3 3 x1 1
    
 4 1 −7 7   x   0 
 2   
Exemple : Ax = e1 ⇒  = ⇒


 −4 13 2 1   x3   0 
    
4 13 −7 14 x4 0
      
1 0 0 0 y 1 1
  1     
 4 1 0 0  y   0   −2 
 2   
= ⇒y=  et
  
 
 −4 1 1 0   y3   0   1 
      
4 13 −7 1 y4 0 11
      
2 2 −3 3 x1 1 −9/40
      
 0 1 −7 7   x   −2   1/40 
 2  
= ⇒x=
   
  
 0 0 2 1   x3   1   1/40 
      
0 0 0 14 x4 11 11/40
      
2 2 −3 3 x1 0 1/40
      
 4 1 −7 7   x   1   1/40 
 2   
Ax = e2 ⇒  = ⇒x= .
  

 −4 13 2 1   x3   0   11/40 
      
4 13 −7 14 x4 0 −9/40
 
1/40
 
 11/40 
De même pour Ax = e3 on trouve, x =   et
 
 −9/40 
 
1/40
   
11/40 −9/40 1/40 1/40 11/40
   
 −9/40   1/40 1/40 11/40 −9/40 
−1
Ax = e4 on trouve, x =  . Donc A = .
   
 
 1/40   1/40 11/40 −9/40 1/40 
   
1/40 11/40 −9/40 1/40 1/40
Travail demandé :
a) Donner le principe des deux décompositions : QR et Cholesky.
b) Choisit l’un des algorithmes qui réalise la décomposition QR (Givens, Gram-
Schmidt, Householder algorithme) puis écrire une fonction qui permet de faire la
decomposition QR.
c) Donner quatres applications de la décomposition QR (avec explication)
d) écrire deux fonctions qui permet de réalisé deux applications.