Factorisation de Cholesky

Un article de Wikivisual, 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=LL^T.

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.

[modifier] Exemple

La matrice symétrique A :

<math> \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 à droite de la matrice triangulaire L :

<math> \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 2 & 0 & 0 \\ 1 & 2 & 3 & 0 \\ 1 & 2 & 3 & 1 \\ \end{pmatrix} </math>

et de sa transposée L^T.

[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=LL^T

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 :

<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é A=LL^T 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 l_pq=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 l_ij de la matrice L doivent satisfaire :

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

(j=1) <math>a_{11}=l_{11}l_{11}</math> d'où <math>l_{11}=\sqrt{a_{11}}</math>

(j=2) <math>a_{12}=l_{11}l_{21}</math> d'où <math>l_{21}=\frac{a_{12}}{l_{11}}</math>

...

(j=n) <math>a_{1n}=l_{11}l_{n1}</math> d'où <math>l_{n1}=\frac{a_{1n}}{l_{11}}</math>

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

(i=j) <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>

(i=j+1) <math>a_{i,i+1}=l_{i1}l_{i+1}+\ldots+l_{ii}l_{i+1,i}</math> d'où <math>l_{i+1,i}=\frac{a_{i,i+1}-{\sum_{k=1}^{i-1}l_{ik}l_{i+1,k}}}{l_{ii}}</math>

...

(i=n) <math>a_{i,n}=l_{i1}l_{n1}+\ldots+l_{ii}l_{ni}</math> d'où <math>l_{ni}=\frac{a_{in}-{\sum_{k=1}^{i-1}l_{ik}l_{nk}}}{l_{ii}}</math>

Il résulte du théorème précédent qu'il est possible de choisir tous les éléments l_ii>0 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.