f4-0

Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).Chapter 4. Integration of Functions 4.0 Introduction Numericalintegration,whichis alsocalled quadrature ,has a historyextending back to the invention of calculus and before. The fact that integrals of elementary functions could not, in general, be computed analytically, while derivatives could be, servedto givethe field a certainpanache,and to set it a cut abovethe arithmeticdrudgeryof numericalanalysis duringthe whole of the 18th and 19thcenturies. Withtheinventionofautomaticcomputing,quadraturebecamejustonenumer- ical task amongmany,and not a very interestingone at that. Automatic computing, eventhemostprimitivesortinvolvingdeskcalculatorsandroomsfullof“computers” (that were, until the 1950s, people rather than machines), opened to feasibility themuch richer field of numerical integration of differential equations. Quadrature is merely the simplest special case: The evaluation of the integral I=/integraldisplay b af(x)dx (4.0.1 ) is precisely equivalentto solvingforthe value I≡y(b)the differentialequation dy dx=f(x)( 4.0.2 ) with the boundary condition y(a)=0 ( 4.0.3 ) Chapter 16 of this book deals with the numerical integration of differential equations. In that chapter, much emphasis is given to the concept of “variable” or“adaptive” choices of stepsize. We will not, therefore, develop that material here. If the function that you propose to integrate is sharply concentrated in one or more peaks, or if its shape is not readily characterized by a single length-scale, then itis likely that you should cast the problem in the form of (4.0.2)–(4.0.3) and use the methods of Chapter 16. Thequadraturemethodsinthischapterarebased,inonewayoranother,onthe obvious device of adding up the value of the integrand at a sequence of abscissas within the range of integration. The game is to obtain the integral as accuratelyas possible with the smallest number of function evaluations of the integrand. Just as in the case of interpolation (Chapter 3), one has the freedom to choose methods 123 124 Chapter4. IntegrationofFunctionsSample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).of various orders, with higher order sometimes, but not always, giving higher accuracy. “Rombergintegration,”which is discussed in §4.3,is a generalformalism for making use of integration methods of a variety of different orders, and we recommend it highly. Apart from the methods of this chapter and of Chapter 16, there are yet other methods for obtaining integrals. One important class is based on function approximation. We discuss explicitly the integration of functions by Chebyshev approximation (“Clenshaw-Curtis” quadrature) in §5.9. Although not explicitly discussedhere,yououghttobeable tofigureouthowto do cubicsplinequadrature using the output of the routine splinein§3.3. (Hint: Integrate equation 3.3.3 over xanalytically. See [1].) Some integrals related to Fourier transforms can be calculated using the fast Fourier transform (FFT) algorithm. This is discussed in §13.9. Multidimensionalintegrals are anotherwhole multidimensionalbag of worms. Section 4.6 is an introductorydiscussion in this chapter; the importanttechnique of Monte-Carlo integration is treated in Chapter 7. CITED REFERENCES AND FURTHER READING: Carnahan, B., Luther, H.A., and Wilkes, J.O. 1969, Applied Numerical Methods (New York: Wiley), Chapter 2. Isaacson,E.,andKeller,H.B.1966, AnalysisofNumericalMethods (NewYork:Wiley),Chapter7. Acton, F.S. 1970, Numerical Methods That Work ; 1990, corrected edition (Washington: Mathe- matical Association of America), Chapter 4. Stoer,J.,andBulirsch,R.1980, IntroductiontoNumericalAnalysis (NewYork:Springer-Verlag), Chapter 3. Ralston, A., and Rabinowitz, P. 1978, A First Course in Numerical Analysis , 2nd ed. (New York: McGraw-Hill), Chapter 4. Dahlquist, G., and Bjorck, A. 1974, Numerical Methods (Englewood Cliffs, NJ: Prentice-Hall), §7.4. Kahaner,D.,Moler,C.,andNash,S.1989, NumericalMethods andSoftware (EnglewoodCliffs, NJ: Prentice Hall), Chapter 5. Forsythe, G.E., Malcolm, M.A., and Moler, C.B. 1977, Computer Methods for Mathematical Computations (Englewood Cliffs, NJ: Prentice-Hall), §5.2, p. 89. [1] Davis, P., and Rabinowitz, P. 1984, Methods of Numerical Integration , 2nd ed. (Orlando, FL: Academic Press). 4.1 Classical Formulas for Equally Spaced Abscissas Where wouldany bookon numericalanalysis be withoutMr. Simpsonand his “rule”? The classical formulas for integrating a function whose value is known at equally spaced steps have a certain elegance about them, and they are redolent withhistoricalassociation. Throughthem,themodernnumericalanalystcommuneswith the spirits of his or her predecessors back across the centuries, as far as the time of Newton, if not farther. Alas, times dochange; with the exception of two of the most modest formulas (“extended trapezoidal rule,” equation 4.1.11, and “extended