Décomposition de Cholesky

Factorisation de Cholesky

La factorisation de Cholesky, nommée d'après André-Louis Cholesky, consiste, pour une matrice symétrique semi 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. Elle est aussi, utilisée en chimie quantique pour accélérer les calculs (voir Décomposition de Cholesky (chimie quantique)).

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.

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.

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$

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

a₁₁ = l₁₁l₁₁ d'où $l_{11}=\sqrt{a_{11}}$

a_1j = l₁₁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}=({a_{ii}-{\sum_{k=1}^{i-1}l_{ik}^{2}}})^{\frac{1}{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 l_ii>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

• Décomposition LU
• Décomposition QR
• (fr) La factorisation de Cholesky

Ce document provient de « Factorisation de Cholesky ».