Efficient algorithms for polynomial interpolation and numerical differentiation
Author:
Fred T. Krogh
Journal:
Math. Comp. 24 (1970), 185190
MSC:
Primary 65.20
MathSciNet review:
0258240
Fulltext PDF Free Access
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 AitkenNeville 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. 5676.
 [2]
E. H. Neville, "Iterative interpolation," J. Indian Math. Soc., v. 20, 1934, pp. 87120.
 [3]
Morris
Gershinsky and David
A. Levine, AitkenHermite interpolation, J. Assoc. Comput.
Mach. 11 (1964), 352–356. MR 0165658
(29 #2938)
 [4]
A.
C. R. Newbery, Interpolation by algebraic and
trigonometric polynomials, Math. Comp. 20 (1966), 597–599.
MR
0203905 (34 #3752), http://dx.doi.org/10.1090/S00255718196602039058
 [5]
D.
B. Hunter, An iterative method of numerical differentiation,
Comput. J. 3 (1960/1961), 270–271. MR 0117883
(22 #8657)
 [6]
J.
N. Lyness and C.
B. Moler, Van der Monde systems and numerical differentiation,
Numer. Math. 8 (1966), 458–464. MR 0201071
(34 #956)
 [7]
F.
B. Hildebrand, Introduction to numerical analysis, McGrawHill
Book Company, Inc., New YorkTorontoLondon, 1956. MR 0075670
(17,788d)
 [8]
J.
F. Steffensen, Interpolation, Chelsea Publishing Co., New
York, N. Y., 1950. 2d ed. MR 0036799
(12,164d)
 [9]
L. B. Winrich, "Note on a comparison of evaluation schemes for the interpolating polynomial," Comput. J., v. 12, 1969, pp. 154155. (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.)
 [1]
 A. C. Aitken, "On interpolation by iteration of proportional parts, without the use of differences," Proc. Edinburgh Math. Soc., v. 3, 1932, pp. 5676.
 [2]
 E. H. Neville, "Iterative interpolation," J. Indian Math. Soc., v. 20, 1934, pp. 87120.
 [3]
 M. Gershinsky & D. A. Levine, "AitkenHermite interpolation," J. Assoc. Comput. Mach., v. 11, 1964, pp. 352356. MR 29 #2938. MR 0165658 (29:2938)
 [4]
 A. C. R. Newbery, "Interpolation by algebraic and trigonometric polynomials," Math. Comp., v. 20, 1966, pp. 597599. MR 34 #3752. MR 0203905 (34:3752)
 [5]
 D. B. Hunter, "An iterative method of numerical differentiation," Comput. J., v. 3, 1960/61, pp. 270271. MR 22 #8657. MR 0117883 (22:8657)
 [6]
 J. N. Lyness & C. B. Moler, "Van Der Monde systems and numerical differentiation," Numer. Math., v. 8, 1966, pp. 458464. MR 0201071 (34:956)
 [7]
 F. B. Hildebrand, Introduction to Numerical Analysis, McGrawHill, New York, 1956. MR 17, 788. MR 0075670 (17:788d)
 [8]
 J. F. Steffensen, Interpolation, Chelsea, New York, 1950. MR 12, 164. MR 0036799 (12:164d)
 [9]
 L. B. Winrich, "Note on a comparison of evaluation schemes for the interpolating polynomial," Comput. J., v. 12, 1969, pp. 154155. (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.)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65.20
Retrieve articles in all journals
with MSC:
65.20
Additional Information
DOI:
http://dx.doi.org/10.1090/S0025571819700258240X
PII:
S 00255718(1970)0258240X
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
