×

Fast barycentric rational interpolations for complex functions with some singularities. (English) Zbl 1531.65023

It’s well known that the barycentric form of the Lagrange interpolation polynomial is numerically stable and used to reconstruct complex functions from discrete data. The interpolation rational function \(\mathcal{R}_{m,n}\) such that \( \mathcal{R}_{m,n}(z_j)=\frac{\mathcal{P}_m(z_j)}{\mathcal{Q}_n(z_j)}=f_j\) for \(j=0,\dots,N\), with \(f_j=f(z_j)\) and \(z_i \neq z_j\), \(i\neq j\) known, and with nonnegative \(m\) and \(n\) satisfying \(N=m+n\) is the second approach in the interpolation problem. These methods become inefficient for functions with a branch cut or essential singularity. Suppose that \(a_j \in \operatorname{int} D_R\), \(j = 1, 2, \dots, m\), \(D_R=\{z: |z|<R\},\) are the singularities of \(f(z)\). The new barycentric rational interpolation function of the form \[ \mathcal{R}_{\mathbf{N}}(z)=\frac{\sum_{j=0}^m \frac{\sigma_j}{N_j}\sum_{k=0}^{N_j-1}\frac{z_{jk}-a_j}{z_{jk}-a}f_{jk}}{\sum_{j=0}^m\frac{\sigma_j}{N_j}\sum_{k=0}^{N_j-1}\frac{z_{jk}-a_j}{z_{jk}-a}} \] is proposed in this paper. This interpolation function is pole-free, exponentially convergent, and numerically stable, requiring only \(\mathcal{O}(N)\) operations. A convergence analysis of the method is provided. Numerical examples that illustrate the theoretical results and demonstrate the accuracy and efficiency of the methodology are given. Some applications of the method, including the numerical solutions of boundary value problems and the zero locations of a holomorphic functions, are discussed in the paper. The article contains many drawings, graphs and Matlab codes illustrating the considered methods.

MSC:

65D05 Numerical interpolation
30E10 Approximation in the complex plane
30E15 Asymptotic representations in the complex plane
30C20 Conformal mappings of special domains
65E99 Numerical methods in complex analysis (potential theory, etc.)

Software:

Matlab; Chebfun
Full Text: DOI

References:

