next up previous contents index
Next: Rayleigh Quotient Iteration. Up: Single- and Multiple-Vector Iterations Previous: Power Method.   Contents   Index

Inverse Iteration.

If we can factor $A - \sigma \, B$ for a shift $\sigma$, we can generalize the inverse iteration to compute eigenvalues of the problem (5.1) near $\sigma$ as shown in Algorithm 5.2.


\begin{algorithm}{Inverse Iteration for GHEP}
{
\begin{tabbing}
(nr)ss\=ijkl\=bb...
...ccept $\lambda=\sigma+1/\theta$\ and $x=y/\theta$ \end{tabbing}}
\end{algorithm}

Here are some comments on this algorithm. In step (3) we multiply by $B$, while in step (5) we solve a system with the shifted matrix $A-\sigma B$. In a practical case, we perform an initial sparse Gaussian elimination and use its $L$ and $U$ factors while operating. Step (4) makes sure that the vector $v$ is of unit $B$ norm. The quantity $\theta $ is a Rayleigh quotient,

\begin{displaymath}
\theta=w^{\ast}y=w^{\ast}(A-\sigma B)^{-1}w=v^{\ast}B(A-\sigma B)^{-1}Bv\,.
\end{displaymath} (71)

In step (7) we test a residual vector,

\begin{displaymath}r=(1/\theta)y-v=(A-\sigma B)^{-1}(\tilde{\lambda}B-A)v\,,\end{displaymath}

where $\tilde{\lambda}=\sigma+1/\theta$ is the current approximate eigenvalue. The inverse iteration converges under conditions similar to those for the standard HEP.



Susan Blackford 2000-11-20