Chez Ptit Gars

Accueil > Informatique > spip > formule latex

formule latex

samedi 25 avril 2009, par Pti Gars

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] = 
{\color{red} \langle \vec k_{3L} \vec k_{3L}^{~:\dagger} \rangle }=
\left[ \begin{array}{rrrr}
S_{11} & S_{21} & S_{31} \\
S_{12} & S_{22} & S_{32} \\
S_{13} & S_{23} & S_{33} 
\end{array} \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}^{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≤j, c’est-à-dire que les éléments lij 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}+\ldots+l_{ii}l_{i+1,i} d’où l_{i+1,i}=\frac{a_{i,i+1}-{\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}=\frac{a_{in}-{\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) × det(L^T)=det(L)^2