Factorisation de Cholesky

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

La matrice symétrique A :


\begin{pmatrix}
1 & 1 & 1  & 1 \\
1 & 5 & 5  & 5 \\
1 & 5 & 14 & 14 \\
1 & 5 & 14 & 15 \\
\end{pmatrix}

est égale au produit de la matrice triangulaire L :


\begin{pmatrix}
1 & 0 & 0  & 0 \\
1 & 2 & 0  & 0 \\
1 & 2 & 3  & 0 \\
1 & 2 & 3  & 1 \\
\end{pmatrix}

avec à sa droite sa transposée LT :


\begin{pmatrix}
1 & 1 & 1  & 1 \\
0 & 2 & 2  & 2 \\
0 & 0 & 3  & 3 \\
0 & 0 & 0  & 1 \\
\end{pmatrix}

Théorème[modifier | modifier le code]

Factorisation de Cholesky d'une matrice —  Si A est une matrice symétrique définie positive, il existe une matrice réelle triangulaire inférieure L telle que :

A=LLT.

On peut également imposer que les éléments diagonaux de la matrice L soient tous positifs, et la factorisation correspondante est alors unique.

Algorithme[modifier | modifier le code]

On cherche la matrice :


L=\begin{bmatrix}
l_{11}\\
l_{21} & l_{22}\\
\vdots & \vdots & \ddots\\
l_{n1} & l_{n2} & \cdots & l_{nn}
\end{bmatrix}

De l'égalité A=LLT on déduit :

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

puisque lpq=0 si 1≤p<q≤n.

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 lij de la matrice L doivent satisfaire :

a_{ij}={\sum_{k=1}^{i}l_{ik}l_{jk}},\;1\leq i\leq j\leq n

Pour i=1, on détermine la première colonne de L :

a_{11}=l_{11}l_{11} d'où l_{11}=\sqrt{a_{11}}
a_{1j}=l_{11}l_{j1} d'où l_{j1}=\frac{a_{1j}}{l_{11}},\;\;\;2\leq j\leq n

On détermine la i-ème colonne de L (2\leq i\leq n), après avoir calculé les (i-1) premières colonnes :

a_{ii}=l_{i1}l_{i1}+\ldots+l_{ii}l_{ii} d'où l_{ii}= \sqrt{{a_{ii}-{\sum_{k=1}^{i-1}l_{ik}^{2}}}}
a_{ij}=l_{i1}l_{j1}+\ldots+l_{ii}l_{ji} d'où l_{ji}=\frac{a_{ij}-{\sum_{k=1}^{i-1}l_{ik}l_{jk}}}{l_{ii}},\;\;\;i+1\leq j\leq n

Il résulte du théorème précédent qu'il est possible de choisir tous les éléments lii>0 en assurant que toutes les quantités

a_{11},\ldots,a_{ii}-{\sum_{k=1}^{i-1}l_{ik}^{2}},\ldots

sont positives.

Décomposition de Cholesky alternative[modifier | modifier le code]

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[1] :

A=LDL^\mathrm{T}

D est une matrice diagonale, et L une matrice triangulaire inférieure avec des 1 sur sa diagonale.

 D_{jj} = A_{jj} - \sum_{k=1}^{j-1} L_{jk}^2 D_{kk}
 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.


Les factorisations LDLT et LLT (notez que la matrice L est différente dans les deux cas) sont liées :

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}

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.

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

Note[modifier | modifier le code]

  1. (en) D. Watkins, Fundamentals of Matrix Computations, p. 84.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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)

Lien externe[modifier | modifier le code]