next up previous contents index
Next: Balancing and Conditioning Up: Further Details: Error Bounds Previous: Further Details: Error Bounds   Contents   Index


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 ith computed eigenvalue and $\lambda_i$ an ith true eigenvalue.4.1 Let $\hat{v}_i$ be the corresponding computed right eigenvector, and vi 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|2 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: si 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}$. si (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|2 / si. 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 Aii 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 Aii be ni-by-ni. 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 Aii; 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 Aii, 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.


next up previous contents index
Next: Balancing and Conditioning Up: Further Details: Error Bounds Previous: Further Details: Error Bounds   Contents   Index
Susan Blackford
1999-10-01