108 Chapter 3.Interpolation and Extrapolation f(,y,z).Multidimensional interpolation is often accomplished by a sequence of one-dimensional interpolations.We discuss this in 83.6. CITED REFERENCES AND FURTHER READING: Abramowitz,M.,and Stegun,I.A.1964,Handbook of Mathematical Functions,Applied Mathe- matics Series,Volume 55 (Washington:National Bureau of Standards;reprinted 1968 by Dover Publications,New York),$25.2. Stoer,J.,and Bulirsch,R.1980,Introduction to Numerical Analysis(New York:Springer-Verlag). Chapter 2. 三 Acton,F.S.1970,Numerica/Methods That Work;1990,corrected edition (Washington:Mathe- matical Association of America),Chapter 3. Kahaner,D.,Moler,C.,and Nash,S.1989,Numerica/Methods and Software (Englewood Cliffs. 心复a NJ:Prentice Hall),Chapter 4. Johnson,L.W.,and Riess,R.D.1982,Numerical Analysis,2nd ed.(Reading,MA:Addison- ICAL Wesley).Chapter 5. Ralston,A.,and Rabinowitz,P.1978,A First Course in Numerical Analysis,2nd ed.(New York: McGraw-Hill),Chapter 3. RECIPES Isaacson,E.,and Keller,H.B.1966,Analysis of Numerica/Methods(New York:Wiley).Chapter 6. 9 Ea 9 3.1 Polynomial Interpolation and Extrapolation 9 Through any two points there is a unique line.Through any three points,a IENTIFIC unique quadratic.Et cetera.The interpolating polynomial of degree N-1 through the N points y1 f(1),y2 =f(2),...,yN f(N)is given explicitly by Lagrange's classical formula, (x-x2)(x-t3)(x-xN) -21--h+2c-- (22-1(2-3)(2-xN (x-x1)(x-x2)(x-xN-1) 2.5兰 Numerica 10.621 十…·十 (EN-1)(EN -)..(N -EN-1)UN (3.1.1) There are N terms,each a polynomial of degree N-1 and each constructed to be (outside zero at all of the i except one,at which it is constructed to be yi. It is not terribly wrong to implement the Lagrange formula straightforwardly, North but it is not terribly right either.The resulting algorithm gives no error estimate,and it is also somewhat awkward to program.A much better algorithm(for constructing the same,unique,interpolating polynomial)is Neville's algorithm,closely related to and sometimes confused with Aitken's algorithm,the latter now considered obsolete. Let P be the value at z of the unique polynomial of degree zero (i.e., a constant)passing through the point (x1,y1);so P=y1.Likewise define P2,P3,...,P.Now let P12 be the value at z of the unique polynomial of degree one passing through both (1,1)and (z2,y2).Likewise P23,P34,..., PN-1)N.Similarly,for higher-order polynomials,up to P123...N,which is the value of the unique interpolating polynomial through all N points,i.e.,the desired answer.108 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). f(x, y, z). Multidimensional interpolation is often accomplished by a sequence of one-dimensional interpolations. We discuss this in §3.6. CITED REFERENCES AND FURTHER READING: Abramowitz, M., and Stegun, I.A. 1964, Handbook of Mathematical Functions, Applied Mathe￾matics Series, Volume 55 (Washington: National Bureau of Standards; reprinted 1968 by Dover Publications, New York), §25.2. 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: Mathe￾matical 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: Addison￾Wesley), 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 Extrapolation Through any two points there is a unique line. Through any three points, a unique quadratic. Et cetera. The interpolating polynomial of degree N − 1 through the N points y1 = f(x1), y2 = f(x2),...,yN = f(xN ) is given explicitly by Lagrange’s classical formula, P(x) = (x − x2)(x − x3)...(x − xN ) (x1 − x2)(x1 − x3)...(x1 − xN ) y1 + (x − x1)(x − x3)...(x − xN ) (x2 − x1)(x2 − x3)...(x2 − xN ) y2 + ··· + (x − x1)(x − x2)...(x − xN−1) (xN − x1)(xN − x2)...(xN − xN−1) yN (3.1.1) There are N terms, each a polynomial of degree N − 1 and each constructed to be zero 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, and it is also somewhat awkward to program. A much better algorithm (for constructing the same, unique, interpolating polynomial) is Neville’s algorithm, closely related to and 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 define P2, P3,...,PN . Now let P12 be the value at x of the unique polynomial of degree 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 value of the unique interpolating polynomial through all N points, i.e., the desired answer