Press, Teukolsly, Vetterling, Flannery - Numerical Recipes in C (523184), страница 30
Текст из файла (страница 30)
Since these can be done by an N log2 7algorithm, so can the matrix inversion!This is fun, but let’s look at practicalities: If you estimate how large N has to bebefore the difference between exponent 3 and exponent log2 7 = 2.807 is substantialenough to outweigh the bookkeeping overhead, arising from the complicated natureof the recursive Strassen algorithm, you will find that LU decomposition is in noimmediate danger of becoming obsolete.If, on the other hand, you like this kind of fun, then try these: (1) Can youmultiply the complex numbers (a+ib) and (c+id) in only three real multiplications?[Answer: see §5.4.] (2) Can you evaluate a general fourth-degree polynomial inx for many different values of x with only three multiplications per evaluation?[Answer: see §5.3.]CITED REFERENCES AND FURTHER READING:Strassen, V. 1969, Numerische Mathematik, vol.
13, pp. 354–356. [1]Kronsjö, L. 1987, Algorithms: Their Complexity and Efficiency, 2nd ed. (New York: Wiley).Winograd, S. 1971, Linear Algebra and Its Applications, vol. 4, pp. 381–388.Pan, V. Ya. 1980, SIAM Journal on Computing, vol. 9, pp. 321–342.Pan, V. 1984, How to Multiply Matrices Faster, Lecture Notes in Computer Science, vol. 179(New York: Springer-Verlag)Pan, V. 1984, SIAM Review, vol. 26, pp. 393–415. [More recent results that show that anexponent of 2.496 can be achieved — theoretically!]Chapter 3.
Interpolation andExtrapolation3.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)106Chapter 3.Interpolation and Extrapolationwhich 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(a)(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 function108Chapter 3.Interpolation and Extrapolationf(x, y, z). Multidimensional interpolation is often accomplished by a sequence ofone-dimensional interpolations. We discuss this in §3.6.CITED REFERENCES AND FURTHER READING:Abramowitz, M., and Stegun, I.A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
