La décomposition LU, étape par étape

Factoriser une matrice en parties triangulaires inférieure et supérieure, pourquoi c’est plus rapide que de refaire l’élimination, et comment Cholesky en est le cas particulier.

La décomposition LU écrit une matrice carrée comme le produit d’une matrice triangulaire inférieure par une triangulaire supérieure : A = L·U. Les facteurs sortent directement de l’élimination de Gauss — U est la forme échelonnée, et L conserve les multiplicateurs utilisés pour y parvenir.

À quoi ça sert

Parce que la factorisation est réutilisable. Résoudre Ax = b depuis zéro coûte environ n³/3 opérations. Une fois L et U obtenues, chaque nouveau second membre ne coûte plus que n² : résolvez Ly = b par substitution avant, puis Ux = y par substitution arrière. Avec des dizaines de seconds membres, le gain est considérable.

Le déterminant devient gratuit lui aussi : c’est le produit de la diagonale de U, multiplié par −1 pour chaque échange de lignes effectué.

Le pivotage

Toutes les matrices n’admettent pas un A = L·U simple : un zéro en position de pivot casse la méthode. La parade est une matrice de permutation, d’où P·A = L·U. En pratique on pivote de toute façon, car choisir le plus grand pivot disponible contient les erreurs d’arrondi.

Cholesky : le cas symétrique

Si A est symétrique définie positive, elle se factorise en A = L·Lᵀ : un seul facteur triangulaire suffit. Cholesky est environ deux fois plus rapide que LU et numériquement très stable, d’où sa domination en optimisation, en moindres carrés et en statistique (les matrices de covariance sont symétriques définies positives par construction).

Si l’algorithme réclame la racine carrée d’un nombre négatif, c’est que la matrice n’était pas définie positive — Cholesky sert donc aussi de test de cette propriété.