Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Explicit barycentric weights for polynomial interpolation in the roots or extrema of classical orthogonal polynomials


Authors: Haiyong Wang, Daan Huybrechs and Stefan Vandewalle
Journal: Math. Comp. 83 (2014), 2893-2914
MSC (2010): Primary 41A05, 65D05, 65D15
DOI: https://doi.org/10.1090/S0025-5718-2014-02821-4
Published electronically: March 28, 2014
MathSciNet review: 3246814
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Barycentric interpolation is arguably the method of choice for numerical polynomial interpolation. The polynomial interpolant is expressed in terms of function values using the so-called barycentric weights, which depend on the interpolation points. Few explicit formulae for these barycentric weights are known. In [H. Wang and S. Xiang, Math. Comp., 81 (2012), 861-877], the authors have shown that the barycentric weights of the roots of Legendre polynomials can be expressed explicitly in terms of the weights of the corresponding Gaussian quadrature rule. This idea was subsequently implemented in the Chebfun package [L. N. Trefethen and others, The Chebfun Development Team, 2011] and in the process generalized by the Chebfun authors to the roots of Jacobi, Laguerre and Hermite polynomials. In this paper, we explore the generality of the link between barycentric weights and Gaussian quadrature and show that such relationships are related to the existence of lowering operators for orthogonal polynomials. We supply an exhaustive list of cases, in which all known formulae are recovered and also some new formulae are derived, including the barycentric weights for Gauss-Radau and Gauss-Lobatto points. Based on a fast $ {\mathcal O}(n)$ algorithm for the computation of Gaussian quadrature, due to Hale and Townsend, this leads to an $ {\mathcal O}(n)$ computational scheme for barycentric weights.


