next up previous contents index
Next: Error Bounds for Fast Up: Error Bounds for the Previous: Error Bounds for the   Contents   Index

Further Details: Error Bounds for the Generalized Singular Value Decomposition

The GSVD algorithm used in LAPACK ([83,10,8]) is backward stable:

Let the computed GSVD of A and B be $\hat{U} \hat{\Sigma}_1 [0,\hat{R}] \hat{Q}^T$ and $\hat{V} \hat{\Sigma}_2 [0,\hat{R}] \hat{Q}^T$. This is nearly the exact GSVD of A+E and B+F in the following sense. E and F are small:

\begin{displaymath}
\Vert E\Vert _2 / \Vert A\Vert _2 \leq p(n) \epsilon \; \; {...
...; \;
\Vert F\Vert _2 / \Vert B\Vert _2 \leq p(n) \epsilon \; ;
\end{displaymath}

there exist small $\delta \hat{Q}$, $\delta \hat{U}$, and $\delta \hat{V}$ such that $\hat{Q} + \delta \hat{Q}$, $\hat{U}+ \delta \hat{U}$, and $\hat{V}+ \delta
\hat{V}$ are exactly orthogonal (or unitary):

\begin{displaymath}
\Vert \delta \hat{Q} \Vert _2 \leq p(n) \epsilon \; \; , \; ...
...\; \;
\Vert \delta \hat{V} \Vert _2 \leq p(n) \epsilon \; \; ;
\end{displaymath}

and

\begin{displaymath}
A + E = ( \hat{U} + \delta \hat{U} ) \hat{\Sigma}_1 [ 0, \ha...
...V} ) \hat{\Sigma}_2 [ 0, \hat{R}] (\hat{Q} + \delta \hat{Q})^T
\end{displaymath}

is the exact GSVD of A+E and B+F. Here p(n) is a modestly growing function of n, and we take p(n)=1 in the above code fragment.

Let $\alpha_i$ and $\beta_i$ be the square roots of the diagonal entries of the exact $\Sigma_1^T \Sigma_1$ and $\Sigma_2^T \Sigma_2$, and let $\hat{\alpha}_i$ and $\hat{\beta}_i$ the square roots of the diagonal entries of the computed $\hat{\Sigma}_1^T \hat{\Sigma}_1$ and $\hat{\Sigma}_2^T \hat{\Sigma}_2$. Let

\begin{displaymath}
G = \left( \begin{array}{c} A \\ B \end{array} \right) \; \;...
...( \begin{array}{c} \hat{A} \\ \hat{B} \end{array} \right) \; .
\end{displaymath}

Then provided G and $\hat{G}$ have full rank n, one can show [96,82] that

\begin{displaymath}
\left( \sum_{i=1}^n [( \hat{\alpha}_i - \alpha_i )^2 +
( \h...
...{\min ( \sigma_{\min} (G) , \sigma_{\min} (\hat{G}) )} \; \; .
\end{displaymath}

In the code fragment we approximate the numerator of the last expression by $\epsilon \Vert\hat{R}\Vert _{\infty}$ and approximate the denominator by $\Vert \hat{R}^{-1} \Vert^{-1}_{\infty}$ in order to compute SERRBD; STRCON returns an approximation RCOND to $1/ (\Vert \hat{R}^{-1} \Vert _{\infty} \Vert \hat{R} \Vert _{\infty})$.

We assume that the rank r of G equals n, because otherwise the $\alpha_i$s and $\beta_i$s are not well determined. For example, if

\begin{displaymath}
A = \left( \begin{array}{cc} 10^{-16} & 0 \\ 0 & 1 \end{arra...
...( \begin{array}{cc} 10^{-16} & 0 \\ 0 & 1 \end{array} \right)
\end{displaymath}

then A and B have $\alpha_{1,2} = 1, .7071$ and $\beta_{1,2} = 0, .7071$, whereas A' and B' have $\alpha'_{1,2} = 0, .7071$ and $\beta'_{1,2} = 1, .7071$, which are completely different, even though $\Vert A - A' \Vert = 10^{-16}$ and $\Vert B - B' \Vert = 10^{-16}$. In this case, $\sigma_{\min} (G) = 10^{-16}$, so G is nearly rank-deficient.

The reason the code fragment assumes $m \geq n$ is that in this case $\hat{R}$ is stored overwritten on A, and can be passed to STRCON in order to compute RCOND. If $m \leq n$, then the first m rows of $\hat{R}$ are stored in A, and the last n-m rows of $\hat{R}$ are stored in B. This complicates the computation of RCOND: either $\hat{R}$ must be copied to a single array before calling STRCON, or else the lower level subroutine SLACON must be used with code capable of solving linear equations with $\hat{R}$ and $\hat{R}^T$ as coefficient matrices.


next up previous contents index
Next: Error Bounds for Fast Up: Error Bounds for the Previous: Error Bounds for the   Contents   Index
Susan Blackford
1999-10-01