Computing Eigenvalues Using the QR Algorithm
Computing Eigenvalues Using the QR Algorithm
Let 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 using the QR iteration method and shows the convergence properties of the iteration method.
A
1
A
1
The QR iteration method is expressed as
A
k+1
R
k
Q
k
A
k
Q
k
R
k
k=1,2,…,p
where is the total number of iterations and and are the orthogonal and uppertriangular matrices obtained when the QR decomposition is performed on .
p=250
Q
k
R
k
A
k
For a nonsymmetric matrix with real eigenvalues, the matrix approaches an upperdiagonal form as increases, with the diagonal elements approximating the desired eigenvalues. You can start the iteration using the original matrix or use the almost uppertriangular Hessenberg form of . With the two sliders, you can change the number of QR iterations or the seed number for generating the random noise. The "convergence" button shows the squared relative error, defined as
n×n
n
A
k
k
A
1
A
1
k
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 . You can see the matrix by clicking the button "eigenvalues at iteration".
k
A
k
th
n