Stopping Criteria and Accuracy Assessment

Since the eigenproblem of a symmetric indefinite pencil does not have any special mathematical properties, we may refer to techniques developed for general non-Hermitian matrices to assess the quality of the approximate eigentriplets of an indefinite pencil. Nonetheless, we can take advantage of the symmetry to simplify the analysis and subsequently the error bound. The simplification stems from the simple relation between the right and left eigenvectors of $H^{-1} B$. If $x$ is a right eigenvector of $H^{-1} B$, then $y = B\bar{x}$ is the corresponding left eigenvector.

To assess the accuracy of a Ritz triplet $\{ \theta^{(j)}_i,{x}^{(j)}_i,{y}^{(j)}_i \}$, by the discussion in §7.8, it is known that there is a matrix $E^{(j)}_i$ such that

$$(H^{-1} B - E^{(j)}_i ) {x}^{(j)}_i = \theta^{(j)}_i {x}^{... ...^{-1} B - E^{(j)}_i ) = \theta^{(j)}_i ({y}^{(j)}_i)^{\ast},$$

where

$$\Vert E^{(j)}_i\Vert _2 = \max \left\{ \frac{\Vert r^{(j)}... ...Vert s^{(j)}_i\Vert _2}{\Vert{y}^{(j)}_i\Vert _2} \right\}.$$

In fact, $\Vert E^{(j)}_i\Vert _2$ is the optimal backward error. By the standard first-order perturbation expansion or the error bound presented in §7.13, there is an eigenvalue $\mu$ of $H^{-1} B$, such that

$$\begin{eqnarray*} \vert \mu - \theta^{(j)}_i \vert & \lapproxeq & \frac{\Vert{... ... _2, \Vert{x}^{(j)}_i\Vert _2 \Vert Bq_{j+1}\Vert _2 \right\}, \end{eqnarray*}$$

where we have made use of equations (8.24), (8.25), and the equality

$$({y}^{(j)}_i)^{\ast} {x}^{(j)}_i = (u^{(j)}_i)^T Q^T_j B Q_j u^{(j)}_i = (u^{(j)}_i)^T \Omega_j u^{(j)}_i.$$

Furthermore, to avoid a bound which explicitly involves the Ritz vectors ${x}^{(j)}_i$, we note that

$$\Vert{x}^{(j)}_i\Vert _2 = \Vert Q_j u^{(j)}_i\Vert _2 \leq \Vert Q_j\Vert _F \leq \sqrt{j}$$

and

$$\Vert{y}^{(j)}_i\Vert _2 = \Vert B Q_j \bar{u}^{(j)}_i\Vert _2 \leq \Vert B Q_j \Vert _F,$$

where it is assumed that $\Vert u^{(j)}_i\Vert = 1$. Recall that the columns of $Q_j$ are normalized to 1. The value of

$$\Vert B Q_j \Vert^2_F = \sum^j_{i=1} \Vert Bq_i\Vert^2_2$$

may be updated in each Lanczos iteration. Therefore the error $\vert \mu - \theta^{(j)}_i \vert$ can also be bounded by

$$\vert \mu - \theta^{(j)}_i \vert \lapproxeq \frac{1}{ \ver... ...\Vert BQ_j\Vert _F, \sqrt{j} \Vert Bq_{j+1}\Vert _2 \right\},$$

which does not explicitly use the Ritz vector ${x}^{(j)}_i$. In conclusion, one may use

$$\frac{1}{ \vert (u^{(j)}_i)^T \Omega_j u^{(j)}_i \vert} \cd... ...{ \Vert BQ_j\Vert _F, \sqrt{j} \Vert Bq_{j+1}\Vert _2 \right\}$$ (239)

as a provisional error estimate in the inner loop of Algorithm 8.4 (i.e., step (19)). Only when the required number of Ritz values $\theta^{(j)}_i$ have passed this test, and not before, may the Ritz vectors ${x}^{(j)}_i$ be computed. At that point the more precise factor,

$$\max\left\{ \Vert B\bar{{x}}^{(j)}_i\Vert _2, \Vert{x}^{(j)}_i\Vert _2 \Vert Bq_{j+1}\Vert _2 \right\},$$

may be computed at the extra cost of forming $B{x}_i^{(j)}$.

The Ritz values $\theta_i^{(j)}$ approximate the eigenvalues of $H^{-1} B$, while the quantities $\sigma+1/\theta_i^{(j)}$ are approximations to the eigenvalues $\lambda$ of the original problem (8.21). We can estimate $\vert\lambda-(\sigma+1/\theta_i^{(j)})\vert$ using the bound above and

$$\left\vert\lambda-\left(\sigma+\frac{1}{\theta_i^{(j)}} \rig... ...c{\vert\mu - \theta_i^{(j)}\vert}{\vert\theta_i^{(j)}\vert^2}.$$