[1] Oppenheim, AV; Willsky, AS; Nawab, SH, Signals and Systems (1997), USA: Pearson Prentice-Hall, USA
[2] Oppenheim, AV; Schafer, RW, Discrete-Time Signal Processing (2009), USA: Pearson Prentice-Hall, USA · Zbl 0676.42001
[3] Sierra, JMG, Digital Signal Processing with Matlab Examples, Volume (1-3) (2017), Singapore: Springer Science+Business Media, Singapore · doi:10.1007/978-981-10-2534-1
[4] Gaier, D.: Vorlesungen über Approximation im Komplexen. Birkhäuser Basel, (1980) · Zbl 0442.30038
[5] Webb, M., Trefethen, L. N.: Computing Complex Singularities of Differential Equations with Chebfun. Electronic Transactions on Numerical Analysis (2011)
[6] Guide, ME; Miedlar, A.; Saad, Y., A rational approximation method for solving acoustic nonlinear eigenvalue problems, Eng. Anal. Bound. Element, 111, 44-54 (2020) · Zbl 1464.76086 · doi:10.1016/j.enganabound.2019.10.006
[7] Gopal, A.; Trefethen, LN, Solving Laplace problems with corner singularities via rational functions, IAM J. Numer. Anal., 57, 5, 2074-2094 (2019) · Zbl 1431.65223 · doi:10.1137/19M125947X
[8] Taylor, WJ, Method of Lagrangian curvilinear interpolation, J. Res. Natl. Bureau Standards, 35, 151-155 (1945) · Zbl 0061.28409 · doi:10.6028/JRES.035.006
[9] Dupuy, M., Le calcul numerique des fonctions par linterpolation barycentrique, Comptes Rendus Hebdomadaires Des Seances De L Acad, 226, 158-159 (1948) · Zbl 0031.03605
[10] Jacobi, C. G. J.: Disquisitiones analyticae de fractionibus simplicibus. Dissertation, Berlin (1825)
[11] Gautschi, W.: Numerical Analysis, 2nd edition. Birkhäuser (2012) · Zbl 1378.65002
[12] Berrut, J-P; Trefethen, LN, Barycentric lagrange interpolation, SIAM Rev., 46, 3, 501-517 (2004) · Zbl 1061.65006 · doi:10.1137/s0036144502417715
[13] Trefethen, LN, Approximation Theory and Approximation Practice (2020), SIAM Philadelphia: Extended edition, SIAM Philadelphia · Zbl 1437.41001
[14] Wang, H.; Xiang, S., On the convergence rates of Legendre approximation, Math. Comput., 278, 81, 861-877 (2012) · Zbl 1242.41016 · doi:10.2307/23267976
[15] Salzer, HE, Lagrangian interpolation at the chebyshev points \(x_n=\cos{v\pi /n}, v = 0(1)n\): some unnoted advantages, Comput. J. (1972) · Zbl 0242.65007 · doi:10.1093/comjnl/15.2.156
[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) · Zbl 1297.41001 · doi:10.1090/S0025-5718-2014-02821-4
[17] Higham, NJ, The numerical stability of barycentric Lagrange interpolation, IMA J. Numer. Anal., 24, 547-556 (2004) · Zbl 1067.65016 · doi:10.1093/imanum/24.4.547
[18] Schneider, C.; Werner, W., Some new aspects of rational interpolation, Math. Comput., 47, 175, 285-299 (1986) · Zbl 0612.65005 · doi:10.2307/2008095
[19] Berrut, J-P, Rational functions for guaranteed and experimentally well-conditioned global interpolation, Comput. Math. Appl., 15, 1, 1-16 (1988) · Zbl 0646.65006 · doi:10.1016/0898-1221(88)90067-3
[20] Floater, MS; Hormann, K., Barycentric rational interpolation with no poles and high rates of approximation, Numer. Math., 107, 315-331 (2007) · Zbl 1221.41002 · doi:10.1007/s00211-007-0093-y
[21] Hormann, K.: Barycentric interpolation. Approximation Theory XIV: San Antonio 2013. Springer International Publishing, 197-218. (2014) doi: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) · Zbl 1291.65036 · doi:10.1016/j.cam.2013.03.044
[23] Berrut, J-P; Mittelmann, HD, Optimized point shifts and poles in the linear rational pseudospectral method for boundary value problems, J. Comput. Phys., 204, 292-301 (2005) · Zbl 1070.65062 · doi:10.1016/j.jcp.2004.10.009
[24] Baltenspeger, R.; Berrut, J-P; Nöel, B., Exponential convergence of a linear rational interpolant between transformed Chebyshev points, Math. Comput., 227, 68, 1109-1120 (1999) · Zbl 0920.65003 · doi:10.1090/S0025-5718-99-01070-4
[25] Berrut, J-P; Mittelmann, HD, Adaptive point shifts in rational approximation with optimized denominator, J. Comput. Appl. Math., 164-165, 81-92 (2004) · Zbl 1038.65011 · doi:10.1016/S0377-0427(03)00485-0
[26] Berrut, J-P; Elefante, G., A periodic map for linear barycentric rational trigonometric interpolation, Appl. Math. Comput., 371 (2020) · Zbl 1433.65015 · doi:10.1016/j.amc.2019.124924
[27] Tee, TW; Trefethen, LN, A Rational Spectral Collocation Method With Adaptively Transformed Chebyshev Grid Points, SIAM J. Sci. Comput., 28, 5, 1798-1811 (2006) · Zbl 1123.65105 · doi:10.1137/050641296
[28] Baltensperger, R., Some Results on Linear Rational Trigonometric Interpolation, Comput. Math. Appl., 43, 737-746 (2002) · Zbl 0995.42003 · doi:10.1016/S0898-1221(01)00317-0
[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 (2021) · Zbl 1469.42007 · doi:10.1016/j.cam.2021.113664
[30] Kong, D., Xiang, S.: Fast rational spectral interpolation for singular functions via scaled transformations. arXiv preprint arXiv:2101.07949, (2021). doi: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) · Zbl 0781.65082 · doi:10.1006/jcph.1993.1044
[32] Bayliss, A.; Turkel, E., Mappings and accuracy for Chebyshev pseudo-spectral approximations, J. Comput. Phys., 101, 349-359 (1992) · Zbl 0757.65009 · doi:10.1016/0021-9991(92)90012-N
[33] Austin, AP; Kravanja, P.; Trefethen, LN, Numerical Algorithms Based on Analytic Function Values at Roots of Unity, SIAM J. Numer. Anal., 52, 4, 1795-1821 (2014) · Zbl 1305.41006 · doi:10.1137/130931035
[34] de Bruin, MG; Dikshit, HP; 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) · Zbl 0961.41002 · doi:10.1023/A:1019147900265
[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) · Zbl 1252.41005 · doi:10.1137/100797291
[36] Gonnet, P.; Pachón, R.; Trefethen, LN, Robust rational interpolation and least-squares, Elect. Trans. Numer. Anal., 38, 146-167 (2011) · Zbl 1293.65017 · doi:10.1142/S0217751X97001079
[37] Henrici, P.: Applied and Computational Complex Analysis. Vol. 1. Wiley-Interscience (John Wiley & Sons), New York-London-Sydney (1974) · Zbl 0313.30001
[38] Driscoll, T. A., Hale, N., Trefethen, L. N.: Chebfun Guide, http://www.chebfun.org/docs/guide/
[39] Trefethen, LN; Weideman, JAC, The exponentially convergent trapezoidal rule, SIAM Rev., 56, 3, 385-458 (2014) · Zbl 1307.65031 · doi:10.1137/130932132
[40] Rizzardi, M., Detection of the singularities of a complex function by numercical approximations of its Laurent coefficients, Numer. Algo., 77, 955-982 (2018) · Zbl 06860398 · doi:10.1007/s11075-017-0349-2
[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) doi: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) · Zbl 1213.65039 · doi:10.1007/s10208-010-9075-z
[44] Jentzsch, R.: Untersuchungen zur Theorie Analytischer Funktionen. Dissertation, Berlin (1914) · JFM 45.0647.02
[45] Walsh, JL, The analogue for maximally convergent polynomials of Jentzsch’s theorem, Duke Math. J., 26, 605-616 (1959) · Zbl 0091.06602 · doi:10.1215/S0012-7094-59-02658-4
[46] Wegert, E., Visual Complex Functions: An Introduction with Phase Portraits (2012), Basel: Springer, Basel · Zbl 1264.30001 · doi:10.1007/978-3-0348-0180-5
[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) · Zbl 1501.30024
[48] Lyness, JN; Delves, LM, On numerical contour integration round a closed contour, Math. Comput., 21, 561-577 (1967) · Zbl 0153.46603 · doi:10.2307/2005000
[49] Kaup, L.; Kaup, B., Holomorphic Functions of Several Variables (1983), Berlin: de Gruyter, Berlin · Zbl 0528.32001 · doi:10.1515/9783110838350
[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). doi:10.1007/11601609-5 · Zbl 1146.41001
[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) doi:10.1007/978-3-662-03329-6 · Zbl 0881.31001
[52] Berrut, J-P; Elefante, G., A linear barycentric rational interpolant on starlike domains, Elect. Trans. Numer. Anal., 55, 726-74 (2022) · Zbl 1524.65049 · doi:10.1553/etna_vol55s726
[53] Kravanja, P.; Barel, MV, Computing the Zeros of Analytic Functions (2000), Berlin Heidelberg: Springer-Verlag, Berlin Heidelberg · Zbl 0945.65018 · doi:10.1007/BFb0103927
[54] Gautschi, W., On the construction of Gaussian quadrature rules from modified moments, Mathematics of Computation, 110, 24, 245-260 (1970) · Zbl 0213.16701 · doi:10.1090/S0025-5718-1970-0285117-6
[55] Gautschi, W., On generating orthogonal polynomials, SIAM J. Sci. Stat. Comput., 3, 3, 289-317 (1982) · Zbl 0482.65011 · doi:10.1137/0903018
[56] Gautschi, W., On the sensitivity of orthogonal polynomials to perturbations in the moments, Numer. Math., 48, 369-382 (1986) · Zbl 0613.65014 · doi:10.1007/bf01389645
[57] Beckermann, B.; Bourreau, E., How to choose modified moments?, J. Comput. Appl. Math., 98, 81-98 (1998) · Zbl 0935.65011 · doi:10.1016/S0377-0427(98)00116-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.