article

Exponentially-convergent strategies for defeating the Runge Phenomenon for the approximation of non-periodic functions, part two: Multi-interval polynomial schemes and multidomain Chebyshev interpolation

Authors:

Jun Rong OngAuthors Info & Claims

Applied Numerical Mathematics, Volume 61, Issue 4

Pages 460 - 472

https://doi.org/10.1016/j.apnum.2010.11.010

Published: 01 April 2011 Publication History

Abstract

Approximating a smooth function from its values f(x"i) at a set of evenly spaced points x"i through P-point polynomial interpolation often fails because of divergence near the endpoints, the ''Runge Phenomenon''. This report shows how to achieve an error that decreases exponentially fast with P by means of polynomial interpolation on N"s subdomains where N"s increases with P. We rigorously prove that in the limit both N"s and M, the degree on each subdomain, increase simultaneously, the approximation error converges proportionally to exp(-constantPlog(P)). Thus, division into ever-shrinking, ever-more-numerous subdomains is guaranteed to defeat the Runge Phenomenon in infinite precision arithmetic. (Numerical ill-conditioning is also discussed, but is not a great difficulty in practice, though not insignificant in theory.) Although a Chebyshev grid on each subdomain is well known to be immune to the Runge Phenomenon, it is still interesting, and the same methodology can be applied as to a uniform grid. When a Chebyshev grid is used on each subdomain, there are two regimes. If c is the distance from the middle of the interval [-1,1] to the nearest singularity of f(x) in the complex plane, then when cN"s@?1, the error is proportional to exp(-cP), independent of the number of subdomains. When cN"s@?1, the rate of convergence slows to exp(-constantPlog(P)), the same as for equispaced interpolation. However, the Chebyshev multidomain error is always smaller than the equispaced multidomain error.

References

[1]

Berzins, M., Adaptive polynomial interpolation on evenly spaced meshes. SIAM Rev. v49. 604-627.

Digital Library

[2]

Boyd, J.P., Chebyshev and Fourier Spectral Methods. 2001. 2nd ed. Dover, Mineola, NY.

[3]

Boyd, J.P., Trouble with Gegenbauer reconstruction for defeating Gibbs' phenomenon: Runge phenomenon in the diagonal limit of Gegenbauer polynomial approximations. J. Comput. Phys. v204. 253-264.

Digital Library

[4]

Boyd, J.P., Exponentially accurate Runge-free approximation of non-periodic functions from samples on an evenly-spaced grid. Appl. Math. Lett. v20. 971-975.

[5]

Boyd, J.P., Defeating Gibbs Phenomenon in Fourier and Chebyshev spectral methods for solving differential equations. In: Jerri, A. (Ed.), Gibbs Phenomenon, Sampling Publishing, Potsdam, New York.

[6]

Boyd, J.P., Six strategies for defeating the Runge Phenomenon in Gaussian radial basis functions on a finite interval. Comput. Math. Appl. v60 i12. 3108-3122.

[7]

Boyd, J.P. and Ong, J.R., Exponentially-convergent strategies for defeating the Runge Phenomenon for the approximation of non-periodic functions, Part I: Single-interval schemes. Commun. Comput. Phys. v5. 484-497.

[8]

Dahlquist, G. and Björck, í., Numerical Methods. 2003. Dover Publications, New York.

[9]

Davis, P.J., Interpolation and Approximation. 1975. Dover Publications, New York.

[10]

Dehghan, M. and Eslahchi, M.R., Best uniform polynomial approximation of some rational functions. Comput. Math. Appl. v59. 382-390.

Digital Library

[11]

Epperson, J.F., On the Runge example. Amer. Math. Monthly. v94. 329-341.

[12]

Eslahchi, M.R. and Dehghan, M., The best uniform polynomial approximation to a class of the form 1/(a2¿x2). Nonlinear Anal.: Theory Meths. Appl. v71. 740-750.

[13]

Gautschi, W., Numerical Analysis: An Introduction. 1997. Birkhäuser, Boston.

[14]

Gottlieb, D. and Gottlieb, S., Spectral methods for compressible reactive flows. Comptes Rend. Mec. v333. 3-16.

[15]

Meray, C., Observations sur la légitime de l'interpolation. Ann. Sci. Ec. Norm. Super. v1. 165-176.

[16]

Meray, C., Nouvelles examples d'interpolation illusoires. Bull. Sci. Math. v20. 266-270.

[17]

Mills, T.M. and Smith, S.J., Lagrange interpolation polynomials based equidistant nodes. Math. Scientist. v16. 107-117.

[18]

Platte, R.B. and Gelb, A., A hybrid Fourier-Chebyshev method for partial differential equations. J. Sci. Comput. v39. 244-264.

Digital Library

[19]

R.B. Platte, L.N. Trefethen, A.B.J. Kuijlaars, Impossibility of approximating analytic functions from equispaced samples, SIAM Rev. (2010), in press.

[20]

Runge, C., íber empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten. Zeitschrift fur Mathematik und Physik. v246. 224-243.

[21]

Schönhage, A., Fehlerfortpflanzung bei Interpolation. Numer. Math. v3. 62-71.

[22]

Turetskii, A.H., The bounding of polynomials prescribed at equally spaced points. Pedag. Inst. Vitebsk. v3. 117-127.

Cited By

Khalil OEl-Sharkawy HYoussef MBaumann G(2023)Adaptive piecewise Poly-Sinc methods for function approximationApplied Numerical Mathematics10.1016/j.apnum.2022.12.016186:C(1-18)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.apnum.2022.12.016
Huybrechs DTrefethen L(2023)AAA interpolation of equispaced dataBIT10.1007/s10543-023-00959-x63:2Online publication date: 14-Mar-2023
https://dl.acm.org/doi/10.1007/s10543-023-00959-x
Kasperski G(2015)A parallel Schwarz preconditioner for the Chebyshev Gauss-Lobatto collocation ( d 2 d x 2 - h 2 ) operatorJournal of Computational Physics10.1016/j.jcp.2015.04.049296:C(101-112)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.jcp.2015.04.049
Show More Cited By

Index Terms

Exponentially-convergent strategies for defeating the Runge Phenomenon for the approximation of non-periodic functions, part two: Multi-interval polynomial schemes and multidomain Chebyshev interpolation
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Numerical analysis

Index terms have been assigned to the content through auto-classification.

Recommendations

Chebyshev interpolation and quadrature formulas of very high degree

All the zeros x_2^m,i, i = 1(1)2^m, of the Chebyshev polynomials T_2^m(x), m = 0(1)n, are found recursively just by taking n2^n-1 real square roots. For interpolation or integration of ƒ(x), given ƒ(x_2^m,i), only x_2^m,i is needed to calculate (a) the (2^m - 1)-...
Divergence (Runge Phenomenon) for least-squares polynomial approximation on an equispaced grid and Mock-Chebyshev subset interpolation

Runge showed more than a century ago that polynomial interpolation of a function f(x), using points evenly spaced on x@?[-1,1], could diverge on parts of this interval even if f(x) was analytic everywhere on the interval. Least-squares fitting of a ...
An approximation method for high-order fractional derivatives of algebraically singular functions

The fractional derivative D^qf(s) (0@__ __s@__ __1) of a given function f(s) with a positive non-integer q is defined in terms of an indefinite integral. We propose a uniform approximation scheme to D^qf(s) for algebraically singular functions f(s)=s^@...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Applied Numerical Mathematics

Applied Numerical Mathematics Volume 61, Issue 4

April, 2011

247 pages

ISSN:0168-9274

Issue’s Table of Contents

Copyright © IMACS © 2010.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 April 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khalil OEl-Sharkawy HYoussef MBaumann G(2023)Adaptive piecewise Poly-Sinc methods for function approximationApplied Numerical Mathematics10.1016/j.apnum.2022.12.016186:C(1-18)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.apnum.2022.12.016
Huybrechs DTrefethen L(2023)AAA interpolation of equispaced dataBIT10.1007/s10543-023-00959-x63:2Online publication date: 14-Mar-2023
https://dl.acm.org/doi/10.1007/s10543-023-00959-x
Kasperski G(2015)A parallel Schwarz preconditioner for the Chebyshev Gauss-Lobatto collocation ( d 2 d x 2 - h 2 ) operatorJournal of Computational Physics10.1016/j.jcp.2015.04.049296:C(101-112)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.jcp.2015.04.049
De Marchi SDell'Accio FMazza M(2015)On the constrained mock-Chebyshev least-squaresJournal of Computational and Applied Mathematics10.1016/j.cam.2014.11.032280:C(94-109)Online publication date: 15-May-2015
https://dl.acm.org/doi/10.1016/j.cam.2014.11.032
Lin HSun L(2015)Searching globally optimal parameter sequence for defeating Runge phenomenon by immunity genetic algorithmApplied Mathematics and Computation10.1016/j.amc.2015.04.069264:C(85-98)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1016/j.amc.2015.04.069
Shahbazi KHesthaven JZhu X(2013)Multi-dimensional hybrid Fourier continuation-WENO solvers for conservation lawsJournal of Computational Physics10.5555/2743135.2743305253:C(209-225)Online publication date: 15-Nov-2013
https://dl.acm.org/doi/10.5555/2743135.2743305
Shahbazi KAlbin NBruno OHesthaven J(2011)Multi-domain Fourier-continuation/WENO hybrid solver for conservation lawsJournal of Computational Physics10.1016/j.jcp.2011.08.024230:24(8779-8796)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1016/j.jcp.2011.08.024

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents