research-article

Algorithm 882: Near-Best Fixed Pole Rational Interpolation with Applications in Spectral Methods

Authors:

Joris van Deun,

Adhemar Bultheel,

J. A. C. WeidemanAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 35, Issue 2

Article No.: 14, Pages 1 - 21

https://doi.org/10.1145/1377612.1377618

Published: 01 July 2008 Publication History

Abstract

We present a numerical procedure to compute the nodes and weights in rational Gauss-Chebyshev quadrature formulas. Under certain conditions on the poles, these nodes are near best for rational interpolation with prescribed poles (in the same sense that Chebyshev points are near best for polynomial interpolation). As an illustration, we use these interpolation points to solve a differential equation with an interior boundary layer using a rational spectral method.

The algorithm to compute the interpolation points (and, if required, the quadrature weights) is implemented as a Matlab program.

Supplementary Material

ZIP File (882.zip)

Software for Near-Best Fixed Pole Rational Interpolation with Applications in Spectral Methods

Download
8.79 KB

References

[1]

Abramowitz, M. and Stegun, I. A. 1964. Handbook of Mathematical Functions With Formulas, Graphs, and Mathematical Tables. Applied Mathematics Series, vol. 55. National Bureau of Standards, Washington, D.C.

Digital Library

[2]

Baltensperger, R., Berrut, J.-P., and Dubey, Y. 2003. The linear rational pseudospectral method with preassigned poles. Numer. Algor. 33, 1-4, 53--63. Also in Proceedings of the International Conference on Numerical Algorithms, Vol. I. Marrakesh, Morocco.

[3]

Baltensperger, R., Berrut, J.-P., and Noël, B. 1999. Exponential convergence of a linear rational interpolant between transformed Chebyshev points. Math. Comput. 68, 227, 1109--1120.

Digital Library

[4]

Berrut, J.-P. 1997. The barycentric weights of rational interpolation with prescribed poles. J. Comput. Appl. Math. 86, 1, 45--52 (special issue dedicated to William B. Gragg).

Digital Library

[5]

Berrut, J.-P. and Baltensperger, R. 2001. The linear rational pseudospectral method for boundary value problems. BIT 41, 5, suppl., 868--879. BIT 40th Anniversary Meeting.

[6]

Berrut, J.-P. and Mittelmann, H. D. 1997. Matrices for the direct determination of the barycentric weights of rational interpolation. J. Comput. Appl. Math. 78, 2, 355--370.

Digital Library

[7]

Berrut, J.-P. and Mittelmann, H. D. 2001. The linear rational pseudospectral method with iteratively optimized poles for two-point boundary value problems. SIAM J. Sci. Comput. 23, 3, 961--975 (electronic).

Digital Library

[8]

Berrut, J.-P. and Mittelmann, H. D. 2004. Adaptive point shifts in rational approximation with optimized denominator. In Proceedings of the 10th International Congress on Computational and Applied Mathematics (ICCAM-2002). Also J. Comput. Appl. Math. 164-165, 81--92.

Digital Library

[9]

Berrut, J.-P. and Mittelmann, H. D. 2005. Optimized point shifts and poles in the linear rational pseudospectral method for boundary value problems. J. Comput. Phys. 204, 1, 292--301.

Digital Library

[10]

Bush, A. W. 1992. Perturbation Methods for Engineers and Scientists. CRC Press Library of Engineering Mathematics. CRC Press, Boca Raton, FL, xii.

[11]

Cuyt, A. and Wuytack, L. 1987. Nonlinear Methods in Numerical Analysis. North-Holland Mathematics Studies, vol. 136. North-Holland Publishing, Amsterdam.

Digital Library

[12]

Deckers, K., van Deun, J., and Bultheel, A. 2006. Computing rational Gauss-Chebyshev quadrature formulas with complex poles. In Proceedings of the 5th International Conference on Engineering Computational Technology, B. H. V. Topping et al., eds. Civil-Comp Press, Stirlingshire, UK, paper 30.

[13]

Deckers, K., van Deun, J., and Bultheel, A. 2007. Rational Gauss-Chebyshev quadrature formulas for complex poles outside { − 1,1}. Math. Comput. (to appear).

[14]

Fornberg, B. 1996. A Practical Guide to Pseudospectral Methods. Cambridge University Press, Cambridge, MA.

[15]

Fritsch, F. N. and Carlson, R. E. 1980. Monotone piecewise cubic interpolation. SIAM J. Numer. Anal. 17, 2, 238--246.

Digital Library

[16]

Gautschi, W. 2000. Quadrature rules for rational functions. Numer. Math. 86, 4, 617--633.

[17]

Gottlieb, D. and Orszag, S. A. 1977. Numerical Analysis of Spectral Methods: Theory and Applications. SIAM, Philadelphia, PA.

[18]

Polezzi, M. and Sri Ranga, A. 2007. On the denominator values and barycentric weights of rational interpolants. J. Comput. Appl. Math. 200, 2, 576--590.

Digital Library

[19]

Schneider, C. and Werner, W. 1991. Hermite interpolation: The barycentric approach. Comput. 46, 1, 35--51.

Digital Library

[20]

Tee, T. W. and Trefethen, L. N. 2006. A rational spectral collocation method with adaptively transformed Chebyshev grid points. SIAM J. Sci. Comput. 28, 5, 1798--1811.

Digital Library

[21]

Trefethen, L. N. 2000. Spectral Methods in MATLAB. Software, Environments, and Tools, vol. 10. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA.

Digital Library

[22]

van Assche, W. and Vanherwegen, I. 1993. Quadrature formulas based on rational interpolation. Math. Comput. 61, 204, 765--783.

[23]

van Deun, J. 2007. Eigenvalue problems to compute almost optimal points for rational interpolation with prescribed poles. Numer. Algor. 45, 89--99.

[24]

van Deun, J. and Bultheel, A. 2003. Orthogonal rational functions and quadrature on an interval. J. Comput. Appl. Math. 153, 1-2, 487--495.

Digital Library

[25]

van Deun, J. and Bultheel, A. 2006. A quadrature formula based on Chebyshev rational functions. IMA J. Numer. Anal. 26, 4, 641--656.

[26]

van Deun, J., Bultheel, A., and González Vera, P. 2006. On computing rational Gauss--Chebyshev quadrature formulas. Math. Comput. 75, 307--326.

[27]

Weideman, J. A. C. 1999. Spectral methods based on nonclassical orthogonal polynomials. In Applications and Computation of Orthogonal Polynomials (Oberwolfach, 1998). International Series on Numerical Mathematics, vol. 131. Birkhäuser, Basel, 239--251.

[28]

Weideman, J. A. C. and Laurie, D. P. 2000. Quadrature rules based on partial fraction expansions. Numer. Algor. 24, 159--178.

Cited By

Kalmykov SLukashov A(2023)Estimates of Lebesgue constants for Lagrange interpolation processes by rational functions under mild restrictions to their fixed polesJournal of Approximation Theory10.1016/j.jat.2023.105909291(105909)Online publication date: Jul-2023
https://doi.org/10.1016/j.jat.2023.105909
Deckers KMougaida ABelhadjsalah H(2017)Algorithm 973ACM Transactions on Mathematical Software10.1145/305407743:4(1-29)Online publication date: 23-Mar-2017
https://dl.acm.org/doi/10.1145/3054077
Deckers K(2014)Christoffel–Darboux-type formulae for orthonormal rational functions with arbitrary complex polesIMA Journal of Numerical Analysis10.1093/imanum/dru04935:4(1842-1863)Online publication date: 6-Nov-2014
https://doi.org/10.1093/imanum/dru049
Show More Cited By

Index Terms

Algorithm 882: Near-Best Fixed Pole Rational Interpolation with Applications in Spectral Methods
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Numerical differentiation
    2. Quadrature
  2. Mathematical software

