Factorisation de Cholesky
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

La factorisation de Cholesky, nommée d'après André-Louis Cholesky, consiste, pour une matrice symétrique définie positive A, à déterminer une matrice triangulaire inférieure L tel que : A=LLT.

La matrice L est en quelque sorte une " racine carrée " de A. Cette décomposition (En biologie, la décomposition est le processus par lequel des corps organisés, qu'ils soient d'origine animale ou végétale dès l'instant qu'ils sont privés de vie,...) permet notamment de calculer la matrice inverse (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de composition interne · notée multiplicativement, est un...) A-1, de calculer le déterminant de A (égal au carré (Un carré est un polygone régulier à quatre côtés. Cela signifie que ses quatre côtés ont la même longueur et ses quatre angles la même mesure. Un...) du produit des éléments diagonaux de L) ou encore de simuler une loi multinormale.

Exemple

La matrice symétrique (ce qui exige que A soit une matrice carrée.) A :

\begin{pmatrix} 1 & 1 & 1  & 1 \\ 1 & 5 & 5  & 5 \\ 1 & 5 & 14 & 14 \\ 1 & 5 & 14 & 15 \\ \end{pmatrix}

est égale au produit à droite de la matrice triangulaire (En algèbre linéaire, les matrices triangulaires sont des matrices carrées dont une partie triangulaire des valeurs, délimitée par la diagonale principale, est nulle.) L :

\begin{pmatrix} 1 & 0 & 0  & 0 \\ 1 & 2 & 0  & 0 \\ 1 & 2 & 3  & 0 \\ 1 & 2 & 3  & 1 \\ \end{pmatrix}

et de sa transposée LT.

Théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir d'axiomes. Un théorème...)

Factorisation de Cholesky (La factorisation de Cholesky, nommée d'après André-Louis Cholesky, consiste, pour une matrice symétrique définie positive A, à déterminer une matrice triangulaire inférieure L tel que :...) 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=LLT

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{bmatrix} l_{11}\\ l_{21} & l_{22}\\ \vdots & \vdots & \ddots\\ l_{n1} & l_{n2} & \cdots & l_{nn} \end{bmatrix}

De l'égalité A=LLT 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 lpq=0 si 1≤p

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 i=1, on détermine la première colonne de L :

(j=1) a11 = l11l11 d'où l_{11}=\sqrt{a_{11}}
(j=2) a12 = l11l21 d'où l_{21}=\frac{a_{12}}{l_{11}}
...
(j=n) a1n = l11ln1 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) a_{i,i+1}=l_{i1}l_{i+1,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) 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}}

Il résulte du théorème précédent qu'il est possible de choisir tous les éléments lii>0 en assurant que toutes les quantités

a_{11},\ldots,a_{ii}-{\sum_{k=1}^{i-1}l_{ik}^{2}},\ldots

sont positives.

Page générée en 0.112 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique