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 summarize all the available error bounds. Later sections will provide further details. The error bounds presented here apply to regular matrix pairs only.

Bounds for individual eigenvalues and eigenvectors are provided by the driver xGGEVX (subsection 2.3.5.2) or the computational routine xTGSNA (subsection 2.4.8). Bounds for cluster of eigenvalues and their associated pair of deflating subspaces are provided by the driver xGGESX (subsection 2.3.5.2) or the computational routine xTGSEN (subsection 2.4.8).

We let $({\hat{\alpha}}_i, {\hat{\beta}}_i)$ be the ith computed eigenvalue pair and $({\alpha}_i, {\beta}_i)$ the ith exact eigenvalue pair.4.2Let $\hat{x}_i$ and $\hat{y}_i$ be the corresponding computed right and left eigenvectors, and xi and yi the exact right and left eigenvectors (so that ${\beta}_i A x_i = {\alpha}_i B x_i$ and ${\beta}_i y_i^H A = {\alpha}_i y_i^H B$). As in the standard nonsymmetric eigenvalue problem, we also want to bound the error in the average of a cluster of eigenvalues, corresponding to a subset $\cal I$ of the integers from 1 to n. However, since there are both finite and infinite eigenvalues, we need a proper definition for the average of the eigenvalues $\lambda_i = \alpha_i / \beta_i$ for $i \in {\cal I}$. Here we let $( {\alpha}_{\cal I}, {\beta}_{\cal I} )$ denote the average of the selected eigenvalues4.3: $( {\alpha}_{\cal I}, {\beta}_{\cal I} ) =
(\sum_{i \in {\cal I}} {\alpha}_i, \sum_{i \in {\cal I}} {\beta}_i )/
(\sum_{i \in {\cal I}} 1)$, and similarly for $( \hat{{\alpha}}_{\cal I}, \hat{{\beta}}_{\cal I} )$. We also let ${\cal L}_{\cal I}$ and ${\cal R}_{\cal I}$ denote the exact pair of left and right deflating subspaces associated with the cluster of selected eigenvalues. Similarly, $\widehat{{\cal L}}_{\cal I}$ and $\widehat{{\cal R}}_{\cal I}$ are the corresponding computed pair of left and right deflating subspaces.

The algorithms for the generalized nonsymmetric eigenproblem are normwise backward stable; the computed eigenvalues, eigenvectors and deflating subspaces are the exact ones of slightly perturbed matrices A + E and B +F, where $\Vert(E, F)\Vert _F \leq p(n) \epsilon \Vert(A, B)\Vert _F$. The code fragment in the previous subsection approximates $\Vert(E, F)\Vert _F$ by $\epsilon \cdot {\tt ABNORM}$, where ${\tt ABNORM} = \sqrt{ {\tt ABNRM}^2 + {\tt BBNRM}^2 }$, and the values ABNRM and BBNRM returned by xGGEVX are the 1-norm of the matrices A and B, respectively.

xGGEVX (or xTGSNA) returns reciprocal condition numbers for each eigenvalue pair $({\hat{\alpha}}_i, {\hat{\beta}}_i)$ and corresponding left and right eigenvectors $\hat{y}_i$ and $\hat{x}_i$: si and ${\rm Dif}_l(i)$. si is a reciprocal condition number for the computed eigenpair $({\hat{\alpha}}_i, {\hat{\beta}}_i)$, and is referred to as RCONDE(i) by xGGEVX. ${\rm Dif}_l(i)$ is a reciprocal condition number for the left and right eigenvectors $\hat{y}_i$ and $\hat{x}_i$, and is referred to as RCONDV(i) by xGGEVX (see subsection 4.11.1.3 for definitions). Similarly, xGGESX (or xTGSEN) returns condition numbers for eigenvalue clusters and deflating subspaces corresponding to a subset $\cal I$ of the eigenvalues. These are $l_{\cal I}$ and $r_{\cal I}$, the reciprocal values of the left and right projection norms p and q, and estimates of the separation between two matrix pairs defined by ${\rm Dif}_u({\cal I})$ and ${\rm Dif}_l({\cal I})$ (see subsection 4.11.1.3 for definitions). xGGESX reports $l_{\cal I}$ and $r_{\cal I}$ in RCONDE(1) and RCONDE(2) (PL and PR in xTGSEN)), respectively, and estimates of ${\rm Dif}_u({\cal I})$ and ${\rm Dif}_l({\cal I})$ in RCONDV(1) and RCONDV(2) (DIF(1) and DIF(2) in xTGSEN), respectively.

