Remarks on Clustered Eigenvalues.

In the case when the eigenvalue $\lambda$ has one or more other eigenvalues of $A$ close by, in other words, when $\lambda$ belongs to clustered eigenvalues, as guaranteed by (4.54), the computed $\wtd\lambda$ is still accurate as long as $\Vert r\Vert _2$ is tiny, but the computed eigenvector $\wtd x$ may be inaccurate because of the appearance of the gap $\delta$ in the denominator of (4.56). It turns out that each individual eigenvector associated with the clustered eigenvalues is very sensitive to perturbations, but the eigenspace spanned by all the eigenvectors associated with the clustered eigenvalues is not. Thus, for the clustered eigenvalues, we should instead compute the entire eigenspace. A theory along the lines given above can be established, starting with a residual matrix

$$R=A\wtd X-\wtd X\wtd\Lambda,$$

where $\wtd\Lambda$ is diagonal with diagonal entries consisting of approximations to all the eigenvalues in the cluster, and the columns of $\wtd X$ are the corresponding approximate eigenvectors. Assume that $\wtd X$ has orthonormal columns and that $\wtd\Lambda$ is closer to $\Lambda$, the diagonal matrix whose diagonal entries consist of all the eigenvalues in the cluster. Let $X$ be the eigenvector matrix associated with $\Lambda$, and let $\delta$ be the smallest difference between any approximate eigenvalue in the diagonal of $\wtd\Lambda$ and those eigenvalues of $A$ not presented in the diagonal of $\Lambda$. Then [101]

$$\Vert\sin\Theta(X,\wtd X)\Vert _{F}\le\frac {\Vert R\Vert _{F}}{\delta},$$

where $\Theta(X,\wtd X)$ is diagonal with diagonal entries being the arccosines of the singular values of $X^*\wtd X$. Because of the way it is defined, this gap is expected to be big and thus $\Vert\sin\Theta(X,\wtd X)\Vert _{F}$ will be small as long as $\Vert R\Vert _{F}$ is.