Description
1. Problem 7.3.2 p373: Suppose the eigenvalues of a real matrix A of largest absolute value are a
complex conjugate pair, and that all the other eigenvalues are strictly smaller in absolute value.
How does the power method behave when started with a real vector? Show the power method
yields an approximate basis for the invariant subspace spanned by the two eigenvectors of those
two largest eigenvalues.
2. What are the eigenvalues and eigenvectors of a Householder reflection P = I − 2uu′ and a 2 × 2
Givens rotation
c s
−s c
?
3. For each of the following upper triangular matrices, list all the eigenvalues together with their
algebraic and geometric multiplicities. Solve for all the corresponding eigenvectors, scaled so
that their largest component in absolute value is a 1. (Hand calculation).
A =
1 1 1
0 1 1
0 0 2
, B =
1 0 1
0 1 1
0 0 2
, C =
1 0 1
0 1 1
0 0 1
, D =
0 1 1
0 1 1
0 0 2
4. Generate a random n×n symmetric matrix A with eigenvalues 1, . . . , n−2, 2n−1, 2n using the
following matlab commands:
• [Q,R] = qr(rand(n,n)) ;
• A = Q * diag([1:n-2,2*n-1,2*n]) * Q’ ;
Use this matrix as test case for the following algorithms. For each algorithm, show the code
[fragment] and give an outline of the method (if not self-explanatory from the code fragment).
find how many steps it takes to find a eigenvalue/vector pair within an accuracy of 10−7
. You
should check the accuracy by computing the residual, not by comparing to the true answer. Use
n = 5, 10 to test your algorithm, and then use n = 40 to report the number of iterations needed.
(a) Power method starting with a random starting vector. At each iteration compute and
save the Rayleigh quotient, then plot the difference between the values of these Rayleigh
quotients and the final value (use semilogy). What is the rate of convergence? Did
the power method converge to the largest eigenvalue? Can the rate of convergence give an
indication of the second largest eigenvalue? Hint: since this matrix is symmetric, you might
need to take the square root of the rate of convergence. Do not go over 1,000 iterations.
(b) Rayleigh Quotient Iteration (RQI: inverse iteration with the shift at each step determined
by the Rayleigh quotient with the iterate). Start with a random normalized vector. Which
eigenvalue does it converge to? To force it to converge to the largest eigenvalue, apply RQI
with a shift fixed at kAk∞ for a few initial iterations before switching to the pure Rayleigh
quotient. How many initial iterations with fixed shifts do you need to make it converge to
the largest eigenvalue? This number should be less than 10.
1
(c) Simple explicit QR algorithm (no shifts). Try symmetrizing after each iteration. Allow up
to 1000 iterations.
5. Implement a simple Lanczos procedure (as given in the lecture notes, or Alg. 10.1.1∗
in the
text or Alg. 36.1 in TB) to compute the factorization AX = XT where A is a given symmetric
matrix, X is a set of generated orthonormal columns, and T is a generated tridiagonal matrix.
Apply the procedure to the test matrices in the previous question and use the result to obtain
a Ritz approximation (§10.1.4) to the leading eigenvalue/vector pair for A. You should use the
standard simple Lanczos procedure, except that you should check for loss of orthogonality by
the following heuristic: check that each generated Lanczos vector is orthogonal to the starting
vector (i.e., the inner product is less than the given tolerance). Carry out the Lanczos expansion
until n Lanczos vectors have been generated, or until an off-diagonal element of T is less than
10−7
(in absolute value), or until orthogonality is lost (to the same tolerance). Use a random
starting vector.
Compute the Ritz approximation to the eigenvalue at each iteration, and plot the differences
between the Ritz values and the final value as done with the Power Method above. You can also
just compute the maximum eigenvalue of the leading k × k principal submatrix of the final T,
for k = 1, 2, . . .. To obtain the Ritz values, just apply the built-in eig function to the tridiagonal
matrix T.
The following is required only for those working in pairs.
6. Apply the power method as well as the Lanczos procedure to the matrix A defined by the
following commands using n = 20:
• A = diag([n+2:-1:2,3:n+2])+diag(ones(2*n,1),-1)+diag(ones(2*n,1),1);
Notice how A−λI almost has a 2-dimensional nullspace for some λ, even though no sub-diagonal
is small.
7. Use your Lanczos procedure to find the leading singular value/vectors of the matrix in lsidata
from the previous homework, by implicitly finding the leading eigepair for AT A (or AAT
if
easier). Write your code so that you do not have to explicitly form AT A or even explicitly
transpose the matrix A at all. You can use the svds function to check your answers.
∗This algorithm should be rearranged so that the matrix A is accessed only once per iteration.
2
