Further Details: Error Bounds for Linear Equation Solving

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

The normwise backward error of the computed solution , with respect to the infinity norm, is the pairwhich minimizesE,f

subject to the constraint . The minimal value of is given by

One can show that the computed solution satisfies , whereis a modestly growing function ofp(n). The corresponding condition number is . The error is bounded byn

In the first code fragment in the last section, , which is in the numerical example, is approximated by . Approximations of -- or, strictly speaking, its reciprocalRCOND-- are returned by computational routines xyyCON (subsection 2.4.1) or driver routines xyySVX (subsection 2.3.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 frombyAx=bequilibration, i.e. scaling the rows and columns ofin 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 .A

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.4.1) or driver routines xyySVX (subsection 2.3.1) will (except in rare cases)
compute a solution
with the following properties:

The componentwise backward error of the computed solution is the pairwhich minimizesE,f

(where we interpret0/0as 0) subject to the constraint . The minimal value of is given by

One can show that for most problems the computed by xyySVX satisfies , whereis a modestly growing function ofp(n). In other words, is the exact solution of the perturbed problem wherenandEare small relative perturbations in each entry offandA, respectively. The corresponding condition number is . The error is bounded byb

The routines xyyRFS and xyySVX return , which is calledBERR(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 forRCOND.

The value ofBERRfor the example in the last section is .

Even in the rare cases where xyyRFS fails to makeBERRclose to its minimum , the error boundFERRmay remain small. See [6] for details.