CS513, Spring 14Prof. RonAssignment #5Due April 17, 2014(1) In this question, you compare the complexity of the two methods we studiedin class for locating the eigenvalues of a tridiago nal symmetric matrix. Method I: LUfactoring A − sI and inspecting the diagonal of U ; Method II: computing the number ofsign changes in the sequence of main principal minors of A − sI. Let A be the matrix−1 1 01 1 10 1 2.(i): Fi nd (by hand) the number of eigenvalues A has in the i nterval (0, 1) using each of theabove methods.(ii): C ount carefully the number of arithmetic operations that were used for each method.Any conclusions?(iii): Now, choose for A a larger order symmetric tridiago nal mat rix (at least 50 × 50),and use Matlab for repeating (i,ii) for thi s matrix. Update your conclusions, if need be.(Run the exp eriment a good number of times, and average the tic-toc clo ck to get reliablereading. Alternati vely, 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 cardi nality of σ(A) (i.e., the number of differenteigenva lues)? What can you say about the multiplicities (a lgebraic, geometric) of eacheigenva lue?(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 Gerschgo r in’s discs of A are disjoint, the(straight) power method based on A must converge. Do yo u ag ree? Explain.(3) In class account (look under demos/power) you will find the file as5q3.mat .Copy that file into your Matlab directory. The file contains a 12 × 12 random matr ix A,which can be lo aded into Matlab by typing (at Matlab’s prompt): load as5q3.You are asked to find the two smallest eigenvalues and the two largest eigenvalues ofthis matrix. Use Matlab as the platform for doing all t he computations here.Step I: in order to find the two largest eigenvalues, run first the power method untilyou obtain (for the first time) an eigenpair with an error < 10−2. Then deflate yourapproximate eigenvalue from the ma trix, and run again the power method as before, butwith respect to the reduced matri x. To see how rel iable you are, use eig to compare theeigenva lues of A and of the reduced matrix.Step II: Repeat Step I, but with the power method replaced by the inverse powermethod (be sure you are implementing the inverse method efficiently).Draw conclusions, and suggest way/ways that can be used to circumvent t he observedproblems.(4) Solve items (a) and (b) in problem 28.2 (page 218) in the book. Study first a fewexamples, to see what’s going on. If you cannot solve then the problem, you may (for halfof the credit), show that the result is true for three different matrices of three differentsizes. Note: the question is as follows: you are given a symmetric tridiag onal matrix A,you factor A into A = QR, and then form a matrix B := RQ. The claim is that B is stilltridiagonal. The fact that the entire process is a part of the so-called QR method (whichwe w ill study shortly in class) is not materia l to the actual