next up previous contents index
Next: Generalized Non-Hermitian Eigenvalue Problems Up: Stability and Accuracy Assessments Previous: Error Bound for Computed   Contents   Index


Error Bound for Computed Eigenvectors.

Instead of presenting available detailed error bounds of computed eigenvectors, which can be complicated and difficult to digest for large sparse eigenproblems, we shall give a brief actual analysis which will bring out the gist of what may contribute to the sensitivity of eigenvectors.

Let us consider the case of having an approximate eigenpair $(\wtd\lambda,\wtd x)$ to an exact pair $(\lambda,x)$. Let $A=QTQ^{\ast}$ be the Schur decomposition of $A$ (see §2.5, p. [*]), where $Q=[x,Q_2]$ is unitary and

\begin{displaymath}
T=\left[\begin{array}{cc}\lambda & a^{\ast} \\ 0 & T_{22}\end{array}\right].
\end{displaymath}

Then from the residual vector $r=A \wtd x-\wtd\lambda\wtd x = Q T Q^{\ast}\wtd x-\wtd\lambda\wtd x$, we have

\begin{displaymath}
Q^{\ast} r=T Q^{\ast} \wtd x-\wtd\lambda Q^{\ast} \wtd x
=(T-\wtd\lambda I)Q^{\ast} \wtd x.
\end{displaymath}

So the second to the last components of the above equation imply

\begin{displaymath}
\Vert r\Vert _2=\Vert Q^{\ast} r\Vert _2
\ge\Vert(T_{22}-\w...
...d\lambda I)^{-1}\Vert _2^{-1} \Vert Q_2^{\ast} \wtd x\Vert _2,
\end{displaymath}

which shows
\begin{displaymath}
\sin\theta(x,\wtd x)\equiv\Vert Q_2^{\ast} \wtd x\Vert _2
\...
... \frac{\Vert r\Vert _2}{\sigma_{\min}(T_{22}-\wtd\lambda I)}.
\end{displaymath} (213)

This inequality reveals another potential factor that may make $\sin\theta(x,\wtd x)$ large. This occurs when $T_{22}$ is too far from the set of normal matrices, in which case $\Vert(T_{22}-\wtd\lambda I)^{-1}\Vert _2$, or the reciprocal of the smallest singular value of $T_{22}-\wtd\lambda I$, can get huge even though none of the rest of $A$'s eigenvalues come close to $\wtd\lambda$.

For the small and dense eigenproblems, $\sigma_{\min}(T_{22}-\wtd\lambda I)$ can be efficiently estimated. This is available in LAPACK [12]. However, for large sparse eigenproblems, since $T_{22}$ is generally not available, the estimation of $\sigma_{\min}(T_{22}-\wtd\lambda I)$ is out of the question. We can only get a gross sense about the quality of computed eigenvectors.

Note that $\sigma_{\min}(T_{22}-\wtd\lambda I)$ roughly measures the separation of $\lambda$ from the eigenvalues of $T_{22}$. We have to say ``roughly'' because

\begin{displaymath}
\sigma_{\min}(T_{22}-\wtd\lambda I) \leq \min_{\mu \in \lambda(T_{22})}
\vert \mu -\wtd\lambda \vert
\end{displaymath}

and the upper bound can be a gross overestimate.

As summarized in [198], the separation of the eigenvalues has a bearing upon eigenvector sensitivity. Indeed, if $\lambda$ is a nondefective, repeated eigenvalue, then there are an infinite number of possible eigenvector bases for the associated invariant subspace. The preceding analysis merely indicates that this indeterminacy begins to be felt as the eigenvalues coalesce. It is well known that each individual eigenvector associated with eigenvalue clusters is very sensitive to perturbations, and consequently such an eigenvector cannot be accurately computed in general. Fortunately, often for the case of an eigenvalue cluster, it is the entire associated eigenspace that is of practical importance, and that eigenspace can be computed with satisfactory accuracy. Detailed treatment is beyond the scope of this book and the interested reader is referred to the literature, for example, [425].

    


next up previous contents index
Next: Generalized Non-Hermitian Eigenvalue Problems Up: Stability and Accuracy Assessments Previous: Error Bound for Computed   Contents   Index
Susan Blackford 2000-11-20