84
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
d´ ecomposition LU de A, et poser M
T =D
−1 U. N´ eanmoins, cet algorithme a
le mˆ eme coˆ ut que la d´ ecomposition LU standard. De mˆ eme, il est aussi possible de calculer les trois matrices de la d´ ecomposition en imposant l’identit´ e
A=LDM
T terme ` a terme.
3.4.2 Matrices sym´ etriques d´ efinies positives : la factorisation
de Cholesky
Comme on l’a d´ ej` a dit plus haut, la factorisation LDM
T se simplifie consid´ erablement quand A est sym´ etrique, car dans ce cas M=L. On obtient alors la
d´ ecomposition LDL
T dont le coˆ ut est d’environ (n
3 /3) flops, soit la moiti´ e du
coˆ ut de la d´ ecomposition LU.
Par exemple, la matrice de Hilbert d’ordre 3 admet la factorisation LDL
T
suivante
H 3 =
⎡
⎢
⎢
⎢
⎣
1
1
2
1
3
1
2
1
3
1
4
1
3
1
4
1
5
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎣
1 0 0
1
2
1 0
1
3
1 1
⎤
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎣
1 0
0
0
1
12
0
0 0
1
180
⎤
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎣
1
1
2
1
3
0 1 1
0 0 1
⎤
⎥
⎥
⎥
⎦
.
Dans le cas o` u A est aussi d´ efinie positive, les termes diagonaux de D dans la
factorisation LDL
T sont strictement positifs. On a de plus le r´ esultat suivant :
Th´ eor` eme 3.6 Soit A ∈ R
n×n une matrice sym´ etrique d´ efinie positive.
Alors, il existe une unique matrice triangulaire sup´ erieure H dont les termes
diagonaux sont strictement positifs telle que
A = H
T H.
(3.41)
Cette factorisation est appel´ ee factorisation de Cholesky et les coefficients h ij
de H
T peuvent ˆ etre calcul´ es comme suit : h 11 =
√
a 11 et, pour i = 2, . . . , n,
h ij =
a ij −
j−1
k=1
h ik h jk
/h jj , j = 1, . . . , i − 1,
h ii =
a ii −
i−1
k=1
h
2
ik
1/2
.
(3.42)
D´ emonstration. Montrons le th´ eor` eme par r´ ecurrence sur la taille i de la matrice (comme dans la preuve du Th´ eor` eme 3.4), en rappelant que si Ai ∈ R
i×i est
sym´ etrique d´ efinie positive, il en est de mˆ eme de toutes ses sous-matrices principales.
Pour i = 1 le r´ esultat est ´ evidemment vrai. Supposons le vrai au rang i − 1 et
montrons le au rang i. Il existe une matrice triangulaire sup´ erieure Hi−1 telle que
Ai−1 = H
T
i−1 Hi−1. D´ ecomposons Ai sous la forme
Ai =
Ai−1 v
v
T
α
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
d´ ecomposition LU de A, et poser M
T =D
−1 U. N´ eanmoins, cet algorithme a
le mˆ eme coˆ ut que la d´ ecomposition LU standard. De mˆ eme, il est aussi possible de calculer les trois matrices de la d´ ecomposition en imposant l’identit´ e
A=LDM
T terme ` a terme.
3.4.2 Matrices sym´ etriques d´ efinies positives : la factorisation
de Cholesky
Comme on l’a d´ ej` a dit plus haut, la factorisation LDM
T se simplifie consid´ erablement quand A est sym´ etrique, car dans ce cas M=L. On obtient alors la
d´ ecomposition LDL
T dont le coˆ ut est d’environ (n
3 /3) flops, soit la moiti´ e du
coˆ ut de la d´ ecomposition LU.
Par exemple, la matrice de Hilbert d’ordre 3 admet la factorisation LDL
T
suivante
H 3 =
⎡
⎢
⎢
⎢
⎣
1
1
2
1
3
1
2
1
3
1
4
1
3
1
4
1
5
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎣
1 0 0
1
2
1 0
1
3
1 1
⎤
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎣
1 0
0
0
1
12
0
0 0
1
180
⎤
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎣
1
1
2
1
3
0 1 1
0 0 1
⎤
⎥
⎥
⎥
⎦
.
Dans le cas o` u A est aussi d´ efinie positive, les termes diagonaux de D dans la
factorisation LDL
T sont strictement positifs. On a de plus le r´ esultat suivant :
Th´ eor` eme 3.6 Soit A ∈ R
n×n une matrice sym´ etrique d´ efinie positive.
Alors, il existe une unique matrice triangulaire sup´ erieure H dont les termes
diagonaux sont strictement positifs telle que
A = H
T H.
(3.41)
Cette factorisation est appel´ ee factorisation de Cholesky et les coefficients h ij
de H
T peuvent ˆ etre calcul´ es comme suit : h 11 =
√
a 11 et, pour i = 2, . . . , n,
h ij =
a ij −
j−1
k=1
h ik h jk
/h jj , j = 1, . . . , i − 1,
h ii =
a ii −
i−1
k=1
h
2
ik
1/2
.
(3.42)
D´ emonstration. Montrons le th´ eor` eme par r´ ecurrence sur la taille i de la matrice (comme dans la preuve du Th´ eor` eme 3.4), en rappelant que si Ai ∈ R
i×i est
sym´ etrique d´ efinie positive, il en est de mˆ eme de toutes ses sous-matrices principales.
Pour i = 1 le r´ esultat est ´ evidemment vrai. Supposons le vrai au rang i − 1 et
montrons le au rang i. Il existe une matrice triangulaire sup´ erieure Hi−1 telle que
Ai−1 = H
T
i−1 Hi−1. D´ ecomposons Ai sous la forme
Ai =
Ai−1 v
v
T
α