194
5 Approximation des valeurs propres et des vecteurs propres
L’ex´ ecution du Programme 31 pour r´ esoudre le syst` eme (5.51), requiert 5
flops et l’´ evaluation d’une racine carr´ ee. Comme on l’a d´ ej` a remarqu´ e pour
les matrices de Householder, il n’est pas n´ ecessaire de calculer explicitement
la matrice de Givens G(i, k, θ) pour effectuer son produit avec une matrice
M∈ R
m×m . Nous utilisons pour cela les Programmes 32 et 33 (6m flops). En
observant la structure (5.43) de la matrice G(i, k, θ), il est clair que le premier
algorithme ne modifie que les lignes i et k de M, tandis que le second ne
modifie que les colonnes i et k.
Notons enfin que le calcul du vecteur de Householder v et des sinus et cosinus
de Givens (c, s), sont des op´ erations bien conditionn´ ees par rapport aux erreurs
d’arrondi (voir [GL89], p. 212-217 et les r´ ef´ erences cit´ ees).
La r´ esolution du syst` eme (5.51) est impl´ ement´ ee dans le Programme 31.
Les param` etres d’entr´ ee sont les composantes x i et x k du vecteur, et on a en
sortie les cosinus et sinus de Givens c et s.
Programme 31 - givcos : Calcul des cosinus et sinus de Givens
function [c,s]=givcos(xi, xk)
%GIVCOS Calcule les cosinus et sinus de Givens.
if xk==0
c=1; s=0;
else
if abs(xk)>abs(xi)
t=-xi/xk; s=1/sqrt(1+tˆ2); c=s*t;
else
t=-xk/xi; c=1/sqrt(1+tˆ2); s=c*t;
end
end
return
Les Programmes 32 et 33 calculent respectivement G(i, k, θ)
T M et MG(i, k, θ).
Les param` etres d’entr´ ee c et s sont les cosinus et sinus de Givens. Dans le
Programme 32, les indices i et k d´ esignent les lignes de la matrice M affect´ ees
par la mise `
a jour M ← G(i, k, θ)
T M, et j1 et j2 sont les indices des colonnes
qui interviennent dans le calcul. De mˆ eme, dans le Programme 33, i et k
d´ esignent les colonnes affect´ ees par la mise ` a jour M ← MG(i, k, θ), et j1 et
j2 sont les indices des lignes qui interviennent dans le calcul.
Programme 32 - garow : Produit G(i, k, θ)
T M
function [M]=garow(M,c,s,i,k,j1,j2)
%GAROW Produit de la transpos´ ee d’une matrice de rotation de Givens
% avec M.
for j=j1:j2
t1=M(i,j);
t2=M(k,j);
5 Approximation des valeurs propres et des vecteurs propres
L’ex´ ecution du Programme 31 pour r´ esoudre le syst` eme (5.51), requiert 5
flops et l’´ evaluation d’une racine carr´ ee. Comme on l’a d´ ej` a remarqu´ e pour
les matrices de Householder, il n’est pas n´ ecessaire de calculer explicitement
la matrice de Givens G(i, k, θ) pour effectuer son produit avec une matrice
M∈ R
m×m . Nous utilisons pour cela les Programmes 32 et 33 (6m flops). En
observant la structure (5.43) de la matrice G(i, k, θ), il est clair que le premier
algorithme ne modifie que les lignes i et k de M, tandis que le second ne
modifie que les colonnes i et k.
Notons enfin que le calcul du vecteur de Householder v et des sinus et cosinus
de Givens (c, s), sont des op´ erations bien conditionn´ ees par rapport aux erreurs
d’arrondi (voir [GL89], p. 212-217 et les r´ ef´ erences cit´ ees).
La r´ esolution du syst` eme (5.51) est impl´ ement´ ee dans le Programme 31.
Les param` etres d’entr´ ee sont les composantes x i et x k du vecteur, et on a en
sortie les cosinus et sinus de Givens c et s.
Programme 31 - givcos : Calcul des cosinus et sinus de Givens
function [c,s]=givcos(xi, xk)
%GIVCOS Calcule les cosinus et sinus de Givens.
if xk==0
c=1; s=0;
else
if abs(xk)>abs(xi)
t=-xi/xk; s=1/sqrt(1+tˆ2); c=s*t;
else
t=-xk/xi; c=1/sqrt(1+tˆ2); s=c*t;
end
end
return
Les Programmes 32 et 33 calculent respectivement G(i, k, θ)
T M et MG(i, k, θ).
Les param` etres d’entr´ ee c et s sont les cosinus et sinus de Givens. Dans le
Programme 32, les indices i et k d´ esignent les lignes de la matrice M affect´ ees
par la mise `
a jour M ← G(i, k, θ)
T M, et j1 et j2 sont les indices des colonnes
qui interviennent dans le calcul. De mˆ eme, dans le Programme 33, i et k
d´ esignent les colonnes affect´ ees par la mise ` a jour M ← MG(i, k, θ), et j1 et
j2 sont les indices des lignes qui interviennent dans le calcul.
Programme 32 - garow : Produit G(i, k, θ)
T M
function [M]=garow(M,c,s,i,k,j1,j2)
%GAROW Produit de la transpos´ ee d’une matrice de rotation de Givens
% avec M.
for j=j1:j2
t1=M(i,j);
t2=M(k,j);