Axel Ruhe
September 27, 2004

2D1252,
Computational Algebra, Fall 2004, 

Programming Assignment 3, second part
2. Eigenvalues of tridiagonal matrices
Symmetric tridiagonal matrices are interesting. You get them as
intermediate
results when you compute eigenvalues of full symmetric matrices by
Householder
QR, and you get them from the Lanczos algorithm for large sparse
eigenvalue
problems. In that case you build them one row and column at a time from
the top and down. Soon some eigenvalues of the k*k matrix T_{k
}for k<<n will be very close to those of the full T_{n}.
In the divide and conquer algorithm you take the eigenvalues of the top
part
T_{k} and the remaining bottom T_{nk } as
starting
guesses for the eigenvalues of the full T_{n}.
a. Eigenvalues of expanding tridiagonals
Plot the eigenvalues of T_{k} versus k. You will get a
characteristic
figure that illustrates the Cauchy interlace theorem. Look at the front
page
of the
Eigentemplates
monograph!
b. Moving eigenvalues in Divide and Conquer
<>
Let us take a few tridiagonal matrices. Replace the sub (and super)
diagonal
element at one point where we divide the matrix t_{k+1,k} with
at_{k+1,k} , and see what happens when we let a
vary
from 0 to 1 in small steps. We get n paths of eigenvalues. Some of the
eigenvalues move, some do not. Do these curves really cross each
other? This
is a very interesting question which has no clear cut answer. When 2
eigenvalues
float together, each of them loses its identity and you cannot say
whether
a path continues up or down or turns.
Test matrices
Use the following matrices which have different characteristics:
 The matrix of a vibrating guitar string with all diagonal
elements 2 and subdiagonal 1. (This one is easy to generate, but very
slow to converge)
 The result of running the Matlab command T=hess(A+A')with
A a matrix of normally distributed random numbers. Note
that Matlab computes the Hessenberg matrix bottom up, it is the last
part that contains the dominating eigenvalues. The
interesting expansion asked for in part (a) is from the bottom up.
 The same as (2) flipped northwest southeast. What is the
difference between the top and the bottom halves of this type of
tridiagonal?
 Some more tridiagonals. Try for instance a
tridiagonal matrix with normally distributed random numbers in the
diagonal and ones in the sub and superdiagonal. It will behave very
differently from those tridiagonals you get as a result of a
Householder tridiagonalisation.