Assignment #5 Solution

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






−110

1 1 1 .




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).




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.




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.




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.