3.5 Changement de pivot
93
U=triu(A); L=P*Minv;
return
function [Mk,Mkinv]=MGauss(A,k,n)
Mk=eye(n);
i=[k+1:n];
Mk(i,k)=-A(i,k)/A(k,k);
Mkinv=2*eye(n)-Mk;
return
function [Pk,Qk]=pivot(A,k,n,I)
[y,i]=max(abs(A(k:n,k:n)));
[piv,jpiv]=max(y);
ipiv=i(jpiv);
jpiv=jpiv+k-1;
ipiv=ipiv+k-1;
Pk=I; Pk(ipiv,ipiv)=0; Pk(k,k)=0; Pk(k,ipiv)=1; Pk(ipiv,k)=1;
Qk=I; Qk(jpiv,jpiv)=0; Qk(k,k)=0; Qk(k,jpiv)=1; Qk(jpiv,k)=1;
return
Remarque 3.3 La pr´ esence de grands pivots ne suffit pas ` a elle seule ` a garantir la pr´ ecision des solutions, comme le montre l’exemple suivant (pris dans
[JM92]). Consid´ erons le syst` eme lin´ eaire Ax = b suivant
⎡
⎣
−4000
2000 2000
2000 0.78125
0
2000
0
0
⎤
⎦
⎡
⎣
x 1
x 2
x 3
⎤
⎦ =
⎡
⎣
400
1.3816
1.9273
⎤
⎦ .
A la premi` ere ´ etape, le pivot est le terme diagonal −4000. Pourtant, la m´ ethode de Gauss appliqu´ ee ` a cette matrice donne
x = [0.00096365, −0.698496, 0.90042329]
T
dont la premi` ere composante diff` ere compl` etement de la premi` ere composante
de la solution exacte x = [1.9273, −0.698496, 0.9004233]
T .
La cause de ce comportement peut ˆ etre imput´ ee ` a la diff´ erence des ordres
de grandeurs entre les coefficients. Ce probl` eme peut ˆ etre corrig´ e par un scaling
convenable de la matrice (voir Section 3.11.1).
Remarque 3.4 (cas des matrices sym´ etriques) On a d´ ej` a not´ e que le
changement de pivot n’est pas strictement n´ ecessaire quand la matrice est
sym´ etrique d´ efinie positive. Le cas d’une matrice sym´ etrique mais non d´ efinie
positive m´ erite un commentaire particulier. Dans ce cas en effet, un changement de pivot risque de d´ etruire la sym´ etrie de la matrice. Ceci peut ˆ etre
´ evit´ e en effectuant un changement de pivot total de la forme PAP
T , mˆ eme si
ce changement de pivot se r´ eduit `
a un simple r´ earrangement des coefficients
93
U=triu(A); L=P*Minv;
return
function [Mk,Mkinv]=MGauss(A,k,n)
Mk=eye(n);
i=[k+1:n];
Mk(i,k)=-A(i,k)/A(k,k);
Mkinv=2*eye(n)-Mk;
return
function [Pk,Qk]=pivot(A,k,n,I)
[y,i]=max(abs(A(k:n,k:n)));
[piv,jpiv]=max(y);
ipiv=i(jpiv);
jpiv=jpiv+k-1;
ipiv=ipiv+k-1;
Pk=I; Pk(ipiv,ipiv)=0; Pk(k,k)=0; Pk(k,ipiv)=1; Pk(ipiv,k)=1;
Qk=I; Qk(jpiv,jpiv)=0; Qk(k,k)=0; Qk(k,jpiv)=1; Qk(jpiv,k)=1;
return
Remarque 3.3 La pr´ esence de grands pivots ne suffit pas ` a elle seule ` a garantir la pr´ ecision des solutions, comme le montre l’exemple suivant (pris dans
[JM92]). Consid´ erons le syst` eme lin´ eaire Ax = b suivant
⎡
⎣
−4000
2000 2000
2000 0.78125
0
2000
0
0
⎤
⎦
⎡
⎣
x 1
x 2
x 3
⎤
⎦ =
⎡
⎣
400
1.3816
1.9273
⎤
⎦ .
A la premi` ere ´ etape, le pivot est le terme diagonal −4000. Pourtant, la m´ ethode de Gauss appliqu´ ee ` a cette matrice donne
x = [0.00096365, −0.698496, 0.90042329]
T
dont la premi` ere composante diff` ere compl` etement de la premi` ere composante
de la solution exacte x = [1.9273, −0.698496, 0.9004233]
T .
La cause de ce comportement peut ˆ etre imput´ ee ` a la diff´ erence des ordres
de grandeurs entre les coefficients. Ce probl` eme peut ˆ etre corrig´ e par un scaling
convenable de la matrice (voir Section 3.11.1).
Remarque 3.4 (cas des matrices sym´ etriques) On a d´ ej` a not´ e que le
changement de pivot n’est pas strictement n´ ecessaire quand la matrice est
sym´ etrique d´ efinie positive. Le cas d’une matrice sym´ etrique mais non d´ efinie
positive m´ erite un commentaire particulier. Dans ce cas en effet, un changement de pivot risque de d´ etruire la sym´ etrie de la matrice. Ceci peut ˆ etre
´ evit´ e en effectuant un changement de pivot total de la forme PAP
T , mˆ eme si
ce changement de pivot se r´ eduit `
a un simple r´ earrangement des coefficients