403/503 – Extra credit problem

April 8, 2015

This problem is due April 30 at the beginning of lecture.

Write a program that receives as input a real symmetric matrix A and some tolerance bound \epsilon, and performs the basic QR method to A generating (and printing) a sequence of matrices A_0=A,A_1,A_2,\dots until a stage n is reached where the entries below the diagonal  of A_n are all in absolute value below \epsilon. Once this happens, the program returns the diagonal entries of A_n as approximations to the eigenvalues of A. (Check on a couple of examples that these are indeed decent approximations, at least for A of small size and reasonably small values of \epsilon.)

Most Computer Algebra Systems already have implemented algorithms to find the QR decomposition of a matrix. Instead of using these pre-programmed algorithms, write your own.

(Turn in the code, plus the couple of examples. Comment your code, so it can be easily understood what you are doing along the way. I’m reasonably familiar with Maple, Mathlab, Sage, and most flavors of C. If you are going to use a different language, please let me know as soon as you can, to see whether it is something I’ll be able to verify or if a different language will be needed instead. Ideally, the user can choose the dimension of the input matrix.)