The conventional error analysis of linear
equation solving goes as follows.
Let `Ax` = `b` be the system to be solved. Let be the solution
computed by LAPACK (or LINPACK) using any of their linear equation solvers.
Let `r` be
the residual . In the absence of rounding error `r`
would be zero and would equal `x`; with rounding error one can
only say the following:

The normwise backward error of the computed solution , with respect to the infinity norm, is the pairE,fwhich minimizessubject to the constraint . The minimal value of is given by

One can show that the computed solution satisfies , where

p(n) is a modestly growing function ofn. The corresponding condition number is . The error is bounded byIn the first code fragment in the last section, , which is in the numerical example, is approximated by . Approximations of - or, strictly speaking, its reciprocal

RCOND- are returned by computational routines xyyCON (subsection 2.3.1) or driver routines xyySVX (subsection 2.2.1). The code fragment makes sureRCONDis at leastEPSMCHto avoid overflow in computingERRBD. This limitsERRBDto a maximum of 1, which is no loss of generality since a relative error of 1 or more indicates the same thing: a complete loss of accuracy. Note that the value ofRCONDreturned by xyySVX may apply to a linear system obtained fromAx=bbyequilibration, i.e. scaling the rows and columns ofAin order to make the condition number smaller. This is the case in the second code fragment in the last section, where the program chose to scale the rows by the factors returned in and scale the columns by the factors returned in , resulting in .

As stated in section 4.3.2,
this approach does not respect the presence
of zero or tiny entries in `A`. In contrast,
the LAPACK computational routines
xyyRFS (subsection 2.3.1) or driver routines xyySVX
(subsection 2.2.1) will (except in rare cases)
compute a solution with the following properties:

The componentwise backward error of the computed solution is the pairE,fwhich minimizes(where we interpret 0 / 0 as 0) subject to the constraint . The minimal value of is given by

One can show that for most problems the computed by xyySVX satisfies , where

p(n) is a modestly growing function ofn. In other words, is the exact solution of the perturbed problem whereEandfare small relative perturbations in each entry ofAandb, respectively. The corresponding condition number is . The error is bounded by

The routines xyyRFS and xyySVX return , which is called

BERR(for Backward ERRor), and a bound on the the actual error , calledFERR(for Forward ERRor), as in the second code fragment in the last section.FERRis actually calculated by the following formula, which can be smaller than the bound given above:Here, is the computed value of the residual , and the norm in the numerator is estimated using the same estimation subroutine used for

RCOND.The value of

BERRfor the example in the last section is .Even in the rare cases where xyyRFS fails to make

BERRclose to its minimum , the error boundFERRmay remain small. See [6] for details.

Tue Nov 29 14:03:33 EST 1994