Factorisation de Cholesky

Restez toujours informé : suivez-nous sur Google (☆)

Introduction

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=LL.

La matrice L est en quelque sorte une « racine carrée » de A. Cette décomposition permet notamment de calculer la matrice inverse A, 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.

Exemple

La matrice symétrique A :

(11111555151414151415)

est égale au produit à droite de la matrice triangulaire L :

(1000120012301231)

et de sa transposée L.

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=LL

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 = [l_{11} l_{21} l_{22} ⋮ ⋮ ⋱ l_{n 1} l_{n 2} \dots l_{nn}]

De l'égalité A=LL on déduit :

a_{ij} = (L L^{T}) ij = \sum k = 1^{n} l_{ik} l_{j k} = k = 1 \sum m i n {i, j} l_{ik} l_{j k}, 1 \leq i, j \leq n

puisque l_pq=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 l_ij de la matrice L doivent satisfaire :

a_{ij} = k = 1 \sum i l_{ik} l_{j k}, 1 \leq i, j \leq n

Pour i=1, on détermine la première colonne de L :

(j=1) a₁₁ = l₁₁l₁₁ d'où $l_{11} = a_{11}$

(j=2) a₁₂ = l₁₁l₂₁ d'où $l_{21} = \frac{a _{12}}{l _{11}}$

...

(j=n) a_1n = l₁₁l_n1 d'où $l_{n 1} = \frac{a _{1 n}}{l _{11}}$

On détermine la j colonne de L, après avoir calculé les (j-1) premières colonnes :

(i=j) $a_{ii} = l_{i 1} l_{i 1} + \dots + l_{ii} l_{ii}$ d'où $l_{ii} = a_{ii} - \sum_{k = 1}^{i - 1} l_{ik}^{2}$

(i=j+1) $a_{i, i + 1} = l_{i 1} l_{i + 1, 1} + \dots + 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_{i 1} l_{n 1} + \dots + 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 l_ii>0 en assurant que toutes les quantités

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

sont positives.