198
5 Approximation des valeurs propres et des vecteurs propres
Programme 34 - qrshift : M´ ethode QR avec translations
function [T,iter]=qrshift(A,tol,nmax)
%QRSHIFT M´ ethode QR avec translations.
% [T,ITER]=QRSHIFT(A,TOL,NMAX) calcule apr` es ITER it´ erations la
% forme de Schur r´ eelle T de la matrice A avec une tol´ erance TOL.
% NMAX est le nombre maximal d’it´ erations.
[n,m]=size(A);
if n˜=m, error(’Seulement pour les matrices carr´ ees’); end
iter=0; [T,Q]=houshess(A);
for k=n:-1:2
I=eye(k);
while abs(T(k,k-1))>tol*(abs(T(k,k))+abs(T(k-1,k-1)))
iter=iter+1;
if iter > nmax
return
end
mu=T(k,k); [Q,R,c,s]=qrgivens(T(1:k,1:k)-mu*I);
T(1:k,1:k)=R*Q+mu*I;
end
T(k,k-1)=0;
end
return
5.8 Calcul des valeurs propres des matrices sym´ etriques
Nous pr´ esentons dans cette section des algorithmes qui, contrairement ` a la
m´ ethode QR, prennent en compte la structure particuli` ere des matrices sym´ etriques A ∈ R
n×n .
Nous consid´ erons tout d’abord la m´ ethode de Jacobi, qui consiste `
a
construire une suite de matrices convergeant vers la forme de Schur diagonale
de A. Nous pr´ esentons ensuite la m´ ethode des suites de Sturm pour traiter le
cas des matrices tridiagonales.
5.8.1 La m´ ethode de Jacobi
La m´ ethode de Jacobi permet de construire une suite de matrices A
(k) , orthogonalement semblables ` a la matrice A, et qui converge vers une matrice
diagonale dont les coefficients sont les valeurs propres de A. On va utiliser
pour cela les transformations de Givens (5.43).
On pose A
(0) = A, et, pour k = 1, 2, . . ., on se donne deux indices p et
q tels que 1 ≤ p < q ≤ n. Puis, en posant G pq = G(p, q, θ), on construit la
matrice A
(k) = (G pq )
T A
(k−1) G pq , orthogonalement semblable `
a A telle que
a
(k)
ij = 0 si (i, j) = (p, q).
(5.54)