78
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
D´ emonstration. Nous pourrions montrer l’existence de la factorisation LU en
suivant les ´ etapes de la m´ ethode de Gauss. Nous pr´ ef´ erons adopter ici une autre
approche que nous r´ eutiliserons dans les prochaines sections et qui nous permet de
prouver en mˆ eme temps l’existence et l’unicit´ e.
Supposons les sous-matrices principales Ai de A inversibles pour i = 1, . . . , n − 1
et montrons par r´ ecurrence sur i l’existence et l’unicit´ e de la factorisation LU de
A(= An) avec lii = 1 pour i = 1, . . . , n.
La propri´ et´ e est ´ evidemment vraie si i = 1. Montrons que s’il existe une unique
factorisation LU de Ai−1 de la forme Ai−1 = L
(i−1) U
(i−1) avec l
(i−1)
kk
= 1 pour k =
1, . . . , i − 1, alors il existe une unique factorisation pour Ai. Pour cela, d´ ecomposons
Ai en blocs
Ai =
⎡
⎣
Ai−1 c
d
T
aii
⎤
⎦
et cherchons une factorisation de Ai de la forme
⎡
⎣
Ai−1
c
d
T
aii
⎤
⎦ = L
(i) U
(i) =
⎡
⎣
L
(i−1)
0
l
T
1
⎤
⎦
⎡
⎣
U
(i−1)
u
0
T
uii
⎤
⎦ ,
(3.35)
o` u l’on a ´ egalement d´ ecompos´ e en blocs les facteurs L
(i) et U
(i) . En calculant le
produit de ces deux matrices et en identifiant par blocs les ´ el´ ements de Ai, on en
d´ eduit que les vecteurs l et u sont les solutions des syst` emes lin´ eaires L
(i−1) u = c,
l
T U
(i−1) = d
T .
Or, 0 = d´ et(Ai−1) = d´ et(L
(i−1) )d´ et(U
(i−1) ), les matrices L
(i−1) et U
(i−1) sont
donc inversibles. Par cons´ equent, u et l existent et sont uniques.
Ainsi, il existe une unique factorisation de Ai, et uii est l’unique solution de
l’´ equation uii = aii − l
T u. Ce qui ach` eve la preuve par r´ ecurrence.
Il reste maintenant `
a prouver que si la factorisation existe et est unique alors les
n − 1 premi` eres sous-matrices principales de A sont inversibles. Nous distinguerons
les cas o` u A est singuli` ere et o` u A est inversible.
Commen¸ cons par le second cas, et supposons l’existence et l’unicit´ e de la factorisation LU de A avec lii = 1 pour i = 1, . . . , n. Alors, d’apr` es (3.35), on a
Ai = L
(i) U
(i) pour i = 1, . . . , n, et donc
d´ et(Ai) = d´ et(L
(i) )d´ et(U
(i) ) = d´ et(U
(i) ) = u11u22 . . . uii.
(3.36)
En prenant i = n et en utilisant le fait que A est inversible, on en d´ eduit que
u11u22 . . . unn = 0, et donc d´ et(Ai) = u11u22 . . . uii = 0 pour i = 1, . . . , n − 1.
Consid´ erons maintenant le cas o` u A est une matrice singuli` ere et supposons
qu’au moins un terme diagonal de U soit ´ egal `
a z´ ero. Notons ukk le terme nul de U
dont l’indice k est le plus petit. D’apr` es (3.35), la factorisation peut ˆ etre effectu´ ee
sans probl` eme jusqu’` a la k + 1-i` eme ´ etape. A partir de cette ´ etape, la matrice U
(k)
´ etant singuli` ere, on perd l’existence et l’unicit´ e du vecteur l
T . On perd donc aussi
l’unicit´ e de la factorisation. Afin que ceci ne se produise pas avant la factorisation
compl` ete de la matrice A, les termes ukk doivent ˆ etre tous non nuls jusqu’` a l’indice
k = n − 1 inclus, et donc, d’apr` es (3.36), toutes les sous-matrices principales Ak
doivent ˆ etre inversibles pour k = 1, . . . , n − 1.
3
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
D´ emonstration. Nous pourrions montrer l’existence de la factorisation LU en
suivant les ´ etapes de la m´ ethode de Gauss. Nous pr´ ef´ erons adopter ici une autre
approche que nous r´ eutiliserons dans les prochaines sections et qui nous permet de
prouver en mˆ eme temps l’existence et l’unicit´ e.
Supposons les sous-matrices principales Ai de A inversibles pour i = 1, . . . , n − 1
et montrons par r´ ecurrence sur i l’existence et l’unicit´ e de la factorisation LU de
A(= An) avec lii = 1 pour i = 1, . . . , n.
La propri´ et´ e est ´ evidemment vraie si i = 1. Montrons que s’il existe une unique
factorisation LU de Ai−1 de la forme Ai−1 = L
(i−1) U
(i−1) avec l
(i−1)
kk
= 1 pour k =
1, . . . , i − 1, alors il existe une unique factorisation pour Ai. Pour cela, d´ ecomposons
Ai en blocs
Ai =
⎡
⎣
Ai−1 c
d
T
aii
⎤
⎦
et cherchons une factorisation de Ai de la forme
⎡
⎣
Ai−1
c
d
T
aii
⎤
⎦ = L
(i) U
(i) =
⎡
⎣
L
(i−1)
0
l
T
1
⎤
⎦
⎡
⎣
U
(i−1)
u
0
T
uii
⎤
⎦ ,
(3.35)
o` u l’on a ´ egalement d´ ecompos´ e en blocs les facteurs L
(i) et U
(i) . En calculant le
produit de ces deux matrices et en identifiant par blocs les ´ el´ ements de Ai, on en
d´ eduit que les vecteurs l et u sont les solutions des syst` emes lin´ eaires L
(i−1) u = c,
l
T U
(i−1) = d
T .
Or, 0 = d´ et(Ai−1) = d´ et(L
(i−1) )d´ et(U
(i−1) ), les matrices L
(i−1) et U
(i−1) sont
donc inversibles. Par cons´ equent, u et l existent et sont uniques.
Ainsi, il existe une unique factorisation de Ai, et uii est l’unique solution de
l’´ equation uii = aii − l
T u. Ce qui ach` eve la preuve par r´ ecurrence.
Il reste maintenant `
a prouver que si la factorisation existe et est unique alors les
n − 1 premi` eres sous-matrices principales de A sont inversibles. Nous distinguerons
les cas o` u A est singuli` ere et o` u A est inversible.
Commen¸ cons par le second cas, et supposons l’existence et l’unicit´ e de la factorisation LU de A avec lii = 1 pour i = 1, . . . , n. Alors, d’apr` es (3.35), on a
Ai = L
(i) U
(i) pour i = 1, . . . , n, et donc
d´ et(Ai) = d´ et(L
(i) )d´ et(U
(i) ) = d´ et(U
(i) ) = u11u22 . . . uii.
(3.36)
En prenant i = n et en utilisant le fait que A est inversible, on en d´ eduit que
u11u22 . . . unn = 0, et donc d´ et(Ai) = u11u22 . . . uii = 0 pour i = 1, . . . , n − 1.
Consid´ erons maintenant le cas o` u A est une matrice singuli` ere et supposons
qu’au moins un terme diagonal de U soit ´ egal `
a z´ ero. Notons ukk le terme nul de U
dont l’indice k est le plus petit. D’apr` es (3.35), la factorisation peut ˆ etre effectu´ ee
sans probl` eme jusqu’` a la k + 1-i` eme ´ etape. A partir de cette ´ etape, la matrice U
(k)
´ etant singuli` ere, on perd l’existence et l’unicit´ e du vecteur l
T . On perd donc aussi
l’unicit´ e de la factorisation. Afin que ceci ne se produise pas avant la factorisation
compl` ete de la matrice A, les termes ukk doivent ˆ etre tous non nuls jusqu’` a l’indice
k = n − 1 inclus, et donc, d’apr` es (3.36), toutes les sous-matrices principales Ak
doivent ˆ etre inversibles pour k = 1, . . . , n − 1.
3