Décomposition de Cholesky

La décomposition de Cholesky exprime une matrice symétrique définie positive $A$ comme le produit $A = L L^T$, où $L$ est une matrice triangulaire inférieure à diagonale strictement positive. C'est la factorisation matricielle la plus efficace pour résoudre les systèmes linéaires symétriques définis positifs.

Théorème

Soit $A$ une matrice réelle symétrique définie positive de taille $n \times n$. Il existe une unique matrice $L$ triangulaire inférieure, à coefficients diagonaux strictement positifs, telle que $A = L L^T$.

Le qualificatif « défini positive » signifie : $x^T A x > 0$ pour tout vecteur $x \neq 0$. C'est équivalent à dire que toutes les valeurs propres de $A$ sont strictement positives.

Algorithme

Les coefficients de $L$ se calculent ligne par ligne, de haut en bas, via les formules :

• Pour $i = 1, \dots, n$ :
•    $L_{ii} = \sqrt{A_{ii} - \sum_{k=1}^{i-1} L_{ik}^2}$
•    Pour $j > i$ : $L_{ji} = \frac{1}{L_{ii}} \left(A_{ji} - \sum_{k=1}^{i-1} L_{jk} L_{ik}\right)$

Exemple à la main

Prenons $A = \begin{pmatrix} 4 & 2 \\ 2 & 3 \end{pmatrix}$.

$L_{11} = \sqrt{4} = 2$. $L_{21} = 2/2 = 1$. $L_{22} = \sqrt{3 - 1^2} = \sqrt{2}$.

Donc $L = \begin{pmatrix} 2 & 0 \\ 1 & \sqrt{2} \end{pmatrix}$ et on vérifie aisément $LL^T = A$.

Pourquoi Cholesky plutôt que LU ?

Pour une matrice SDP, Cholesky nécessite environ $n^3/6$ opérations contre $2n^3/3$ pour la factorisation LU. C'est deux fois plus rapide, et la matrice résultante prend deux fois moins de mémoire (on ne stocke que $L$, pas $L$ et $U$).

De plus, l'algorithme est numériquement stable sans pivotage — rarement le cas pour LU.

Applications pratiques

La décomposition de Cholesky intervient dans de nombreux domaines :

• Moindres carrés : la matrice $A^T A$ est SDP, et résoudre $A^T A x = A^T b$ par Cholesky est la méthode standard pour la régression linéaire.
• Éléments finis : les matrices de rigidité issues des formulations variationnelles sont souvent SDP, Cholesky est la méthode de choix.
• Filtrage de Kalman : la mise à jour de la matrice de covariance utilise Cholesky pour maintenir la définie positive numériquement.
• Simulation de lois normales multivariées : si $Z \sim \mathcal{N}(0, I)$ et $A = L L^T$, alors $LZ \sim \mathcal{N}(0, A)$. C'est la méthode de génération d'échantillons corrélés.

Cholesky vs Cholesky modifié (LDL^T)

Une variante utile, dite décomposition $LDL^T$, évite les racines carrées. On écrit $A = L D L^T$ avec $L$ triangulaire unitaire (1 sur la diagonale) et $D$ diagonale.

Avantages : pas de calcul de racines carrées (utile si les coefficients de $A$ sont rationnels), et on peut étendre à des matrices symétriques (non nécessairement définies positives) avec une $D$ contenant des coefficients négatifs.

Inconvénient : stocker et manipuler $L$ et $D$ séparément (plutôt que la seule matrice $L$ de Cholesky).

Implémentation numpy / scipy

En Python, on utilise numpy.linalg.cholesky(A) qui retourne directement $L$, ou scipy.linalg.cholesky(A, lower=True) pour plus de contrôle.

import numpy as np

L = np.linalg.cholesky(A)

assert np.allclose(L @ L.T, A)

Les implémentations professionnelles (LAPACK, utilisé sous le capot par numpy) gèrent finement la précision numérique et détectent si $A$ n'est pas définie positive (une des racines carrées devient négative).

Une question ou une suggestion ? Écrivez-nous.