References [Enhancements On Off] (What's this?)

  • [1] Jean-Paul Berrut and Lloyd N. Trefethen, Barycentric Lagrange interpolation, SIAM Rev. 46 (2004), no. 3, 501-517 (electronic). MR 2115059 (2005k:65018), https://doi.org/10.1137/S0036144502417715
  • [2] I. Bogaert, B. Michiels, and J. Fostier, $ \mathcal {O}(1)$ computation of Legendre polynomials and Gauss-Legendre nodes and weights for parallel computing, SIAM J. Sci. Comput. 34 (2012), no. 3, C83-C101. MR 2970283, https://doi.org/10.1137/110855442
  • [3] Yang Chen and Mourad E. H. Ismail, Ladder operators and differential equations for orthogonal polynomials, J. Phys. A 30 (1997), no. 22, 7817-7829. MR 1616931 (2000i:33011), https://doi.org/10.1088/0305-4470/30/22/020
  • [4] E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York, 1966. MR 0222517 (36 #5568)
  • [5] Germund Dahlquist and Åke Björck, Numerical methods in scientific computing. Vol. I, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. MR 2412832 (2009b:65003)
  • [6] Philip J. Davis, Interpolation and approximation, Dover Publications Inc., New York, 1975. Republication, with minor corrections, of the 1963 original, with a new preface and bibliography. MR 0380189 (52 #1089)
  • [7] Philip J. Davis and Philip Rabinowitz, Methods of numerical integration, 2nd ed., Computer Science and Applied Mathematics, Academic Press Inc., Orlando, FL, 1984. MR 760629 (86d:65004)
  • [8] A. Dutt, M. Gu, and V. Rokhlin, Fast algorithms for polynomial interpolation, integration, and differentiation, SIAM J. Numer. Anal. 33 (1996), no. 5, 1689-1711. MR 1411845 (97h:65015), https://doi.org/10.1137/0733082
  • [9] Walter Gautschi, Numerical analysis, An introduction, Birkhäuser Boston, Inc., Boston, MA, 1997. MR 1454125 (98d:65001)
  • [10] Walter Gautschi, High-order Gauss-Lobatto formulae, Mathematical journey through analysis, matrix theory and scientific computation (Kent, OH, 1999), Numer. Algorithms 25 (2000), no. 1-4, 213-222. MR 1827155 (2002c:65043), https://doi.org/10.1023/A:1016689830453
  • [11] Walter Gautschi, Gauss-Radau formulae for Jacobi and Laguerre weight functions, Math. Comput. Simulation 54 (2000), no. 4-5, 403-412. 1999 International Symposium on Computational Sciences, to honor John R. Rice (West Lafayette, IN). MR 1808697 (2001k:65049), https://doi.org/10.1016/S0378-4754(00)00179-8
  • [12] Andreas Glaser, Xiangtao Liu, and Vladimir Rokhlin, A fast algorithm for the calculation of the roots of special functions, SIAM J. Sci. Comput. 29 (2007), no. 4, 1420-1438. MR 2341794 (2009c:33056), https://doi.org/10.1137/06067016X
  • [13] Gene H. Golub and John H. Welsch, Calculation of Gauss quadrature rules, Math. Comp. 23 (1969), 221-230; addendum, ibid. 23 (1969), no. 106, loose microfiche suppl, A1-A10. MR 0245201 (39 #6513)
  • [14] Nicholas Hale and Alex Townsend, Fast and accurate computation of Gauss-Legendre and Gauss-Jacobi quadrature nodes and weights, SIAM J. Sci. Comput. 35 (2013), no. 2, A652-A674. MR 3033086, https://doi.org/10.1137/120889873
  • [15] Nicholas Hale and Lloyd N. Trefethen, Chebfun and numerical quadrature, Sci. China Math. 55 (2012), no. 9, 1749-1760. MR 2960859, https://doi.org/10.1007/s11425-012-4474-z
  • [16] Peter Henrici, Essentials of numerical analysis with pocket calculator demonstrations, John Wiley & Sons Inc., New York, 1982. MR 655251 (83h:65002)
  • [17] Nicholas J. Higham, The numerical stability of barycentric Lagrange interpolation, IMA J. Numer. Anal. 24 (2004), no. 4, 547-556. MR 2094569 (2005e:65007), https://doi.org/10.1093/imanum/24.4.547
  • [18] J. C. Mason and D. C. Handscomb, Chebyshev polynomials, Chapman & Hall/CRC, Boca Raton, FL, 2003. MR 1937591 (2004h:33001)
  • [19] Arnold F. Nikiforov and Vasilii B. Uvarov, Special functions of mathematical physics, Birkhäuser Verlag, Basel, 1988. A unified introduction with applications; Translated from the Russian and with a preface by Ralph P. Boas; With a foreword by A. A. Samarskiĭ. MR 922041 (89h:33001)
  • [20] Rodrigo B. Platte, Lloyd N. Trefethen, and Arno B. J. Kuijlaars, Impossibility of fast stable approximation of analytic functions from equispaced samples, SIAM Rev. 53 (2011), no. 2, 308-318. MR 2806639 (2012e:41018), https://doi.org/10.1137/090774707
  • [21] H. E. Salzer, Lagrangian interpolation at the Chebyshev points $ x_{n,\nu }\equiv {\rm cos}(\nu \pi /n)$, $ \nu =0(1)n$; some unnoted advantages, Comput. J. 15 (1972), 156-159. MR 0315865 (47 #4414)
  • [22] Jie Shen and Tao Tang, Spectral and high-order methods with applications, Mathematics Monograph Series, vol. 3, Science Press Beijing, Beijing, 2006. MR 2723481 (2012b:65001)
  • [23] Eduard L. Stiefel, An introduction to numerical mathematics, Translated by Werner C. Rheinboldt and Cornelie J. Rheinboldt, Academic Press, New York, 1963. MR 0181077 (31 #5306)
  • [24] Endre Süli and David F. Mayers, An introduction to numerical analysis, Cambridge University Press, Cambridge, 2003. MR 2006500
  • [25] G. Szegő, Orthogonal Polynomials, Colloquium Publications 23, A, Providence, Rhode Island, 1939.
  • [26] Craig A. Tracy and Harold Widom, Fredholm determinants, differential equations and matrix models, Comm. Math. Phys. 163 (1994), no. 1, 33-72. MR 1277933 (95e:82005)
  • [27] Lloyd N. Trefethen, Approximation theory and approximation practice, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. MR 3012510
  • [28] L. N. Trefethen and others, Chebfun Version 4.0, The Chebfun Development Team, http://www.maths.ox.ac.uk/chebfun/, 2011.
  • [29] Haiyong Wang and Shuhuang Xiang, On the convergence rates of Legendre approximation, Math. Comp. 81 (2012), no. 278, 861-877. MR 2869040 (2012k:41021), https://doi.org/10.1090/S0025-5718-2011-02549-4
  • [30] M. Webb, L. N. Trefethen and P. Gonnet, Stability of barycentric interpolation formulas for extrapolation, SIAM J. Sci. Comput., 34 (2012), A3009-A3015.
  • [31] Wilhelm Werner, Polynomial interpolation: Lagrange versus Newton, Math. Comp. 43 (1984), no. 167, 205-217. MR 744931 (86g:65024), https://doi.org/10.2307/2007406

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 41A05, 65D05, 65D15

Retrieve articles in all journals with MSC (2010): 41A05, 65D05, 65D15


Additional Information

Haiyong Wang
Affiliation: School of Mathematics and Statistics, Huazhong University of Science and Technology, Wuhan 430074, People’s Republic of China
Email: haiyongwang@hust.edu.cn

Daan Huybrechs
Affiliation: Department of Computer Science, K.U.Leuven, Celestijnenlaan 200A, B-3001 Leuven, Belgium
Email: daan.huybrechs@cs.kuleuven.be

Stefan Vandewalle
Affiliation: Department of Computer Science, K.U.Leuven, Celestijnenlaan 200A, B-3001 Leuven, Belgium
Email: stefan.vandewalle@cs.kuleuven.be

DOI: https://doi.org/10.1090/S0025-5718-2014-02821-4
Received by editor(s): November 12, 2012
Received by editor(s) in revised form: March 22, 2013
Published electronically: March 28, 2014
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society