Méthode de la décomposition LU

Principe de la méthode:
1. Décomposition de la matrice A de façon à la mettre sous la forme A = LU où L est une matrice
triangulaire inférieure unitaire et U est une matrice triangulaire supérieure.

2. Résolution : Le système AX = b devient


LY = b
AX = b ⇐⇒ LU X ⇐⇒
|{z} UX = Y
Y

donc la résolution du système AX = b revient à la résolution de deux systèmes triangulaires.

Théorème 6.1. Soit A une matrice telle que les sous matrices principales A[k] = (aij )1≤i,j≤k de
A soient inversibles pour tous 1 ≤ k ≤ n, alors il existe une matrice L = (lij )1≤i,j≤n triangulaire
inférieure telle que lii = 1, i = 1, n et une matrice triangulaire supérieure U telle que A = LU.
De plus cette décomposition est unique.

Démonstration. Existence : Montrons que tous les pivots d'élimination de Gauss sont non nuls,
(k)
c'est à dire akk 6= 0 pour 1 ≤ k ≤ n − 1. On le démontre par récurrence.
(1) (1)
Le premier pivot a11 est forcément non nul car a11 = det(A[1] ) 6= 0.
(k) (r)
Supposons que akk 6= 0 pour 1 ≤ k ≤ r − 1 et montrons que arr 6= 0.
(1) (2) (r−1) (r)
On a det(A[r] ) = a11 a22 . . . ar−1,r−1 arr . Or d'une part, par hypothèse det(A[r] ) est diérent de
(k) (r)
zéro et d'autre part, par hypothèse de récurrence akk 6= 0 pour 1 ≤ k ≤ r − 1. Donc arr est
aussi diérent de zéro.
Unicité : Soit A = L1 U1 = L2 U2 , d'où U1 U2−1 = L−1
1 L2 = D.
Comme U1 U2 est une matrice triangulaire supérieure et L−1
−1
1 L2 est une matrice triangulaire
inférieure et D a des 1 sur la diagonale, alors D = In ce qui implique que U1 = U2 et L1 = L2 .

Détermination des matrices L et U

a) En utilisant l'algorithme d'élimination de Gauss ordinaire : Au premier pas d'élimina-
tion de Gauss, on trouve

 
1
 −α21
 ..
. 0 

A(2) = E (1) .A(1) où E (1) =  −α31 1
 

0
 . ..

 .. . 
−αn1 1
6.2. MÉTHODES DIRECTES 69

Au deuxième pas, on trouve

 
1
 0 1 0 
 ..
 
..
 . −α32 .

(3) (2) (2) (2)

A =E .A où E =
 ... −α 0 ..

.

 42 
 . ..
.

 . . 
0 −αn2 1
de la même manière au k -ième pas d'élimination, on obtient
 
1


..
. 0 

1
 
 
−αk+1,k
(k+1) (k) (k) (k)
 
A =E .A où E = 
0 ..
 

 −αk+2,k .


..
0
 
 . 
−αnk 1
ce qui nous donne
A(n) = E (n−1) .A(n−1)
= E (n−1) .E (n−2) .A(n−2)
= E (n−1) .E (n−2) . . . E (1) .A.
Posons U = A(n) et L−1 = E (n−1) .E (n−2) · · · E (1)
alors U = L−1 A d'où A = LU où

−1
L = E (n−1) .E (n−2) . . . E (2) .E (1)

−1
−1
−1
= E (1) . E (2) . . . E (n−1)
 
1
 α21 1 0 
.
 
=  α31 α32 . .
 

 . .. .. ..

 .. . . . 
αn1 αn2 · · · αn,n−1 1
et
(1) (1) (1)
 
a11 a12 · · · · · · a1n
(2) (2)

 a22 · · · · · · a2n 
 .. .. 
U = A(n) =
 . . 

0 .. .. 

 . . 
(n)
ann
b) En appliquant l'algorithme de la méthode :
En connaissant A = (aij )1≤i,j≤n , on écrit l'égalité A = LU
a11 · · · a1j · · · a1n u11 u12 · · · · · · u1n
    
