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)).

Exemple La matrice symétrique :

est égale au produit de la matrice triangulaire :

avec à sa droite sa transposée :

Théorème

Algorithme

On cherche la matrice :

De l'égalité on déduit :

puisque si .

La matrice étant symétrique, il suffit que les relations ci-dessus soient vérifiées pour , 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 , 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.

Décomposition de Cholesky alternative ou décomposition de Crout

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 et 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 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 :

Les factorisations et (il faut noter que si les noms des méthodes sont ¿ proches/voisins ? , 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, ) 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 quatre étapes :

Calcul des éléments des matrice et à l'aide des formules de la section précédente 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) Division des valeurs de par les coefficients de : ( étant diagonale contient l'inverse des éléments de la diagonale de ) 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 , 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 mort.. Il est probable que Cholesky ait découvert cette méthode en 1902.

La méthode, définie pour un problème de topographie, resta longtemps inconnue des mathématiciens. Elle fut remise en avant par en 1946 dans son cours d'analyse numérique au King's College de Londres.

Cette méthode est aujourd'hui centrale en analyse numérique.

Note

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

Liens externes Sur la résolution numérique des systèmes linéaires, manuscrit de Cholesky en ligne et commenté sur le site BibNum.

Catégorie:Analyse numérique matricielle Catégorie:Algèbre bilinéaire