Error Bounds for Linear Equation Solving

Let Ax=b be the system to be solved, and $\hat{x}$ the computed solution. Let n be the dimension of A. An approximate error bound for $\hat{x}$ may be obtained in one of the following two ways, depending on whether the solution is computed by a simple driver or an expert driver:

1.

Suppose that Ax=b is solved using the simple driver SGESV (subsection 2.3.1). Then the approximate error bound^4.10

$$\frac{\Vert \hat{x} - x \Vert _{\infty}}{\Vert x\Vert _{\infty}} \leq {\tt ERRBD}$$

can be computed by the following code fragment.

      EPSMCH = SLAMCH( 'E' )
*     Get infinity-norm of A
      ANORM = SLANGE( 'I', N, N, A, LDA, WORK )
*     Solve system; The solution X overwrites B
      CALL SGESV( N, 1, A, LDA, IPIV, B, LDB, INFO )
      IF( INFO.GT.0 ) THEN
         PRINT *,'Singular Matrix'
      ELSE IF (N .GT. 0) THEN
*        Get reciprocal condition number RCOND of A
         CALL SGECON( 'I', N, A, LDA, ANORM, RCOND, WORK, IWORK, INFO )
         RCOND = MAX( RCOND, EPSMCH )
         ERRBD = EPSMCH / RCOND
      END IF

For example, suppose^4.11 ${\tt SLAMCH('E')} = 2^{-24} = 5.961 \cdot 10^{-8}$,

$$A = \left( \begin{array}{ccc} 4 & 16000 & 17000 \\ 2 & 5 & 8... ...in{array}{c} 100.1 \\ .1 \\ .01 \end{array} \right) \; . \; \;$$

Then (to 4 decimal places)

$$x = \left( \begin{array}{c} -.3974 \\ -.3349 \\ .3211 \end{a... ...n{array}{c} -.3968 \\ -.3344 \\ .3207 \end{array} \right) \; ,$$

${\tt ANORM} = 3.300 \cdot 10^4$, ${\tt RCOND} = 3.907 \cdot 10^{-6}$, the true reciprocal condition number $= 3.902 \cdot 10^{-6}$, ${\tt ERRBD} = 1.5 \cdot 10^{-2}$, and the true error $= 1.5 \cdot 10^{-3}$.

2.

Suppose that Ax=b is solved using the expert driver SGESVX (subsection 2.3.1). This routine provides an explicit error bound FERR, measured with the infinity-norm:

$$\frac{\Vert \hat{x} - x \Vert _{\infty}}{\Vert x\Vert _{\infty}} \leq {\tt FERR}$$

For example, the following code fragment solves Ax=b and computes an approximate error bound FERR:

      CALL SGESVX( 'E', 'N', N, 1, A, LDA, AF, LDAF, IPIV,
     $             EQUED, R, C, B, LDB, X, LDX, RCOND, FERR, BERR,
     $             WORK, IWORK, INFO )
      IF( INFO.GT.0 ) PRINT *,'(Nearly) Singular Matrix'

For the same A and b as above, $\hat{x} = \left( \begin{array}{c} -.3974 \\ -.3349 \\ .3211 \end{array} \right)$, ${\tt FERR} = 3.0 \cdot 10^{-5}$, and the actual error is $4.3 \cdot 10^{-7}$.

This example illustrates that the expert driver provides an error bound with less programming effort than the simple driver, and also that it may produce a significantly more accurate answer.

Similar code fragments, with obvious adaptations, may be used with all the driver routines for linear equations listed in Table 2.2. For example, if a symmetric system is solved using the simple driver xSYSV, then xLANSY must be used to compute ANORM, and xSYCON must be used to compute RCOND.