Recommendations

Algorithm 973: Extended Rational Fejér Quadrature Rules Based on Chebyshev Orthogonal Rational Functions

We present a numerical procedure to approximate integrals of the form ∫^b_af(x)dx, where f is a function with singularities close to, but outside the interval [a, b], with − ∞ ⩽ a < b ⩽ +∞. The algorithm is based on rational interpolatory Fejér quadrature ...
Subresultants, Sylvester sums and the rational interpolation problem

We present a solution for the classical univariate rational interpolation problem by means of (univariate) subresultants. In the case of Cauchy interpolation (interpolation without multiplicities), we give explicit formulas for the solution in terms of ...
Linear barycentric rational quadrature
Abstract
Linear interpolation schemes very naturally lead to quadrature rules. Introduced in the eighties, linear barycentric rational interpolation has recently experienced a boost with the presentation of new weights by Floater and Hormann. The ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 35, Issue 2

July 2008

144 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1377612

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2008

Accepted: 01 January 2008

Revised: 01 September 2007

Received: 01 February 2007

Published in TOMS Volume 35, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Fund for Scientific Research
National Research Foundation in South Africa

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
441
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kalmykov SLukashov A(2023)Estimates of Lebesgue constants for Lagrange interpolation processes by rational functions under mild restrictions to their fixed polesJournal of Approximation Theory10.1016/j.jat.2023.105909291(105909)Online publication date: Jul-2023
https://doi.org/10.1016/j.jat.2023.105909
Deckers KMougaida ABelhadjsalah H(2017)Algorithm 973ACM Transactions on Mathematical Software10.1145/305407743:4(1-29)Online publication date: 23-Mar-2017
https://dl.acm.org/doi/10.1145/3054077
Deckers K(2014)Christoffel–Darboux-type formulae for orthonormal rational functions with arbitrary complex polesIMA Journal of Numerical Analysis10.1093/imanum/dru04935:4(1842-1863)Online publication date: 6-Nov-2014
https://doi.org/10.1093/imanum/dru049
Hochman ALeviatan YWhite J(2013)On the use of rational-function fitting methods for the solution of 2D Laplace boundary-value problemsJournal of Computational Physics10.1016/j.jcp.2012.08.015238(337-358)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1016/j.jcp.2012.08.015
Corless RFillion NCorless RFillion N(2013)The Discrete Fourier TransformA Graduate Introduction to Numerical Methods10.1007/978-1-4614-8453-0_9(403-418)Online publication date: 21-Nov-2013
https://doi.org/10.1007/978-1-4614-8453-0_9
Corless RFillion NCorless RFillion N(2013)Polynomial and Rational InterpolationA Graduate Introduction to Numerical Methods10.1007/978-1-4614-8453-0_8(331-401)Online publication date: 21-Nov-2013
https://doi.org/10.1007/978-1-4614-8453-0_8
Deckers KBultheel A(2012)The existence and construction of rational Gauss-type quadrature rulesApplied Mathematics and Computation10.1016/j.amc.2012.04.008218:20(10299-10320)Online publication date: Jun-2012
https://doi.org/10.1016/j.amc.2012.04.008
Druskin VKnizhnerman LSimoncini V(2011)Analysis of the Rational Krylov Subspace and ADI Methods for Solving the Lyapunov EquationSIAM Journal on Numerical Analysis10.1137/10081325749:5(1875-1898)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1137/100813257
Deckers KCantero MMoral LVelázquez L(2011)Full length articleJournal of Approximation Theory10.1016/j.jat.2011.01.002163:4(524-546)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1016/j.jat.2011.01.002
Butcher JCorless RGonzalez-Vega LShakoori A(2011)Polynomial algebra for Birkhoff interpolantsNumerical Algorithms10.1007/s11075-010-9385-x56:3(319-347)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1007/s11075-010-9385-x
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents