c3-0 (779470), страница 2
Текст из файла (страница 2)
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).(a)108Chapter 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:Stoer, J., and Bulirsch, R.
1980, Introduction to Numerical Analysis (New York: Springer-Verlag),Chapter 2.Acton, F.S. 1970, Numerical Methods That Work; 1990, corrected edition (Washington: Mathematical Association of America), Chapter 3.Kahaner, D., Moler, C., and Nash, S. 1989, Numerical Methods and Software (Englewood Cliffs,NJ: Prentice Hall), Chapter 4.Johnson, L.W., and Riess, R.D. 1982, Numerical Analysis, 2nd ed. (Reading, MA: AddisonWesley), Chapter 5.Ralston, A., and Rabinowitz, P.
1978, A First Course in Numerical Analysis, 2nd ed. (New York:McGraw-Hill), Chapter 3.Isaacson, E., and Keller, H.B. 1966, Analysis of Numerical Methods (New York: Wiley), Chapter 6.3.1 Polynomial Interpolation and ExtrapolationThrough any two points there is a unique line. Through any three points, aunique quadratic. Et cetera.
The interpolating polynomial of degree N − 1 throughthe N points y1 = f(x1 ), y2 = f(x2 ), . . . , yN = f(xN ) is given explicitly byLagrange’s classical formula,(x − x2 )(x − x3 )...(x − xN )(x − x1 )(x − x3 )...(x − xN )y1 +y2(x1 − x2 )(x1 − x3 )...(x1 − xN )(x2 − x1 )(x2 − x3 )...(x2 − xN )(x − x1 )(x − x2 )...(x − xN−1 )yN+···+(xN − x1 )(xN − x2 )...(xN − xN−1 )(3.1.1)There are N terms, each a polynomial of degree N − 1 and each constructed to bezero at all of the xi except one, at which it is constructed to be yi .It is not terribly wrong to implement the Lagrange formula straightforwardly,but it is not terribly right either.
The resulting algorithm gives no error estimate, andit is also somewhat awkward to program. A much better algorithm (for constructingthe same, unique, interpolating polynomial) is Neville’s algorithm, closely related toand sometimes confused with Aitken’s algorithm, the latter now considered obsolete.Let P1 be the value at x of the unique polynomial of degree zero (i.e.,a constant) passing through the point (x1 , y1 ); so P1 = y1 . Likewise defineP2 , P3 , .
. . , PN . Now let P12 be the value at x of the unique polynomial ofdegree one passing through both (x1 , y1 ) and (x2 , y2 ). Likewise P23 , P34, . . . ,P(N−1)N . Similarly, for higher-order polynomials, up to P123...N , which is the valueof the unique interpolating polynomial through all N points, i.e., the desired answer.P (x) =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).Abramowitz, M., and Stegun, I.A. 1964, Handbook of Mathematical Functions, Applied Mathematics Series, Volume 55 (Washington: National Bureau of Standards; reprinted 1968 byDover Publications, New York), §25.2..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
