5.6 La m´ ethode QR pour les matrices de Hessenberg
183
Remarquer la structure “presque diagonale" de la matrice T
(20) et les effets d’arrondi
qui alt` erent l´ eg` erement la sym´ etrie pr´ evue. On trouve une bonne correspondance
entre les coefficients sous-diagonaux et l’estimation (5.37).
•
Une impl´ ementation MATLAB de la m´ ethode QR de base est donn´ ee dans
le Programme 26. La factorisation QR est effectu´ ee en utilisant le proc´ ed´ e de
Gram-Schmidt modifi´ e (Programme 8). Le param` etre d’entr´ ee nmax d´ esigne
le nombre maximum d’it´ erations admissible, et les param` etres de sortie T, Q
et R sont les matrices T, Q et R de (5.32) apr` es nmax it´ erations de la m´ ethode
QR.
Programme 26 - basicqr : M´ ethode QR de base
function [T,Q,R]=basicqr(A,nmax)
%BASICQR M´ ethode QR de base
% [T,Q,R]=BASICQR(A,NMAX) effectue NMAX it´ erations de la
% version de base de la m´ ethode QR
T=A;
for i=1:nmax
[Q,R]=modgrams(T);
T=R*Q;
end
return
5.6 La m´ ethode QR pour les matrices de Hessenberg
L’impl´ ementation na¨ ıve de la m´ ethode QR vue ` a la section pr´ ec´ edente repr´ esente un calcul dont le coˆ ut (pour une matrice pleine) est de l’ordre de n
3
flops par it´ eration. Dans cette section, nous proposons une variante, appel´ ee
m´ ethode QR-Hessenberg, qui permet une grande ´ economie de calcul. L’id´ ee
consiste ` a d´ emarrer les it´ erations avec une matrice T
(0) de type Hessenberg
sup´ erieure, c’est-` a-dire telle que t
(0)
ij = 0 pour i > j + 1. On peut en effet
montrer qu’avec ce choix le calcul de T
(k) dans (5.32) ne requiert que n
2 flops
par it´ eration.
Afin d’assurer l’efficacit´ e et la stabilit´ e de l’algorithme, on utilise des matrices de transformation appropri´ ees. Plus pr´ ecis´ ement, la r´ eduction pr´ eliminaire de la matrice A sous la forme de Hessenberg sup´ erieure est r´ ealis´ ee avec
des matrices de Householder, tandis que la factorisation QR de T
(k) est effectu´ ee avec des matrices de Givens, plutˆ ot que par le proc´ ed´ e de Gram-Schmidt
modifi´ e vu `
a la Section 3.4.3.
Nous d´ ecrivons bri` evement les matrices de Householder et de Givens dans la
prochaine section, et nous renvoyons `
a la Section 5.6.5 pour les impl´ ementations. L’algorithme ainsi que des exemples de calcul de la forme de Schur
183
Remarquer la structure “presque diagonale" de la matrice T
(20) et les effets d’arrondi
qui alt` erent l´ eg` erement la sym´ etrie pr´ evue. On trouve une bonne correspondance
entre les coefficients sous-diagonaux et l’estimation (5.37).
•
Une impl´ ementation MATLAB de la m´ ethode QR de base est donn´ ee dans
le Programme 26. La factorisation QR est effectu´ ee en utilisant le proc´ ed´ e de
Gram-Schmidt modifi´ e (Programme 8). Le param` etre d’entr´ ee nmax d´ esigne
le nombre maximum d’it´ erations admissible, et les param` etres de sortie T, Q
et R sont les matrices T, Q et R de (5.32) apr` es nmax it´ erations de la m´ ethode
QR.
Programme 26 - basicqr : M´ ethode QR de base
function [T,Q,R]=basicqr(A,nmax)
%BASICQR M´ ethode QR de base
% [T,Q,R]=BASICQR(A,NMAX) effectue NMAX it´ erations de la
% version de base de la m´ ethode QR
T=A;
for i=1:nmax
[Q,R]=modgrams(T);
T=R*Q;
end
return
5.6 La m´ ethode QR pour les matrices de Hessenberg
L’impl´ ementation na¨ ıve de la m´ ethode QR vue ` a la section pr´ ec´ edente repr´ esente un calcul dont le coˆ ut (pour une matrice pleine) est de l’ordre de n
3
flops par it´ eration. Dans cette section, nous proposons une variante, appel´ ee
m´ ethode QR-Hessenberg, qui permet une grande ´ economie de calcul. L’id´ ee
consiste ` a d´ emarrer les it´ erations avec une matrice T
(0) de type Hessenberg
sup´ erieure, c’est-` a-dire telle que t
(0)
ij = 0 pour i > j + 1. On peut en effet
montrer qu’avec ce choix le calcul de T
(k) dans (5.32) ne requiert que n
2 flops
par it´ eration.
Afin d’assurer l’efficacit´ e et la stabilit´ e de l’algorithme, on utilise des matrices de transformation appropri´ ees. Plus pr´ ecis´ ement, la r´ eduction pr´ eliminaire de la matrice A sous la forme de Hessenberg sup´ erieure est r´ ealis´ ee avec
des matrices de Householder, tandis que la factorisation QR de T
(k) est effectu´ ee avec des matrices de Givens, plutˆ ot que par le proc´ ed´ e de Gram-Schmidt
modifi´ e vu `
a la Section 3.4.3.
Nous d´ ecrivons bri` evement les matrices de Householder et de Givens dans la
prochaine section, et nous renvoyons `
a la Section 5.6.5 pour les impl´ ementations. L’algorithme ainsi que des exemples de calcul de la forme de Schur