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$, de calculer le déterminant de $A$ (égal au carré du produit des éléments diagonaux de $L$).
Exemple
La matrice symétrique $[C_3] = \colorred \langle \vec k_3L \vec k_3L^\:\dagger \rangle = \left[ \beginarrayrrrr S_11 & S_21 & S_31 \\ S_12 & S_22 & S_32 \\ S_13 & S_23 & S_33 \endarray \right] $
est égale au produit de la matrice triangulaire $L$ et de sa transposée $L^T$:
$$ \pmatrix 1 & 1 & 1 & 1 \cr 1 & 5 & 5 & 5 \cr 1 & 5 & 14 & 14 \cr 1 & 5 & 14 & 15 = \pmatrix 1 & 0 & 0 & 0 \cr 1 & 2 & 0 & 0 \cr 1 & 2 & 3 & 0 \cr 1 & 2 & 3 & 1 \dot \pmatrix 1 & 1 & 1 & 1 \cr 0 & 2 & 2 & 2 \cr 0 & 0 & 3 & 3 \cr 0 & 0 & 0 & 1 $$
avec
$$L= \pmatrix 1 & 0 & 0 & 0 \cr 1 & 2 & 0 & 0 \cr 1 & 2 & 3 & 0 \cr 1 & 2 & 3 & 1 $$
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=\pmatrix l_11\cr l_21 & l_22\cr \vdots & \vdots & \ddots\cr l_n1 & l_n2 & \cdots & l_nn $$
De l’égalité $A=LL^T$ on déduit : $a_ij=\left(LL^T\right)_ij=\sum_k=1^nl_ikl_jk=\sum_k=1^\min\left\ i,j\right\ l_ikl_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≤j, c'est-à-dire que les éléments lij de la matrice $L$ doivent satisfaire : $a_ij=\sum_k=1^il_ikl_jk,\;1\leq i,j\leq n$
Pour j=1, on détermine la première colonne de $L$ : – (i=1) $a_11=l_11l_11$ d’où $l_11=\sqrta_11$ – (i=2) $a_12=l_11l_21$ d’où $l_21=\fraca_12l_11$ – … – (i=n) $a_1n=l_11l_n1$ d’où $l_n1=\fraca_1nl_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_i1l_i1+\ldots+l_iil_ii$ d’où $l_ii=\sqrta_ii–\sum_k=1^i-1l_ik^2$ – (i=j+1) $\displaystyle a_i,i+1=l_i1l_i+1+\ldots+l_iil_i+1,i$ d’où $l_i+1,i=\fraca_i,i+1–\sum_k=1^i-1l_ikl_i+1,kl_ii$ – … – (i=n) $\displaystyle a_i,n=l_i1l_n1+\ldots+l_iil_ni$ d’où $l_ni=\fraca_in–\sum_k=1^i-1l_ikl_nkl_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\\beginarraycc Ly = b& (1),\\ L^Tx = y &(2). \endarray\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) × det(L^T)=det(L)^2$$