5.6 La m´ ethode QR pour les matrices de Hessenberg
193
et qui retourne un vecteur q ∈ R
n−k (le vecteur de Householder w
(k) ), pour
un coˆ ut de l’ordre de n flops.
Soit M ∈ R
m×m une matrice quelconque qu’on veut multiplier par la
matrice de Householder P (5.38). En posant w = M
T v, on a
PM = M − βvw
T ,
β = 2/v
2
2 .
(5.49)
Ainsi, le produit PM se ram` ene ` a un produit matrice-vecteur (w = M
T v) plus
un produit vecteur-vecteur (vw
T ) ; le coˆ ut global du calcul de PM est donc
de 2(m
2 + m) flops. Par des consid´ erations analogues,
MP = M − βwv
T ,
(5.50)
o` u on a pos´ e w = Mv. Remarquer que (5.49) et (5.50) ne n´ ecessitent pas la
construction explicite de la matrice P. Ceci ram` ene le coˆ ut du calcul `
a m
2
flops, alors que si on avait effectu´ e le produit PM sans prendre en compte la
structure particuli` ere de P, on aurait augment´ e le nombre d’op´ erations de m
3
flops.
Programme 30 - vhouse : Construction du vecteur de Householder
function [v,beta]=vhouse(x)
%VHOUSE Vecteur de Householder
n=length(x); x=x/norm(x); s=x(2:n)’*x(2:n); v=[1; x(2:n)];
if s==0
beta=0;
else
mu=sqrt(x(1)ˆ2+s);
if x(1)<=0
v(1)=x(1)-mu;
else
v(1)=-s/(x(1)+mu);
end
beta=2*v(1)ˆ2/(s+v(1)ˆ2); v=v/v(1);
end
return
En ce qui concerne les matrices de rotation de Givens, le calcul de c et s
est effectu´ e comme suit. Supposons qu’on se donne deux indices i et k et
qu’on veuille annuler la k-i` eme composante d’un vecteur x ∈ R
n . En posant
r =
x 2
i + x 2
k , la relation (5.44) donne
c −s
s
c
x i
x k
=
r
0
.
(5.51)
Il n’est donc n´ ecessaire ni de calculer explicitement θ, ni d’´ evaluer une fonction
trigonom´ etrique.