Answer Happy

2. Convergence of the Inverse Iteration on Symmetric Matrices. (30 marks) Consider the inverse iteration (Algorithm 6.32) applied to a real symmetric matrix A € Rnxn. Suppose AK is the closest eigenvalue to u and A, is the second closest, that is, K-M<AL-AS-, for each i + K. Let gi....,In denote eigenvectors corresponding the eigenvalues of A. Suppose further we have an initial vector i such that i"OK # 0. Prove that, at iteration k, the vector 7) in the inverse iteration converges as LAKH || Ök) – 7x || = 0 | AL-H You may consider taking the following steps: (i) Suppose all the eigenvectors 71, 72, .., în are orthonormal, write down the eigen- decomposition of (A - MI)-! (ii) Use induction to show that the inverse iteration method produces a sequence of vectors 6), k=1,2,... in the form of 5l) – (A - "I)*70) ||(A - MI-k 0)| (iii) Use the results in (i) and (ii) to complete the rest of the proof. a Algorithm 6.32: Inverse Iteration Input: Matrix A € Rnxn, an initial vector 50) = 7 € R" where | 7|| = 1, and a shift scalar u € R. Output: An eigenvalue (m) and its eigenvector Ölm) 1: for k=1,2,...,m do Solve (A - ul)w(k) = 7(k-1) for (k) Apply (A - HI)-1 7(4) = u(k) /||2w3(k) || Normalise (iu))" (AĞ")) Estimate eigenvalue 5: end for 2: 3: 1(k)