c3-0 (779470)
Текст из файла
3.0 IntroductionWe sometimes know the value of a function f(x) at a set of points x1, x2, . . . , xN(say, with x1 < . . . < xN ), but we don’t have an analytic expression for f(x) that letsus calculate its value at an arbitrary point. For example, the f(xi )’s might result fromsome physical measurement or from long numerical calculation that cannot be castinto a simple functional form. Often the xi ’s are equally spaced, but not necessarily.The task now is to estimate f(x) for arbitrary x by, in some sense, drawing asmooth curve through (and perhaps beyond) the xi .
If the desired x is in between thelargest and smallest of the xi ’s, the problem is called interpolation; if x is outsidethat range, it is called extrapolation, which is considerably more hazardous (as manyformer stock-market analysts can attest).Interpolation and extrapolation schemes must model the function, between orbeyond the known points, by some plausible functional form. The form shouldbe sufficiently general so as to be able to approximate large classes of functionswhich might arise in practice. By far most common among the functional formsused are polynomials (§3.1).
Rational functions (quotients of polynomials) also turnout to be extremely useful (§3.2). Trigonometric functions, sines and cosines, giverise to trigonometric interpolation and related Fourier methods, which we defer toChapters 12 and 13.There is an extensive mathematical literature devoted to theorems about whatsort of functions can be well approximated by which interpolating functions. Thesetheorems are, alas, almost completely useless in day-to-day work: If we knowenough about our function to apply a theorem of any power, we are usually not inthe pitiful state of having to interpolate on a table of its values!Interpolation is related to, but distinct from, function approximation.
That taskconsists of finding an approximate (but easily computable) function to use in placeof a more complicated one. In the case of interpolation, you are given the function fat points not of your own choosing. For the case of function approximation, you areallowed to compute the function f at any desired points for the purpose of developingyour approximation. We deal with function approximation in Chapter 5.One can easily find pathological functions that make a mockery of any interpolation scheme. Consider, for example, the functionf(x) = 3x2 +1ln (π − x)2 + 14π105(3.0.1)Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-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 copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).Chapter 3.
Interpolation andExtrapolation106Chapter 3.Interpolation and ExtrapolationSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-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 copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (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 basedon the values x = 3.13, 3.14, 3.15, 3.16, will assuredly get a very wrong answer forthe value x = 3.1416, even though a graph plotting those five points looks reallyquite smooth! (Try it on your calculator.)Because pathologies can lurk anywhere, it is highly desirable that an interpolation and extrapolation routine should provide an estimate of its own error. Suchan 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 betweentwo tabulated points.
Interpolation always presumes some degree of smoothnessfor the function interpolated, but within this framework of presumption, deviationsfrom smoothness can be detected.Conceptually, the interpolation process has two stages: (1) Fit an interpolatingfunction to the data points provided. (2) Evaluate that interpolating function atthe target point x.However, this two-stage method is generally not the best way to proceed inpractice.
Typically it is computationally less efficient, and more susceptible toroundoff error, than methods which construct a functional estimate f(x) directlyfrom the N tabulated values every time one is desired. Most practical schemes startat 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 takesO(N 2 ) operations. If everything is well behaved, the last correction will be thesmallest, 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 thecoefficients of the interpolating polynomial are of interest, even though their usein evaluating the interpolating function should be frowned on.
We deal with thiseventuality in §3.5.Local interpolation, using a finite number of “nearest-neighbor” points, givesinterpolated values f(x) that do not, in general, have continuous first or higherderivatives. That happens because, as x crosses the tabulated values xi , theinterpolation scheme switches which tabulated points are the “local” ones. (If sucha switch is allowed to occur anywhere else, then there will be a discontinuity in theinterpolated function itself at that point. Bad idea!)In situations where continuity of derivatives is a concern, one must usethe “stiffer” interpolation provided by a so-called spline function. A spline isa polynomial between each pair of table points, but one whose coefficients aredetermined “slightly” nonlocally.
The nonlocality is designed to guarantee globalsmoothness 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 continuousthrough the second derivative. Splines tend to be stabler than polynomials, with lesspossibility of wild oscillation between the tabulated points.The number of points (minus one) used in an interpolation scheme is calledthe order of the interpolation. Increasing the order does not necessarily increasethe accuracy, especially in polynomial interpolation.
If the added points are distantfrom the point of interest x, the resulting higher-order polynomial, with its additionalconstrained points, tends to oscillate wildly between the tabulated values. Thisoscillation may have no relation at all to the behavior of the “true” function (seeFigure 3.0.1). Of course, adding points close to the desired point usually does help,3.0 Introduction107(b)Figure 3.0.1.(a) A smooth function (solid line) is more accurately interpolated by a high-orderpolynomial (shown schematically as dotted line) than by a low-order polynomial (shown as a piecewiselinear dashed line). (b) A function with sharp corners or rapidly changing higher derivatives is lessaccurately approximated by a high-order polynomial (dotted line), which is too “stiff,” than by a low-orderpolynomial (dashed lines).
Even some smooth functions, such as exponentials or rational functions, canbe badly approximated by high-order polynomials.but a finer mesh implies a larger table of values, not always available.Unless there is solid evidence that the interpolating function is close in form tothe true function f, it is a good idea to be cautious about high-order interpolation.We enthusiastically endorse interpolations with 3 or 4 points, we are perhaps tolerantof 5 or 6; but we rarely go higher than that unless there is quite rigorous monitoringof estimated errors.When your table of values contains many more points than the desirable orderof interpolation, you must begin each interpolation with a search for the right “local”place in the table.
While not strictly a part of the subject of interpolation, this task isimportant enough (and often enough botched) that we devote §3.4 to its discussion.The routines given for interpolation are also routines for extrapolation. Animportant application, in Chapter 16, is their use in the integration of ordinarydifferential equations. There, considerable care is taken with the monitoring oferrors. Otherwise, the dangers of extrapolation cannot be overemphasized: Aninterpolating function, which is perforce an extrapolating function, will typically goberserk when the argument x is outside the range of tabulated values by more thanthe typical spacing of tabulated points.Interpolation can be done in more than one dimension, e.g., for a functionSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
