Top

Foundations of Computational Mathematics

Published in:

01-08-2014

On the Numerical Stability of Fourier Extensions

Authors: Ben Adcock, Daan Huybrechs, Jesús Martín-Vaquero

Published in: Foundations of Computational Mathematics | Issue 4/2014

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

search-config

AI-assisted search

Off

Abstract

An effective means to approximate an analytic, nonperiodic function on a bounded interval is by using a Fourier series on a larger domain. When constructed appropriately, this so-called Fourier extension is known to converge geometrically fast in the truncation parameter. Unfortunately, computing a Fourier extension requires solving an ill-conditioned linear system, and hence one might expect such rapid convergence to be destroyed when carrying out computations in finite precision. The purpose of this paper is to show that this is not the case. Specifically, we show that Fourier extensions are actually numerically stable when implemented in finite arithmetic, and achieve a convergence rate that is at least superalgebraic. Thus, in this instance, ill-conditioning of the linear system does not prohibit a good approximation.

In the second part of this paper we consider the issue of computing Fourier extensions from equispaced data. A result of Platte et al. (SIAM Rev. 53(2):308–318, 2011) states that no method for this problem can be both numerically stable and exponentially convergent. We explain how Fourier extensions relate to this theoretical barrier, and demonstrate that they are particularly well suited for this problem: namely, they obtain at least superalgebraic convergence in a numerically stable manner.

previous article High-Dimensional Adaptive Sparse Polynomial Interpolation and Applications to Parametric PDEs

next article Effective Approximation for the Semiclassical Schrödinger Equation

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

The constant of growth was obtained in private communication with A. Kuijlaars. A closed expression (up to several integrals involving the potential function ϕ for the nodes z _n) can be found for c(γ;T). We omit the full argument as it is rather lengthy, but note that it is based on standard results in potential theory. A general reference is [29].

B. Adcock, D. Huybrechs, On the resolution power of Fourier extensions for oscillatory functions. Technical Report TW597, Dept. Computer Science, K.U. Leuven, 2011.

N. Albin, O.P. Bruno, A spectral FC solver for the compressible Navier–Stokes equations in general domains. I: Explicit time-stepping, J. Comput. Phys. 230(16), 6248–6270 (2011). CrossRefMATHMathSciNet

H. Bateman, Higher Transcendental Functions, vol. 2 (McGraw–Hill, New York, 1953).

J.P. Boyd, Chebyshev and Fourier Spectral Methods (Springer, Berlin, 1989). CrossRef

J.P. Boyd, A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds, J. Comput. Phys. 178, 118–160 (2002). CrossRefMATHMathSciNet

J. Boyd, Fourier embedded domain methods: extending a function defined on an irregular region to a rectangle so that the extension is spatially periodic and C ^∞, Appl. Math. Comput. 161(2), 591–597 (2005). CrossRefMATHMathSciNet

J.P. Boyd, Trouble with Gegenbauer reconstruction for defeating Gibbs phenomenon: Runge phenomenon in the diagonal limit of Gegenbauer polynomial approximations, J. Comput. Phys. 204(1), 253–264 (2005). CrossRefMATHMathSciNet

J.P. Boyd, J.R. Ong, Exponentially-convergent strategies for defeating the Runge phenomenon for the approximation of non-periodic functions. I. Single-interval schemes, Commun. Comput. Phys. 5(2–4), 484–497 (2009). MathSciNet

J. Boyd, F. Xu, Divergence (Runge phenomenon) for least-squares polynomial approximation on an equispaced grid and Mock–Chebyshev subset interpolation, Appl. Math. Comput. 210(1), 158–168 (2009). CrossRefMATHMathSciNet

10.

O.P. Bruno, Fast, high-order, high-frequency integral methods for computational acoustics and electromagnetics, in Topics in Computational Wave Propagation: Direct and Inverse Problems, ed. by M. Ainsworth et al. Lecture Notes in Computational Science and Engineering, vol. 31 (Springer, Berlin, 2003), pp. 43–82. CrossRef

11.

O. Bruno, M. Lyon, High-order unconditionally stable FC–AD solvers for general smooth domains. I. Basic elements, J. Comput. Phys. 229(6), 2009–2033 (2010). CrossRefMATHMathSciNet

12.

O.P. Bruno, Y. Han, M.M. Pohlman, Accurate, high-order representation of complex three-dimensional surfaces via Fourier continuation analysis, J. Comput. Phys. 227(2), 1094–1125 (2007). CrossRefMATHMathSciNet

13.

C. Canuto, M.Y. Hussaini, A. Quarteroni, T.A. Zang, Spectral Methods: Fundamentals in Single Domains (Springer, Berlin, 2006).

