Inverse Iteration

To find eigenvectors.

Suppose $A$ has a Jordan canonical form which is diagonal.

$$P^{-1}AP=\mbox {diag }[\lambda_1, \lambda_2,\ldots ,\lambda_n]$$

Let the columns of $P$ be denoted by $x_1, x_2, \ldots, x_n$. Then

$$Ax_i=\lambda_ix_i\quad i=1, 2,\ldots , n.$$

Assume $\vert\vert x_i\vert\vert _{\infty}=1$ (can always be done). Let $\lambda$ be an approximation to a simple eigenvalue $\lambda_k$ of $A$. Given an initial $z^{(0)}$, define $\{w^{(m)}\}$ and $\{z^{(m)}\}$ by

$$\begin{eqnarray*} (A-\lambda I)w^{(m+1)}=z^{(m)}\\ z^{(m+1)}=\frac{w^{(m+1)}}{\vert\vert w^{(m+1)}\vert\vert _{\infty}}\quad m\ge 0. \end{eqnarray*}$$

Note: Here we want $\lambda$ to be a ``poor'' guess of $\lambda_k$, since otherwise we get a severely ill-conditioned matrix $A-\lambda I$! So choose a ``close'' value.

More precisely: let

$$z^{(0)}=\displaystyle \sum^{n}_{i=1}\alpha_i x_i, \quad \quad \alpha_k\ne 0.$$ (95)

from the power method:

$$z^{(m)}=\frac{\sigma_m (A-\lambda I)^{-m}z^{(0)}}{\vert\vert(A-\lambda I)^{-m}z^ {(0)}\vert\vert}_{\infty}$$ (96) (97)

$$\vert\sigma_m\vert=1\mbox { i.e. either }\pm 1.$$ (98)

substituting (96):

$$(A-\lambda I)^{-m}z^{(0)}=\sum^n_{i=1}\alpha_i[\frac{1}{\lambda_i -\lambda}]^m x_i$$ (99)

let $\lambda_1-\lambda=\varepsilon$ and assume $\vert\lambda_1-\lambda\vert\ge c>0\quad i=1, 2,\ldots , n\quad i\ne k$.

>From (99) and (100)

$$z^{(m)}=\sigma_m \frac{x_k+\varepsilon ^m\sum_{i\ne k}\frac... ...a_k} [\frac{1}{\lambda_i-\lambda}]^m x_1\vert\vert _{\infty}}.$$ (100)

If $\vert\varepsilon \vert< c$ then

$$\vert\vert\varepsilon ^m\sum_{i\ne k}\frac{\alpha_i}{\alph... ...} \right]^m \sum_{i\ne k}\vert\frac{\alpha_i} {\alpha_k}\vert$$

which tends to $0$ as $m\rightarrow \infty$, and with (101) shows that $z^{(m)}$ converges to a multiple of $x_k$. The convergence is linear, though. In its implementation, a sensible thing to do is to $LU$-factorize $A-\lambda I$.

$\Box$