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


Error Bounds for the Symmetric Eigenproblem

The eigendecomposition of an n-by-n real symmetric matrix is the factorization $A=Z \Lambda Z^T$ ( $A= Z \Lambda Z^H$ in the complex Hermitian case), where Z is orthogonal (unitary) and $\Lambda = {\mbox {\rm diag}}( \lambda_1 , \ldots , \lambda_n )$ is real and diagonal, with $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$. The $\lambda_i$ are the eigenvalues of A and the columns zi of Z are the eigenvectors. This is also often written $A z_i = \lambda_i z_i$. The eigendecomposition of a symmetric matrix is computed by the driver routines xSYEV, xSYEVX, xSYEVD, xSYEVR, xSBEV, xSBEVX, xSBEVD, xSPEV, xSPEVX, xSPEVD, xSTEV, xSTEVX, xSTEVD and xSTEVR. The complex counterparts of these routines, which compute the eigendecomposition of complex Hermitian matrices, are the driver routines xHEEV, xHEEVX, xHEEVD, xHEEVR, xHBEV, xHBEVX, xHBEVD, xHPEV, xHPEVX, and xHPEVD (see subsection 2.3.4).

The approximate error bounds4.10 for the computed eigenvalues $\hat{\lambda}_1 \leq \cdots \leq \hat{\lambda}_n$ are

\begin{displaymath}
\vert \hat{\lambda}_i - \lambda_i \vert \leq {\tt EERRBD} \; \; .
\end{displaymath}

The approximate error bounds for the computed eigenvectors $\hat{z}_i$, which bound the acute angles between the computed eigenvectors and true eigenvectors zi, are:

\begin{displaymath}
\theta ( \hat{z}_i , z_i ) \leq {\tt ZERRBD} (i) \; .
\end{displaymath}

These bounds can be computed by the following code fragment:

      EPSMCH = SLAMCH( 'E' )
*     Compute eigenvalues and eigenvectors of A
*     The eigenvalues are returned in W
*     The eigenvector matrix Z overwrites A
      CALL SSYEV( 'V', UPLO, N, A, LDA, W, WORK, LWORK, INFO )
      IF( INFO.GT.0 ) THEN
         PRINT *,'SSYEV did not converge'
      ELSE IF ( N.GT.0 ) THEN
*        Compute the norm of A
         ANORM = MAX( ABS( W(1) ), ABS( W(N) ) )
         EERRBD = EPSMCH * ANORM
*        Compute reciprocal condition numbers for eigenvectors
         CALL SDISNA( 'Eigenvectors', N, N, W, RCONDZ, INFO )
         DO 10 I = 1, N
            ZERRBD( I ) = EPSMCH * ( ANORM / RCONDZ( I ) )
10       CONTINUE
      ENDIF

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

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

then the eigenvalues, approximate error bounds, and true errors are

i $\hat{\lambda}_i$ EERRBD true $\vert \hat{\lambda}_i - \lambda_i \vert$ ZERRBD(i) true $\theta ( \hat{z}_i , z_i )$
1 -.5157 $6.7 \cdot 10^{-7}$ $1.6 \cdot 10^{-7}$ $9.8 \cdot 10^{-7}$ $1.2\cdot10^{-7}$
2 .1709 $6.7 \cdot 10^{-7}$ $3.2 \cdot 10^{-7}$ $9.8 \cdot 10^{-7}$ $7.0 \cdot 10^{-8}$
3 11.34 $6.7 \cdot 10^{-7}$ $2.8 \cdot 10^{-6}$ $6.1 \cdot 10^{-8}$ $9.7 \cdot 10^{-8}$




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