Overview

In this subsection, we will summarize all the available error bounds. Later subsections will provide further details. The reader may also refer to [12,95].

Bounds for individual eigenvalues and eigenvectors are provided by driver xGEEVX (subsection 2.3.4) or computational routine xTRSNA (subsection 2.4.5). Bounds for clusters of eigenvalues and their associated invariant subspace are provided by driver xGEESX (subsection 2.3.4) or computational routine xTRSEN (subsection 2.4.5).

We let $\hat{\lambda}_i$ be the i^th computed eigenvalue and $\lambda_i$ an i^th true eigenvalue.^4.1 Let $\hat{v}_i$ be the corresponding computed right eigenvector, and v_i a true right eigenvector (so $A v_i = \lambda_i v_i$). If $\cal I$ is a subset of the integers from 1 to n, we let $\lambda_{\cal I}$ denote the average of the selected eigenvalues: $\lambda_{\cal I} = (\sum_{i \in \cal I} \lambda_i)/(\sum_{i \in \cal I} 1)$, and similarly for $\hat{\lambda}_{\cal I}$. We also let ${\cal S}_{\cal I}$ denote the subspace spanned by $\{ v_i \, , \, i \in \cal I \}$; it is called a right invariant subspace because if v is any vector in ${\cal S}_{\cal I}$ then Av is also in ${\cal S}_{\cal I}$. ${\hat{\cal S}}_{\cal I}$ is the corresponding computed subspace.

The algorithms for the nonsymmetric eigenproblem are normwise backward stable: they compute the exact eigenvalues, eigenvectors and invariant subspaces of slightly perturbed matrices A+E, where $\Vert E\Vert \leq p(n) \epsilon \Vert A\Vert$. Some of the bounds are stated in terms of |E|₂ and others in terms of |E|_F; one may use $p(n) \epsilon \Vert A\Vert _1$ to approximate either quantity. The code fragment in the previous subsection approximates |E| by $\epsilon \cdot {\tt ABNRM}$, where ${\tt ABNRM} = \Vert A\Vert _1$ is returned by xGEEVX.

xGEEVX (or xTRSNA) returns two quantities for each $\hat{\lambda}_i$, $\hat{v}_i$ pair: s_i and ${\rm sep}_i$. xGEESX (or xTRSEN) returns two quantities for a selected subset $\cal I$ of eigenvalues: $s_{\cal I}$ and ${\rm sep}_{\cal I}$. s_i (or $s_{\cal I}$) is a reciprocal condition number for the computed eigenvalue $\hat{\lambda}_i$ (or $\hat{\lambda}_{\cal I}$), and is referred to as RCONDE by xGEEVX (or xGEESX). ${\rm sep}_i$ (or ${\rm sep}_{\cal I}$) is a reciprocal condition number for the right eigenvector $\hat{v}_i$ (or ${\cal S}_{\cal I}$), and is referred to as RCONDV by xGEEVX (or xGEESX). The approximate error bounds for eigenvalues, averages of eigenvalues, eigenvectors, and invariant subspaces provided in Table 4.5 are true for sufficiently small |E|, which is why they are called asymptotic.

Table 4.5: Asymptotic error bounds for the nonsymmetric eigenproblem

Simple eigenvalue	$\vert\hat{\lambda}_i - \lambda_i \vert \mathrel{\raisebox{-.75ex}{$\mathop{\sim}\limits^{\textstyle <}$}}\Vert E\Vert _2 / s_i$
Eigenvalue cluster	$\vert\hat{\lambda}_{\cal I} - \lambda_{\cal I} \vert \mathrel{\raisebox{-.75ex}{$\mathop{\sim}\limits^{\textstyle <}$}}\Vert E\Vert _2 / s_{\cal I}$
Eigenvector	$\theta ( \hat{v}_i , v_i ) \mathrel{\raisebox{-.75ex}{$\mathop{\sim}\limits^{\textstyle <}$}}\Vert E\Vert _F / {\rm sep}_i$
Invariant subspace	$\theta ( {\hat{\cal S}}_{\cal I}, {\cal S}_{\cal I}) \mathrel{\raisebox{-.75ex}{$\mathop{\sim}\limits^{\textstyle <}$}}\Vert E\Vert _F / {\rm sep}_{\cal I}$

If the problem is ill-conditioned, the asymptotic bounds may only hold for extremely small |E|. Therefore, in Table 4.6 we also provide global bounds which are guaranteed to hold for all $\Vert E\Vert _F < s \cdot {\rm sep}/ 4$.

Table: Global error bounds for the nonsymmetric eigenproblem assuming $\Vert E\Vert _F < s_i \cdot {\rm sep}_i / 4$

Eigenvalue cluster	$\vert\hat{\lambda}_{\cal I} - \lambda_{\cal I} \vert \leq 2 \Vert E\Vert _2 / s_{\cal I}$
Eigenvector	$\theta ( \hat{v}_i , v_i ) \leq \arctan (2 \Vert E\Vert _F/({\rm sep}_i - 4 \Vert E\Vert _F/s_i))$
Invariant subspace	$\theta ( {\hat{\cal S}}_{\cal I}, {\cal S}_{\cal I}) \leq \arctan (2 \Vert E\Vert _F/({\rm sep}_{\cal I} - 4 \Vert E\Vert _F/s_{\cal I}))$

We also have the following bound, which is true for all E: all the $\lambda_i$ lie in the union of n disks, where the i-th disk is centered at $\hat{\lambda}_i$ and has radius n |E|₂ / s_i. If k of these disks overlap, so that any two points inside the k disks can be connected by a continuous curve lying entirely inside the k disks, and if no larger set of k+1 disks has this property, then exactly k of the $\lambda_i$ lie inside the union of these k disks. Figure 4.1 illustrates this for a 10-by-10 matrix, with 4 such overlapping unions of disks, two containing 1 eigenvalue each, one containing 2 eigenvalues, and one containing 6 eigenvalues.

Figure 4.1: Bounding eigenvalues inside overlapping disks

Finally, the quantities s and ${\rm sep}$ tell use how we can best (block) diagonalize a matrix A by a similarity, $V^{-1}AV = {\mbox {\rm diag}}(A_{11} , \ldots , A_{bb})$, where each diagonal block A_ii has a selected subset of the eigenvalues of A. Such a decomposition may be useful in computing functions of matrices, for example. The goal is to choose a V with a nearly minimum condition number $\kappa_2 (V)$ which performs this decomposition, since this generally minimizes the error in the decomposition. This may be done as follows. Let A_ii be n_i-by-n_i. Then columns $1+\sum_{j=1}^{i-1} n_j$ through $\sum_{j=1}^{i} n_j$ of V span the invariant subspace of A corresponding to the eigenvalues of A_ii; these columns should be chosen to be any orthonormal basis of this space (as computed by xGEESX, for example). Let $s_{{\cal I}_i}$ be the value corresponding to the cluster of eigenvalues of A_ii, as computed by xGEESX or xTRSEN. Then $\kappa_2 (V) \leq b/ \min_i (s_{{\cal I}_i})$, and no other choice of V can make its condition number smaller than $1/ \min_i (s_{{\cal I}_i})$ [26]. Thus choosing orthonormal subblocks of V gets $\kappa_2 (V)$ to within a factor b of its minimum value.

In the case of a real symmetric (or complex Hermitian) matrix, s=1 and ${\rm sep}$ is the absolute gap, as defined in subsection 4.7. The bounds in Table 4.5 then reduce to the bounds in subsection 4.7.