14.

O. Christensen, An Introduction to Frames and Riesz Bases (Birkhauser, Basel, 2003). CrossRefMATH

15.

D. Coppersmith, T. Rivlin, The growth of polynomials bounded at equally spaced points, SIAM J. Math. Anal. 23, 970–983 (1992). CrossRefMATHMathSciNet

16.

R.J. Duffin, A.C. Schaeffer, A class of nonharmonic Fourier series, Trans. Am. Math. Soc. 72, 341–366 (1952). CrossRefMATHMathSciNet

17.

A. Edelman, P. McCorquodale, S. Toledo, The future Fast Fourier Transform? SIAM J. Sci. Comput. 20(3), 1094–1114 (1999). CrossRefMATHMathSciNet

18.

B. Fornberg, A Practical Guide to Pseudospectral Methods (Cambridge University Press, Cambridge, 1996). MATH

19.

D. Gottlieb, S.A. Orszag, Numerical Analysis of Spectral Methods: Theory and Applications, 1st edn. (SIAM, Philadelphia, 1977). CrossRefMATH

20.

D. Gottlieb, C.-W. Shu, On the Gibbs’ phenomenon and its resolution, SIAM Rev. 39(4), 644–668 (1997). CrossRefMATHMathSciNet

21.

D. Gottlieb, C.-W. Shu, A. Solomonoff, H. Vandeven, On the Gibbs phenomenon. I: Recovering exponential accuracy from the Fourier partial sum of a nonperiodic analytic function, J. Comput. Appl. Math. 43(1–2), 91–98 (1992). MathSciNet

22.

D. Huybrechs, On the Fourier extension of non-periodic functions, SIAM J. Numer. Anal. 47(6), 4326–4355 (2010). CrossRefMATHMathSciNet

23.

D. Kosloff, H. Tal-Ezer, A modified Chebyshev pseudospectral method with an \(\mathcal {O}(N^{-1})\) time step restriction, J. Comput. Phys. 104, 457–469 (1993). CrossRefMATHMathSciNet

24.

M. Lyon, Approximation error in regularized SVD-based Fourier continuations, Appl. Numer. Math. 62, 1790–1803 (2012). CrossRefMATHMathSciNet

25.

M. Lyon, A fast algorithm for Fourier continuation, SIAM J. Sci. Comput. 33(6), 3241–3260 (2012). CrossRefMathSciNet

26.

M. Lyon, O. Bruno, High-order unconditionally stable FC–AD solvers for general smooth domains. II. Elliptic, parabolic and hyperbolic PDEs; theoretical considerations, J. Comput. Phys. 229(9), 3358–3381 (2010). CrossRefMATHMathSciNet

27.

R. Pasquetti, M. Elghaoui, A spectral embedding method applied to the advection–diffusion equation, J. Comput. Phys. 125, 464–476 (1996). CrossRefMATHMathSciNet

28.

R. Platte, L.N. Trefethen, A. Kuijlaars, Impossibility of fast stable approximation of analytic functions from equispaced samples, SIAM Rev. 53(2), 308–318 (2011). CrossRefMATHMathSciNet

29.

T. Ransford, Potential Theory in the Complex Plane (Cambridge Univ. Press, Cambridge, 1995). CrossRefMATH

30.

T.J. Rivlin, Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory (Wiley, New York, 1990). MATH

31.

D. Slepian, Prolate spheroidal wave functions. Fourier analysis, and uncertainty. V: The discrete case, Bell Syst. Tech. J. 57, 1371–1430 (1978). CrossRefMATH

32.

L.N. Trefethen, D. Bau, Numerical Linear Algebra (SIAM, Philadelphia, 1997). CrossRefMATH

33.

J. Varah, The prolate matrix, Linear Algebra Appl. 187(1), 269–278 (1993). CrossRefMATHMathSciNet

Title: On the Numerical Stability of Fourier Extensions
Authors: Ben Adcock
Daan Huybrechs
Jesús Martín-Vaquero
Publication date: 01-08-2014
Publisher: Springer US
Published in: Foundations of Computational Mathematics / Issue 4/2014
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-013-9158-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2014

Robust Statistics, Hypothesis Testing, and Confidence Intervals for Persistent Homology on Metric Measure Spaces

New Tools for Classifying Hamiltonian Circle Actions with Isolated Fixed Points

High-Dimensional Adaptive Sparse Polynomial Interpolation and Applications to Parametric PDEs

Erratum to: Smale’s Fundamental Theorem of Algebra Reconsidered

Computing Cup Products in -Cohomology of 3D Polyhedral Complexes

Effective Approximation for the Semiclassical Schrödinger Equation

Premium Partner