A Numerical study of Newton interpolation with extremely high degrees
Michael Breuß; Friedemann Kemm; Oliver Vogel
Kybernetika (2018)
- Volume: 54, Issue: 2, page 279-288
- ISSN: 0023-5954
Access Full Article
top
Abstract
topHow to cite
topBreuß, Michael, Kemm, Friedemann, and Vogel, Oliver. "A Numerical study of Newton interpolation with extremely high degrees." Kybernetika 54.2 (2018): 279-288. <http://eudml.org/doc/294275>.
@article{Breuß2018,
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.},
author = {Breuß, Michael, Kemm, Friedemann, Vogel, Oliver},
journal = {Kybernetika},
keywords = {polynomial interpolation; Newton interpolation; interpolation nodes; Chebyshev nodes; Leja ordering; fast Leja points},
language = {eng},
number = {2},
pages = {279-288},
publisher = {Institute of Information Theory and Automation AS CR},
title = {A Numerical study of Newton interpolation with extremely high degrees},
url = {http://eudml.org/doc/294275},
volume = {54},
year = {2018},
}
TY - JOUR
AU - Breuß, Michael
AU - Kemm, Friedemann
AU - Vogel, Oliver
TI - A Numerical study of Newton interpolation with extremely high degrees
JO - Kybernetika
PY - 2018
PB - Institute of Information Theory and Automation AS CR
VL - 54
IS - 2
SP - 279
EP - 288
AB - 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.
LA - eng
KW - polynomial interpolation; Newton interpolation; interpolation nodes; Chebyshev nodes; Leja ordering; fast Leja points
UR - http://eudml.org/doc/294275
ER -
References
top- Atkinson, K. E., An Introduction to Numerical Analysis. Second edition., John Wiley and Sons, Inc., New York 1989. MR1007135
- Baglama, J., Calvetti, D., Reichel, L., 10.1007/bf01731924, BIT 36 (1996), 3, 400-421. MR1410088DOI10.1007/bf01731924
- Baglama, J., Calvetti, D., Reichel, L., Fast Leja points., ETNA, Electron. Trans. Numer. Anal. 7 (1998), 124-140. MR1667643
- Calvetti, D., Reichel, L., 10.1016/0377-0427(96)87162-7, J. Comput. Appl. Math. 71 (1996), 2, 267-286. MR1399896DOI10.1016/0377-0427(96)87162-7
- Calvetti, D., Reichel, L., 10.1023/a:1025555803588, Numer. Algorithms 33 (2003), 1-4, 153-161. MR2005559DOI10.1023/a:1025555803588
- Boor, C. de, A Practical Guide to Splines. Revised edition., Springer-Verlag, Inc., New York 2001. MR1900298
- Eisinberg, A., Fedele, G., 10.1016/j.amc.2005.06.014, Appl. Math. Comput. 174 (2006), 2, 1384-1397. MR2220623DOI10.1016/j.amc.2005.06.014
- Gautschi, W., Numerical Analysis. An Introduction., Birkhäuser, Boston 1997. MR1454125
- Higham, N. J., 10.1137/0611002, SIAM J. Matrix Anal. Appl. 11 (1990), 1, 23-41. MR1032215DOI10.1137/0611002
- Horner, W. G., 10.1098/rstl.1819.0023, In: Philosophical Transactions of the Royal Society of London, 1819, pp. 308-335. DOI10.1098/rstl.1819.0023
- Natanson, I. P., Konstruktive Funktionentheorie., Mathematische Lehrbücher und Monographien. I. Abteilung, Bd. VII., Akademie-Verlag. XIV, 515 S., 2. Abb. (1955), Berlin 1955. MR0640867
- Reichel, L., 10.1007/bf02017352, BIT 30 (1990), 2, 332-346. MR1039671DOI10.1007/bf02017352
- Runge, C., Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten., Schlömilch Z. 46 (1901), 224-243.
- Tal-Ezer, H., 10.1137/0912034, SIAM J. Sci. Stat. Comput. 12 (1991), 3, 648-667. MR1093210DOI10.1137/0912034
- Trefethen, L. N., Approximation Theory and Approximation Practice., PA: Society for Industrial and Applied Mathematics (SIAM), Philadelphia 2013. Zbl1264.41001MR3012510
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.