méthode de Cholesky

Imaginez un tableau carré de nombres qui se répondent de part et d'autre de sa diagonale. La méthode de Cholesky remplace ce tableau par un tableau triangulaire plus simple et sa copie transposée.

Cette décomposition évite de refaire deux fois des calculs équivalents. Elle rend ainsi plus directe la résolution de certains systèmes d'équations, à condition que la matrice soit symétrique et définie positive.

La décomposition de Cholesky est une factorisation réservée aux matrices carrées réelles symétriques définies positives. La matrice donnée est notée A. La méthode construit une matrice triangulaire inférieure L dont les coefficients diagonaux sont strictement positifs, telle que :

La lettre T indique la transposition : les lignes de L deviennent les colonnes de L^T. Le choix d'une diagonale positive rend L unique. Cette structure transforme le système Ax = b en deux systèmes triangulaires successifs : on résout d'abord Ly = b, puis L^Tx = y. Elle donne aussi le déterminant de A par le carré du produit des coefficients diagonaux de L. En exploitant la symétrie, elle demande environ deux fois moins de calculs qu'une décomposition LU générale dans ce domaine. Elle peut enfin intervenir comme étape efficace dans des calculs numériques liés aux valeurs propres.

Si A est une matrice réelle symétrique définie positive, alors il existe une unique matrice triangulaire inférieure L à diagonale strictement positive telle que A = LL^T. Le calcul avance colonne après colonne : chaque coefficient diagonal est la racine carrée d'un reste positif, puis les coefficients situés dessous sont obtenus par division par ce pivot. Le procédé s'arrête lorsque la dernière colonne de L est déterminée.

La matrice A doit être carrée, réelle et symétrique : son coefficient situé à la ligne i et à la colonne j doit égaler celui situé à la ligne j et à la colonne i. Elle doit aussi être définie positive, ce qui signifie que, pour tout vecteur colonne non nul x, la quantité suivante est strictement positive : $x^{\mathsf{T}}Ax>0x^\{\backslash mathsf\; T\}Ax>0$. Sous ces conditions, tous les pivots rencontrés sont positifs et L existe de manière unique avec une diagonale positive.

Une matrice symétrique comme ne suffit pas : avec le vecteur x de coordonnées 1 et −1, on obtient x^TAx = −2. La racine carrée d'un pivot négatif bloque la factorisation réelle ; il faut alors employer une factorisation adaptée aux matrices symétriques indéfinies ou une décomposition LU.

On veut résoudre le système Ax = b. Les données sont la matrice A de lignes (4, 2) et (2, 3), et le vecteur b de coordonnées 6 et 5. On cherche une matrice L de lignes (ℓ₁₁, 0) et (ℓ₂₁, ℓ₂₂).

1. Le premier coefficient diagonal vérifie ℓ₁₁² = 4, donc ℓ₁₁ = 2.
2. Le coefficient inférieur vérifie 2ℓ₂₁ = 2, donc ℓ₂₁ = 1.
3. Le dernier coefficient vérifie ℓ₂₁² + ℓ₂₂² = 3, donc ℓ₂₂ = √2.

La factorisation obtenue est : La figure matérialise ce produit et les trois valeurs calculées.

4. La résolution de Ly = b donne y₁ = 3 puis y₂ = √2.
5. La résolution de L^Tx = y donne x₂ = 1 puis x₁ = 1. Le résultat est donc le vecteur x de coordonnées 1 et 1. Le contrôle direct donne Ax de coordonnées 4 + 2 = 6 et 2 + 3 = 5, exactement comme b.

Pour résoudre plusieurs systèmes Ax = b avec la même matrice A, on calcule L une seule fois. Chaque nouveau second membre b ne demande ensuite que deux résolutions triangulaires.

Pour calculer le déterminant, on multiplie les coefficients diagonaux de L puis on élève le résultat au carré. Dans l'exemple, (2 × √2)² = 8, ce qui coïncide avec 4 × 3 − 2 × 2.

Quand la matrice n'est pas symétrique définie positive, une décomposition LU est une alternative plus générale. Quand elle remplit ces conditions, Cholesky exploite sa symétrie et demande environ deux fois moins d'opérations que LU.

Décomposition LU. Elle écrit une matrice comme le produit d'une matrice triangulaire inférieure et d'une matrice triangulaire supérieure qui n'est pas nécessairement sa transposée. Pour la matrice symétrique définie positive de l'exemple, Cholesky produit directement L et L^T ; pour une matrice non symétrique, on se tourne plutôt vers LU.

Élimination de Gauss. L'élimination transforme directement un système par opérations sur les lignes. Cholesky commence par factoriser la matrice ; ce facteur peut ensuite servir à plusieurs seconds membres, comme lorsque A reste fixe et que b change.

Symétrique ne signifie pas définie positive. Un pivot nul ou négatif pendant le calcul signale que la factorisation de Cholesky réelle ne peut pas continuer. La matrice de lignes (1, 2) et (2, 1) fournit un pivot final égal à −3 ; il faut changer de factorisation.

Positive au sens large ne suffit pas à l'unicité annoncée. Si x^TAx peut valoir zéro pour un vecteur non nul, la matrice n'est que semi-définie positive. Un coefficient diagonal de L peut alors être nul, et la procédure fondée sur une division par ce pivot peut se bloquer.

La diagonale positive fixe le signe. Sans cette convention, changer simultanément le signe d'une colonne de L ne modifie pas LL^T. L'unicité porte donc sur le facteur triangulaire dont chaque coefficient diagonal est strictement positif.

Les valeurs propres ne sortent pas directement de L. La factorisation peut accélérer des méthodes numériques qui les estiment, mais ses coefficients diagonaux ne sont pas, en général, les valeurs propres de A. Dans l'exemple, la diagonale de L vaut 2 et √2, tandis que les valeurs propres de A sont (7 + √17)/2 et (7 − √17)/2.

Symétrique positive (matrice) précise la condition qui garantit l'existence de la factorisation et la positivité des pivots.

LU (décomposition) présente la factorisation triangulaire plus générale à employer lorsque les hypothèses de Cholesky ne sont pas réunies.