Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
polynomial interpolation; Newton interpolation; interpolation nodes; Chebyshev nodes; Leja ordering; fast Leja points
polynomial interpolation; Newton interpolation; interpolation nodes; Chebyshev nodes; Leja ordering; fast Leja points
Summary:
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.
References:
[1] Atkinson, K. E.: An Introduction to Numerical Analysis. Second edition. John Wiley and Sons, Inc., New York 1989. MR 1007135
[2] Baglama, J., Calvetti, D., Reichel, L.: Iterative methods for the computation of a few eigenvalues of a large symmetric matrix. BIT 36 (1996), 3, 400-421. DOI 10.1007/bf01731924 | MR 1410088
[3] Baglama, J., Calvetti, D., Reichel, L.: Fast Leja points. ETNA, Electron. Trans. Numer. Anal. 7 (1998), 124-140. MR 1667643
[4] Calvetti, D., Reichel, L.: Adaptive Richardson iteration based on Leja points. J. Comput. Appl. Math. 71 (1996), 2, 267-286. DOI 10.1016/0377-0427(96)87162-7 | MR 1399896
[5] Calvetti, D., Reichel, L.: On the evaluation of polynomial coefficients. Numer. Algorithms 33 (2003), 1-4, 153-161. DOI 10.1023/a:1025555803588 | MR 2005559
[6] Boor, C. de: A Practical Guide to Splines. Revised edition. Springer-Verlag, Inc., New York 2001. MR 1900298
[7] Eisinberg, A., Fedele, G.: On the inversion of the Vandermonde matrix. Appl. Math. Comput. 174 (2006), 2, 1384-1397. DOI 10.1016/j.amc.2005.06.014 | MR 2220623
[8] Gautschi, W.: Numerical Analysis. An Introduction. Birkhäuser, Boston 1997. MR 1454125
[9] Higham, N. J.: Stability analysis of algorithms for solving confluent Vandermonde-like systems. SIAM J. Matrix Anal. Appl. 11 (1990), 1, 23-41. DOI 10.1137/0611002 | MR 1032215
[10] Horner, W. G.: A new method of solving numerical equations of all orders, by continuous approximation. In: Philosophical Transactions of the Royal Society of London, 1819, pp. 308-335. DOI 10.1098/rstl.1819.0023
[11] Natanson, I. P.: Konstruktive Funktionentheorie. Mathematische Lehrbücher und Monographien. I. Abteilung, Bd. VII., Akademie-Verlag. XIV, 515 S., 2. Abb. (1955), Berlin 1955. MR 0640867
[12] Reichel, L.: Newton interpolation at Leja points. BIT 30 (1990), 2, 332-346. DOI 10.1007/bf02017352 | MR 1039671
[13] Runge, C.: Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten. Schlömilch Z. 46 (1901), 224-243.
[14] Tal-Ezer, H.: High degree polynomial interpolation in Newton form. SIAM J. Sci. Stat. Comput. 12 (1991), 3, 648-667. DOI 10.1137/0912034 | MR 1093210
[15] Trefethen, L. N.: Approximation Theory and Approximation Practice. PA: Society for Industrial and Applied Mathematics (SIAM), Philadelphia 2013. MR 3012510 | Zbl 1264.41001
Search
Partner of
