La 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=LL^T$. Une matrice symétrique $A$ est dite définie positive si, pour tout vecteur $x$, le produit $x^TAx$ est positif.

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}$ et de calculer le déterminant de $A$ (égal au carré du produit des éléments diagonaux
de $L$).

Exemple

La matrice symétrique
$A=\begin{pmatrix} 1 & 1 & 1 & 1 \cr 1 & 5 & 5 & 5 \cr 1 & 5 & 14 & 14 \cr 1 & 5 & 14 & 15 \end{pmatrix} $

est égale au produit de la matrice triangulaire $L$ et de sa transposée $L^T$ :

$$ \begin{pmatrix} 1 & 1 & 1 & 1 \cr 1 & 5 & 5 & 5 \cr 1 & 5 & 14 & 14 \cr 1 & 5 & 14 & 15 \end{pmatrix}= \begin{pmatrix} 1 & 0 & 0 & 0 \cr 1 & 2 & 0 & 0 \cr 1 & 2 & 3 & 0 \cr 1 & 2 & 3 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 & 1 \cr 0 & 2 & 2 & 2 \cr 0 & 0 & 3 & 3 \cr 0 & 0 & 0 & 1 \end{pmatrix}$$

avec

$$L= \begin{pmatrix} 1 & 0 & 0 & 0 \cr 1 & 2 & 0 & 0 \cr 1 & 2 & 3 & 0 \cr 1 & 2 & 3 & 1 \end{pmatrix}$$

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{pmatrix} l_{11}\cr l_{21} & l_{22}\cr \vdots & \vdots & \ddots\cr l_{n1} & l_{n2} & \cdots & l_{nn} \end{pmatrix} $$

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_{ij}=0$ si $1 \leq i < j \leq n.$

La matrice $A$ étant symétrique, il suffit que les relations ci-dessus soient vérifiées pour $i\leq 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 j=1, on détermine la première colonne de $L$ :
– (i=1) $a_{11}=l_{11}l_{11}$ d’o๠$l_{11}=\sqrt{a_{11}}$
– (i=2) $a_{12}=l_{11}l_{21}$ d’o๠$l_{21}=\frac{a_{12}}{l_{11}}$
– ...
– (i=n) $a_{1n}=l_{11}l_{n1}$ 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) $\displaystyle a_{i,i+1}=l_{i1}l_{i+1,1}+\ldots+l_{ii}l_{i+1,i}$ d’o๠$l_{i+1,i}=\displaystyle\frac{a_{i,i+1}-{\displaystyle\sum_{k=1}^{i-1}l_{ik}l_{i+1,k}}}{l_{ii}}$
– ...
– (i=n) $\displaystyle a_{i,n}=l_{i1}l_{n1}+\ldots+l_{ii}l_{ni}$ d’o๠$l_{ni}=\displaystyle\frac{a_{in}-{\displaystyle\sum_{k=1}^{i-1}l_{ik}l_{nk}}}{l_{ii}}$

Résolution de système

Pour la résolution de système linéaire de la forme :$Ax=b$, le système devient

$$LL^Tx = b \Leftrightarrow \left\{\begin{array}{cc} Ly = b& (1),\\ L^Tx = y &(2). \end{array}\right. $$

On résout le système (1) pour trouver le vecteur $y$, puis le système (2) pour trouver le vecteur $x$. La résolution est facilitée par la forme triangulaire des matrices.

Calcul de déterminant

La méthode de Cholesky permet aussi de calculer le déterminant de $A$, qui est égal au carré du produit des éléments diagonaux de la matrice $L$, puisque

$$det(A) = det(L)\times det(L^T)=det(L)^2$$