Nous allons montrer que moyennant une hypothèse souvent satisfaite, on peut
calculer efficacement des matrices L et U telle que A = LU .
Recherche de la factorisation
On dit qu’une matrice A possède une factorisation LU s’il existe une matrice L
triangulaire inférieure à coefficients diagonaux tous égaux à 1 et une matrice U triangulaire supérieure, telles que A = LU (l’appellation « LU » vient de l’anglais « lower
triangular » et « upper triangular »).
Notation : Si M est une matrice carrée d’ordre n et si k est un entier tel que
1 k n, notons M
(k) la matrice carrée de taille k formée avec les k premières
lignes et les k premières colonnes de M .
Ainsi par exemple, pour L =
1 0 0
21 1 0
31 32 1
et U =
u 11 u 12 u 13
0 u 22 u 23
0 0 u 33
, on a
L
(1) = [ 1 ]
U
(1) = [ u 11 ]
L
(1) U
(1) = [ u 11 ] = (LU )
(1)
L
(2) =
1 0
21 1
U
(2) =
u 11 u 12
0 u 22
L
(2) U
(2) =
u 11
u 12
21 u 11 21 u 12 + u 22
= (LU )
(2)
et plus généralement, pour des matrices L et U de taille quelconque, on a L
(k) U
(k) =
(LU )
(k) .
Si A = LU , alors L et U sont inversibles (car A est inversible), donc leurs coefficients
diagonaux sont tous non nuls. Par suite, les matrices L
(k) et U
(k) sont inversibles et
le déterminant de A
(k) = (LU )
(k) = L
(k) U
(k) est non nul. Pour que la matrice A se
factorise en LU , il faut donc que les déterminants des matrices A
(k) soient tous non
nuls. La proposition suivante affirme que cette condition est aussi suffisante.
Proposition. Soit A une matrice inversible. Si toutes les matrices A
(k) ont un déterminant non nul, alors A possède une factorisation LU unique.
Démonstration. Décomposons A sous la forme A =
A
P
Q a
, où A
est carrée de taille n−1,
P est une matrice-colonne à n−1 lignes, Q est une matrice-ligne à n−1 colonnes et a ∈ R.
Cherchons aussi L et U sous la forme L =
L
0
X 1
et U =
U
Y
0 u
. L’égalité LU = A équivaut à
L
U
=A
, L
Y =P , XU
=Q et XY +u=a. Pour montrer l’existence de L et U , raisonnons par
récurrence sur la taille de la matrice A. Les matrices A
(1) =A
(1) ,A
(2) =A
(2) ,. . .,A
(n−1) =A
(n−1)
ayant leur déterminant non nul, la décomposition A
= L
U
existe par hypothèse de récurrence. Les équations L
Y = P et XU
= Q ont une solution car L
et U
sont inversibles et
l’on pose u = a − XY : cela définit les matrices L et U . Si A = ˜
L ˜
U est une (autre) factorisation
LU, alors la matrice L
−1 ˜
L = U ˜
U
−1 est triangulaire supérieure et triangulaire inférieure avec
des 1 sur la diagonale, donc L
−1 ˜
L = U ˜
U
−1 = I n et ˜
L = L, ˜
U = U .
Chapitre 8 – DES M ´
ETHODES NUM ´
ERIQUES – 247
calculer efficacement des matrices L et U telle que A = LU .
Recherche de la factorisation
On dit qu’une matrice A possède une factorisation LU s’il existe une matrice L
triangulaire inférieure à coefficients diagonaux tous égaux à 1 et une matrice U triangulaire supérieure, telles que A = LU (l’appellation « LU » vient de l’anglais « lower
triangular » et « upper triangular »).
Notation : Si M est une matrice carrée d’ordre n et si k est un entier tel que
1 k n, notons M
(k) la matrice carrée de taille k formée avec les k premières
lignes et les k premières colonnes de M .
Ainsi par exemple, pour L =
1 0 0
21 1 0
31 32 1
et U =
u 11 u 12 u 13
0 u 22 u 23
0 0 u 33
, on a
L
(1) = [ 1 ]
U
(1) = [ u 11 ]
L
(1) U
(1) = [ u 11 ] = (LU )
(1)
L
(2) =
1 0
21 1
U
(2) =
u 11 u 12
0 u 22
L
(2) U
(2) =
u 11
u 12
21 u 11 21 u 12 + u 22
= (LU )
(2)
et plus généralement, pour des matrices L et U de taille quelconque, on a L
(k) U
(k) =
(LU )
(k) .
Si A = LU , alors L et U sont inversibles (car A est inversible), donc leurs coefficients
diagonaux sont tous non nuls. Par suite, les matrices L
(k) et U
(k) sont inversibles et
le déterminant de A
(k) = (LU )
(k) = L
(k) U
(k) est non nul. Pour que la matrice A se
factorise en LU , il faut donc que les déterminants des matrices A
(k) soient tous non
nuls. La proposition suivante affirme que cette condition est aussi suffisante.
Proposition. Soit A une matrice inversible. Si toutes les matrices A
(k) ont un déterminant non nul, alors A possède une factorisation LU unique.
Démonstration. Décomposons A sous la forme A =
A
P
Q a
, où A
est carrée de taille n−1,
P est une matrice-colonne à n−1 lignes, Q est une matrice-ligne à n−1 colonnes et a ∈ R.
Cherchons aussi L et U sous la forme L =
L
0
X 1
et U =
U
Y
0 u
. L’égalité LU = A équivaut à
L
U
=A
, L
Y =P , XU
=Q et XY +u=a. Pour montrer l’existence de L et U , raisonnons par
récurrence sur la taille de la matrice A. Les matrices A
(1) =A
(1) ,A
(2) =A
(2) ,. . .,A
(n−1) =A
(n−1)
ayant leur déterminant non nul, la décomposition A
= L
U
existe par hypothèse de récurrence. Les équations L
Y = P et XU
= Q ont une solution car L
et U
sont inversibles et
l’on pose u = a − XY : cela définit les matrices L et U . Si A = ˜
L ˜
U est une (autre) factorisation
LU, alors la matrice L
−1 ˜
L = U ˜
U
−1 est triangulaire supérieure et triangulaire inférieure avec
des 1 sur la diagonale, donc L
−1 ˜
L = U ˜
U
−1 = I n et ˜
L = L, ˜
U = U .
Chapitre 8 – DES M ´
ETHODES NUM ´
ERIQUES – 247