Write a function that implements the basic QR iteration for
finding eigenvalues (Algorithm 4.7 in the text).
This basic algorithm is very simple, as all
the work is done by a call to the built-in function qr. All you
need to do is add a termination criterion, stopping when the norm of the
lower triangular part of Ak
(square root of the sum of the squares of the strictly lower triangular entries)
is sufficiently small, or a maximum iteration limit is exceeded.
The input parameters should be the matrix A,
the tolerance and the iteration limit. The output parameters should be
- the final matrix Ak
- the approximate eigenvalues of A
returned as a vector (this is just the diagonal of Ak),
sorted into increasing order; you can use Matlab's sort, which
sorts by real part in the case of complex numbers
- the norm of the lower triangular part of Ak
(which is useful since we know that the smaller it is is, the more accurate
the eigenvalues are)
- the number of iterations that were needed
According to the discussion in the text, this algorithm should work
for matrices with the property that all the eigenvalues have different
magnitudes (complex modulus), although depending on the input,
it might need a lot of iterations.
Test the program on the following examples, comparing your results with
the built-in Matlab function eig(A). For printing small examples,
use n=7 for real matrices and n=3 for complex matrices, so you can easily
display the matrix with format short e. Try some runs with
bigger n as well (e.g. n=10, n=30), but don't print these matrices.
- a randomly generated complex matrix, generated by
A=randn(n) + i*randn(n) (where i is the imaginary unit;
make sure you have not redefined it to be something else).
Does the final Ak have small lower triangular entries?
If not, either there is a bug in your program, or your iteration limit is too small.
- a randomly generated complex Hermitian matrix, generated by
A=randn(n) + i*randn(n); A = A + A'.
What is the structure of the final Ak, neglecting small entries,
and why?
- a randomly generated real symmetric matrix, generated by
A=randn(n); A = A + A'.
What is the structure of the final Ak, neglecting small entries,
and why?
- a randomly generated real (but not symmetric) matrix, generated by
A=randn(n).
What is the structure of the final Ak, neglecting small entries,
and why?