A new efficient algorithm for polynomial interpolation

DOI10.1007/S00607-006-0185-ZMaRDI QIDQ873149zbMATH OpenOpenAlexFDO

Authors Alicja Smoktunowicz, Iwona Wróbel, Przemysław Kosowski

Publication date 28 March 2007

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00607-006-0185-z

zbMATH Keywords

Aitken's algorithmcomparison of methodscondition numberdivided differenceserror analysisinterpolation polynomialLagrange formNewton formnumerical examplesnumerical stability

Mathematics Subject Classification ID

Numerical interpolation (65D05) Roundoff error (65G50)

Review text

The authors propose a new algorithm for the evaluation of the Lagrange interpolation polynomial and for computing its Newton coefficients. The algorithm does not require any special ordering of the interpolation points. The given error analysis proves that this algorithm is backward stable with respect to perturbations in the function values, for any choice of interpolating knots. Numerical examples show that the new algorithm is more accurate than Aitken's algorithm and the divided differences scheme.

Recommendations

• A Note on Polynomial Interpolation
• A comparison of algorithms for polynomial interpolation
• Publication:4945930
• A parallel method for fast and practical high-order Newton interpolation
• scientific article; zbMATH DE number 2217764

Cites work

• Backward stability of Clenshaw's algorithm
• High Degree Polynomial Interpolation in Newton Form
• Newton interpolation at Leja points
• On improving the accuracy of Horner's and Goertzel's algorithms
• On the evaluation of polynomial coefficients
• The numerical stability of evaluation schemes for polynomials based on the Lagrange interpolation form

Cited in

(20)

• A comparison of algorithms for polynomial interpolation
• Reliable determination of interpolating polynomials
• Iterative polynomial interpolation and data compression
• Recursive polynomial interpolation algorithm (RPIA)
• Efficient Ehrlich-Aberth iteration for finding intersections of interpolating polynomials and rational functions
• Advanced algorithm for interpolation with Wendland functions
• Backward and forward stability analysis of Neville's algorithm for interpolation and a pyramid algorithm for the computation of Lebesgue functions
• Rounding error analysis of divided differences schemes: Newton's divided differences; Neville's algorithm; Richardson extrapolation; Romberg quadrature; etc.
• scientific article; zbMATH DE number 5714299 (Why is no real title available?)
• Polynomial Interpolation: Lagrange versus Newton
• Pipelined algorithm for Newton's divided difference interpolation
• A Note on Polynomial Interpolation
• scientific article; zbMATH DE number 2087114 (Why is no real title available?)
• scientific article; zbMATH DE number 1424904 (Why is no real title available?)
• Fast and stable contour integration for high order divided differences via elliptic functions
• Constructing New Time Integrators Using Interpolating Polynomials
• Efficient Interpolation in the Guruswami–Sudan Algorithm
• scientific article; zbMATH DE number 5209793 (Why is no real title available?)
• scientific article; zbMATH DE number 2217764 (Why is no real title available?)
• scientific article; zbMATH DE number 7709336 (Why is no real title available?)

This page was built for publication: A new efficient algorithm for polynomial interpolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q873149)