La factorisation de Cholesky

La factorisation de Cholesky, consiste, pour une matrice symétrique définie positive , à déterminer une matrice triangulaire inférieuretel que . Une matrice symétrique est dite définie positive si, pour tout vecteur , le produit est positif.

La matrice est en quelque sorte une « racine carrée » de . Cette décomposition permet notamment de calculer la matrice inverse $A^{-1}$ et de calculer le déterminant de (égal au carré du produit des éléments diagonaux de ).

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 et de sa transposée :

$\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 est une matrice symétrique définie positive, il existe au moins une matrice réelle triangulaire inférieure telle que :

On peut également imposer que les éléments diagonaux de la matrice 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é 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 é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 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 :
(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 , 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 :, 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 , puis le système (2) pour trouver le vecteur . 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 , qui est égal au carré du produit des éléments diagonaux de la matrice , puisque

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

La factorisation de Cholesky

Mots-clés:

Exemple

Théorème

Algorithme

Résolution de système

Calcul de déterminant

Rubriques

Dans la même rubrique

Mots-clés