92
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
Une fois calcul´ ees les matrices L, U et P, la r´ esolution du syst` eme initial
se ram` ene ` a la r´ esolution des syst` emes triangulaires Ly = Pb et Ux = y. Remarquer que les coefficients de la matrice L co¨ ıncident avec les multiplicateurs
calcul´ es par une factorisation LU de la matrice PA sans changement de pivot.
Si on adopte une strat´ egie de pivot total, `
a la premi` ere ´ etape, une fois trouv´ e
l’´ el´ ement a qr de plus grand module dans la sous-matrice A(1 : n, 1 : n), on
doit ´ echanger la premi` ere ligne et la premi` ere colonne avec la q-i` eme ligne
et la r-i` eme colonne. Ceci conduit ` a la matrice P 1 A
(1) Q 1 , o` u P 1 et Q 1 sont
respectivement des matrices de permutation de lignes et de colonnes.
A ce stade, la matrice M 1 est donc telle que A
(2) = M 1 P 1 A
(1) Q 1 . En r´ ep´ etant
ce processus, on obtient ` a la derni` ere ´ etape
U = A
(n) = M n−1 P n−1 · · · M 1 P 1 A
(1) Q 1 · · · Q n−1 ,
au lieu de (3.48).
Dans le cas d’un changement de pivot total, la factorisation LU devient
PAQ = LU
o` u Q = Q 1 · · · Q n−1 est une matrice de permutation prenant en compte toutes
les permutations effectu´ ees. Par construction, la matrice L est encore triangulaire inf´ erieure, et ses ´ el´ ements ont tous un module inf´ erieur ou ´ egal ` a 1.
Comme pour le changement de pivot partiel, les ´ el´ ements de L sont les multiplicateurs produits par la factorisation LU de la matrice PAQ sans changement
de pivot.
Le Programme 9 est un code MATLAB de la factorisation LU avec changement de pivot total. Pour une impl´ ementation efficace de la factorisation
LU avec changement de pivot partiel, nous renvoyons le lecteur `
a la fonction
lu de MATLAB.
Programme 9 - LUpivtot : Factorisation LU avec changement de pivot total
function [L,U,P,Q]=LUpivtot(A)
%LUPIVOT Factorisation LU avec changement de pivot total
% [L,U,P,Q]=LUPIVOT(A) retourne une matrice triangulaire inf´ erieure L,
% une matrice triangulaire sup´ erieure U et des matrices de
% permutation P et Q telles que P*A*Q=L*U.
[n,m]=size(A);
if n ˜= m, error(’Seulement syst` emes carr´ es’); end
P=eye(n); Q=P; Minv=P; I=eye(n);
for k=1:n-1
[Pk,Qk]=pivot(A,k,n,I); A=Pk*A*Qk;
[Mk,Mkinv]=MGauss(A,k,n);
A=Mk*A; P=Pk*P;
Q=Q*Qk;
Minv=Minv*Pk*Mkinv;
end
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
Une fois calcul´ ees les matrices L, U et P, la r´ esolution du syst` eme initial
se ram` ene ` a la r´ esolution des syst` emes triangulaires Ly = Pb et Ux = y. Remarquer que les coefficients de la matrice L co¨ ıncident avec les multiplicateurs
calcul´ es par une factorisation LU de la matrice PA sans changement de pivot.
Si on adopte une strat´ egie de pivot total, `
a la premi` ere ´ etape, une fois trouv´ e
l’´ el´ ement a qr de plus grand module dans la sous-matrice A(1 : n, 1 : n), on
doit ´ echanger la premi` ere ligne et la premi` ere colonne avec la q-i` eme ligne
et la r-i` eme colonne. Ceci conduit ` a la matrice P 1 A
(1) Q 1 , o` u P 1 et Q 1 sont
respectivement des matrices de permutation de lignes et de colonnes.
A ce stade, la matrice M 1 est donc telle que A
(2) = M 1 P 1 A
(1) Q 1 . En r´ ep´ etant
ce processus, on obtient ` a la derni` ere ´ etape
U = A
(n) = M n−1 P n−1 · · · M 1 P 1 A
(1) Q 1 · · · Q n−1 ,
au lieu de (3.48).
Dans le cas d’un changement de pivot total, la factorisation LU devient
PAQ = LU
o` u Q = Q 1 · · · Q n−1 est une matrice de permutation prenant en compte toutes
les permutations effectu´ ees. Par construction, la matrice L est encore triangulaire inf´ erieure, et ses ´ el´ ements ont tous un module inf´ erieur ou ´ egal ` a 1.
Comme pour le changement de pivot partiel, les ´ el´ ements de L sont les multiplicateurs produits par la factorisation LU de la matrice PAQ sans changement
de pivot.
Le Programme 9 est un code MATLAB de la factorisation LU avec changement de pivot total. Pour une impl´ ementation efficace de la factorisation
LU avec changement de pivot partiel, nous renvoyons le lecteur `
a la fonction
lu de MATLAB.
Programme 9 - LUpivtot : Factorisation LU avec changement de pivot total
function [L,U,P,Q]=LUpivtot(A)
%LUPIVOT Factorisation LU avec changement de pivot total
% [L,U,P,Q]=LUPIVOT(A) retourne une matrice triangulaire inf´ erieure L,
% une matrice triangulaire sup´ erieure U et des matrices de
% permutation P et Q telles que P*A*Q=L*U.
[n,m]=size(A);
if n ˜= m, error(’Seulement syst` emes carr´ es’); end
P=eye(n); Q=P; Minv=P; I=eye(n);
for k=1:n-1
[Pk,Qk]=pivot(A,k,n,I); A=Pk*A*Qk;
[Mk,Mkinv]=MGauss(A,k,n);
A=Mk*A; P=Pk*P;
Q=Q*Qk;
Minv=Minv*Pk*Mkinv;
end