Factorisation de Cholesky
La factorisation de Cholesky, nommée d'après André-Louis Cholesky, consiste, pour une matrice
symétrique définie positive A, à déterminer une matrice triangulaire inférieure L telle que : A =
LLT.
La matrice L est en quelque sorte une « racine carrée » de A. Cette décomposition permet
notamment de calculer la matrice inverse A−1, de calculer le déterminant de A (égal au carré du
produit des éléments diagonaux de L) 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)).
Exemple
La matrice symétrique A :
est égale au produit de la matrice triangulaire L :
avec à sa droite sa transposée LT :
Théorème
Théorème — Si A est une matrice symétrique définie positive, il existe une matrice
réelle triangulaire inférieure L telle que1:
A = LLT.
De plus cette décomposition est unique si l'on impose à L d'avoir des coefficients
diagonaux strictement positifs.
Démonstration
Notons la base canonique de .
A est symétrique définie positive, donc elle représente un certain produit scalaire
dans B.
Soit une base orthonormée pour ce produit scalaire. On note P
la matrice de passage de B' vers B.
La formule de changement de base pour une application bilinéaire donne
On va chercher à bien choisir B' de sorte que P soit triangulaire supérieure à
coefficient diagonaux positifs.
Pour cela, on cherche B' orthonormée telle que :
L'algorithme de Gram-Schmidt garantit l'existence et l'unicité d'une telle base, d'où
l'existence et l'unicité de P. Enfin on pose dont on déduit la forme voulue.
Algorithme
On cherche la matrice :
De l'égalité A = LLT on déduit :
puisque l =0 si 1 ≤ p < q ≤ n.
pq
La matrice A étant symétrique, il suffit que les relations ci-dessus soient vérifiées pour i ≤ j,
c'est-à-dire que les éléments l de la matrice L doivent satisfaire :
ij
Pour i = 1, on détermine la première colonne de L :
d'où
d'où
On détermine la i-ème colonne de L 2 ≤ i ≤ n, après avoir calculé les (i – 1) 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 l > 0 en assurant
ii
que toutes les quantités
sont positives.
Décomposition de Cholesky alternative ou décomposition de
Crout2
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 n'impose plus non plus
l'obligation que la matrice A soit définie positive, elle se calcule de la façon suivante3 :
où D est une matrice diagonale, et L une matrice triangulaire inférieure avec des 1 sur sa
diagonale.
Les remarque suivantes n'ont d'intérêt qu'en mathématique pure, mais pas pour la résolution de
système d'équations par la méthode LDLT :
Les factorisations LDLT et LLT (notez que la matrice L 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 LLT.
On remarquera que la racine carrée d'une matrice diagonale (ici, D1/2) se calcule trivialement en
prenant les racines carrées de chacun de ses éléments.
Résolution d'un système d'équation par la méthode de Cholesky alternative
Soit un système d'équation linéaire à matrice symétrique. la méthode de résolution du
système se décompose en 4 étapes :
1. Calcul des éléments des matrice L et D à l'aide des formules de la section précédente
2. Résolution du système intermédiaire (voir méthode LU pour la résolution d'un
système d'équation sous forme d'une matrice triangulaire inférieure)
3. Division des valeurs de Y' par les coefficients de D : (D étant
diagonale contient l'inverse des éléments de la diagonale de D)
4. Résolution du système intermédiaire (voir méthode LU pour la résolution d'un
système d'équation sous forme d'une matrice triangulaire supérieure)
Histoire
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. Daté du 2 décembre
1910, son contenu n'était auparavant connu que par une publication du commandant Benoît, qui
décrivit la méthode de Cholesky en 1924, soit plusieurs années après sa mort4. Il est probable
que Cholesky ait découvert cette méthode en 19024.
La méthode, définie pour un problème de topographie, resta longtemps inconnue des
mathématiciens4. Elle fut remise en avant par John Todd (en) en 1946 dans son cours d'analyse
numérique au King's College de Londres4.
Cette méthode est aujourd'hui centrale en analyse numérique.
Note
1. Xavier Gourdon, Les Maths en tête: Algèbre, page 247
2. « Décomposition de Cholesky et de Crout ([Link]
affiche&quoi=./c/[Link]) [archive] », sur [Link] (consulté le 21 juillet 2024)
3. (en) D. Watkins, Fundamentals of Matrix Computations, p. 84.
4. Claude Brezinski et Dominique Tournès, « André–Louis Cholesky (1875-1918),
mathématicien, topographe, enseignant et officier ([Link]
[Link]) [archive] »,
sur Images des maths, 15 juillet 2015.
Voir aussi
Articles connexes
Décomposition LU
Décomposition QR
Racine carrée d'une matrice
Bibliographie
La méthode de Cholesky est essentielle en analyse numérique. Il existe donc une multitude de
références, parmi lesquelles :
Philippe Ciarlet, Introduction à l'analyse numérique matricielle et à l'optimisation, 1985 (rééd.
2001), éd. Masson, coll. Math. Appl. pour la Maîtrise (ISBN 2-225-68893-1)
Patrick Lascaux et Raymond Theodor, Analyse numérique matricielle appliquée à l'art de
l'ingénieur - Volume 1 Méthodes directes, Dunod, 2000
Lien externe
Sur la résolution numérique des systèmes linéaires ([Link]
ues/algebre/sur-la-resolution-numerique-des-systemes-d-equations-lineaires) [archive] ,
manuscrit de Cholesky en ligne et commenté sur le site BibNum.
Portail de l’algèbre
