Décomposition de LDLT
La décomposition LDLT est une généralisation de la décomposition de Cholesky aux matrices symétriques non définies positives. Contrairement à la décomposition de Cholesky, n'étant valable que pour les matrices symétriques définies positives, la décomposition LDLT est valable pour toute matrice symétrique.
La décomposition LDLT de la matrice A est une décomposition de la forme A = L·D·L·T ou A = U·D·U·T. Elle diffère de la décomposition de Cholesky par deux points : premièrement, elle utilise la matrice D, une matrice diagonale par blocs de dimensions 1×1 ou 2×2 ; deuxièmement, les matrices L et U ne sont pas triangulaires, mais des produits de matrices triangulaires et de matrices de permutation :
|
L = P1L1·...·PkLk·... U = PnLn·...·PkLk·... | E v E | Uk = | E | | E | | E v E | Kk = | E | | E | |
Ici, v représente une colonne. Sa largeur s est égale à la largeur du bloc diagonal numéro k dans la matrice D (1 ou 2), et sa hauteur est égale à k - s pour la matrice Uk et à n - k - s + 1 pour la matrice Lk.
On constate que la structure de la décomposition LDLT est beaucoup plus complexe que celles des décompositions de Cholesky et LU. Cependant, contrairement à la décomposition de Cholesky, elle permet de factoriser toute matrice symétrique et est plus rapide que la décomposition LU, plus générale. Il est à noter que la décomposition LDLT est plus rapide que la décomposition LU, mais plus lente que la décomposition de Cholesky ; il est donc recommandé d'utiliser cette dernière autant que possible.
Description de la sous-routine
La décomposition matricielle est effectuée par la sous-routine SMatrixLDLT, prenant en entrée le triangle supérieur ou inférieur de la matrice A et le remplace par les matrices L et D, entreposées sous forme compacte.
Les algorithmes d'inversion de matrices et de résolution de systèmes d'équations linéaires utilisent des matrices sous forme compacte et n'ont pas besoin des matrices L et U. Par conséquent, aucune sous-routine n'est prévue pour les « décompresser ». Une description détaillée de la structure des matrices L et U est disponible dans les commentaires du programme ; vous pouvez donc, si nécessaire, les décompresser vous-même.
Cet algorithme provient de la bibliothèque LAPACK.