Top

Calcolo

Published in:

01-11-2023

Fast barycentric rational interpolations for complex functions with some singularities

Authors: Shunfeng Yang, Shuhuang Xiang

Published in: Calcolo | Issue 4/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Based on Cauchy’s integral formula and conformal maps, this paper presents a new method for constructing barycentric rational interpolation formulae for complex functions, which may contain singularities such as poles, branch cuts, or essential singularities. The resulting interpolations are pole-free, exponentially convergent, and numerically stable, requiring only \({\mathcal {O}}(N)\) operations. Inspired by the logarithm equilibrium potential, we introduce a Möbius transform to concentrate nodes to the vicinity of singularity to get a spectacular improvement on approximation quality. A thorough convergence analysis is provided, alongside numerous numerical examples that illustrate the theoretical results and demonstrate the accuracy and efficiency of the methodology. Meanwhile, the paper also discusses some applications of the method including the numerical solutions of boundary value problems and the zero locations of holomorphic functions.

previous article A linear algebra perspective on the random multi-block ADMM: the QP case

next article Elliptic polytopes and invariant norms of linear operators

Oppenheim, A.V., Willsky, A.S., Nawab, S.H.: Signals and Systems, 2nd edn. Pearson Prentice-Hall, USA (1997)

Oppenheim, A.V., Schafer, R.W.: Discrete-Time Signal Processing, 3rd edn. Pearson Prentice-Hall, USA (2009)MATH

Sierra, J.M.G.: Digital Signal Processing with Matlab Examples, Volume (1–3). Springer Science+Business Media, Singapore (2017)CrossRef

Gaier, D.: Vorlesungen über Approximation im Komplexen. Birkhäuser Basel, (1980)

Webb, M., Trefethen, L. N.: Computing Complex Singularities of Differential Equations with Chebfun. Electronic Transactions on Numerical Analysis (2011)

Guide, M.E., Miedlar, A., Saad, Y.: A rational approximation method for solving acoustic nonlinear eigenvalue problems. Eng. Anal. Bound. Element 111, 44–54 (2020). https://doi.org/10.1016/j.enganabound.2019.10.006MathSciNetCrossRefMATH

Gopal, A., Trefethen, L.N.: Solving Laplace problems with corner singularities via rational functions. IAM J. Numer. Anal. 57(5), 2074–2094 (2019). https://doi.org/10.1137/19M125947XMathSciNetCrossRefMATH

Taylor, W.J.: Method of Lagrangian curvilinear interpolation. J. Res. Natl. Bureau Standards 35, 151–155 (1945). https://doi.org/10.6028/JRES.035.006MathSciNetCrossRefMATH

Dupuy, M.: Le calcul numerique des fonctions par linterpolation barycentrique. Comptes Rendus Hebdomadaires Des Seances De L Acad 226, 158–159 (1948)MathSciNetMATH

10.

Jacobi, C. G. J.: Disquisitiones analyticae de fractionibus simplicibus. Dissertation, Berlin (1825)

11.

Gautschi, W.: Numerical Analysis, 2nd edition. Birkhäuser (2012)

12.

Berrut, J.-P., Trefethen, L.N.: Barycentric lagrange interpolation. SIAM Rev. 46(3), 501–517 (2004). https://doi.org/10.1137/s0036144502417715MathSciNetCrossRefMATH

13.

Trefethen, L.N.: Approximation Theory and Approximation Practice. Extended edition, SIAM Philadelphia (2020)MATH

14.

Wang, H., Xiang, S.: On the convergence rates of Legendre approximation. Math. Comput. 278(81), 861–877 (2012). https://doi.org/10.2307/23267976MathSciNetCrossRefMATH

15.

Salzer, H.E.: Lagrangian interpolation at the chebyshev points \(x_n=\cos {v\pi /n}\), \(v = 0(1)n\): some unnoted advantages. Comput. J. (1972). https://doi.org/10.1093/comjnl/15.2.156CrossRefMATH

16.

Wang, H., Huybrechs, D., Vandewalle, S.: Explicit barycentric weights for polynomial interpolation in the roots or extrema of classical orthogonal polynomials. Math. Comput. 290(83), 2893–2914 (2014). https://doi.org/10.1090/S0025-5718-2014-02821-4MathSciNetCrossRefMATH

17.

Higham, N.J.: The numerical stability of barycentric Lagrange interpolation. IMA J. Numer. Anal. 24, 547–556 (2004). https://doi.org/10.1093/imanum/24.4.547MathSciNetCrossRefMATH

18.

Schneider, C., Werner, W.: Some new aspects of rational interpolation. Math. Comput. 47(175), 285–299 (1986). https://doi.org/10.2307/2008095MathSciNetCrossRefMATH

19.

Berrut, J.-P.: Rational functions for guaranteed and experimentally well-conditioned global interpolation. Comput. Math. Appl. 15(1), 1–16 (1988). https://doi.org/10.1016/0898-1221(88)90067-3MathSciNetCrossRefMATH

20.

