Knowledge base dedicated to Linux and applied mathematics.
Accueil > Mathématiques > Résolution de systèmes linéaires > La factorisation de Cholesky
Toutes les versions de cet article : <English> <français>
Nous allons étudier une méthode directe de résolution de système linéaire : la méthode de Cholesky. L’objectif est de construire pour une matrice A symétrique définie positive une matrice triangulaire L
telle que A soit égale au produit de la matrice triangulaire L et de la transposée de cette dernière.
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$).
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}$$
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.
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}}$
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.
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$$