Factorisation de Cholesky

Factorisation de Cholesky : encyclopédie mathématiques

Cet article est issu de l'encyclopédie libre Wikipedia.
Vous pouvez consulter l'article ici ainsi que son historique.
Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.

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

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 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 :

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

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