Floater, M.S., Hormann, K.: Barycentric rational interpolation with no poles and high rates of approximation. Numer. Math. 107, 315–331 (2007). https://doi.org/10.1007/s00211-007-0093-yMathSciNetCrossRefMATH

21.

Hormann, K.: Barycentric interpolation. Approximation Theory XIV: San Antonio 2013. Springer International Publishing, 197–218. (2014) https://doi.org/10.1007/978-3-319-06404-8-11

22.

Berrut, J.-P., Klein, G.: Recent advances in linear barycentric rational interpolation. J. Comput. Appl. Math. 259, 95–107 (2014). https://doi.org/10.1016/j.cam.2013.03.044MathSciNetCrossRefMATH

23.

Berrut, J.-P., Mittelmann, H.D.: Optimized point shifts and poles in the linear rational pseudospectral method for boundary value problems. J. Comput. Phys. 204, 292–301 (2005). https://doi.org/10.1016/j.jcp.2004.10.009MathSciNetCrossRefMATH

24.

Baltenspeger, R., Berrut, J.-P., Noël, B.: Exponential convergence of a linear rational interpolant between transformed Chebyshev points. Math. Comput. 227(68), 1109–1120 (1999). https://doi.org/10.1090/S0025-5718-99-01070-4MathSciNetCrossRefMATH

25.

Berrut, J.-P., Mittelmann, H.D.: Adaptive point shifts in rational approximation with optimized denominator. J. Comput. Appl. Math. 164–165, 81–92 (2004). https://doi.org/10.1016/S0377-0427(03)00485-0MathSciNetCrossRefMATH

26.

Berrut, J.-P., Elefante, G.: A periodic map for linear barycentric rational trigonometric interpolation. Appl. Math. Comput. 371, 124924 (2020). https://doi.org/10.1016/j.amc.2019.124924MathSciNetCrossRefMATH

27.

Tee, T.W., Trefethen, L.N.: A Rational Spectral Collocation Method With Adaptively Transformed Chebyshev Grid Points. SIAM J. Sci. Comput. 28(5), 1798–1811 (2006). https://doi.org/10.1137/050641296MathSciNetCrossRefMATH

28.

Baltensperger, R.: Some Results on Linear Rational Trigonometric Interpolation. Comput. Math. Appl. 43, 737–746 (2002). https://doi.org/10.1016/S0898-1221(01)00317-0MathSciNetCrossRefMATH

29.

Berrut, J.-P., Elefante, G.: Bounding the Lebesgue constant for a barycentric rational trigonometric interpolant at periodic well-spaced nodes. J. Comput. Appl. Math. 398, 113664 (2021). https://doi.org/10.1016/j.cam.2021.113664MathSciNetCrossRefMATH

30.

Kong, D., Xiang, S.: Fast rational spectral interpolation for singular functions via scaled transformations. arXiv preprint arXiv:2101.07949, (2021). https://doi.org/10.48550/arXiv.2101.07949

31.

Kosloff, D., Tal-Ezer, H.: A modified Chebyshev pseudospectral method with an \({\cal{O} }(N^{-1})\) time step restriction. J. Comput. Phys. 104, 457–469 (1993). https://doi.org/10.1006/jcph.1993.1044MathSciNetCrossRefMATH

32.

Bayliss, A., Turkel, E.: Mappings and accuracy for Chebyshev pseudo-spectral approximations. J. Comput. Phys. 101, 349–359 (1992). https://doi.org/10.1016/0021-9991(92)90012-NMathSciNetCrossRefMATH

33.

Austin, A.P., Kravanja, P., Trefethen, L.N.: Numerical Algorithms Based on Analytic Function Values at Roots of Unity. SIAM J. Numer. Anal. 52(4), 1795–1821 (2014). https://doi.org/10.1137/130931035MathSciNetCrossRefMATH

34.

de Bruin, M.G., Dikshit, H.P., Sharma, A.: Birkhoff interpolation on unity and on M\(\ddot{{\rm o}}\)bius transform of the roots of unity. Numer. Algo. 23, 115–125 (2000). https://doi.org/10.1023/A:1019147900265CrossRefMATH

35.

Pachón, R., Gonnet, P., van Deun, J.: Fast and Stable Rational Interpolation in Roots of Unity and Chebyshev points. SIAM J. Numer. Anal. 50(3), 1713–1734 (2012). https://doi.org/10.1137/100797291MathSciNetCrossRefMATH

36.

Gonnet, P., Pachón, R., Trefethen, L.N.: Robust rational interpolation and least-squares. Elect. Trans. Numer. Anal. 38, 146–167 (2011). https://doi.org/10.1142/S0217751X97001079MathSciNetCrossRefMATH

37.

Henrici, P.: Applied and Computational Complex Analysis. Vol. 1. Wiley-Interscience (John Wiley & Sons), New York-London-Sydney (1974)

38.

Driscoll, T. A., Hale, N., Trefethen, L. N.: Chebfun Guide, http://www.chebfun.org/docs/guide/

39.

