3.10 Un calcul approch´ e de K(A)
105
Par cons´ equent
x − x ∞
x ∞
uK ∞ (A).
(3.61)
En supposant que u β
−t et K ∞ (A) β
m , on en d´ eduit que la solution
x
calcul´ ee par la m´ ethode de Gauss aura au moins t − m chiffres exacts, o` u t
est le nombre de chiffres de la mantisse. En d’autres termes, le mauvais conditionnement d’un syst` eme d´ epend `
a la fois de la pr´ ecision de l’arithm´ etique `
a
virgule flottante utilis´ ee et de la tol´ erance requise pour la solution.
3.10 Un calcul approch´ e de K(A)
Supposons que le syst` eme lin´ eaire (3.2) ait ´ et´ e r´ esolu par une m´ ethode de factorisation. La pr´ ecision de la solution calcul´ ee peut ˆ etre ´ evalu´ ee en utilisant
l’analyse effectu´ ee ` a la Section 3.9. Mais il faut pour cela disposer d’une estimation
K(A) du conditionnement K(A) de A. En effet, s’il est facile d’´ evaluer
pour une norme donn´ ee (par exemple · · 1 ou · · ∞ ), il n’est en aucun
cas raisonnable de calculer A
−1 dans le seul but d’´ evaluer A
−1
.
Un algorithme pour le calcul approch´ e de K 1 (A) (c’est-` a-dire le conditionnement pour la norme · · 1 ) est pr´ esent´ e en d´ etail dans [QSS07], Section 3.10. Nous en proposons une impl´ ementation dans le Programme 14 cidessous. C’est le mˆ eme algorithme qui est impl´ ement´ e dans la biblioth` eque
LINPACK [BDMS79] et dans la fonction rcond de MATLAB. Cette derni` ere
retourne l’inverse de
K 1 (A) afin d’´ eviter les erreurs d’arrondi. Un estimateur
plus pr´ ecis, d´ ecrit dans [Hig88], est impl´ ement´ e dans la fonction condest de
MATLAB.
Le Programme 14 propose une ´ evaluation approch´ ee de K 1 (A) pour une
matrice A de forme quelconque. Les param` etres en entr´ ee sont la taille n de
A, la matrice A et les matrices L, U de la factorisation PA=LU.
Programme 14 - condest2 : Evaluation approch´ ee de K 1 (A)
function [k1]=condest2(A,L,U,theta)
%CONDEST2 Conditionnement
% K1=CONDEST2(A,L,U,THETA) renvoie une approximation du conditionnement
% de la matrice A. L et U sont les matrices de la factorisation LU de A.
% THETA contient des nombres al´ eatoires.
[n,m]=size(A);
if n ˜= m, error(’Seulement des matrices carr´ ees’); end
p = zeros(1,n);
for k=1:n
zplus=(theta(k)-p(k))/U(k,k); zminu=(-theta(k)-p(k))/U(k,k);
105
Par cons´ equent
x − x ∞
x ∞
uK ∞ (A).
(3.61)
En supposant que u β
−t et K ∞ (A) β
m , on en d´ eduit que la solution
x
calcul´ ee par la m´ ethode de Gauss aura au moins t − m chiffres exacts, o` u t
est le nombre de chiffres de la mantisse. En d’autres termes, le mauvais conditionnement d’un syst` eme d´ epend `
a la fois de la pr´ ecision de l’arithm´ etique `
a
virgule flottante utilis´ ee et de la tol´ erance requise pour la solution.
3.10 Un calcul approch´ e de K(A)
Supposons que le syst` eme lin´ eaire (3.2) ait ´ et´ e r´ esolu par une m´ ethode de factorisation. La pr´ ecision de la solution calcul´ ee peut ˆ etre ´ evalu´ ee en utilisant
l’analyse effectu´ ee ` a la Section 3.9. Mais il faut pour cela disposer d’une estimation
K(A) du conditionnement K(A) de A. En effet, s’il est facile d’´ evaluer
pour une norme donn´ ee (par exemple · · 1 ou · · ∞ ), il n’est en aucun
cas raisonnable de calculer A
−1 dans le seul but d’´ evaluer A
−1
.
Un algorithme pour le calcul approch´ e de K 1 (A) (c’est-` a-dire le conditionnement pour la norme · · 1 ) est pr´ esent´ e en d´ etail dans [QSS07], Section 3.10. Nous en proposons une impl´ ementation dans le Programme 14 cidessous. C’est le mˆ eme algorithme qui est impl´ ement´ e dans la biblioth` eque
LINPACK [BDMS79] et dans la fonction rcond de MATLAB. Cette derni` ere
retourne l’inverse de
K 1 (A) afin d’´ eviter les erreurs d’arrondi. Un estimateur
plus pr´ ecis, d´ ecrit dans [Hig88], est impl´ ement´ e dans la fonction condest de
MATLAB.
Le Programme 14 propose une ´ evaluation approch´ ee de K 1 (A) pour une
matrice A de forme quelconque. Les param` etres en entr´ ee sont la taille n de
A, la matrice A et les matrices L, U de la factorisation PA=LU.
Programme 14 - condest2 : Evaluation approch´ ee de K 1 (A)
function [k1]=condest2(A,L,U,theta)
%CONDEST2 Conditionnement
% K1=CONDEST2(A,L,U,THETA) renvoie une approximation du conditionnement
% de la matrice A. L et U sont les matrices de la factorisation LU de A.
% THETA contient des nombres al´ eatoires.
[n,m]=size(A);
if n ˜= m, error(’Seulement des matrices carr´ ees’); end
p = zeros(1,n);
for k=1:n
zplus=(theta(k)-p(k))/U(k,k); zminu=(-theta(k)-p(k))/U(k,k);