CS513 Spring 14 Prof Ron Assignment 5 Due April 17 2014 1 In this question you compare the complexity of the two methods we studied in class for locating the eigenvalues of a tridiagonal symmetric matrix Method I LU factoring A sI and inspecting the diagonal of U Method II computing the number of sign changes in the sequence of main principal minors of A sI Let A be the matrix 1 1 0 1 1 1 0 1 2 i Find by hand the number of eigenvalues A has in the interval 0 1 using each of the above methods ii Count carefully the number of arithmetic operations that were used for each method Any conclusions iii Now choose for A a larger order symmetric tridiagonal matrix at least 50 50 and use Matlab for repeating i ii for this matrix Update your conclusions if need be Run the experiment a good number of times and average the tic toc clock to get reliable reading Alternatively insert an operation counter in your code 2 Let A be an n n real matrix whose n Gerschgorin s discs are pairwise disjoint i e each two have empty intersection i What can you say about the cardinality of A i e the number of different eigenvalues What can you say about the multiplicities algebraic geometric of each eigenvalue ii Your friend Leon claims that the matrix A must be diagonalizable Do you agree Explain iii Your friend Nina claims that necessarily A IR Do you agree Explain iv Your friend Elvis says that because the Gerschgorin s discs of A are disjoint the straight power method based on A must converge Do you agree Explain 3 In class account look under demos power you will find the file as5 q3 mat Copy that file into your Matlab directory The file contains a 12 12 random matrix A which can be loaded into Matlab by typing at Matlab s prompt load as5 q3 You are asked to find the two smallest eigenvalues and the two largest eigenvalues of this matrix Use Matlab as the platform for doing all the computations here Step I in order to find the two largest eigenvalues run first the power method until you obtain for the first time an eigenpair with an error 10 2 Then deflate your approximate eigenvalue from the matrix and run again the power method as before but with respect to the reduced matrix To see how reliable you are use eig to compare the eigenvalues of A and of the reduced matrix Step II Repeat Step I but with the power method replaced by the inverse power method be sure you are implementing the inverse method efficiently Draw conclusions and suggest way ways that can be used to circumvent the observed problems 4 Solve items a and b in problem 28 2 page 218 in the book Study first a few examples to see what s going on If you cannot solve then the problem you may for half of the credit show that the result is true for three different matrices of three different sizes Note the question is as follows you are given a symmetric tridiagonal matrix A you factor A into A QR and then form a matrix B RQ The claim is that B is still tridiagonal The fact that the entire process is a part of the so called QR method which we will study shortly in class is not material to the actual question