Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Accueil > Mathématiques > Résolution de systèmes linéaires > La factorisation de Cholesky

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érieureLtel 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 Lest 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

Un message, un commentaire ?

comments powered by Disqus