Heath - Scientific Computing, страница 6

For this same reason, relativeerror is often taken to be relative to the approximate value rather than to the true value,as in the foregoing definition.1.2.5Sensitivity and ConditioningDifficulties in solving a problem accurately are not always due to an ill-conceived formula oralgorithm, but may be inherent in the problem being solved. Even with exact computation,the solution to the problem may be highly sensitive to perturbations in the input data.A problem is said to be insensitive, or well-conditioned , if a given relative change in theinput data causes a reasonably commensurate relative change in the solution. A problemis said to be sensitive, or ill-conditioned , if the relative change in the solution can be muchlarger than that in the input data.More formally, we define the condition number of a problem f at x asCond =|relative change in solution||(f (x̂) − f (x))/f (x)|=,|relative change in input data||(x̂ − x)/x|where x̂ is a point near x.

A problem is sensitive, or ill-conditioned, if its condition numberis much larger than 1. Anyone who has felt a shower go from freezing to scalding, or vice6CHAPTER 1. SCIENTIFIC COMPUTINGversa, at the slightest touch of the temperature control has had first-hand experience witha sensitive system.Example 1.2 Evaluating a Function. Consider the propagated data error when afunction f is evaluated for an approximate input argument x̂ = x + h instead of the “true”input value x.

We know from calculus thatAbsolute error = f (x + h) − f (x) ≈ hf 0 (x),so thatRelative error =and hencef (x + h) − f (x)f 0 (x)≈h,f (x)f (x) 0 hf (x)/f (x) f 0 (x) Cond ≈ = x f (x) .h/xThus, the relative error in the function value can be much larger or smaller than that inthe input, depending on the properties of the function involved and the particular value ofthe input. For example, if f (x) = ex , then the absolute error ≈ hex , relative error ≈ h, andcond ≈ |x|.Example 1.3 Sensitivity.

Consider the problem of computing values of the cosinefunction for arguments near π/2. Let x ≈ π/2 and let h be a small perturbation to x. Thenthe error in computing cos(x + h) is given byAbsolute error = cos(x + h) − cos(x) ≈ −h sin(x) ≈ −h,and henceRelative error ≈ −h tan(x) ≈ ∞.Thus, small changes in x near π/2 cause large relative changes in cos(x) regardless of themethod for computing it. For example,cos(1.57079) = 0.63267949 × 10−5 ,whereascos(1.57078) = 1.63267949 × 10−5 ,so that the relative change in the output, 1.58, is about a quarter of a million times largerthan the relative change in the input, 6.37 × 10−6 .1.2.6Backward Error AnalysisAnalyzing the forward propagation of errors in a computation is often very difficult. Moreover, the worst-case assumptions made at each stage often lead to a very pessimistic boundon the overall error. An alternative approach is backward error analysis: Consider the approximate solution obtained to be the exact solution for a modified problem, then ask how1.2.

APPROXIMATIONS IN SCIENTIFIC COMPUTATION7large a modification to the original problem is required to give the result actually obtained.In other words, how much data error in the initial input would be required to explain all ofthe error in the final computed result? In terms of backward error analysis, an approximatesolution to a given problem is good if it is the exact solution to a “nearby” problem.These relationships are illustrated schematically (and not to scale) in Fig.

1.1, where xand f denote the exact input and function, respectively, fˆ denotes the approximate functionactually computed, and x̂ denotes an input value for which the exact function would givethis computed result. Note that the equality f (x̂) = fˆ(x) is due to the choice of x̂; indeed,this requirement defines x̂.fx •......................................................................................................................................................................................................• f (x)..................↑↑..................||..................||ˆ......... f....................................backward errorforward error....................................||..................|.........

... |..↓↓.....f................x̂ •......................................................................................................................................................................................• f (x̂) = fˆ(x)Figure 1.1: Schematic diagram of backward error analysis.Example 1.4 Backward Error Analysis. Suppose we want a simple function forapproximating the exponential function f (x) = ex , and we want to examine its accuracy forthe argument x = 1.

We know that the exponential function is given by the infinite seriesf (x) = ex = 1 + x +x2 x3++ ···,2!3!so we might consider truncating the series after, say, four terms to get the approximationx2 x3fˆ(x) = 1 + x ++ .26The forward error in this approximation is then given byfˆ(x) − f (x).To determine the backward error, we must find the input value x̂ for f that gives the outputvalue we actually obtained for fˆ, that is, for which f (x̂) = fˆ(x). For the exponentialfunction, we know that this value is given byx̂ = log(fˆ(x)).Thus, for the particular input value x = 1, we have, to seven decimal places,f (x) = 2.718282,fˆ(x) = 2.666667,x̂ = log(2.666667) = 0.980829,Forward error = fˆ(x) − f (x) = −0.051615,8CHAPTER 1.

