Accueil > Informatique > spip > formule latex

formule latex

samedi 25 avril 2009, par frederic

La factorisation de Cholesky, consiste, pour une matrice symétrique définie positive , à déterminer une matrice triangulaire inférieure tel 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}$ , de calculer le déterminant de (égal au carré du produit des éléments diagonaux
de ).

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

$\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 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=\pmatrix{ l_{11}\cr l_{21} & l_{22}\cr \vdots & \vdots & \ddots\cr l_{n1} & l_{n2} & \cdots & l_{nn} }$

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≤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}+\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 :, 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 A, qui est égal au carré du produit des éléments diagonaux de la matrice L, puisque