106 Chapter 3.Interpolation and Extrapolation which is well-behaved everywhere except at x=m,very mildly singular at =m. and otherwise takes on all positive and negative values.Any interpolation based on the values x 3.13,3.14,3.15,3.16,will assuredly get a very wrong answer for the value z =3.1416,even though a graph plotting those five points looks really quite smooth!(Try it on your calculator.) Because pathologies can lurk anywhere,it is highly desirable that an interpo- lation and extrapolation routine should provide an estimate of its own error.Such an error estimate can never be foolproof,of course.We could have a function that, for reasons known only to its maker.takes off wildly and unexpectedly between two tabulated points.Interpolation always presumes some degree of smoothness for the function interpolated,but within this framework of presumption,deviations from smoothness can be detected. Conceptually,the interpolation process has two stages:(1)Fit an interpolating function to the data points provided.(2)Evaluate that interpolating function at the target point z. However,this two-stage method is generally not the best way to proceed in practice.Typically it is computationally less efficient,and more susceptible to roundoff error,than methods which construct a functional estimate f(z)directly from the N tabulated values every time one is desired.Most practical schemes start 9 at a nearby point f(i),then add a sequence of(hopefully)decreasing corrections, as information from other f(i)'s is incorporated.The procedure typically takes O(N2)operations.If everything is well behaved,the last correction will be the smallest,and it can be used as an informal (though not rigorous)bound on the error. 9 In the case of polynomial interpolation,it sometimes does happen that the A之白 coefficients of the interpolating polynomial are of interest,even though their use in evaluating the interpolating function should be frowned on.We deal with this eventuality in $3.5. 6 Local interpolation,using a finite number of"nearest-neighbor"points,gives interpolated values f()that do not,in general,have continuous first or higher derivatives.That happens because,as z crosses the tabulated values zi,the interpolation scheme switches which tabulated points are the "local"ones.(If such a switch is allowed to occur anywhere else,then there will be a discontinuity in the interpolated function itself at that point.Bad idea!) Numeric 10621 In situations where continuity of derivatives is a concern,one must use the "stiffer"interpolation provided by a so-called spline function.A spline is a polynomial between each pair of table points,but one whose coefficients are 、三GN determined"slightly"nonlocally.The nonlocality is designed to guarantee global smoothness in the interpolated function up to some order of derivative.Cubic splines (83.3)are the most popular.They produce an interpolated function that is continuous North through the second derivative.Splines tend to be stabler than polynomials,with less possibility of wild oscillation between the tabulated points. The number of points(minus one)used in an interpolation scheme is called the order of the interpolation.Increasing the order does not necessarily increase the accuracy,especially in polynomial interpolation.If the added points are distant from the point of interest z,the resulting higher-order polynomial,with its additional constrained points,tends to oscillate wildly between the tabulated values.This oscillation may have no relation at all to the behavior of the "true"function (see Figure 3.0.1).Of course,adding points close to the desired point usually does help,106 Chapter 3. Interpolation and Extrapolation Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). which is well-behaved everywhere except at x = π, very mildly singular at x = π, and otherwise takes on all positive and negative values. Any interpolation based on the values x = 3.13, 3.14, 3.15, 3.16, will assuredly get a very wrong answer for the value x = 3.1416, even though a graph plotting those five points looks really quite smooth! (Try it on your calculator.) Because pathologies can lurk anywhere, it is highly desirable that an interpo￾lation and extrapolation routine should provide an estimate of its own error. Such an error estimate can never be foolproof, of course. We could have a function that, for reasons known only to its maker, takes off wildly and unexpectedly between two tabulated points. Interpolation always presumes some degree of smoothness for the function interpolated, but within this framework of presumption, deviations from smoothness can be detected. Conceptually, the interpolation process has two stages: (1) Fit an interpolating function to the data points provided. (2) Evaluate that interpolating function at the target point x. However, this two-stage method is generally not the best way to proceed in practice. Typically it is computationally less efficient, and more susceptible to roundoff error, than methods which construct a functional estimate f(x) directly from the N tabulated values every time one is desired. Most practical schemes start at a nearby point f(xi), then add a sequence of (hopefully) decreasing corrections, as information from other f(xi)’s is incorporated. The procedure typically takes O(N2) operations. If everything is well behaved, the last correction will be the smallest, and it can be used as an informal (though not rigorous) bound on the error. In the case of polynomial interpolation, it sometimes does happen that the coefficients of the interpolating polynomial are of interest, even though their use in evaluating the interpolating function should be frowned on. We deal with this eventuality in §3.5. Local interpolation, using a finite number of “nearest-neighbor” points, gives interpolated values f(x) that do not, in general, have continuous first or higher derivatives. That happens because, as x crosses the tabulated values xi, the interpolation scheme switches which tabulated points are the “local” ones. (If such a switch is allowed to occur anywhere else, then there will be a discontinuity in the interpolated function itself at that point. Bad idea!) In situations where continuity of derivatives is a concern, one must use the “stiffer” interpolation provided by a so-called spline function. A spline is a polynomial between each pair of table points, but one whose coefficients are determined “slightly” nonlocally. The nonlocality is designed to guarantee global smoothness in the interpolated function up to some order of derivative. Cubic splines (§3.3) are the most popular. They produce an interpolated function that is continuous through the second derivative. Splines tend to be stabler than polynomials, with less possibility of wild oscillation between the tabulated points. The number of points (minus one) used in an interpolation scheme is called the order of the interpolation. Increasing the order does not necessarily increase the accuracy, especially in polynomial interpolation. If the added points are distant from the point of interest x, the resulting higher-order polynomial, with its additional constrained points, tends to oscillate wildly between the tabulated values. This oscillation may have no relation at all to the behavior of the “true” function (see Figure 3.0.1). Of course, adding points close to the desired point usually does help