SCIENTIFIC COMPUTINGBackward error = x̂ − x = −0.019171.The point here is not to compare the numerical values of the forward and backward errorsquantitatively, but merely to illustrate the concepts involved and to show that both arelegitimate approaches to assessing accuracy. In this case, the forward error indicates thatthe accuracy is fairly good because the output is close to what we wanted to compute,whereas the backward error indicates that the accuracy is fairly good because the outputwe obtained is correct for an input that is only slightly perturbed.1.2.7Stability and AccuracyThe concept of stability of a computational algorithm is analogous to conditioning of amathematical problem.

Both concepts have to do with sensitivity to perturbations, butthe term stability is usually used for algorithms and conditioning for problems (althoughstability is sometimes used for problems as well, especially in differential equations). Analgorithm is stable if the result it produces is relatively insensitive to perturbations resultingfrom approximations made during the computation. From the viewpoint of backward erroranalysis, an algorithm is stable if the result it produces is the exact solution to a nearbyproblem.Accuracy, on the other hand, refers to the closeness of a computed solution to the truesolution of the problem under consideration. Stability of an algorithm does not by itselfguarantee that the computed solution is accurate: accuracy depends on the conditioningof the problem as well as the stability of the algorithm. Stability tells us that the solutionobtained is exact for a nearby problem, but the solution to that nearby problem is not necessarily close to the solution to the original problem unless the problem is well-conditioned.Thus, inaccuracy can result from applying a stable algorithm to an ill-conditioned problemas well as from applying an unstable algorithm to a well-conditioned problem.1.3Computer ArithmeticAs noted earlier, one type of approximation inevitably made in scientific computing is inrepresenting real numbers on a computer.

In this section we will examine in some detail thefinite-precision arithmetic systems that are used for most scientific computations on digitalcomputers.1.3.1Floating-Point NumbersIn a digital computer, the real number system of mathematics is represented approximatelyby a floating-point number system. The basic idea resembles scientific notation, in whicha number of very large or very small magnitude is expressed as a number of moderatesize times an appropriate power of ten. For example, 2347 and 0.0007396 are written as2.347×103 and 7.396×10−4 , respectively. In this format, the decimal point moves, or floats,as the power of 10 changes. Formally, a floating-point number system is characterized byfour integers:1.3.

COMPUTER ARITHMETIC9βt[L, U ]Base or radixPrecisionExponent rangeBy definition, any number x in the floating-point system is represented as follows:x = ±(d0 +d1d2dt−1+ 2 + · · · + t−1 )β e ,βββwhere0 ≤ di ≤ β − 1,i = 0, . . . , t − 1,andL ≤ e ≤ U.The part in parentheses, represented by the string of base-β digits d0 d1 · · · dt−1 , is called themantissa or significand , and e is called the exponent or characteristic of the floating-pointnumber x.

The portion d1 d2 · · · dt−1 of the mantissa is called the fraction. In a computer,the sign, exponent, and mantissa are stored in separate fields of a given floating-point word,each of which has a fixed width. The number zero is represented uniquely by having bothits mantissa and its exponent equal to zero.Most computers today use binary (β = 2) arithmetic, but other bases have also beenused in the past, such as hexadecimal (β = 16) in IBM mainframes and β = 3 in an ill-fatedRussian computer.

Octal (β = 8) and hexadecimal notations are also commonly used as aconvenient shorthand for writing binary numbers in groups of three or four binary digits(bits), respectively. For obvious reasons, decimal (β = 10) arithmetic is popular in handheld calculators. To facilitate human interaction, a computer usually converts numericalvalues from decimal notation on input and to decimal notation for output, regardless ofthe base it uses internally. Parameters for some typical floating-point systems are givenin Table 1.1, which illustrates the trade-off between precision and exponent range impliedby their respective field widths.

For example, working with the same 64-bit word length,the Cray system has a wider exponent range than does IEEE double precision, but at theexpense of carrying less precision.Table 1.1: Parameters for some typical floating-point systemsSystemβtLUIEEE SP2 24−126127IEEE DP2 53−1, 0221, 023Cray2 48 −16, 383 16, 384HP calculator10 12−499499IBM mainframe 166−6463The IEEE standard single-precision (SP) and double-precision (DP) binary floatingpoint systems are by far the most important today.