D´ecompositions LU et Choleski
D´ecompositions LU et Choleski
Programming, Math · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente les décompositions LU et de Choleski, deux méthodes fondamentales en algèbre linéaire pour la résolution de systèmes linéaires et l'inversion de matrices. Destiné aux étudiants préparant l’épreuve d’informatique de l’École Polytechnique, il expose les définitions, conditions d’existence, algorithmes de calcul, ainsi que des exemples et démonstrations, en utilisant le langage Maple.
Soit A une matrice carrée inversible d’ordre n sur un corps K. Une décomposition LU de A est une écriture :
A = LU
où L est une matrice triangulaire inférieure à diagonale unité (tous les coefficients diagonaux valent 1) et U est une matrice triangulaire supérieure inversible (ses coefficients diagonaux sont non nuls).
On note aij, lij et uij les coefficients généraux de A, L et U respectivement. Alors :
aij = ∑k=1min(i,j) lik ukj
En particulier :
Ces relations permettent de calculer progressivement les coefficients de L et U, colonne par colonne.
La décomposition LU existe et est unique si et seulement si tous les mineurs principaux de A sont non nuls. Les mineurs principaux ∆k sont les déterminants des sous-matrices carrées extraites des k premières lignes et colonnes de A.
On peut traduire les formules précédentes en une procédure algorithmique (ici en pseudo-code Maple) :
LU1 := proc(A::array, L::name, U::name, n::integer)
local i, j, k, c;
L := matrix(n, n, 0);
U := matrix(n, n, 0);
for j to n do
for i to j do
c := A[i, j];
for k to i-1 do
c := c - L[i, k] * U[k, j];
od;
U[i, j] := c;
od;
L[j, j] := 1;
for i from j+1 to n do
c := A[i, j];
for k to j-1 do
c := c - L[i, k] * U[k, j];
od;
L[i, j] := c / U[j, j];
od;
od;
end:
Cette procédure calcule explicitement L et U à partir de A.
Pour économiser la mémoire, on peut stocker simultanément L et U dans la même matrice B, définie par :
La formule de calcul devient :
Pour j de 1 à n, et pour i de 1 à n :
bij = aij − ∑k=1min(i,j)-1 bik bkj
Si i > j, alors :
bij ← bij / bjj
Cette méthode permet de modifier la matrice A directement en B, évitant la création de matrices supplémentaires.
LU2 := proc(A::array, n)
local i, j, k, p;
for j to n do
for i to n do
for k to min(i, j) - 1 do
A[i, j] := A[i, j] - A[i, k] * A[k, j];
od;
if i > j then
A[i, j] := A[i, j] / A[j, j];
fi;
od;
od;
end:
La décomposition LU classique nécessite que les pivots (coefficients diagonaux de U) soient non nuls. Si un pivot est nul ou trop petit, on effectue des échanges de lignes. Cela revient à décomposer une matrice P A, où P est une matrice de permutation.
Une matrice de permutation P correspond à une permutation σ de {1, ..., n} telle que :
pij = δσ(i), j
où δ est le symbole de Kronecker.
On a la propriété suivante :
Proposition : Pour toute matrice inversible A, il existe une matrice de permutation P telle que P A admet une décomposition LU.
Cette procédure recherche à chaque étape le pivot de valeur absolue maximale dans la colonne courante, échange les lignes correspondantes, puis effectue la décomposition in situ.
LU := proc(A::array, s::name, n::integer)
local i, j, k, p, q, t;
s := array(1..n);
for i to n do s[i] := i od;
for j to n do
p := A[j, j];
i := j;
for k from j+1 to n do
if abs(A[k, j]) > abs(p) then
p := A[k, j];
i := k;
fi;
od;
if p = 0 then
ERROR("matrice non inversible");
fi;
if i <> j then
for k to n do
t := A[j, k];
A[j, k] := A[i, k];
A[i, k] := t;
od;
t := s[j];
s[j] := s[i];
s[i] := t;
fi;
for k from j+1 to n do
A[k, j] := A[k, j] / p;
od;
for i from j+1 to n do
for k from j+1 to n do
A[i, k] := A[i, k] - A[i, j] * A[j, k];
od;
od;
od;
end:
Soit P la matrice de permutation associée à la décomposition P A = LU. Le système AX = B est équivalent à :
LU X = P B
On pose Y = U X, alors :
Les formules sont :
yi = bσ(i) − ∑j=1i−1 lij yj
xi = (yi − ∑j=i+1n uij xj) / uii
syst := proc(A::array, B::array, s::array, n::integer)
local X, i, j, t;
X := array(1..n);
for i to n do
X[i] := B[s[i]];
od;
for i from 2 to n do
t := 0;
for j to i-1 do
t := t + A[i, j] * X[j];
od;
X[i] := X[i] - t;
od;
for i from n to 1 by -1 do
t := 0;
for j from i+1 to n do
t := t + A[i, j] * X[j];
od;
X[i] := (X[i] - t) / A[i, i];
od;
RETURN(X);
end:
Considérons la matrice :
| 2 | −3 | 1 | −1 |
| −2 | 2 | −3 | 2 |
| 4 | −9 | −2 | 3 |
| −2 | 5 | 5 | −4 |
et le vecteur second membre B = (1, 6, 5, 2). La décomposition LU avec permutation permet de résoudre le système AX = B avec une solution X = (−17, −10, −2, −7).
On remarque que la méthode LU avec pivot partiel est plus précise que la méthode LU2 sans permutation, notamment lorsque certains coefficients sont très petits.
Pour inverser une matrice A, on résout n systèmes linéaires AX = B où B est chaque colonne de la matrice identité.
inv := proc(A::array, n::integer)
local B, M, AA, s, i, j;
M := array(1..n, 1..n);
AA := copy(A);
LU(AA, 's', n);
for j to n do
B := array(1..n, 0);
B[j] := 1;
B := syst(AA, B, s, n);
for i to n do
M[i, j] := B[i];
od;
od;
RETURN(eval(M));
end:
Cette méthode est efficace et donne un résultat identique à l’inversion intégrée de Maple.
Considérons une matrice S réelle, carrée d’ordre n, symétrique et définie positive. Cela signifie que :
La décomposition de Choleski affirme qu’il existe une unique matrice triangulaire inférieure L à coefficients diagonaux strictement positifs telle que :
S = L tL
En identifiant les coefficients, on obtient :
ljj2 = sjj − ∑k=1j−1 ljk2
lij = (1 / ljj) (sij − ∑k=1j−1 lik ljk)
Ces formules permettent de calculer L colonne par colonne.
choleski := proc(S::array, n::integer)
local L, i, j, k, t;
L := matrix(n, n, 0);
for j to n do
t := S[j, j];
for k to j-1 do
t := t - L[j, k]^2;
od;
if t <= 0 then
ERROR("matrice non définie positive");
fi;
L[j, j] := sqrt(t);
for i from j+1 to n do
t := S[i, j];
for k to j-1 do
t := t - L[i, k] * L[j, k];
od;
L[i, j] := t / L[j, j];
od;
od;
RETURN(eval(L));
end:
Soit la matrice symétrique :
| 1 | −2 | 4 |
| −2 | 13 | −11 |
| 4 | −11 | 21 |
La décomposition de Choleski donne :
| 1 | 0 | 0 |
| −2 | 3 | 0 |
| 4 | −1 | 2 |
et on vérifie que L tL = S.