Shampine, Allen, Pruess - Fundamentals of Numerical Computing (523185), страница 2
Текст из файла (страница 2)
For example, GAMS provides a link tonetlib, a large collection of public-domain mathematical software. Most of the programs in netlib are written in FORTRAN, although some are in C. A number of thepackages found in netlib are state-of-the-art software that are cited in this book. Theinternet address ishttp://gams.nist.govfor GAMS.A useful source of microcomputer software and pointers to other sources of software is the Mathematics Archives athttp://archives.math.utk.edu:80/It is worth remarking that one item listed there is an “Index of resources for numericalcomputation in C or C++.”There are a number of commercial packages that can be located by means ofGAMS. We are experienced with the NAG and IMSL libraries, which are large collections of high-quality mathematical software found in most computing centers.
Thecomputing environments MATLAB and Mathematica mentioned in the preceding section can also be located through GAMS.REFERENCES1. C. Moler, J. Little, S. Bangert, and S. Kleiman, ProMatlab User’s Guide, MathWorks, Sherborn,Mass., 1987. email: info@mathworks.com2. S. Wolfram, Mathematica, Addison-Wesley, Redwood City, Calif., 1991. email: info@wri.comviiiPRELIMINARIESACKNOWLEDGMENTSThe authors are indebted to many individuals who have contributed to the productionof this book. Professors Bernard Bialecki and Michael Hosea have been especiallysharp-eyed at catching errors in the latest versions. We thank the people at Wiley, Barbara Holland, Cindy Rhoads, and Nancy Prinz, for their contributions. David Richardsat the University of Illinois played a critical role in getting thefunctioningfor us, and quickly and accurately fixing otherWe also acknowledgethe work of James Otto in checking all solutions and examples, and Hong-sung Jinwho generated most of the figures.
Last, but certainly not least, we are indeed gratefulto the many students, too numerous to mention, who have made valuable suggestionsto us over the years.CONTENTSCHAPTER 1ERRORS AND FLOATING POINT ARITHMETIC 11.1 Basic Concepts 11.2 Examples of Floating Point Calculations1.3 Case Study 1 251.4 Further Reading 28CHAPTER 2SYSTEMS OF LINEAR EQUATIONS 302.12.22.32.42.52.6CHAPTER 3Gaussian Elimination with Partial Pivoting 32Matrix Factorization 44Accuracy 4 8Routines Factor and Solve 61Matrices with Special Structure 65Case Study 2 72INTERPOLATION 823.13.23.33.43.53.63.7CHAPTER 412Polynomial Interpolation 83More Error Bounds 90Newton Divided Difference Form 93Assessing Accuracy 98Spline Interpolation 101Interpolation in the Plane 119Case Study 3 128ROOTS OF NONLINEAR EQUATIONS 1344.1 Bisection, Newton’s Method, and the Secant Rule 1374.2 An Algorithm Combining Bisection and the Secant Rule 1504.3 Routines for Zero Finding 1524.4 Condition, Limiting Precision, and Multiple Roots 1574.5 Nonlinear Systems of Equations 1604.6 Case Study 4 163ixXCONTENTSCHAPTER5NUMERICAL INTEGRATION 1705.15.25.35.45.55.65.7CHAPTER 6ORDINARY DIFFERENTIAL EQUATIONS 2106.16.26.36.46.56.66.76.8APPENDIX ABasic Quadrature Rules 170Adaptive Quadrature 184Codes for Adaptive Quadrature 188Special Devices for Integration 191Integration of Tabular Data 200Integration in Two Variables 202Case Study 5 203Some Elements of the Theory 210A Simple Numerical Scheme 216One-Step Methods 221Errors-Local and Global 228The Algorithms 233The Code Rke 236Other Numerical Methods 240Case Study 6 244NOTATION AND SOME THEOREMS FROM THECALCULUS 251A.1 Notation 251A.2 Theorems 252ANSWERS TO SELECTED EXERCISES 255INDEX 266Previous Home NextCHAPTER 1ERRORS AND FLOATING POINTARITHMETICErrors in mathematical computation have several sources.
One is the modeling thatled to the mathematical problem, for example, assuming no wind resistance in studying projectile motion or ignoring finite limits of resources in population and economicgrowth models. Such errors are not the concern of this book, although it must be keptin mind that the numerical solution of a mathematical problem can be no more meaningful than the underlying model. Another source of error is the measurement of datafor the problem. A third source is a kind of mathematical error called discretizationor truncation error. It arises from mathematical approximations such as estimating anintegral by a sum or a tangent line by a secant line.
Still another source of error is theerror that arises from the finite number of digits available in the computers and calculators used for the computations. It is called roundoff error. In this book we studythe design and implementation of algorithms that aim to avoid severe roundoff errors,estimate truncation errors, and give some indication of the sensitivity of the problemto errors in the data. This chapter is devoted to some fundamental definitions and astudy of roundoff by means of simple but illuminating computations.1.1 BASIC CONCEPTSHow well a quantity is approximated is measured in two ways:absolute error = true value - approximate valuerelative error =true value - approximate value.true valueRelative error is not defined if the true value is zero.
In the arithmetic of computers,relative error is the more natural concept, but absolute error may be preferable whenstudying quantities that are close to zero.A mathematical problem with input (data) x and output (answer) y = F(x) is saidto be well-conditioned if “small” changes in x lead to “small” changes in y.
If the12CHAPTER 1ERRORS AND FLOATING POINT ARITHMETICchanges in y are “large,” the problem is said to be ill-conditioned. Whether a problemis well- or ill-conditioned can depend on how the changes are measured. A conceptrelated to conditioning is stability. It is concerned with the sensitivity of an algorithmfor solving a problem with respect to small changes in the data, as opposed to the sensitivity of the problem itself. Roundoff errors are almost inevitable, so the reliabilityof answers computed by an algorithm depends on whether small roundoff errors mightseriously affect the results. An algorithm is stable if “small” changes in the input leadto “small” changes in the output. If the changes in the output are “large,” the algorithmis unstable.To gain some insight about condition, let us consider a differentiable function F(x)and suppose that its argument, the input, is changed from x to x + εx.
This is a relativechange of ε in the input data. According to Theorem 4 of the appendix, the changeinduces an absolute change in the output value F(x) ofF(x) - F( x+εx)(x).The relative change isF (x) - F(x+ εx )F´(x)F(x)F(x).Example 1.1. If, for example, F(x) = ex, the absolute change in the value of theexponential function due to a change εx in its argument x is approximately −εxex, andthe relative change is about −εx.
When x is large, the conditioning of the evaluation ofthis function with respect to a small relative change in the argument depends stronglynon whether the change is measured in an absolute or relative sense.Example 1.2. If F(x) = cosx, then near x = π/2 the absolute error due to perturbing2. The relative error at x = π/2 is notx to x + εx is approximately −εx( - sin x)defined since cos(π/2) = 0. However, the accurate valuescos( 1.57079) = 0.63267949 × 10-5cos( 1.57078) = 1.63267949 × 10-5show how a very small change in the argument near π/2 can lead to a significant (63%)change in the value of the function.
In contrast, evaluation of the cosine function isnwell-conditioned near x = 0 (see Exercise 1.4).Example 1.3. A common application of integration by parts in calculus courses isthe evaluation of families of integrals by recursion. As an example, considerEn =dx for n = 1, 2,....From this definition it is easy to see thatE1>E2>-->En-1>En>-->0.1.1 BASIC CONCEPTS3To obtain a recursion, integrate by parts to getE n = x n e x-1nxn-1ex-1dx= 1 - nE n-1 .The first member of the family isE1= lex-1dx = e-1,and from it we can easily compute any En. If this is done in single precision on a PCor workstation (IEEE standard arithmetic), it is found thatElE2==0.3678790.264241E10El1E12===0.05067440.442581-4.31097(the exact En decrease!)(the exact En are positive!)11(the exact En are between 0 and 1!)E20 = -0.222605 × 10This is an example of an unstable algorithm.
A little analysis helps us understand whatis happening. Suppose we had started with Ê1 = E1 + δ and made no arithmetic errorswhen evaluating the recurrence. ThenÊ 2 = l - 2Ê1 = l - 2 Ê 1 - 2 δ = E2 - 2δÊ 3 = l - 3Ê2 = l - 3 E2 + 6δ = E3 + 3!δÊn= E n + n!δ.A small change in the first value E1 grows very rapidly in the later En.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
