Methode de Cholesky

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 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 Methode de Cholesky de Wikipédia en français (auteurs)

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

Regardez d'autres dictionnaires:

  • Methode de Jacobi — Méthode de Jacobi La méthode de Jacobi, due au mathématicien allemand Karl Jacobi, est une méthode itérative de résolution d un système matriciel de la forme Ax=b. Pour cela, on utilise une suite x(k) qui converge vers un point fixe x, solution… …   Wikipédia en Français

  • Méthode De Jacobi — La méthode de Jacobi, due au mathématicien allemand Karl Jacobi, est une méthode itérative de résolution d un système matriciel de la forme Ax=b. Pour cela, on utilise une suite x(k) qui converge vers un point fixe x, solution du système d… …   Wikipédia en Français

  • Méthode de jacobi — La méthode de Jacobi, due au mathématicien allemand Karl Jacobi, est une méthode itérative de résolution d un système matriciel de la forme Ax=b. Pour cela, on utilise une suite x(k) qui converge vers un point fixe x, solution du système d… …   Wikipédia en Français

  • Methode de Gauss-Seidel — Méthode de Gauss Seidel La méthode de Gauss Seidel est une méthode itérative de résolution d un système matriciel de la forme Ax = b. Pour cela, on utilise une suite x(k) qui converge vers un point fixe x, solution du système d équations… …   Wikipédia en Français

  • Méthode De Gauss-Seidel — La méthode de Gauss Seidel est une méthode itérative de résolution d un système matriciel de la forme Ax = b. Pour cela, on utilise une suite x(k) qui converge vers un point fixe x, solution du système d équations linéaires. En notant A = [aij]ij …   Wikipédia en Français

  • Méthode de gauss-seidel — La méthode de Gauss Seidel est une méthode itérative de résolution d un système matriciel de la forme Ax = b. Pour cela, on utilise une suite x(k) qui converge vers un point fixe x, solution du système d équations linéaires. En notant A = [aij]ij …   Wikipédia en Français

  • Méthode des moindres carrés — Illustration de la méthode des moindres carrés. Les données suivent la courbe figurée en pointillés et sont affectées par un bruit gaussien centré, de variance 1. Le meilleur ajustement déterminé par la méthode des moindres carrés est représenté… …   Wikipédia en Français

  • Méthode de Jacobi — La méthode de Jacobi, due au mathématicien allemand Karl Jacobi, est une méthode itérative de résolution d un système matriciel de la forme Ax=b. Pour cela, on utilise une suite x(k) qui converge vers un point fixe x, solution du système d… …   Wikipédia en Français

  • Méthode de Gauss-Seidel — La méthode de Gauss Seidel est une méthode itérative de résolution d un système matriciel de la forme Ax = b. Pour cela, on utilise une suite x(k) qui converge vers un point fixe x, solution du système d équations linéaires. En notant A = [aij]… …   Wikipédia en Français

  • Methode des moindres carres — Méthode des moindres carrés Illustration de la méthode des moindres carrés. Les données suivent la courbe figurée en pointillés et sont affectées par un bruit gaussien centré, de variance 1. Le meilleur ajustement déterminé par la méthode des… …   Wikipédia en Français

Share the article and excerpts

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