Factorisation de Cholesky

Un article de Wikipédia, l'encyclopédie libre.

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

Sommaire

[modifier] Exemple

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 à droite 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}

et de sa transposée LT.

[modifier] Théorème

Factorisation de Cholesky d'une matrice :

Si A est une matrice symétrique définie positive, il existe au moins 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.

[modifier] Algorithme

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,j\leq n

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

(j=1) a11 = l11l11 d'où l_{11}=\sqrt{a_{11}}
(j=2) a12 = l11l21 d'où l_{21}=\frac{a_{12}}{l_{11}}
...
(j=n) a1n = l11ln1 d'où l_{n1}=\frac{a_{1n}}{l_{11}}

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

(i=j) 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}}}
(i=j+1) a_{i,i+1}=l_{i1}l_{i+1,1}+\ldots+l_{ii}l_{i+1,i} d'où l_{i+1,i}=\frac{a_{i,i+1}-{\sum_{k=1}^{i-1}l_{ik}l_{i+1,k}}}{l_{ii}}
...
(i=n) a_{i,n}=l_{i1}l_{n1}+\ldots+l_{ii}l_{ni} d'où l_{ni}=\frac{a_{in}-{\sum_{k=1}^{i-1}l_{ik}l_{nk}}}{l_{ii}}

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.

[modifier] Voir aussi