Factorisation de Cholesky

La factorisation de 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
1 Exemple
2 Théorème
3 Algorithme
4 Voir aussi

Exemple

La matrice symétrique : 

 1 1  1  1
 1 5  5  5
 1 5 14 14
 1 5 14 15

est égale au produit à droite de la triangulaire 

 1  0 0 0
 3  4 0 0
 6 10 9 0
 5  8 6 1

et de sa transposée.

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.

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) a_{11}=l_{11}^{2} 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 ième colonne de L, après avoir calculé les (i-1) premières colonnes :

(j=i) a_{ii}=l_{i1}+\ldots+l_{ii}l_{ii} d'où l_{ii}=\sqrt{a_{ii}-{\sum_{k=1}^{i-1}l_{ik}^{2}}}
(j=i+1) a_{i,i+1}=l_{i1}l_{i+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}}
...
(j=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 bii>0 en assurant que toutes les quantités

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

sont positives.

Voir aussi

See also: Factorisation de Cholesky, Décomposition LU, Déterminant (mathématiques), Loi normale, Matrice, Matrice définie positive, Matrice triangulaire