A numerical study of Newton interpolation with extremely high degrees

DOI10.14736/KYB-2018-2-0279MaRDI QIDQ4568266zbMATH OpenOpenAlexFDO

Authors Michael Breuß, Friedemann Kemm, Oliver Vogel

Publication date 15 June 2018

Published in Kybernetika (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.08839

zbMATH Keywords

Chebyshev nodesfast Leja pointsinterpolation nodesLeja orderingNewton interpolationpolynomial interpolation

Mathematics Subject Classification ID

Interpolation in approximation theory (41A05) Approximation by polynomials (41A10) Numerical interpolation (65D05)

Abstract: In current textbooks the use of Chebyshev nodes with Newton interpolation is advocated as the most efficient numerical interpolation method in terms of approximation accuracy and computational effort. However, we show numerically that the approximation quality obtained by Newton interpolation with Fast Leja (FL) points is competitive to the use of Chebyshev nodes, even for extremely high degree interpolation. This is an experimental account of the analytic result that the limit distribution of FL points and Chebyshev nodes is the same when letting the number of points go to infinity. Since the FL construction is easy to perform and allows to add interpolation nodes on the fly in contrast to the use of Chebyshev nodes, our study suggests that Newton interpolation with FL points is currently the most efficient numerical technique for polynomial interpolation. Moreover, we give numerical evidence that any reasonable function can be approximated up to machine accuracy by Newton interpolation with FL points if desired, which shows the potential of this method.

Recommendations

• High Degree Polynomial Interpolation in Newton Form
• An Improved Convergence and Complexity Analysis for the Interpolatory Newton Method
• scientific article; zbMATH DE number 4077928
• scientific article; zbMATH DE number 4037012
• A new method of interpolation and numerical integration
• scientific article; zbMATH DE number 1150187
• A new approach to Newton-type polynomial interpolation with parameters
• A high-order Newton-like method
• A parallel method for fast and practical high-order Newton interpolation
• Numerical Differentiation by High Order Interpolation

Cites work

• A practical guide to splines.
• Adaptive Richardson iteration based on Leja points
• Approximation theory and approximation practice
• Fast Leja points
• High Degree Polynomial Interpolation in Newton Form
• scientific article; zbMATH DE number 45971 (Why is no real title available?)
• scientific article; zbMATH DE number 1061412 (Why is no real title available?)
• scientific article; zbMATH DE number 3111287 (Why is no real title available?)
• Iterative methods for the computation of a few eigenvalues of a large symmetric matrix
• Newton interpolation at Leja points
• On the evaluation of polynomial coefficients
• On the inversion of the Vandermonde matrix
• Stability Analysis of Algorithms for Solving Confluent Vandermonde-Like Systems

Cited in

(2)

• High Degree Polynomial Interpolation in Newton Form
• On the approximation properties of fast Leja points

Describes a project that uses

Uses Software

• Matlab

This page was built for publication: A numerical study of Newton interpolation with extremely high degrees

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