Factorisation de Cholesky

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 « 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 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}

avec à sa droite sa transposée LT :

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

Théorème

Factorisation de Cholesky d'une matrice :

Si A est une matrice symétrique définie positive, il existe 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\leq 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}= \sqrt{{a_{ii}-{\sum_{k=1}^{i-1}l_{ik}^{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.

Décomposition de Cholesky Alternative

La décomposition de Cholesky alternative permet d'éviter l'utilisation des racines carrées au sein des sommes, source potentielle de problème en calcul numérique, elle se calcule de la façon suivante[1]  :

{\mathbf{A=LDL}^\mathrm{T}}

où D est une matrice diagonale, et L une matrice triangulaire inférieure avec des 1 sur sa diagonale.

D_{jj} = A_{jj} - \sum_{k=1}^{j-1} L_{jk}^2 D_{kk}
L_{ij} = \frac{1}{D_{jj}} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk} D_{kk} \right), \qquad\text{pour } i>j.


La factorisation LDLT et LLT (notez que la matrice L est différente dans les deux cas) sont liés:

\mathbf{A = L D L}^\mathrm{T} = \mathbf L \mathbf D^{\frac 1 2} \mathbf D^{\frac 1 2} \mathbf L^\mathrm{T} = \mathbf L \mathbf D^{\frac 1 2} (\mathbf D^{\frac 1 2})^\mathrm{T} \mathbf L^\mathrm{T} = \mathbf L \mathbf D^{\frac 1 2} (\mathbf L \mathbf D^{\frac 1 2})^\mathrm{T}

La dernière expression étant le produit d'une matrice triangulaire et de sa transposée, de la même manière que dans la factorisation LLT.

Notez que la racine carré d'une matrice diagonale (ici, D½) se calcule trivialement en prenant les racines carrées de chacun de ses éléments.

Notes

  1. ↑ D. Watkins, Fundamentals of Matrix Computations, p. 84

Voir aussi

Bibliographie

La méthode de Cholesky est essentielle en analyse numérique. Il existe donc une multitude de références rien qu'en français. Citons par exemple :

  • P. G. Ciarlet, Introduction à l'analyse numérique matricielle et à l'optimisation, 1985 (rééd. 2001), éd. Masson, coll. Math. Appl. pour la Maîtrise (ISBN 2-225-68893-1)

Articles connexes

Lien externe

  • Sur la résolution numérique des systèmes linéaires, manuscrit de Cholesky en ligne et commenté sur le site BibNum.

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • 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… …   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 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Methode 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… …   Wikipédia en Français

  • Factorisation 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

  • André-Louis Cholesky — (15 octobre 1875 à Montguyon 31 août 1918 à Bagneux) est un polytechnicien et officier français, ingénieur topographe et géodésien. Il est célèbre pour sa méthode de résolution des systèmes d équations linéaires, toujours… …   Wikipédia en Français

  • Andre-Louis Cholesky — André Louis Cholesky André Louis Cholesky (15 octobre 1875 à Montguyon 31 août 1918) était un mathématicien et officier français. Il entre en 1895 à l École polytechnique. De 1897 à 1899, il est élève de l École d Application… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   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 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

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

Share the article and excerpts

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