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 i^th computed eigenvalue pair and $({\alpha}_i, {\beta}_i)$ the i^th exact eigenvalue pair.^4.2Let $\hat{x}_i$ and $\hat{y}_i$ be the corresponding computed right and left eigenvectors, and x_i and y_i 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 eigenvalues^4.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$: s_i and ${\rm Dif}_l(i)$. s_i 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:
Eigenvalue cluster:
Eigenvector pair:
Left	$\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	$\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	$\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	$\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

• ${\Delta} \equiv \frac{1}{4} \min (l_i,r_i) {\min({\rm Dif}_u(i), {\rm Dif}_l(i))}$ for an individual eigenvector pair, and
• ${\Delta} \equiv \frac{1}{4} \min (l_{\cal I},r_{\cal I}) {\min({\rm Dif}_u({\cal I}), {\rm Dif}_l({\cal I}))}$ for a cluster of eigenvalues or a deflating subspace pair.

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'')

$$\left\{ (\alpha,\beta), \vert\alpha\vert^2 + \vert\beta\vert... ..._i, {\hat{\beta}}_i)) \leq n \Vert(E,F)\Vert _2/ s_i \right\}.$$ (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 l_i, r_i, $\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 \}$.