next up previous contents index
Next: Further Details: Error Bounds Up: Accuracy and Stability Previous: Computing s and   Contents   Index


Error Bounds for the Singular Value Decomposition

The singular value decomposition (SVD) of a real m-by-n matrix A is defined as follows. Let $r = \min (m,n)$. The SVD of A is $A=U \Sigma V^T$ ( $A=U \Sigma V^H$ in the complex case), where U and V are orthogonal (unitary) matrices and $\Sigma = {\mbox {\rm diag}}( \sigma_1 , \ldots , \sigma_r )$ is diagonal, with $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_{r} \geq 0$. The $\sigma _ i $ are the singular values of A and the leading r columns ui of U and vi of V the left and right singular vectors, respectively. The SVD of a general matrix is computed by xGESVD or xGESDD (see subsection 2.3.4).

The approximate error bounds4.10for the computed singular values $\hat{\sigma}_1 \geq \cdots \geq \hat{\sigma}_{r}$ are

\begin{displaymath}
\vert \hat{\sigma}_i - \sigma_i \vert \leq {\tt SERRBD} \; \; .
\end{displaymath}

The approximate error bounds for the computed singular vectors $\hat{v}_i$ and $\hat{u}_i$, which bound the acute angles between the computed singular vectors and true singular vectors vi and ui, are

\begin{eqnarray*}
\theta ( \hat{v}_i , v_i ) & \leq & {\tt VERRBD}(i) \\
\theta ( \hat{u}_i , u_i ) & \leq & {\tt UERRBD}(i) \; \; .
\end{eqnarray*}


These bounds can be computing by the following code fragment.

      EPSMCH = SLAMCH( 'E' )
*     Compute singular value decomposition of A
*     The singular values are returned in S
*     The left singular vectors are returned in U
*     The transposed right singular vectors are returned in VT
      CALL  SGESVD( 'S', 'S', M, N, A, LDA, S, U, LDU, VT, LDVT,
     $              WORK, LWORK, INFO )
      IF( INFO.GT.0 ) THEN
         PRINT *,'SGESVD did not converge'
      ELSE IF ( MIN(M,N) .GT. 0 ) THEN
         SERRBD  = EPSMCH * S(1)
*        Compute reciprocal condition numbers for singular vectors
         CALL SDISNA( 'Left', M, N, S, RCONDU, INFO )
         CALL SDISNA( 'Right', M, N, S, RCONDV, INFO )
         DO 10 I = 1, MIN(M,N)
            VERRBD( I ) = EPSMCH*( S(1)/RCONDV( I ) )
            UERRBD( I ) = EPSMCH*( S(1)/RCONDU( I ) )
10       CONTINUE
      END IF

For example4.11, if ${\tt SLAMCH('E')} = 2^{-24} = 5.961 \cdot 10^{-8}$ and

\begin{displaymath}
A = \left( \begin{array}{ccc} 4 & 3 & 5 \\ 2 & 5 & 8 \\ 3 & 6 & 10 \\ 4 & 5 & 11 \end{array} \right) \; ,
\end{displaymath}

then the singular values, approximate error bounds, and true errors are given below.

i $\hat{\sigma}_i$ SERRBD true $\vert \hat{\sigma}_i - \sigma_i \vert$ VERRBD(i) true $\theta ( \hat{v}_i , v_i )$ UERRBD(i) true $\theta ( \hat{u}_i , u_i )$
1 21.05 $1.3 \cdot 10^{-6}$ $1.7 \cdot 10^{-6}$ $6.7 \cdot 10^{-8}$ $8.1 \cdot 10^{-8}$ $6.7 \cdot 10^{-8}$ $1.5 \cdot 10^{-7}$
2 2.370 $1.3 \cdot 10^{-6}$ $5.8 \cdot 10^{-7}$ $1.0 \cdot 10^{-6}$ $2.9 \cdot 10^{-7}$ $1.0 \cdot 10^{-6}$ $2.4 \cdot 10^{-7}$
3 1.143 $1.3 \cdot 10^{-6}$ $3.2 \cdot 10^{-7}$ $1.0 \cdot 10^{-6}$ $3.0 \cdot 10^{-7}$ $1.1 \cdot 10^{-6}$ $2.4 \cdot 10^{-7}$




next up previous contents index
Next: Further Details: Error Bounds Up: Accuracy and Stability Previous: Computing s and   Contents   Index
Susan Blackford
1999-10-01