Trefethen, L.N., Weideman, J.A.C.: The exponentially convergent trapezoidal rule. SIAM Rev. 56(3), 385–458 (2014). https://doi.org/10.1137/130932132MathSciNetCrossRefMATH

40.

Rizzardi, M.: Detection of the singularities of a complex function by numercical approximations of its Laurent coefficients. Numer. Algo. 77, 955–982 (2018). https://doi.org/10.1007/s11075-017-0349-2MathSciNetCrossRefMATH

41.

Rizzardi, M.: http://dist.uniparthenope.it/mariarosaria.rizzardi, (2017)

42.

Lyness, J. N.: Numerical algorithms based on the theory of complex variables. In: Proceedings of the 1967 22nd National Conference, 125–133. (1967) https://doi.org/10.1145/800196.805983

43.

Bornemann, F.: Accuracy and stability of computing high-order derivatives of analytic functions by cauchy integrals. Found. Comput. Math. 11, 1–63 (2011). https://doi.org/10.1007/s10208-010-9075-zMathSciNetCrossRefMATH

44.

Jentzsch, R.: Untersuchungen zur Theorie Analytischer Funktionen. Dissertation, Berlin (1914)

45.

Walsh, J.L.: The analogue for maximally convergent polynomials of Jentzsch’s theorem. Duke Math. J. 26, 605–616 (1959). https://doi.org/10.1215/S0012-7094-59-02658-4CrossRefMATH

46.

Wegert, E.: Visual Complex Functions: An Introduction with Phase Portraits. Springer, Basel (2012)CrossRefMATH

47.

Wegert, E.: Phase Plots of Complex Functions (https://www.mathworks.com/matlabcentral/fileexchange/44375-phase-plots-of-complex-functions), MATLAB Central File Exchange. Retrieved March 25, (2022)

48.

Lyness, J.N., Delves, L.M.: On numerical contour integration round a closed contour. Math. Comput. 21, 561–577 (1967). https://doi.org/10.2307/2005000MathSciNetCrossRefMATH

49.

Kaup, L., Kaup, B.: Holomorphic Functions of Several Variables. de Gruyter, Berlin (1983)CrossRefMATH

50.

Levin, E., Saff, E.B.: Potential Theoretic Tools in Polynomial and Rational Approximation. In: Harmonic Analysis and Rational Approximation, Springer, Berlin Heidelberg 327, 71–94 (2006). https://doi.org/10.1007/11601609-5

51.

Saff, E. B., Totik, V.: Logarithmic Potentials with External Fields. Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer, Berlin, 316: 505. (1997) https://doi.org/10.1007/978-3-662-03329-6

52.

Berrut, J.-P., Elefante, G.: A linear barycentric rational interpolant on starlike domains. Elect. Trans. Numer. Anal. 55, 726–74 (2022). https://doi.org/10.1553/etna_vol55s726MathSciNetCrossRefMATH

53.

Kravanja, P., Barel, M.V.: Computing the Zeros of Analytic Functions. Springer-Verlag, Berlin Heidelberg (2000)CrossRefMATH

54.

Gautschi, W.: On the construction of Gaussian quadrature rules from modified moments. Mathematics of Computation 110(24), 245–260 (1970). https://doi.org/10.1090/S0025-5718-1970-0285117-6MathSciNetCrossRefMATH

55.

Gautschi, W.: On generating orthogonal polynomials. SIAM J. Sci. Stat. Comput. 3(3), 289–317 (1982). https://doi.org/10.1137/0903018MathSciNetCrossRefMATH

56.

Gautschi, W.: On the sensitivity of orthogonal polynomials to perturbations in the moments. Numer. Math. 48, 369–382 (1986). https://doi.org/10.1007/bf01389645MathSciNetCrossRefMATH

57.

Beckermann, B., Bourreau, E.: How to choose modified moments? J. Comput. Appl. Math. 98, 81–98 (1998). https://doi.org/10.1016/S0377-0427(98)00116-2MathSciNetCrossRefMATH

Title: Fast barycentric rational interpolations for complex functions with some singularities
Authors: Shunfeng Yang
Shuhuang Xiang
Publication date: 01-11-2023
Publisher: Springer International Publishing
Published in: Calcolo / Issue 4/2023
Print ISSN: 0008-0624
Electronic ISSN: 1126-5434
DOI: https://doi.org/10.1007/s10092-023-00550-4

Springer Professional

Fast barycentric rational interpolations for complex functions with some singularities

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 4/2023

On greedy randomized block Gauss–Seidel method with averaging for sparse linear least-squares problems

Two-dimensional Jacobi pseudospectral quadrature solutions of two-dimensional fractional Volterra integral equations

A linear algebra perspective on the random multi-block ADMM: the QP case

Preconditioning of discrete state- and control-constrained optimal control convection-diffusion problems

A Banach spaces-based mixed finite element method for the stationary convective Brinkman–Forchheimer problem

Accurate and efficient numerical methods for the nonlinear Schrödinger equation with Dirac delta potential

Premium Partner