3.3 M´ ethode d’´ elimination de Gauss et factorisation LU
81
Un exemple de factorisation LU en version jki et orient´ e colonne est donn´ e
dans le Programme 5. Cette version est appel´ ee GAXP Y −jki, car l’op´ eration
de base de cette impl´ ementation est le produit matrice-vecteur (GAXP Y
provenant de “sAXP Y G´ en´ eralis´ e”, ce qu’il faut interpr´ eter comme “SAXP Y
dans lequel le produit par un scalaire est remplac´ e par le produit par une
matrice”; pour plus de pr´ ecisions voir [DGK84]).
Programme 5 - lujki : Factorisation LU de la matrice A, version jki
function [A]=lujki(A)
% LUJKI Factorisation LU de la matrice A dans la version jki
% Y=LUJKI(A): U est stock´ e dans la partie triangulaire sup´ erieure
% de Y et L est stock´ e dans la partie triangulaire inf´ erieure
% stricte de Y.
[n,m]=size(A);
if n ˜= m, error(’Seulement les syst` emes carr´ es’); end
for j=1:n
if A(j,j)==0; error(’Pivot nul’); end
for k=1:j-1
i=[k+1:n]; A(i,j)=A(i,j)-A(i,k)*A(k,j);
end
i=[j+1:n]; A(i,j)=A(i,j)/A(j,j);
end
return
3.3.4 Formes compactes de factorisation
La factorisation dite de Crout et celle dite de Doolittle constituent des variantes de la factorisation LU. On les appelle aussi formes compactes de la
m´ ethode d’´ elimination de Gauss car elles n´ ecessitent moins de r´ esultats interm´ ediaires que la m´ ethode de Gauss classique pour produire une factorisation
de A.
Calculer la factorisation de A est formellement ´ equivalent `
a r´ esoudre le
syst` eme lin´ eaire suivant de n
2 ´ equations
a ij =
min(i,j)
r=1
l ir u rj ,
(3.39)
les inconnues ´ etant les n
2 + n coefficients des matrices triangulaires L et U. Si
on donne arbitrairement la valeur 1 `
a n coefficients, par exemple les ´ el´ ements
diagonaux de L ou de U, on aboutit respectivement aux m´ ethodes de Doolittle
et de Crout, qui constituent une mani` ere efficace de r´ esoudre le syst` eme (3.39).
Supposons que les k − 1 premi` eres colonnes de L et U soient disponibles
et fixons l kk = 1 (m´ ethode de Doolittle). La relation (3.39) donne alors