Axel Ruhe
September  27, 2004
2D1252, Computational Algebra, Fall 2004,  Nada

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 Tk for k<<n will be very close to those of the full Tn.
 
In the divide and conquer algorithm you take the eigenvalues of the top part Tk and the remaining  bottom Tn-k  as starting guesses for the eigenvalues of the full Tn.

a. Eigenvalues of expanding tridiagonals

Plot the eigenvalues of Tk 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 tk+1,k with atk+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:
  1. 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)
  2. 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.
  3. The same as (2) flipped northwest southeast. What is the difference between the top and the bottom halves of this type of tridiagonal?
  4. 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.