PCSI 1 - Stanislas - Informatique (2esem.) - Chap.6 - Résolution des systèmes linéaires A.

MARTIN

IV. Pour aller plus loin : la décomposition LU IV.2. Construction

Les matrices L et U sont obtenues progressivement par l’algorithme du pivot
IV.1. Principe de Gauss, dont chaque étape peut se ramener à une multiplication à gauche par
On se place dans le cadre de résolutions multiples d’un même système où seul une matrice.
le second membre change : Ô Soit A(0) = A la matrice initiale. La première étape du pivot de Gauss peut
A X = bp pour p = 1, M être mise sous la forme
Deux solutions sont possibles :  
1 0 0 ... 0
— Si tous les seconds membres bp sont connus à l’avance, on applique l’algo-  a(0) 
rithme en traitant tout les seconds membres en même temps. On n’inverse  − 10 1 0 ... 0
 a(0) 
00
donc qu’une seule fois la matrice A. 
 a(0)

A(1) = P (0) A(0) P (0) − ...

avec =  a(0)
20
0 1 0 .
— Sinon, on trouve un moyen de stocker les opérations conduisant à l’in-

00 
version de la matrice A. C’est le principe de la décomposition LU.
 .. .. .. .. .. 

 . . . . .

 (0) 
Théorème : (complément) Si les coefficients de la matrice A sont tirés au aN −1 0
− (0) 0 0 ... 1
hasard dans K, alors la probabilité est de 1 de trouver une matrice A : a0 0

• qui soit inversible ; (0)

ai 0
• pour laquelle on n’ait jamais à permuter les lignes ou les colonnes lors de la On retrouve pour chaque ligne i la relation Li ← Li − (0)
L0 .
triangularisation par le pivot de Gauss (le pivot trouvé sera toujours non a0 0
nul) ; Ô La k-ième étape du pivot de Gauss peut être mise sous la forme

Propriété - Définition : Décomposition LU

 
1 ... 0 0 ... 0
Si les conditions ci-dessus sont réunies, alors la matrice A admet une dé- . .. .. . . .. 
. ..
composition LU : il existe deux matrices L et U inversibles, telles que . .

. . . .
L est triangulaire inférieure (Lower), U est triangulaire supérieure
 
0 ... 1 0 ... 0
 
(Upper), et  (k−1)

ak+1 k
A = LU
 
A(k) = P (k−1) A(k−1) avec P (k−1) = 0
 ... − (k−1) 1 ... 0 .
ak k
 (k−1) 
ak+2 k
0 ... − 0 ... 0
 
(k−1)
Conséquence : Si cette décomposition LU est connue, alors la résolution du  ak k 
système linéaire AX = B se réduit à la résolution de deux systèmes
 .. .. .. .. 
0 ... . . . .
triangulaires, donc elle est de complexité O(N 2 ).
 
 (k−1) 
aN −1 k
0 ... − (k−1) 0 ... 1
ak k
Remarque : Si par malheur on tombe sur des zéros sur la diagonale (méthode
du pivot partiel ou global), alors on peut toutefois (si A est tout de même (k−1)
inversible) obtenir la décomposition plus générale (décomposition de Bru- ai k
On retrouve pour chaque ligne i la relation Li ← Li − (k−1)
L0 .
hat) ak k
A = L Tσ U ou A = L U Tσ0 Ô Par récurrence simple, on obtient finalement la matrice triangulaire supérieure
où Tσ et Tσ0 sont des matrices de permutation. On garde la même com-
plexité. A(N −1) = P (N −2) P (N −3) . . . P (0) A(0) = U .
5
PCSI 1 - Stanislas - Informatique (2esem.) - Chap.6 - Résolution des systèmes linéaires A. MARTIN

Ô Les matrices P (k) sont des matrices triangulaires inférieures. Or on peut mon-
trer que le produit de 2 matrices triangulaires inférieures reste triangulaire       
inférieure. De même l’inverse d’une matrice triangulaire inférieure est trian- 10 7 8 7 x0 32 1 0 0 0
      
gulaire inférieure. 0 0,1 0,4 0,1 x1 
   = 0,6
  0 1 0 0
En notant L(k) l’inverse de la matrice P (k) , on obtient alors
  
0 0,4 3,6 3,4 x2  7,4 L2 ← L2 − 4L1 0 4 1 0
      

0 0,1 3,4 5,1 x3 8,6 L3 ← L3 − L1 0 1 0 1

A = A(0) = (P (N −2) P (N −3) ...P (0) )−1 U = (L(0) L(1) ...L(N −2) ) U = LU | {z }
L(1)
| {z }
L

      
(k) (k)
10 7 8 7 x0 32 1 0 0 0
Ô Les matrices L s’obtiennent très simplement à partir des P en mettant       
0 0,1 0,4 0,1 x1 
   = 0,6
inversant les signes des termes extra-diagonaux :   0 1 0 0
  
0 0 2 3  x2   5  0 0 1 0
      
3 3
L3 ← L3 −
 
1 ... 0 0 ... 0 0 0 3 5 x3 8 L
2 2
0 0 2
1
. | {z }
. .. .. .. . . ..  L(2)
. .

. . . .
 
0 ... 1 0 ... 0
 
    
 −1

 (k−1)
ak+1 k

 10 7 8 7 x0 32
L(k−1) = P (k−1) = 0
 ... + (k−1) 1 ... 0 .
    
0 0,1 0,4 0,1 x1 
ak k
   = 0,6
 
 (k−1)  
ak+2 k
0 ... + 0 ... 0 0 0 2 3  x2   5 
      
(k−1)
 ak k 
 .. .. .. ..  0 0 0 0,5 x3 0,5
0
 ... . . . . | {z }
 (k−1)  U
aN −1 k
0 ... + (k−1) 0 ... 1
ak k
L(1) L(2)
z }| { z }| {
On en déduit l’existence de la décomposition LU, qui peut être stoquée une    
1 0 0 0 1 0 0 0
fois pour toute puisque la matrice A du système ne change pas.    
0 1 0 0 0 1 0 0
   
0 4 1 0 0 0 1 0
   
3
Exemple : Soit le système linéaire 4 × 4 suivant 0 1 0 1 0 0 2
1
Calcul de L :      
1 0 0 0 1 0 0 0 1 0 0 0
       7  7  7 
10 7 8 x07 32 1 0 0 0  10 1 0 0  10 1 0 0  10 1 0 0
     
       8 8 8
7 7 0 1 0 4 1 0 4 1 0
  
5  x1  23 L1 ← L1 − 10 L0
7 5 6     1 0 0  10  10  10
 10
  =  
 
7 7 7 3
0 0 1 1 0 1 1 1
  
8 8
 x2  33 L2 ← L2 − 10 L0
8 6 10 9      0 1 0 10 10 10 2
  10  | {z } | {z }
7 7 L(0) L
7 5 9 10 x3 31 L3 ← L3 − 10 L0 10 0 0 1
Reste à vérifier que le produit LU = A...
| {z }
L(0)