Numerical continued fraction interpolation

Oliver Salazar Celis

doi:10.3842/umzh.v74i4.7349

Oliver Salazar Celis Department of Mathematics and Computer Science, University of Antwerp, Belgium and ING Belgium, Brussels

DOI: https://doi.org/10.3842/umzh.v74i4.7349

Keywords: Thiele continued fractions, univariate rational interpolation, best approximations

Abstract

UDC 517.524

We show that highly accurate approximations can often be obtained by constructing Thiele interpolating continued fractions by a Greedy selection of the interpolation points together with an early termination condition. The obtained results are comparable with the outcome of state-of-the-art rational interpolation techniques based on the barycentric form.

References

B. Beckermann, J. Bisch, R. Luce, On the rational approximation of Markov functions, with applications to the computation of Markov functions of Toeplitz matrices, Numer. Algorithms, 91, 109–144 (2022). DOI: https://doi.org/10.1007/s11075-022-01256-4

A. A. Cuyt, L. Jacobsen, B. M. Verdonk, Instability and modification of thiele interpolating continued fractions, Appl. Numer. Math., 4, 253–262 (1988). DOI: https://doi.org/10.1016/0168-9274(83)90005-3

S.-I. Filip, Y. Nakatsukasa, L. N. Trefethen, B. Beckermann, Rational minimax approximation via adaptive barycentric representations, SIAM J. Sci. Comput., 40, A2427–A2455 (2018). DOI: https://doi.org/10.1137/17M1132409

P. R. Graves-Morris, Practical, reliable, rational interpolation, IMA J. Appl. Math., 25, 267–286 (1980). DOI: https://doi.org/10.1093/imamat/25.3.267

C. Hofreither, An algorithm for best rational approximation based on barycentric rational interpolation, Numer. Algorithms, 88, 365–388 (2021). DOI: https://doi.org/10.1007/s11075-020-01042-0

G. Ion Victor, A. C. Athanasios, Rational approximation of the absolute value function from measurements: a numerical study of recent methods; arXiv (2020).

W. B. Jones, W. J. Thron, Numerical stability in evaluating continued fractions, Math. Comput., 28, 795–810 (1974). DOI: https://doi.org/10.1090/S0025-5718-1974-0373265-5

L. M. Milne-Thomson, The calculus of finite differences, Macmillan and Co. Ltd., London (1933).

Y. Nakatsukasa, O. Sète, L. Trefethen, The AAA algorithm for rational approximation, SIAM J. Sci. Comput., 40, 1494–1522 (2018). DOI: https://doi.org/10.1137/16M1106122

Y. Nakatsukasa, L. N. Trefethen, An algorithm for real and complex rational minimax approximation, SIAM J. Sci. Comput., 42, A3157–A3179 (2020). DOI: https://doi.org/10.1137/19M1281897

D. J. Newman, Rational approximation to $|x|$, Michigan Math. J., 11, 11–14 (1964). DOI: https://doi.org/10.1307/mmj/1028999029

R. Pachón, Algorithms for polynomial and rational approximation, PhD Thesis, Univ. Oxford (2010).

R. Core Team, R: a language and environment for statistical computing, R Foundation for Statistical Computing, Vienna (2020); https://www.R-project.org/.

S. Robert Forsyth, A treatise on the theory of determinants: and their applications in analysis and geometry, Cambridge Univ. Press, Cambridge (1880).

R. Varga, A. Ruttan, A. Karpenter, Numerical results on best numerical approximation of $|x|$ on $[-1, +1]$, Math. USSR-Sb., 74, 271–290 (1993). DOI: https://doi.org/10.1070/SM1993v074n02ABEH003347

J. Wallis, Arithmetica infinitorum (1655).

J. L. Walsh, On approximation to an analytic function by rational functions of best approximation, Math. Z., 38, 163–176 (1934). DOI: https://doi.org/10.1007/BF01170632

H. Werner, A reliable method for rational interpolation, Padé Approximation and Its Applications, L. Wuytack (ed.), Springer, Berlin, Heidelberg, (1979), p. 257–277. DOI: https://doi.org/10.1007/BFb0085585

T. F. Xie, S. P. Zhou, The asymptotic property of approximation to $|x|$ by Newman's rational operators, Acta Math. Hungar., 103, 313–319 (2004). DOI: https://doi.org/10.1023/B:AMHU.0000028831.89374.d3