Inverse Power Method - due Monday, January 24

Write a program that uses the shifted inverse power method to find an approximation to the eigenvalue of a matrix which is closest to a given number $\alpha$ and the corresponding eigenvector. In addition to the matrix A and the number $\alpha$, the program should take as inputs a limit, m, on the number of iterations and a tolerance $\epsilon$ (not necessarily the machine ``epsilon'') whose role is explained below. It should also take as input an initial approximation, v, to the eigenvector. The program should terminate when successive estimates of the eigenvalue differ by less than $\epsilon$ or when the number of iterations reaches m. The program should use Rayleigh quotients to estimate the eigenvalue. The program should return the final estimate of the eigenvalue, the corresponding eigenvector estimate and information as to whether the method converged.

An optional addition to the return values of the program would be a list (vector) with all the (Rayleigh quotient) estimates of the eigenvalue, and a matrix with the corresponding eigenvector extimates. Two optional additional programs and or additions to the program would be

a)

An implementation of Richardson extrapolation to produce an improved eigenvalue estimate together with an upper bound on the absolute error in the improved estimate. (This should not be restricted to symmetric matrices, even though the examples below are symmetric.)

(ii)

An adaptation of the discussion on p.94 of Johnson and Reiss, and Problem 7, in section 3.2 of JR, to use ratios of successive differences in eigenvalue estimates for symmetric matrices to generate estimates of the eigenvalue which is second closest to $\alpha$. (The adaptation of Problem 7 to Rayleigh quotient eigenvalue estimates for symmetric A will involve $(\lambda_2/\lambda_1)^{2i}$. The further adaptation to the shifted inverse power method is then a question of algebra. Any analysis/discussion associated with this addition should explain/derive the method/formulae used.)

Run the program on the following matrices and find all of their eigenvalues. The first digits of the eigenvalues are given. In each case use $v=[1, \sqrt 2, \sqrt 3, \ldots, \sqrt n]^T$ as initial guess.

$$\begin{bmatrix} 2&-1&0&0&0&0\\ -1&2&-1&0&0&0\\ 0&-1&2&-1&0&0\\ 0&0&-1&2&-1&0\\ 0&0&0&-1&2&-1\\ 0&0&0&0&-1&2 \end{bmatrix}$$ (1)

$$\begin{bmatrix} 100&20&0&0\\ 20&110&16&0\\ 0&16&120&-8\\ 0&0&-8&130 \end{bmatrix}$$ (2)

$$\begin{bmatrix} 4&1&0&0&0\\ 1&4&1&0&0\\ 0&1&4&1&0\\ 0&0&1&4&1\\ 0&0&0&1&4 \end{bmatrix}$$ (3)

First digits of the eigenvalues: (Be sure to explain how you have used this information in relation to the theory of the convergence of the shifted inverse power method and the general theory of eigenvalues to assure that you have obtained all the eigenvalues for the given matrices.)

(a)

3, 3, 2, 1, .7, .1

(b)

1e2, 1e2, 1e2, 8e1

(c)

5, 5, 4, 3, 2