188
5 Approximation des valeurs propres et des vecteurs propres
colonnes. Apr` es n − 2 ´ etapes de la r´ eduction de Householder, on obtient une
matrice H = A
(n−2) sous la forme de Hessenberg sup´ erieure.
Remarque 5.4 (le cas sym´ etrique) Si A est sym´ etrique, la transformation (5.45) conserve cette propri´ et´ e. En effet
(A
(k) )
T = (Q
T
(k) AQ (k) )
T = A
(k) ,
∀k ≥ 1,
H doit donc ˆ etre tridiagonale. Ses valeurs propres peuvent ˆ etre calcul´ ees de
mani` ere efficace en utilisant la m´ ethode des suites de Sturm qui a un coˆ ut de
l’ordre de n flops. Nous verrons ceci `
a la Section 5.8.2.
Une impl´ ementation MATLAB de la m´ ethode de Householder est propos´ ee
dans le Programme 27. On utilise le Programme 30 pour calculer le vecteur
de Householder. En sortie, la matrice H est de Hessenberg, Q est orthogonale
et H = Q
T AQ.
Programme 27 - houshess : M´ ethode de Householder-Hessenberg
function [H,Q]=houshess(A)
%HOUSHESS M´ ethode de Householder-Hessenberg.
% [H,Q]=HOUSHESS(A) calcule les matrices H et Q telles que H=Q’AQ.
[n,m]=size(A);
if n˜=m; error(’Seulement pour les matrices carr´ ees’); end
Q=eye(n); H=A;
for k=1:n-2
[v,beta]=vhouse(H(k+1:n,k)); I=eye(k); N=zeros(k,n-k);
m=length(v);
R=eye(m)-beta*v*v’;
H(k+1:n,k:n)=R*H(k+1:n,k:n);
H(1:n,k+1:n)=H(1:n,k+1:n)*R; P=[I, N; N’, R]; Q=Q*P;
end
return
L’algorithme du Programme 27 a un coˆ ut de 10n
3 /3 flops et il est bien
conditionn´ e par rapport aux erreurs d’arrondi. On a en effet l’estimation (voir
[Wil65], p. 351)
H = Q
T (A + E) Q,
E F ≤ cn
2 uA F ,
(5.46)
o` u
H est la matrice de Hessenberg calcul´ ee par le Programme 27, Q est une
matrice orthogonale, c est une constante, u est l’unit´ e d’arrondi et · · F est
la norme de Frobenius (voir (1.19)).
Exemple 5.7 Consid´ erons la r´ eduction de la matrice de Hilbert H4 ∈ R
4×4 sous la
forme de Hessenberg sup´ erieure. Comme H4 est sym´ etrique, sa forme de Hessenberg