Inverse Iteration

The method is defined by

$$(A-\alpha I)\mbox{\boldmath$ x $ } _{m+1}=\mbox{\boldmath$ x $ } _m,\quad m=0,1,\ldots .$$

At each iteration, we have a set of linear equations to solve, but if we decompose $A-\alpha I$ into lower and upper factors, we can use these repeatedly. To analyse convergence, we assume that $A-\alpha I$ is nonsingular and write the iteration as

$$\mbox{\boldmath$ x $ } _{m+1}=(A-\alpha I)^{-1}\mbox{\boldmath$ x $ } _m,$$

so that with the usual expansion $\mbox{\boldmath$\space x $ } _0=\sum _{i=1}^na_i\mbox{\boldmath$\space u $ } _i$,

$$\begin{eqnarray*}\mbox{\boldmath$ x $ } _m & = & (A-\alpha I)^{-m}\mbox{\boldmat... ...m _{i=1}^na_i(\lambda _i-\alpha )^{-m}\mbox{\boldmath$ u $ } _i. \end{eqnarray*}$$

Now choose $\alpha$ close to one of the eigenvalues of A, so that, with suitable numbering,

$$\vert\lambda _1-\alpha \vert<\vert\lambda _2-\alpha \vert\leq \vert\lambda _k-\alpha \vert,\quad k=3,4,\ldots .$$

Then $\mbox{\boldmath$\space x $ } _m$ looks like $a_1(\lambda _1-\alpha )^{-m}\mbox{\boldmath$\space u $ } _1$ for large m. Also

$$\begin{eqnarray*}\sigma _{m,k} & = & \frac{a_1(\lambda _1-\alpha )^{-m-1}u_{1,k}... ...ht) ^m+\cdots \right\} \\ & \to & \frac{1}{\lambda _1-\alpha }. \end{eqnarray*}$$

The asymptotic convergence factor is $\left\vert \frac{\lambda _1-\alpha }{\lambda _2-\alpha }\right\vert$, so the closer we choose $\alpha$ to $\lambda$, the better the convergence.

This method turns out to be very stable numerically, even though one might expect a problem because we choose $\alpha$ close to $\lambda _1$, which means that the eigenvalue $\lambda _1-\alpha$ is nearly zero, so $A-\alpha I$ is nearly singular, and the solution for the iterates is apparently ill-conditioned.

However, it is not the size of the iterates which matters, but the ratios of the components, and these turn out to be accurate. We can see roughly why this is. The solution of $(A-\alpha I)\mbox{\boldmath$\space x $ } _{m+1}=\mbox{\boldmath$\space x $ } _m$is approximately that of $(A-\alpha I)\mbox{\boldmath$\space x $ } _{m+1}=\mbox{\bf0}$ because of the ill-conditioning of the matrix, and this gives $A\mbox{\boldmath$\space x $ } _{m+1} = \alpha \mbox{\boldmath$\space x $ } _{m+1} \approx \lambda _1\mbox{\boldmath$\space x $ } _{m+1}$, which is precisely what we want.