1
 ..
 .
..
.
.. 
. 
 l21 1 0  u22 · · · · · · u2n 
. .. ..
  
..
 ai1 · · · aij · · · ain  =  l31 . .
    
 
0
 . .. ..   ... .. .. . ..
   
 .. . . . .  .. . 
an1 · · · an2 · · · ann ln1 · · · ln,n−1 1 unn
70 CHAPITRE 6. RÉSOLUTION DES SYSTÈMES LINÉAIRES

n(n+1) n(n−1)
(U contient 2
éléments et L contient 2
éléments). Par identication on obtient un
2 2
système linéaire de n équations à n inconnues. En résolvant le système obtenu dans des cas
particuliers (n = 2, 3, 4), on constate que la détermination des éléments de L et U cherchés se
fait suivant l'algorithme général :


 lii = 1, 1 ≤ i ≤ n;



 
 u1j = a1j , 1 ≤ j ≤ n;







ai1

li1 = , 2 ≤ i ≤ n;

 
 u11

  m−1
 P
u = a − lmk .ukj , m ≤ j ≤ n;

 
mj mj
 

 

  k=1
2 ≤ m ≤ n.



  

 
 m−1
P
 lim = aim − lik .ukm /umm , m + 1 ≤ i ≤ n;

 


k=1

Coût de la méthode
n
(m − 1)(n − m + 1) = O( 61 n3 )
P
 Calcul de U: coût(×)=coût(+)=
m=1
n−1
(m − 1)(n − m) = O( 16 n3 )
P
 Calcul de L: coût(×)=coût(+)=
m=1
n
P n(n−1)
et coût(/)= (n − m) = 2
.
m=1
D'où, coût total = O( 23 n3 )=coût de Gauss.

Utilité de la détermination LU
Calcul de déterminant Grâce à la factorisation LU, on peut calculer le déterminant d'une matrice
carrée avec O( 23 n3 ) opérations, vu que

n
Y
det(A) = det(L) × det(U ) = det(U ) = ukk .
k=1

Résolution : Supposons qu'on veut résoudre le système AX = b. Décomposons A

LU, sous forme
alors AX = b devient (LU )X = b ou encore L(U X) = b. Posons Y = U X, on
cherche alors Y
tel que LY = b est un système triangulaire inférieur qu'on résout par la méthode descendante. Y
étant trouvé, on cherche X tel que U X = Y est un système triangulaire supérieur qu'on résout
par la méthode ascendante.
Coût total : coût(décomposition LU)+coût(résolution de deux systèmes triangulaires), c'est à
dire, Coût total=O( 32 n3 ) + 2n2 = O( 23 n3 ).
Calcul de l'inverse d'une matrice : Soit A une matrice carrée inversible d'ordre n,
(1) (n) −1 −1
notons par v , . . . , v les colonnes de sa matrice inverse A , i.e. A = (v (1) , . . . , v (n) ).
−1
La relation A.A = In se traduit par les n systèmes linéaires suivants :
Av (k) = e(k) , 1 ≤ k ≤ n, (6.3)
où e(k)
est le vecteur colonne ayant toutes les composantes nulles sauf la k−ième composonte
(k)
qui est 1, e = (0, . . . , 1, . . . , 0)t . Une fois connues les matrices L et U qui décomposent la
matrice A, résoudre les n systèmes (6.3) gouvernés par la même matrice A.
6.2. MÉTHODES DIRECTES 71

Exemple 6.3. Soit le système linéaire suivant

    
2 −5 1 x1 12
 −1 3 −1   x2  =  −8 
3 −4 2 x3 16

A l'aide de la décomposition LU de A:
1. Résoudre le système donné en déterminant les matrices L et U :

a) En utilisant l'algorithme d'élimination de Gauss ordinaire.

b) En appliquant l'algorithme de la méthode.

2. Calculer l'inverse de A.