3.4 Autres types de factorisation
83
end
k=[1:i-1];
for j=i+1:n
A(i,j)=A(i,j)-A(i,k)*A(k,j);
end
end
return
3.4 Autres types de factorisation
Nous pr´ esentons maintenant des factorisations sp´ ecifiques aux matrices sym´ etriques ou rectangulaires.
3.4.1 La factorisation LDM
T
Consid´ erons une factorisation de A de la forme
A = LDM
T ,
o` u L, M
T et D sont des matrices respectivement triangulaire inf´ erieure, triangulaire sup´ erieure et diagonale.
Une fois construite la factorisation, la r´ esolution du syst` eme peut ˆ etre
effectu´ ee en r´ esolvant d’abord le syst` eme triangulaire inf´ erieur Ly=b, puis le
syst` eme diagonal Dz=y, et enfin le syst` eme triangulaire sup´ erieur M
T x=z,
ce qui repr´ esente un coˆ ut global de n
2 + n flops. Dans le cas sym´ etrique, on
obtient M = L et la factorisation LDL
T peut ˆ etre calcul´ ee avec un coˆ ut deux
fois moindre (voir Section 3.4.2).
La factorisation LDL
T poss` ede une propri´ et´ e analogue `
a celle de la factorisation LU ´ enonc´ ee dans le Th´ eor` eme 3.4. On a en particulier le r´ esultat
suivant :
Th´ eor` eme 3.5 Si tous les mineurs principaux d’une matrice A∈ R
n×n sont
non nuls, alors il existe une unique matrice diagonale D, une unique matrice
triangulaire inf´ erieure L et une unique matrice triangulaire sup´ erieure M
T ,
telles que L et M n’aient que des 1 sur la diagonale et A = LDM
T .
D´ emonstration. D’apr` es le Th´ eor` eme 3.4, nous savons d´ ej` a qu’il existe une unique
factorisation LU de A avec lii = 1 pour i = 1, . . . , n. Si on choisit les ´ el´ ements
diagonaux de D ´ egaux ` a uii (non nuls puisque U est inversible), alors A = LU =
LD(D
−1 U). En posant M
T = D
−1 U (qui est une matrice triangulaire sup´ erieure avec
des 1 sur la diagonale), l’existence de la d´ ecomposition LDM
T en d´ ecoule. L’unicit´ e
de la factorisation LDM
T est une cons´ equence de celle de la factorisation LU.
3
La preuve ci-dessus montre que, puisque les termes diagonaux de D co¨ ıncident avec ceux de U, on pourrait calculer L, M
T et D en partant de la
83
end
k=[1:i-1];
for j=i+1:n
A(i,j)=A(i,j)-A(i,k)*A(k,j);
end
end
return
3.4 Autres types de factorisation
Nous pr´ esentons maintenant des factorisations sp´ ecifiques aux matrices sym´ etriques ou rectangulaires.
3.4.1 La factorisation LDM
T
Consid´ erons une factorisation de A de la forme
A = LDM
T ,
o` u L, M
T et D sont des matrices respectivement triangulaire inf´ erieure, triangulaire sup´ erieure et diagonale.
Une fois construite la factorisation, la r´ esolution du syst` eme peut ˆ etre
effectu´ ee en r´ esolvant d’abord le syst` eme triangulaire inf´ erieur Ly=b, puis le
syst` eme diagonal Dz=y, et enfin le syst` eme triangulaire sup´ erieur M
T x=z,
ce qui repr´ esente un coˆ ut global de n
2 + n flops. Dans le cas sym´ etrique, on
obtient M = L et la factorisation LDL
T peut ˆ etre calcul´ ee avec un coˆ ut deux
fois moindre (voir Section 3.4.2).
La factorisation LDL
T poss` ede une propri´ et´ e analogue `
a celle de la factorisation LU ´ enonc´ ee dans le Th´ eor` eme 3.4. On a en particulier le r´ esultat
suivant :
Th´ eor` eme 3.5 Si tous les mineurs principaux d’une matrice A∈ R
n×n sont
non nuls, alors il existe une unique matrice diagonale D, une unique matrice
triangulaire inf´ erieure L et une unique matrice triangulaire sup´ erieure M
T ,
telles que L et M n’aient que des 1 sur la diagonale et A = LDM
T .
D´ emonstration. D’apr` es le Th´ eor` eme 3.4, nous savons d´ ej` a qu’il existe une unique
factorisation LU de A avec lii = 1 pour i = 1, . . . , n. Si on choisit les ´ el´ ements
diagonaux de D ´ egaux ` a uii (non nuls puisque U est inversible), alors A = LU =
LD(D
−1 U). En posant M
T = D
−1 U (qui est une matrice triangulaire sup´ erieure avec
des 1 sur la diagonale), l’existence de la d´ ecomposition LDM
T en d´ ecoule. L’unicit´ e
de la factorisation LDM
T est une cons´ equence de celle de la factorisation LU.
3
La preuve ci-dessus montre que, puisque les termes diagonaux de D co¨ ıncident avec ceux de U, on pourrait calculer L, M
T et D en partant de la