Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Factorisation de Cholesky
Résumé
La factorisation de Cholesky, nommée d'après André-Louis Cholesky, consiste, pour une matrice symétrique définie positive , à déterminer une matrice triangulaire inférieure telle que : .
La matrice est en quelque sorte une « racine carrée » de . Cette décomposition permet notamment de calculer la matrice inverse , de calculer le déterminant de A (égal au carré du produit des éléments diagonaux
de ) ou encore de simuler une loi multinormale. Elle est aussi utilisée en chimie quantique pour accélérer les calculs (voir Décomposition de Cholesky (chimie quantique)).
La matrice symétrique :
est égale au produit de la matrice triangulaire :
avec à sa droite sa transposée :
On cherche la matrice :
De l'égalité on déduit :
puisque si 1 ≤ p < q ≤ n.
La matrice étant symétrique, il suffit que les relations ci-dessus soient vérifiées pour i ≤ j, c'est-à-dire que les éléments de la matrice doivent satisfaire :
Pour , on détermine la première colonne de :
d'où
d'où
On détermine la i-ème colonne de 2 ≤ i ≤ n, après avoir calculé les premières colonnes :
d'où
d'où
Il résulte du théorème précédent qu'il est possible
de choisir tous les éléments en assurant que
toutes les quantités
sont positives.
La décomposition de Cholesky alternative permet d'éviter l'utilisation des racines carrées au sein des sommes, source potentielle de problème en calcul numérique, elle se calcule de la façon suivante :
où est une matrice diagonale, et une matrice triangulaire inférieure avec des 1 sur sa diagonale.
Les factorisations et (notez que la matrice est différente dans les deux cas) sont liées :
La dernière expression étant le produit d'une matrice triangulaire et de sa transposée, de la même manière que dans la factorisation .
On remarquera que la racine carrée d'une matrice diagonale (ici, D) se calcule trivialement en prenant les racines carrées de chacun de ses éléments.
La décomposition porte le nom d'André-Louis Cholesky un officier et ingénieur français. Elle figure dans le manuscrit intitulé « Sur la résolution numérique des systèmes d'équations linéaires », manuscrit porté en 2005 aux Archives de l'École Polytechnique.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.