Factorisation de Cholesky
La factorisation de Cholesky, nommée d'après André-Louis Cholesky, consiste, pour une matrice symétrique définie positive Modèle:Formule, à déterminer une matrice triangulaire inférieure Modèle:Formule telle que : Modèle:Formule.
La matrice Modèle:Formule est en quelque sorte une « racine carrée » de Modèle:Formule. Cette décomposition permet notamment de calculer la matrice inverse Modèle:Formule, de calculer le déterminant de A (égal au carré du produit des éléments diagonaux de Modèle:Formule) 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 Modèle:Formule :
<math display=block> \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 5 & 5 & 5 \\ 1 & 5 & 14 & 14 \\ 1 & 5 & 14 & 15 \\ \end{pmatrix} </math>
est égale au produit de la matrice triangulaire Modèle:Formule :
<math display=block> \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 2 & 0 & 0 \\ 1 & 2 & 3 & 0 \\ 1 & 2 & 3 & 1 \\ \end{pmatrix} </math>
avec à sa droite sa transposée Modèle:Formule :
<math display=block> \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 2 & 2 & 2 \\ 0 & 0 & 3 & 3 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix} </math>
Théorème
Modèle:ThéorèmeModèle:Démonstration
Algorithme
On cherche la matrice :
- <math>
L=\begin{bmatrix} l_{11}\\ l_{21} & l_{22}\\ \vdots & \vdots & \ddots\\ l_{n1} & l_{n2} & \cdots & l_{nn} \end{bmatrix} </math>
De l'égalité Modèle:Formule on déduit :
- <math>a_{ij}=\left(LL^{T}\right)_{ij}={\sum_{k=1}^{n}l_{ik}l_{jk}}={\sum_{k=1}^{\min\left\{ i,j\right\} }l_{ik}l_{jk}},\;1\leq i,j\leq n</math>
puisque Modèle:Formule si Modèle:Math.
La matrice Modèle:Formule étant symétrique, il suffit que les relations ci-dessus soient vérifiées pour Modèle:Math, c'est-à-dire que les éléments Modèle:Formule de la matrice Modèle:Formule doivent satisfaire :
- <math>a_{ij}={\sum_{k=1}^{i}l_{ik}l_{jk}},\;1\leq i\leq j\leq n</math>
Pour Modèle:Formule, on détermine la première colonne de Modèle:Formule :
- <math>a_{11}=l_{11}l_{11}</math> d'où <math>l_{11}=\sqrt{a_{11}}</math>
- <math>a_{1j}=l_{11}l_{j1}</math> d'où <math>l_{j1}=\frac{a_{1j}}{l_{11}},\;\;\;2\leq j\leq n</math>
On détermine la i-ème colonne de Modèle:Formule Modèle:Math, après avoir calculé les Modèle:Formule premières colonnes :
- <math>a_{ii}=l_{i1}l_{i1}+\ldots+l_{ii}l_{ii}</math> d'où <math>l_{ii}= \sqrt{{a_{ii}-{\sum_{k=1}^{i-1}l_{ik}^{2}}}}</math>
- <math>a_{ij}=l_{i1}l_{j1}+\ldots+l_{ii}l_{ji}</math> d'où <math>l_{ji}=\frac{a_{ji}-{\sum_{k=1}^{i-1}l_{ik}l_{jk}}}{l_{ii}},\;\;\;i+1\leq j\leq n</math>
Il résulte du théorème précédent qu'il est possible de choisir tous les éléments Modèle:Formule en assurant que toutes les quantités
- <math>a_{11},\ldots,a_{ii}-{\sum_{k=1}^{i-1}l_{ik}^{2}},\ldots</math>
sont positives.
Décomposition de Cholesky alternative
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<ref>{{#invoke:Langue|indicationDeLangue}} D. Watkins, Fundamentals of Matrix Computations, p. 84.</ref> :
- <math>A=LDL^\mathrm{T}</math>
où Modèle:Formule est une matrice diagonale, et Modèle:Formule une matrice triangulaire inférieure avec des 1 sur sa diagonale.
- <math> D_{jj} = A_{jj} - \sum_{k=1}^{j-1} L_{jk}^2 D_{kk} </math>
- <math> L_{ij} = \frac{1}{D_{jj}} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk} D_{kk} \right), \qquad\text{pour } i>j. </math>
Les factorisations Modèle:Formule et Modèle:Formule (notez que la matrice Modèle:Formule est différente dans les deux cas) sont liées :
- <math>A = L D L^\mathrm{T} = L D^{\frac 1 2} D^{\frac 1 2} L^\mathrm{T} =
L D^{\frac 1 2} ( D^{\frac 1 2})^\mathrm{T} L^\mathrm{T} =
L D^{\frac 1 2} ( L D^{\frac 1 2})^\mathrm{T}
</math>
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 Modèle:Formule.
On remarquera que la racine carrée d'une matrice diagonale (ici, Modèle:Math) se calcule trivialement en prenant les racines carrées de chacun de ses éléments.
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 mort<ref name=IdM>Modèle:Lien web.</ref>. Il est probable que Cholesky ait découvert cette méthode en 1902<ref name=IdM/>.
La méthode, définie pour un problème de topographie, resta longtemps inconnue des mathématiciens<ref name=IdM/>. Elle fut remise en avant par Modèle:Lien en 1946 dans son cours d'analyse numérique au King's College de Londres<ref name=IdM/>.
Cette méthode est aujourd'hui centrale en analyse numérique.
Note
Voir aussi
Articles connexes
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 Modèle:ISBN
Lien externe
- Sur la résolution numérique des systèmes linéaires, manuscrit de Cholesky en ligne et commenté sur le site BibNum.
