MATH 372 -- Numerical Linear Algebra
QR iteration for eigenvalues
April 4, 2007

% Consider the following 4 x 4 symmetric matrix:

A =

     2     3     4     5
     3     1     1     1
     4     1     1     1
     5     1     1     2

% As we expect all the eigenvalues are real: 

>> eig(A)

ans =

   -4.4264
    0.0393
    0.5859
    9.8011

% One iterative method for finding these is called 
% QR iteration.  We first use reflectors to put 
% find a matrix similar to H in "upper Hessenberg" 
% form (for symmetric matrices, this means tridiagonal
% form):

>> H=hess(A)

H =

    0.0455   -0.0895         0         0
   -0.0895   -0.6381    4.2710         0
         0    4.2710    4.5926   -5.1962
         0         0   -5.1962    2.0000

% Then QR iteration consists of the following steps:
%    a) compute the QR-factorization H_old = QR
%    b) H_new = RQ (note reversal) -- this implies 
%                H_new = Q^(-1) H_old Q
%       is similar to H_old
% It can be proved that ``in most cases'' if these
% steps are iterated, the sequence of H matrices 
% converges to a diagonal matrix, so diagonal entries
% are the eigenvalues of A.

for i=1:20
     [Q,R]=qr(H)
     H = R*Q
end


% after 5 iterations:

H =

    9.7019    1.1844   -0.0000   -0.0000
    1.1844   -4.3271    0.0011   -0.0000
         0    0.0011    0.5859    0.0000
         0         0    0.0000    0.0393

% after 10 iterations:

H = 

    9.8011   -0.0224   -0.0000    0.0000
   -0.0224   -4.4263   -0.0000    0.0000
         0   -0.0000    0.5859   -0.0000
         0         0   -0.0000    0.0393

% after 15 iterations:

H =

    9.8011    0.0004   -0.0000   -0.0000
    0.0004   -4.4264    0.0000   -0.0000
         0    0.0000    0.5859    0.0000
         0         0    0.0000    0.0393

% after 20 iterations:
 
H =

    9.8011   -0.0000   -0.0000    0.0000
   -0.0000   -4.4264    0.0000    0.0000
         0   -0.0000    0.5859   -0.0000
         0         0   -0.0000    0.0393