Heath - Scientific Computing (523150), страница 5
Текст из файла (страница 5)
At each step of this process, wewould need to verify that the solution is unchanged, or is at least within some requiredtolerance of the true solution.To make this general strategy work for solving a given problem, we must have• An alternative problem, or class of problems, that is easier to solve• A transformation of the given problem into a problem of this alternative type that preserves the solution in some senseThus, much of our effort will go into identifying suitable problem classes with simple solutions and solution-preserving transformations into those classes.Ideally, the solution to the transformed problem is identical to that of the original problem, but this is not always possible.
In the latter case the solution may only approximatethat of the original problem, but the accuracy can usually be made arbitrarily good at theexpense of additional work and storage. Thus, primary concerns are estimating the accuracy of such an approximate solution and establishing convergence to the true solution inthe limit.1.21.2.1Approximations in Scientific ComputationSources of ApproximationThere are many sources of approximation or inexactness in computational science. Some ofthese occur even before computation begins:• Modeling: Some physical features of the problem or system under study may be simplified or omitted (e.g., friction, viscosity).• Empirical measurements: Laboratory instruments have finite precision. Their accuracy may be further limited by small sample size, or readings obtained may be subject to1.2.
APPROXIMATIONS IN SCIENTIFIC COMPUTATION3random noise or systematic bias. For example, even the most careful measurements of important physical constants, such as Newton’s gravitational constant or Planck’s constant,typically yield values with at most eight or nine significant decimal digits.• Previous computations: Input data may have been produced by a previous step whoseresults were only approximate.The approximations just listed are usually beyond our control, but they still play an important role in determining the accuracy that should be expected from a computation. Wewill focus most of our attention on approximations over which we do have some influence.These systematic approximations that occur during computation include• Truncation or discretization: Some features of a mathematical model may be omittedor simplified (e.g., replacing a derivative by a difference quotient or using only a finitenumber of terms in an infinite series).• Rounding The computer representation of real numbers and arithmetic operations uponthem is generally inexact.The accuracy of the final results of a computation may reflect a combination of any or allof these approximations, and the resulting perturbations may be amplified or magnified bythe nature of the problem being solved or the algorithm being used, or both.
The study ofthe effects of such approximations on the accuracy and stability of numerical algorithms istraditionally called error analysis.Example 1.1 Approximations. The surface area of the Earth might be computed usingthe formulaA = 4πr2for the surface area of a sphere of radius r. The use of this formula for the computationinvolves a number of approximations:• The Earth is modeled as a sphere, which is an idealization of its true shape.• The value for the radius, r ≈ 6370 km, is based on a combination of empirical measurements and previous computations.• The value for π is given by an infinite limiting process, which must be truncated at somepoint.• The numerical values for the input data, as well as the results of the arithmetic operationsperformed on them, are rounded in a computer.The accuracy of the computed result depends on all of these approximations.1.2.2Data Error and Computational ErrorAs we have just seen, some errors can be attributed to the input data, whereas others aredue to subsequent computational processes.
Although this distinction is not always clearcut (rounding, for example, may affect both the input data and subsequent computational4CHAPTER 1. SCIENTIFIC COMPUTINGresults), it is nevertheless helpful in understanding the overall effects of approximations innumerical computations.A typical problem can be viewed as the computation of the value of a function, sayf : R → R (most realistic problems are multidimensional, but for now we consider onlyone dimension for illustration). Denote the true value of the input data by x, so that thedesired true result is f (x). Suppose that we must work with inexact input, say x̂, and wecan compute only an approximation to the function, say fˆ. ThenTotal error =fˆ(x̂) − f (x)=(fˆ(x̂) − f (x̂))+(f (x̂) − f (x))= computational error + propagated data error.The first term in the sum is the difference between the exact and approximate functions forthe same input and hence can be considered pure computational error .
The second termis the difference between exact function values due to error in the input and thus can beviewed as pure propagated data error . Note that the choice of algorithm has no effect onthe propagated data error.1.2.3Truncation Error and Rounding ErrorSimilarly, computational error (that is, error made during the computation) can be subdivided into truncation (or discretization) error and rounding error:• Truncation error is the difference between the true result (for the actual input) and theresult that would be produced by a given algorithm using exact arithmetic. It is dueto approximations such as truncating an infinite series, replacing a derivative by a finitedifference quotient, replacing an arbitrary function by a polynomial, or terminating aniterative sequence before convergence.• Rounding error is the difference between the result produced by a given algorithm usingexact arithmetic and the result produced by the same algorithm using finite-precision,rounded arithmetic.
It is due to inexactness in the representation of real numbers andarithmetic operations upon them, which we will consider in detail in Section 1.3.By definition, then, computational error is simply the sum of truncation error and roundingerror.Although truncation error and rounding error can both play an important role in a givencomputation, one or the other is usually the dominant factor in the overall computationalerror. Roughly speaking, rounding error tends to dominate in purely algebraic problemswith finite solution algorithms, whereas truncation error tends to dominate in problemsinvolving integrals, derivatives, or nonlinearities, which often require a theoretically infinitesolution process.The distinctions we have made among the different types of errors are important forunderstanding the behavior of numerical algorithms and the factors affecting their accuracy,but it is usually not necessary, or even possible, to quantify precisely the individual typesof errors.
Indeed, as we will soon see, it is often advantageous to lump all of the errorstogether and attribute them to error in the input data.1.2. APPROXIMATIONS IN SCIENTIFIC COMPUTATION1.2.45Absolute Error and Relative ErrorThe significance of an error is obviously related to the magnitude of the quantity beingmeasured or computed. For example, an error of 1 is much less significant in counting thepopulation of the Earth than in counting the occupants of a phone booth. This motivatesthe concepts of absolute error and relative error , which are defined as follows:Absolute error = approximate value − true value,absolute errorRelative error =.true valueSome authors define absolute error to be the absolute value of the foregoing difference, butwe will take the absolute value explicitly when only the magnitude of the error is needed.Relative error can also be expressed as a percentage, which is simply the relative errortimes 100.
Thus, for example, an absolute error of 0.1 relative to a true value of 10 wouldbe a relative error of 0.01, or 1 percent. A completely erroneous approximation wouldcorrespond to a relative error of at least 1, or at least 100 percent, meaning that theabsolute error is as large as the true value. One interpretation of relative error is that if aquantity x̂ has a relative error of about 10−t , the decimal representation of x̂ has about tcorrect significant digits.Another useful way to express the relationship between absolute and relative error isthe following:Approximate value = (true value) × (1 + relative error).Of course, we do not usually know the true value; if we did, we would not need to botherwith approximating it. Thus, we will usually merely estimate or bound the error ratherthan compute it exactly, because the true value is unknown.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
