Décomposition de Cholesky

Décomposition de Cholesky

Factorisation de Cholesky

La factorisation de Cholesky, nommée d'après André-Louis Cholesky, consiste, pour une matrice symétrique semi 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 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) ou encore de simuler une loi multinormale. Elle est aussi, utilisée en chimie quantique pour accélérer les calculs (voir Décomposition de Cholesky (chimie quantique)).

Sommaire

Exemple

La matrice symétrique 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 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

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

a11 = l11l11 d'où l_{11}=\sqrt{a_{11}}
a1j = l11lj1 d'où l_{j1}=\frac{a_{1j}}{l_{11}},\;\;\;2\leq j\leq n

On détermine la ième colonne de L (2\leq i\leq n), après avoir calculé les (i-1) premières colonnes :

a_{ii}=l_{i1}l_{i1}+\ldots+l_{ii}l_{ii} d'où l_{ii}=({a_{ii}-{\sum_{k=1}^{i-1}l_{ik}^{2}}})^{\frac{1}{2}}
a_{ij}=l_{i1}l_{j1}+\ldots+l_{ii}l_{ji} d'où l_{ji}=\frac{a_{ij}-{\sum_{k=1}^{i-1}l_{ik}l_{jk}}}{l_{ii}},\;\;\;i+1\leq j\leq n

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.

Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Factorisation de Cholesky ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Décomposition de Cholesky de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Décomposition de Cholesky (chimie quantique) — La décomposition de Cholesky (Cholesky Decomposition: CD) est une technique de chimie numérique pour réduire le nombre d intégrales calculées, et donc accélérer le calcul et préserver de la mémoire. Cette technique est basée sur la décomposition… …   Wikipédia en Français

  • Cholesky decomposition — In linear algebra, the Cholesky decomposition or Cholesky triangle is a decomposition of a Hermitian, positive definite matrix into the product of a lower triangular matrix and its conjugate transpose. It was discovered by André Louis Cholesky… …   Wikipedia

  • Decomposition LU — Décomposition LU En algèbre linéaire, la décomposition LU est une méthode de décomposition d une matrice en une matrice triangulaire inférieure L (comme Low , bas) et une matrice triangulaire supérieure U (comme Up , haut). Cette décomposition… …   Wikipédia en Français

  • Décomposition lu — En algèbre linéaire, la décomposition LU est une méthode de décomposition d une matrice en une matrice triangulaire inférieure L (comme Low , bas) et une matrice triangulaire supérieure U (comme Up , haut). Cette décomposition est utilisée en… …   Wikipédia en Français

  • Decomposition QR — Décomposition QR En algèbre linéaire, la décomposition QR (appelée aussi, décomposition QU) d une matrice A est une décomposition de la forme A = QR où Q est une matrice orthogonale (QQT = I), et R une matrice triangulaire supérieure. Il existe… …   Wikipédia en Français

  • Decomposition method — is a generic term for solutions of various problems and design of algorithms in which the basic idea is to decompose the problem into question into subproblems. The term may specifically refer to one of the following. Decomposition method… …   Wikipedia

  • Décomposition LU — En algèbre linéaire, la décomposition LU est une méthode de décomposition d une matrice comme produit d une matrice triangulaire inférieure L (comme Low , bas) et une matrice triangulaire supérieure U (comme Up , haut). Cette décomposition est… …   Wikipédia en Français

  • Décomposition QR — En algèbre linéaire, la décomposition QR (appelée aussi, décomposition QU) d une matrice A est une décomposition de la forme A = QR où Q est une matrice orthogonale (QQT = I), et R une matrice triangulaire supérieure. Ce type de décomposition est …   Wikipédia en Français

  • Décomposition polaire — Sommaire 1 Décomposition polaire d une matrice réelle 2 Décomposition polaire d une matrice complexe 3 Application 4 Références …   Wikipédia en Français

  • 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 telle que : A=LLT. La matrice L est en quelque sorte une… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”