Efficient algorithms for polynomial interpolation and numerical differentiation

Author:
Fred T. Krogh

Journal:
Math. Comp. **24** (1970), 185-190

MSC:
Primary 65.20

DOI:
https://doi.org/10.1090/S0025-5718-1970-0258240-X

MathSciNet review:
0258240

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Algorithms based on Newton's interpolation formula are given for: simple polynomial interpolation, polynomial interpolation with derivatives supplied at some of the data points, interpolation with piecewise polynomials having a continuous first derivative, and numerical differentiation. These algorithms have all the advantages of the corresponding algorithms based on Aitken-Neville interpolation, and are more efficient.

**[1]**A. C. Aitken, "On interpolation by iteration of proportional parts, without the use of differences,"*Proc. Edinburgh Math. Soc.*, v. 3, 1932, pp. 56-76.**[2]**E. H. Neville, "Iterative interpolation," J.*Indian Math. Soc.*, v. 20, 1934, pp. 87-120.**[3]**Morris Gershinsky and David A. Levine,*Aitken-Hermite interpolation*, J. Assoc. Comput. Mach.**11**(1964), 352–356. MR**0165658**, https://doi.org/10.1145/321229.321237**[4]**A. C. R. Newbery,*Interpolation by algebraic and trigonometric polynomials*, Math. Comp.**20**(1966), 597–599. MR**0203905**, https://doi.org/10.1090/S0025-5718-1966-0203905-8**[5]**D. B. Hunter,*An iterative method of numerical differentiation*, Comput. J.**3**(1960/1961), 270–271. MR**0117883**, https://doi.org/10.1093/comjnl/3.4.270**[6]**J. N. Lyness and C. B. Moler,*Van der Monde systems and numerical differentiation*, Numer. Math.**8**(1966), 458–464. MR**0201071**, https://doi.org/10.1007/BF02166671**[7]**F. B. Hildebrand,*Introduction to numerical analysis*, McGraw-Hill Book Company, Inc., New York-Toronto-London, 1956. MR**0075670****[8]**J. F. Steffensen,*Interpolation*, Chelsea Publishing Co., New York, N. Y., 1950. 2d ed. MR**0036799****[9]**L. B. Winrich, "Note on a comparison of evaluation schemes for the interpolating polynomial,"*Comput. J.*, v. 12, 1969, pp. 154-155. (For comparison with the results given in Table 1 of this reference, our Algorithm II involves subtractions and divisions for setup, and additions, subtractions, and multiplications for each evaluation.)

Retrieve articles in *Mathematics of Computation*
with MSC:
65.20

Retrieve articles in all journals with MSC: 65.20

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1970-0258240-X

Keywords:
Interpolation,
numerical differentiation,
Newton's interpolation formula,
Aitken interpolation,
Neville interpolation,
Lagrange interpolation,
Hermite interpolation,
spline function

Article copyright:
© Copyright 1970
American Mathematical Society