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


Inverse Iteration

Inverse iteration, described in Algorithm 4.2, can also be used to solve the NHEP without any apparent change.
\begin{algorithm}{The Inverse Iteration for the computing an
eigenvalue closest ...
... w - \theta \, z\vert\vert _2 \leq \epsilon $\\
\end{tabbing}}
\end{algorithm}
As in the Hermitian case, assume that $\lambda_j$ and $q_j$ are an eigenvalue and eigenvector pair of $A$ so that $\vert\lambda_j - \sigma \vert^{-1}$ is the largest eigenvalue of $(A - \sigma I)^{-1}$ in magnitude. The inverse power method converges if the starting vector $v$ is not perpendicular to $q_j$. The convergence rate is $\left\vert(\lambda_j - \sigma )/(\lambda_k
- \sigma )\right\vert$, where $\lambda_k$ is an eigenvalue of $A$ such that $\vert\lambda_k - \sigma \vert^{-1}$ is the second largest eigenvalue of $(A - \sigma I)^{-1}$ in magnitude.

In general, inverse iteration tends to have much more rapid convergence than the power method if $\sigma$ is chosen to be very close to a desired eigenvalue. However, inverse iteration does require a factorization of the matrix $A-\sigma I$, making it less attractive when this factorization is expensive.



Susan Blackford 2000-11-20