190
5 Approximation des valeurs propres et des vecteurs propres
5.6.4 M´ ethode QR de base en partant d’une matrice de
Hessenberg sup´ erieure
On propose dans le Programme 28 une impl´ ementation MATLAB simple de
la m´ ethode QR pour construire la d´ ecomposition de Schur r´ eelle de la matrice
A en partant de sa forme de Hessenberg sup´ erieure.
Le Programme 28 utilise le Programme 27 pour r´ eduire A sous sa forme
de Hessenberg sup´ erieure ; chaque factorisation QR dans (5.32) est effectu´ ee
avec le Programme 29 qui utilise les rotations de Givens. L’efficacit´ e globale
de l’algorithme est assur´ ee par l’utilisation des matrices de Givens (voir Section 5.6.5) et par la construction de la matrice Q
(k) = G
(k)
1 · · · G
(k)
n−1 dans la
fonction prodgiv, avec un coˆ ut de n
2
− 2 flops, sans calculer explicitement les
matrices de Givens G
(k)
j , pour j = 1, . . . , n − 1.
En ce qui concerne la stabilit´ e de la m´ ethode QR par rapport `
a la propagation des erreurs d’arrondi, on peut montrer que la forme de Schur r´ eelle
calcul´ ee ˆ
T satisfait
ˆ
T = Q
T (A + E)Q,
o` u Q est orthogonale et E 2 uA 2 , u ´ etant l’unit´ e d’arrondi de la machine.
Le Programme 28 retourne, apr` es nmax it´ erations de la m´ ethode QR, les
matrices T, Q et R de (5.32).
Programme 28 - hessqr : M´ ethode de Hessenberg-QR
function [T,Q,R]=hessqr(A,nmax)
%HESSQR M´ ethode de Hessenberg-QR.
% [T,Q,R]=HESSQR(A,NMAX) calcule la d´ ecomposition de Schur r´ eelle
% de la matrice A dans sa forme de Hessenberg en NMAX iterations.
[n,m]=size(A);
if n˜=m, error(’Seulement pour les matrices carr´ ees’); end
[T,Qhess]=houshess(A);
for j=1:nmax
[Q,R,c,s]= qrgivens(T);
T=R;
for k=1:n-1,
T=gacol(T,c(k),s(k),1,k+1,k,k+1);
end
end
return