Higham - Accuracy and Stability of Numerical Algorithms (523152), страница 7
Текст из файла (страница 7)
A result of the form(1.2)is known as a mixed forward-backward error result and is illustrated in Figure 1.2. Provided thatandare sufficiently small, (1.2) says that thecomputed valuescarcely differs from the value + that would have beenproduced by an input +scarcely different from the actual inputEvenmore simply,is almost the right answer for almost the right data.In general, an algorithm is called numerically stable if it is stable in themixed forward-backward error sense of (1.2) (hence a backward stable algorithm can certainly be called numerically stable).
Note that this definition isspecific to problems where rounding errors are the dominant form of errors.The term stability has different meanings in other areas of numerical analysis.1.6 CONDITIONINGInput spaceFigure 1.2. Mixed forward-backward error for y =line = computed.Output spaceSolid line = exact; dotted1.6. ConditioningThe relationship between forward and backward error for a problem is governed by the conditioning of the problem, that is, the sensitivity of the solutionto perturbations in the data. Continuing the y =example of the previous section, let an approximate solutionsatisfy=Then,assuming for simplicity that f is twice continuously differentiable,and we can bound or estimate the right-hand side.
This expansion leads tothe notion of condition number. Sincethe quantitymeasures, for smallthe relative change in the output for a given relativechange in the input, and it is called the (relative) condition number of f . Ifor f is a vector then the condition number is defined in a similar way usingnorms and it measures the maximum relative change, which is attained forsome, but not all, vectorsAs an example, consider the function= logThe condition numberis=which is large for1. This means that a small relativechange in can produce a much larger relative change in log for1.
The10PRINCIPLES OF FINITE PRECISION COMPUTATIONreason is that a small relative change inproduces a small absolute changein= log(sinceand thatchange in log may be large in a relative sense.When backward error, forward error, and the condition number are definedin a consistent fashion we have the useful rule of thumb thatforward errorcondition number × backward error,with approximate equality possible. One way to interpret this rule of thumbis to say that the computed solution to an ill-conditioned problem can have alarge forward error.
For even if the computed solution has a small backwarderror, this error can be amplified by a factor as large as the condition numberwhen passing to the forward error.One further definition is useful. If a method produces answers with forward errors of similar magnitude to those produced by a backward stablemethod, then it is called forward stable. Such a method need not be backward stable itself.
Backward stability implies forward stability, but not viceversa. An example of a method that is forward stable but not backward stableis Cramer’s rule for solving a 2 × 2 linear system, which is discussed in §1.10.1.1.7. CancellationCancellation is what happens when two nearly equal numbers are subtracted.It is often, but not always, a bad thing. Consider the function= (1 With= 1.2×10-5 the value ofrounded to 10 significantfigures isc = 0.9999 9999 99,so that1 - c = 0.0000 0000 01.-10Then (1 - c)= 10 /1.44×10-10 = 0.6944.
. . , which is clearly wronggiven the fact that 0 << l/2 for all0. A 10 significant figureapproximation to cos is therefore not sufficient to yield a value ofwitheven one correct figure. The problem is that 1 - c has only 1 significantfigure. The subtraction 1 - c is exact, but this subtraction produces a resultof the same size as the error in c. In other words, the subtraction elevates theimportance of the earlier error.
In this particular example it is easy to rewriteto avoid the cancellation. Since cos = 1 - 2 sin2Evaluating this second formula forwith a 10 significant figure approximation to sinyields= 0.5, which is correct to 10 significant figures.1.8 SOLVING A QUADRATIC EQUATION11To gain more insight into the cancellation phenomenon consider the subtraction (in exact arithmetic)whereandThe terms ∆a and ∆b are relative errors or uncertainties in the data, perhapsattributable to previous computations. With x = a - b we haveThe relative error bound foris large when |a - b| << |a| + |b|, that is,when there is heavy cancellation in the subtraction.
This analysis shows thatsubtractive cancellation causes relative errors or uncertainties already presentinand b to be magnified. In other words, subtractive cancellation bringsearlier errors into prominence.It is important to realize that cancellation is not always a bad thing. Thereare several reasons. First, the numbers being subtracted may be error free,as when they are from initial data that is known exactly. The computationof divided differences, for example, involves many subtractions, but half ofthem involve the initial data and are harmless for suitable orderings of thepoints (see §5.3 and §21.3). The second reason is that cancellation may bea symptom of intrinsic ill conditioning of a problem, and may therefore beunavoidable.
Third, the effect of cancellation depends on the role that theresult plays in the remaining computation. For example, if x >> yz > 0then the cancellation in the evaluation of x + (y - z) is harmless.1.8. Solving a Quadratic EquationMathematically, the problem of solving the (real) quadratic equation ax 2bx + c = 0 is trivial: there are two roots (if a 0)) given by+(1.3)Numerically, the problem is more challenging, as neither the successful evaluation of (1.3) nor the accuracy of the computed roots can be taken for granted.The easiest issue to deal with is the choice of formula for computing theroots. If b2 >> |4ac| thenand so for one choice of sign the formula (1.3) suffers massive cancellation.
This is damaging cancellation becauseone of the arguments,is inexact, so the subtraction brings intoprominence the earlier rounding errors. How to avoid the cancellation is wellknown: obtain the larger root (in absolute value), x 1, fromand the other from the equation x 1 x 2 = c/a.12PRINCIPLES OF FINITE PRECISION COMPUTATIONUnfortunately, there is a more pernicious source of cancellation: the subtraction b 2 - 4ac. Accuracy is lost here when b 24ac (the case of nearlyequal roots), and no algebraic rearrangement can avoid the cancellation.
Theonly way to guarantee accurate computed roots is to use double precision (orsome trick tantamount to the use of double precision) in the evaluation ofb 2 - 4ac.Another potential difficulty is underflow and overflow. If we apply theformula (1.3) in IEEE single precision arithmetic (described in §2.3) to theequation 1020 x2 - 3·1020 x+2·1020 = 0 then overflow occurs, since the maximum floating point number is of order 10 the roots, however, are innocuous:x = 1 and x = 2.
Dividing through the equation by max(| a|, |b|, |c |) = 1020cures the problem, but this strategy is ineffective for the equation 10-20x 2 3x+2·1020 = 0, whose roots are 1020 and 2·1020. In the latter equation we needto scale the variable: defining x = 1020 y gives 1020 y2 -3·10 20 y+ 2 · 1 0 2 0 = 0 ,which is the first equation we considered. These ideas can be built into ageneral scaling strategy (see the Notes and References), but the details arenontrivial.As this discussion indicates, not only is it difficult to devise an accurate androbust algorithm for solving a quadratic equation, but it is a nontrivial taskto prepare specifications that define precisely what “accurate” and “robust”mean for a given system of floating point arithmetic.1.9.
Computing the Sample VarianceIn statistics the sample variance of n numbers x 1, . . . , xn is defined as(1.4)where the sample meanComputingfrom this formula requires two passes through the data, oneto computeand the other to accumulate the sum of squares. A two-passcomputation is undesirable for large data sets or when the sample varianceis to be computed as the data is generated. An alternative formula, foundin many statistics textbooks, uses about the same number of operations butrequires only one pass through the data:(1.5)1.10 SOLVING LINEAR EQUATIONS13This formula is very poor in the presence of rounding errors because it computes the sample variance as the difference of two positive numbers, andtherefore can suffer severe cancellation that leaves the computed answer dominated by roundoff.
In fact, the computed answer can be negative, an eventaptly described by Chan, Golub, and LeVeque [194, 1983] as “a blessing indisguise since this at least alerts the programmer that disastrous cancellation has occurred”. In contrast, the original formula (1.4) always yields avery accurate (and nonnegative) answer, unless n is large (see Problem 1.10).Surprisingly, current calculators from more than one manufacturer (but notHewlett-Packard) appear to use the one-pass formula, and they list it in theirmanuals.As an example, if x = [10000, 10001, 10002]T then, in single precisionarithmetic (u6 × 10-8), the sample variance is computed as 1.0 by thetwo-pass formula (relative error 0) but 0.0 by the one-pass formula (relativeerror 1). It might be argued that this data should be shifted by some estimateof the mean before applying the one-pass formulawhichdoes not change), but a good estimate is not always available and thereare alternative one-pass algorithms that will always produce an acceptablyaccurate answer.
For example, instead of accumulatingandwecan accumulatewhich can be done via the updating formulae(1.6a)(1.6b)after which= Q n / (n - 1). Note that the only subtractions in these recurrences are relatively harmless ones that involve the data xi .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