As for the nonsymmetric eigenvalue problem we provide both asymptotic and global error bounds. The asymptotic approximate error bounds for eigenvalues, averages of eigenvalues, eigenvectors, and deflating subspaces provided in Table 4.7 are true only for sufficiently small $\Vert(E, F)\Vert _F$.


Table 4.7: Asymptotic error bounds for the generalized nonsymmetric eigenvalue problem
Simple eigenvalue: % latex2html id marker 16841
${\cal X}(({\hat{\alpha}}_i,{\hat{\beta}}_i), ({\al...
...n{$;\hfil ...
Eigenvalue cluster: % latex2html id marker 16845
${\cal X}( ({\hat{\alpha}}_{\cal I},{\hat{\beta}}_{...
...fil ...
Eigenvector pair:  
   Left % latex2html id marker 16849
$\theta_{\max} (\hat{{\em y}}_i , {\em y}_i) \def \...
...il$\crcr S\crcr
\theguybelow\crcr}}PMlt;}
{\Vert(E,F)\Vert _F}/{{\rm Dif}_l(i)}$
   Right % latex2html id marker 16853
$\theta_{\max} (\hat{{\em x}}_i , {\em x}_i) \def \...
...il$\crcr S\crcr
\theguybelow\crcr}}PMlt;}
{\Vert(E,F)\Vert _F}/{{\rm Dif}_l(i)}$
Deflating subspace pair:  
   Left % latex2html id marker 16857
$\theta_{\max} ({\widehat{{\cal L}}}_{\cal I} , {\c...
...cr S\crcr
\theguybelow\crcr}}PMlt;}{\Vert(E,F)\Vert _F}/{{\rm Dif}_l({\cal I})}$
   Right % latex2html id marker 16861
$\theta_{\max} ({\widehat{{\cal R}}}_{\cal I} , {\c...
...cr S\crcr
\theguybelow\crcr}}PMlt;}{\Vert(E,F)\Vert _F}/{{\rm Dif}_l({\cal I})}$

If the problem is ill-conditioned, the asymptotic bounds may only hold for extremely small values of $\Vert(E, F)\Vert _F$. Therefore, we also provide similar global error bounds, which are valid for all perturbations that satisfy an upper bound on $\Vert(E, F)\Vert _F$. The global error bounds in Table 4.8 are guaranteed to hold for all $\Vert(E,F)\Vert _F < {\Delta}$, where

We let $\delta \equiv \Vert(E,F)\Vert _F / {\Delta}$ in Table 4.8. If $\delta$ is small, then the computed pair of left and right deflating subspaces (or computed left and right eigenvectors) are small perturbations of the exact pair of deflating subspaces (or the true left and right eigenvectors). The error bounds conform with the corresponding bounds for the nonsymmetric eigenproblem (see subsection 4.8.1.1 ).


Table: Global error bounds for the generalized nonsymmetric eigenvalue problem assuming $\delta \equiv \Vert(E,F)\Vert _F/{\Delta} < 1$.
Eigenvalue cluster: ${\cal X}( ({\hat{\alpha}}_{\cal I},{\hat{\beta}}_{\cal I}),
({\alpha}_{\cal I},{\beta}_{\cal I}) )
\leq 2 \Vert(E,F)\Vert _F/ l_{\cal I}$
Eigenvector pair:  
   Left $\theta_{\max} (\hat{y}_i , y_i) \leq
\arctan \left(
{\delta \cdot l_i}/{(1 - \delta \sqrt{1 - l_i^2})}
\right)$
   Right $\theta_{\max} (\hat{x}_i , x_i) \leq
\arctan \left(
{\delta \cdot r_i}/{(1 - \delta \sqrt{1 - r_i^2})}
\right)$
Deflating subspace pair:  
   Left $\theta_{\max} ({\widehat{{\cal L}}}_{\cal I},{\cal L}_{\cal I})\leq
\arctan \left(
{\delta \cdot l_{\cal I}}/{(1 - \delta \sqrt{1 - l_{\cal I}^2})}
\right)$
   Right $\theta_{\max}({\widehat{{\cal R}}}_{\cal I},{\cal R}_{\cal I})\leq
\arctan \left(
{\delta \cdot r_{\cal I}}/{(1 - \delta \sqrt{1 - r_{\cal I}^2 })}
\right)$

