3.3 M´ ethode d’´ elimination de Gauss et factorisation LU
77
Les matrices M k sont des matrices triangulaires inf´ erieures dont les coefficients
diagonaux valent 1 et dont l’inverse est donn´ e par
M
−1
k = 2I n − M k = I n + m k e
T
k .
(3.33)
Les produits (m i e
T
i )(m j e
T
j ) ´ etant nuls pour i = j, on a :
A = M
−1
1 M
−1
2 . . . M
−1
n−1 U
= (I n + m 1 e
T
1 )(I n + m 2 e
T
2 ) . . . (I n + m n−1 e
T
n−1 )U
=
I n +
n−1
i=1
m i e
T
i
U
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1
0
. . .
. . .
0
m 21
1
. . .
. . .
m 32
. . .
. . .
. . .
. . .
. . .
0
m n1 m n2 . . . m n,n−1 1
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
U.
(3.34)
Posons L = (M n−1 M n−2 . . . M 1 )
−1 = M
−1
1 . . . M
−1
n−1 , on a alors
A = LU.
Remarquons que, d’apr` es (3.34), les ´ el´ ements sous-diagonaux de L sont les
multiplicateurs m ik g´ en´ er´ es par la m´ ethode de Gauss, tandis que les termes
diagonaux sont ´ egaux `
a 1.
Une fois calcul´ ees les matrices L et U, r´ esoudre le syst` eme lin´ eaire consiste
simplement ` a r´ esoudre successivement les deux syst` emes triangulaires
Ly = b ,
Ux = y .
Le coˆ ut de la factorisation est ´ evidemment le mˆ eme que celui de la m´ ethode
de Gauss.
Le r´ esultat suivant ´ etablit un lien entre les mineurs principaux d’une matrice et sa factorisation LU induite par la m´ ethode de Gauss.
Th´ eor` eme 3.4 Soit A ∈ R
n×n . La factorisation LU de A avec l ii = 1 pour
i = 1, . . ., n existe et est unique si et seulement si les sous-matrices principales
A i de A d’ordre i = 1, . . ., n − 1 sont inversibles.