WOLFRAM|DEMONSTRATIONS PROJECT

Computing Eigenvalues Using the QR Algorithm

​
ctrl
matrix elements
eigenvalues at
th
n
iteration and actual eigenvalues
convergence of
th
n
eigenvalue
first
second
third
fourth
QR iteration
Hessenberg decomposition
number of iterations k
108
seed
8
1.0180
3.
5.
7.
11.
12.9714
17.
19.
23.
29.
30.3986
37.
41.
43.
47.
52.4267
Let
A
1
be a 4×4 matrix whose entries are the first 16 prime numbers with the main diagonal perturbed by some random noise. This Demonstration calculates the eigenvalues of
A
1
using the QR iteration method and shows the convergence properties of the iteration method.
The QR iteration method is expressed as
A
k+1
=
R
k
Q
k
, where
A
k
=
Q
k
R
k
,
k=1,2,…,p
,
where
p=250
is the total number of iterations and
Q
k
and
R
k
are the orthogonal and upper-triangular matrices obtained when the QR decomposition is performed on
A
k
.
For a nonsymmetric
n×n
matrix with
n
real eigenvalues, the matrix
A
k
approaches an upper-diagonal form as
k
increases, with the diagonal elements approximating the desired eigenvalues. You can start the iteration using the original matrix
A
1
or use the almost upper-triangular Hessenberg form of
A
1
. With the two sliders, you can change the number
k
of QR iterations or the seed number for generating the random noise. The "convergence" button shows the squared relative error, defined as
2

n
=
2

λ
n
-
λ
n,exact


2
λ
n,exact
,
n=1,2,3,4
,
as a function of the number of iterations up to the selected iteration number
k
. You can see the matrix
A
k
by clicking the button "eigenvalues at
th
n
iteration".