For ill-conditioned problems the restriction $\Delta$ on $\Vert(E, F)\Vert _F$ may also be small. Indeed, a small value of $\Delta$ shows that the cluster of eigenvalues (in the (1,1)-blocks of (A, B)) is ill-conditioned in the sense that small perturbations of (A, B) may imply that one eigenvalue in the cluster moves and coalesces with another eigenvalue (outside the cluster). Accordingly, this also means that the associated (left and right) deflating subspaces are sensitive to small perturbations, since the size of the perturbed subspaces may change for small perturbations of (A, B). See also the discussion of singular problems in section 4.11.1.4.

As for the nonsymmetric eigenvalue problem we have global error bounds for eigenvalues which are true for all E and F. Let (A, B) be a diagonalizable matrix pair. We let the columns of $\widehat{Y}$ and $\widehat{X}$ be the computed left and right eigenvectors associated with the computed generalized eigenvalue pairs $({\hat{\alpha}}_i, {\hat{\beta}}_i), i = 1, \ldots, n$. Moreover, we assume that $\widehat{Y}$ and $\widehat{X}$ are normalized such that $\vert\hat{\alpha}_i\vert^2 + \vert\hat{\beta}_i\vert^2 = 1$ and $\Vert\hat{y}_i\Vert _2 = 1$, i.e., we overwrite $\hat{y}_i$ with $\hat{y_i}/ \Vert\hat{y_i}\Vert _2$, $({\hat{\alpha}}_i, {\hat{\beta}}_i)$ with $({\hat{\alpha}}_i, {\hat{\beta}}_i) /
(\vert\hat{\alpha}_i\vert^2 + \vert\hat{\beta}_i\vert^2)^{1/2}$ and $\hat{x}_i$ with $\hat{x}_i \Vert\hat{y}_i\Vert _2 / (\vert\hat{\alpha}_i\vert^2 + \vert\hat{\beta}_i\vert^2)^{1/2}$. Then all eigenvalues $({\alpha}_i, {\beta}_i)$ of (A, B) with $\vert{\alpha}_i\vert^2 + \vert{\beta}_i\vert^2 = 1$ lie in the union of n regions (``spheres'')

\begin{displaymath}
\left\{ (\alpha,\beta), \vert\alpha\vert^2 + \vert\beta\vert...
..._i, {\hat{\beta}}_i))
\leq n \Vert(E,F)\Vert _2/ s_i \right\}.
\end{displaymath} (4.10)

If k of the regions overlap, so that any two points inside the k ``spheres'' can be connected by a continuous curve lying entirely inside the k regions, and if no larger set of k + 1 regions has this property, then exactly k of the eigenvalues $({\alpha}_i, {\beta}_i)$ lie inside the union of these ``spheres''. In other words, the global error bound with respect to an individual eigenvalue $({\alpha}_i, {\beta}_i)$ is only useful if it defines a region that does not intersect with regions corresponding to other eigenvalues. If two or more regions intersect, then we can only say that a (true) eigenvalue of (A, B) lies in the union of the overlapping regions. If $\Vert(E,F)\Vert _2$ is so large that (A+E,B+F) could be singular, which means that the eigenvalues are not well-determined by the data, then the error bound from (4.10) will be so large as to not limit the eigenvalues at all; see section 4.11.1.4 for details.

Notation Conversion For easy of reference, the following table summarizes the notation used in mathematical expression of the error bounds in tables 4.7 and 4.8 and in the corresponding driver and computational routines.

Mathematical Driver Routines Computational Routines
notation name parameter name parameter
si xGGEVX RCONDE(i) xTGSNA S(i)   
$\mbox{Dif}_l(i)$ xGGEVX RCONDV(i) xTGSNA DIF(i)
$l_{\cal I}$ xGGESX RCONDE(1) xTGSEN PL
$r_{\cal I}$ xGGESX RCONDE(2) xTGSEN PR
$\mbox{Dif}_u({\cal I})$ xGGESX RCONDV(1) xTGSEN DIF(1)
$\mbox{Dif}_l({\cal I})$ xGGESX RCONDV(2) xTGSEN DIF(2)

The quantities li, ri, $\mbox{Dif}_u(i)$ and $\mbox{Dif}_l(i)$ used in Table 4.8 (for the global error bounds of the $i^{\mbox{th}}$ computed eigenvalue pair $(\hat{\alpha},\hat{\beta})$ and the left and right eigenvectors $\hat{y}_i$ and $\hat{x}_i$) can be obtained by calling xTGSEN with ${\cal I} = \{ i \}$.


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