Décomposition LU
décomposition LU
Unité Pédagogique de Mathématiques
Module : Analyse Numérique (AN)
Novembre 2020
1/17
décomposition LU
La décomposition LU :
Soit S un système linéaire défini par
(S) : AX = b
où A est une matrice dont tous les mineurs principaux sont non
nuls.
• Le mineur principal Mp,p de A est le déterminant de la
sous-matrice de A formée des p premières lignes et p premières
colonnes
2/17
décomposition LU
Exemple :
Soit A la matrice suivante :
A =
5
−1 2
4
1
0 −1
9
2
Alors
M1,1 = (cid:12)
(cid:12)
(cid:12)
5(cid:12)
(cid:12) , M2,2 =
(cid:12)
(cid:12)
0
5
(cid:12)
(cid:12)
−1 2
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
,
et M3,3 = det(A)
sont les mineurs principaux de la matrice A.
• Remarque : Si A est d’ordre n alors elle admet n mineurs
principaux.
3/17
décomposition LU
. Le principe de la méthode est de se ramener à deux
systèmes triangulaires en appliquant les étapes suivantes:
1 Décomposition de A : Trouver les matrices L et U vérifiant
A = LU où :
L est une matrice triangulaire inférieure dont les coefficients
de la diagonale sont égaux à 1.
et
U est une matrice triangulaire supérieure.
4/17
décomposition LU
2 Résolution du système triangulaire inférieur
LY = b.(Descente)
3 Résolution du système triangulaire supérieur UX = Y .
AX = b
Décomposition LU
−−−−−−−−−−−−−−→ A = L UX
|{z}
Y
= b →
(LY = b
UX = Y
5/17
décomposition LU
. L’existence de la décomposition LU est assurée par le
théorème suivant :
Théorème :
Soit A ∈ Mn(R) une matrice dont tous les mineurs principaux
Publicité
sont non nuls alors il existe un unique couple de matrices
(L, U), avec U triangulaire supérieure, et L triangulaire
inférieure dont les coefficients de la diagonale sont égaux à 1.
(i.e. li,i = 1), vérifiant A = LU.
6/17
décomposition LU
Si A une matrice dont tous les mineurs principaux sont non nuls
⇒ ∃ deux matrices
L triangulaire inférieure dont les coefficients
de la diagonale sont égaux à 1.
U triangulaire supérieure.
vérifiant
A=LU
7/17
décomposition LU
Étude d’un exemple :
Soit (S) un système défini par : (S) : AX = b où A, b et X sont
les matrices suivantes :
3
1
1 −3
1
1
1
1 −3
,
b =
1
−3
1
et X =
x1
x2
x3
A =
8/17
décomposition LU
1 Existence de la décomposition LU :
A est une matrice dont tous les mineurs principaux sont non nuls.
En effet,
det(3) = 3 6= 0
det
det
!
3
1
1 −3
= −8 6= 0
3
1
1 −3
1
1
1
1 −3
= det A = 32 6= 0
Publicité
Donc, A admet une décomposition LU.
9/17
décomposition LU
2 Calculons les matrices L et U de la factorisation de A :
D’après ce qui précède A = LU avec
u1,1 u1,2 u1,3
0
u2,2 u2,3
0
0
u3,3
1
l2,1
l3,1
, U =
0
0
1
0
l3,2 1
L =
10/17
décomposition LU
A = LU =
u1,1
l2,1u1,1
l3,1u1,1
u1,2
l2,1u1,2
l3,1u1,2 + l3,2u2,2
u1,3
l2,1u1,3 + u2,3
l3,1u1,3 + l3,2u2,3 + u3,3
11/17
décomposition LU
Alors par identification :
• 1 × u1,1 = 3 ⇒ u1,1 = 3
• 1 × u1,2 = 1 ⇒ u1,2 = 1
• 1 × u1,3 = 1 ⇒ u1,3 = 1
• l2,1 × 3 = 1 ⇒ l2,1 = 1
3
• 1
• 1
• 3 × l3,1 = 1 ⇒ l3,1 = 1
3
• 1
3 × 1 + l3,2 × − 10
3 × 1 − 1
5 × 2
• 1
3
3
3 × 1 + 1 × u2,2 = −3 ⇒ u2,2 = − 10
3 × 1 + 1 × u2,3 = 1 ⇒ u2,3 = 2
3
3
= 1 ⇒ l3,2 = − 1
5
+ 1 × u3,3 = −3 ⇒ u3,3 = − 48
15
12/17
décomposition LU
1
1
3
1
0
1
3 − 1
5
Publicité
0
0
, U =
1
3
1
1
0 − 10
2
3
3
0 − 48
0
15
On obtient :
L =
13/17
décomposition LU
3 Cherchons Y la solution du système linéaire LY = b :
1
1
3
1
0
1
3 − 1
5
0
0
1
y1
y2
y3
= b =
1
−3
1
⇒
y1
y2
y3
=
1
− 10
3
0
Publicité
14/17
décomposition LU
4 Cherchons X la solution du système linéaire UX = Y :
3
1
1
0 − 10
2
3
3
0 − 48
0
15
x1
x2
x3
=
1
− 10
3
0
⇒ X =
0
1
0
15/17
décomposition LU
Remarques :
1 La matrice U est exactement égale à la matrice triangulaire
supérieure obtenue en appliquant la méthode de pivot de
Gauss.
16/17
décomposition LU
Remarques :
2 La matrice L est une matrice triangulaire inférieure avec des 1
à la diagonale et les coefficients l2,1, l3,1 et l3,2 s’obtiennent à
partir des transformations de ligne de gauss précédentes de la
manière suivante :
L2 ←− L2 −
L3 ←− L3 −
(cid:19)
(cid:19)
(cid:18) 1
3
(cid:18) 1
3
L1 (cid:121) l2,1 =
L1 (cid:121) l3,1 =
1
3
1
3
L3 ←− L3 +
(cid:19)
(cid:18) 1
5
L2 (cid:121) l3,2 = −
1
5
17/17
décomposition LU