Higham - Accuracy and Stability of Numerical Algorithms (523152), страница 11
Текст из файла (страница 11)
Figure 1.6plots the computed function values together with a much more accurate approximation to r(x) (computed from a continued fraction representation).The striking pattern formed by the values computed by Horner’s rule showsclearly that the rounding errors in this example are not random.30P RINCIPLESOFFINITE P RECISION C OMPUTATION1.18. Designing Stable AlgorithmsThere is no simple recipe for designing numerically stable algorithms.
Whilethis helps to keep numerical analysts in business (even in proving each other’salgorithms to be unstable!) it is not good news for computational scientistsin general. The best advice is to be aware of the need for numerical stabilitywhen designing an algorithm and not to concentrate solely on other issues,such as computational cost and parallelizability.A few guidelines can be given.1.
Try to avoid subtracting quantities contaminated by error (though suchsubtractions may be unavoidable).2. Minimize the size of intermediate quantities relative to the final solution. The reason is that if intermediate quantities are very large thenthe final answer may be the result of damaging subtractive cancellation. Looked at another way, large intermediate numbers swamp theinitial data, resulting in loss of information. The classic example of analgorithm where this considerat ion is import ant is Gaussian elimination(§9.2), but an even simpler one is recursive summation (§4.2).3.
Look for different formulations of a computation that are mathematically but not numerically equivalent. For example, the classical GramSchmidt method is unstable, but a trivial modification produces thestable modified Gram-Schmidt (MGS) method (§18.7). There are twoways of using the MGS method to solve a least squares problem, themore obvious of which is unstable (§19.3).4. It is advantageous to express update formulae asnew-value = old-value + small-correct ionif the small correction can be computed with many correct significantfigures.
Numerical methods are often naturally expressed in this form;examples include met hods for solving ordinary differential equations,where the correction is proportional to a step size, and Newton’s methodfor solving a nonlinear system. A classic example of the use of thisupdate strategy is in iterative refinement for improving the computedsolution to a linear system Ax = b, in which by computing residualsr = b - Ay in extended precision and solving update equations thathave the residuals as right-hand sides a highly accurate solution can becomputed: see Chapter 11. For another example (in which the correctionis not necessarily small), see Problem 2.8.5. Use only well-conditioned transformations of the problem. In matrixcomputations this amounts to multiplying by orthogonal matrices where1.19 M ISCONCEPTIONS31possible, instead of nonorthogonal, and possibly, ill-conditioned matrices.
See §6.2 for a simple explanation of this advice in terms of norms.6. Take precautions to avoid unnecessary overflow and underflow (see §25.8).Concerning the second point, good advice is to look at the numbers generated during a computation. This was common practice in the early daysof electronic computing. On some machines it was unavoidable because thecontents of the store were displayed on lights or monitor tubes! Wilkinsongained much insight into numerical stability by inspecting the progress of analgorithm, and sometimes altering its course (for an iterative process withparameters): “Speaking for myself I gained a great deal of experience fromuser participation, and it was this that led to my own conversion to backwarderror analysis” [1099, 1980, pp.
112-113] see also [1083, 1955]). It is ironicthat with the wealth of facilities we now have for tracking the progress of numerical algorithms (multiple windows in colour, graphical tools, fast printers)we often glean less than Wilkinson and his co-workers did from mere papertape and lights.1.19. MisconceptionsSeveral common misconceptions and myths have been dispelled in this chapter(none of them for the first time-see the Notes and References). We highlightthem in the following list.1.
Cancellation in the subtraction of two nearly equal numbers is always abad thing (§1.7).2. Rounding errors can overwhelm a computation only if vast numbers ofthem accumulate (§1.11).3. A short computation free from cancellation, underflow, and overflowmust be accurate (§1.12).4. Increasing the precision at which a computation is performed increasesthe accuracy of the answer (§1.13).5. The final computed answer from an algorithm cannot be more accuratethan any of the intermediate quantities, that is, errors cannot cancel(§1.14).6.
Rounding errors can only hinder, not help, the success of a computation(§1.15).32P RINCIPLESOFFINITE P RECISION C OMPUTATION1.20. Rounding Errors in Numerical AnalysisInevitably, much of this book is concerned with numerical linear algebra, because this is the area of numerical analysis in which the effects of roundingerrors are most important and have been most studied. In nonlinear problems rounding errors are often not a major concern because other forms oferror dominate. Although we give examples for numerical methods involvingderivatives and integrals (for example, Euler’s met hod in §4.3 and quadraturein Problem 3.12), it is beyond our scope to give a treatment of the effects andinfluence of rounding errors on these methods.
We do. however, give someselected references to the literature. grouped by subject area.Approximation theory: Clenshaw [212, 19551], Cox [249, 19721], [250, 19751],[251, 1978], Cox and Harris [253, 1989], de Boor [272, 19721], and de Boorand Pinkus [273, 1977].Chaos and dynamical systems: Cipra [211, 19 88], Coomes, Koçak, andPalmer [242, 1995], Corless [246. 1992], [247, 1992], Hammel, Yorke,and Grebogi [499, 1988], and Sanz-Serna and Larsson [893, 1993].Nonlinear equations: Dennis and Walker [302,and Wozniakowski [1111, 1977].1984],Spellucci [933,1980],Optimization: Dennis and Schnabel [300, 1983], Fletcher [377, 1986], [379,19 88], [380, 1993 ], [381, 1994 ]. Gill, Murray, and Wright [447, 19 8 1 ],Gurwitz [490, 1992], Müller-Merbach [783, 1970], and Wolfe [1108, 1965].Ordinary differential equation initial value problems: Henrici[517, 1962], [518, 1963], [519, 1964], D.
J. Higham [525, 1991]. SanzSerna [891, 1992, §12], Sanz-Serna and Calvo [892, 1994], and Shampine[910, 1994, §3.3, §5.6].Partial differential equations: Ames [14, 1977], Birkhoff and Lynch [101,1984], Canuto, Hussaini, Quarteroni, and Zang [183, 1988], Douglas [319,1959 ], Forsythe and Wasow [397, 19 6 0 ], Richtmyer and Morton [872,1967, §1.8], and Trefethen and Trummer [1020, 1987].Quadrature: Davis and Rabinowitz [267, 198 4, §4.2], Lyness [717,and Piessens et al. [832, 1983, §3.4.3.1].19 6 9 ],1.21. Notes and ReferencesThe term “correct significant digits” is rarely defined in textbooks: it is apparently assumed that the definition is obvious. One of the earliest books on1.21 N OTESANDR EFERENCES33numerical analysis, by Scarborough [897, 1950] (first edition 1930), is noteworthy for containing theorems describing the relationship between correctsignificant digits and relative error.The first definition of correct significant digits in §1.2 is suggested byHildebrand [571, 1974, §1.41], who notes its weaknesses.For a formal proof and further explanation of the fact that precision doesnot limit accuracy see Priest [844, 1992].It is possible to develop formal definitions of numerical stability, eitherwith respect to a particular problem, as is frequently done in research papers,or for a very general class of problems, as is done, for example, by de Jong [274,1977 ].
Except in §7.6, we do not give formal definitions of stability in thisbook, preferring instead to adapt informally the basic notions of backwardand forward stability to each problem, and thereby to minimize the amountof notation and abstraction.Backward error analysis was systematically developed, exploited, and popularized by Wilkinson in the 1950s and 1960s in his research papers and, inparticular, through his books [1088, 1963], [1089, 1965] (for more about thebooks see the Notes and References for Chapter 2). Backward error ideas hadearlier appeared implicitly in papers by von Neumann and Goldstine (1057,1947] and Turing [1027, 1948], both of which deal with the solution of linear systems, and explicitly in an unpublished technical report of Givens [451,1954] on the solution of the symmetric eigenproblem by reduction to tridiagonal form followed by the use of Sturm sequences. The concept of backwarderror is not limited to numerical linear algebra.
It is used, for example, inthe numerical solution of differential equations; see Eirola [349, 1993], Enright [352, 1989], and Shampine [910, 1994, §2.2], in addition to the referencesof Sanz-Serna and his co-authors cited in §1.20. Backward error is also usedin understanding chaotic behaviour of iterations; see the references in §1.20.Conditioning of problems has been studied by numerical analysts sincethe 1940s but the first general theory was developed by Rice [871, 1966]. Innumerical linear algebra, developing condition numbers is part of the subjectof perturbation theory, on which there is a large literature.The solution of a quadratic equation is a classic problem in numerical analysis.
In 1969 Forsythe [393, 1969] pointed out “the near absence of algorithmsto solve even a quadratic equation in a satisfactory way on actually used digital computer systems” and he presented specifications suggested by Kahanfor a satisfactory solver. Similar, but less technical, presentations are given byForsythe [392, 1969] and Forsythe, Malcolm, and Moler [395, 1977, §2.6]. Kahan [627, 1972] and Sterbenz [938, 1974] both present algorithms for solvinga quadratic equation, accompanied by error analysis.For more details of algorithms for computing the sample variance andtheir error analysis, see Chan and Lewis [195, 1979], Chan, Golub, and LeVeque [194, 1983], Barlow [61, 1991], and the references therein.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
