Norm Wise Relative Backward Error
Contents |
y=f(z). Let the output of the subroutine which implements f(z) be denoted ; this includes the effects of roundoff. If where is small, then we say is a backward stable algorithm for f, or that the backward error is small. In other norm error matlab words, is the exact value of f at a slightly perturbed input .4.5 Suppose now
L2 Error Norm
that f is a smooth function, so that we may approximate it near z by a straight line: . Then we have the infinity norm error simple error estimate Thus, if is small, and the derivative f'(z) is moderate, the error will be small4.6. This is often written in the similar form This approximately bounds the relative error by the product of the condition norm 2 error number of f at z, , and the relative backward error . Thus we get an error bound by multiplying a condition number and a backward error (or bounds for these quantities). We call a problem ill-conditioned if its condition number is large, and ill-posed if its condition number is infinite (or does not exist)4.7. If f and z are vector quantities, then f'(z) is a matrix (the Jacobian). So instead of using absolute values as
Relative Residual
before, we now measure by a vector norm and f'(z) by a matrix norm |f'(z)|. The conventional (and coarsest) error analysis uses a norm such as the infinity norm. We therefore call this normwise backward stability. For example, a normwise stable method for solving a system of linear equations Ax=b will produce a solution satisfying where and are both small (close to machine epsilon). In this case the condition number is (see section 4.4 below). Almost all of the algorithms in LAPACK (as well as LINPACK and EISPACK) are stable in the sense just described4.8: when applied to a matrix A they produce the exact result for a slightly different matrix A+E, where is of order . In a certain sense, a user can hardly ask for more, provided the data is at all uncertain. It is often possible to compute the norm |E| of the actual backward error by computing a residual r, such as r=Ax-b or , and suitably scaling its norm |r|. The expert driver routines for solving Ax=b do this, for example. For details see [55,67,85,95]. Condition numbers may be expensive to compute exactly. For example, it costs about operations to solve Ax=b for a general matrix A, and computing exactly costs an additional operations, or twice as much. But can be estimated in only O(n2) operations beyond those necessary for soluti
be down. Please try the request again. Your cache administrator is webmaster. Generated Fri, 21 Oct 2016 20:41:24 GMT by s_wx1196 (squid/3.5.20)
be down. Please try the request again. Your cache administrator is webmaster. Generated Fri, 21 Oct 2016 20:41:24 GMT by s_wx1196 (squid/3.5.20)
be down. Please try the request again. Your cache administrator is webmaster. Generated Fri, 21 Oct 2016 20:41:24 GMT by s_wx1196 (squid/3.5.20)