On the numerical stability of Fourier extensions

DOI10.1007/S10208-013-9158-8zbMATH Open1298.65198arXiv1206.4111OpenAlexW2113499611WikidataQ117717434 ScholiaQ117717434MaRDI QIDQ404262FDOQ404262

Authors: Ben Adcock, Daan Huybrechs, J. Martín-Vaquero 

Publication date: 4 September 2014

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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, Trefethen & Kuijlaars 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.

Full work available at URL: https://arxiv.org/abs/1206.4111

Recommendations

• On the Fourier Extension of Nonperiodic Functions
• Function approximation on arbitrary domains using Fourier extension frames
• Fast algorithms for the computation of Fourier extensions of arbitrary length
• A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds
• Parameter selection and numerical approximation properties of Fourier extensions from fixed data

zbMATH Keywords

numerical examplescondition numberconvergence ratenumerical stabilityRunge phenomenonequispaced dataFourier extensionframe approximationnonperiodic functionnumerical Fourier extension

Mathematics Subject Classification ID

Trigonometric approximation (42A10) Numerical methods for trigonometric approximation and interpolation (65T40) Ill-posedness and regularization problems in numerical linear algebra (65F22) General harmonic expansions, frames (42C15)

Cites Work

• Title not available (Why is that?)
• A Practical Guide to Pseudospectral Methods
• Spectral Methods
• A Class of Nonharmonic Fourier Series
• Title not available (Why is that?)
• Title not available (Why is that?)
• Prolate Spheroidal Wave Functions, Fourier Analysis, and Uncertainty-V: The Discrete Case
• Title not available (Why is that?)
• An introduction to frames and Riesz bases
• A modified Chebyshev pseudospectral method with an \(O(N^{-1})\) time step restriction
• Title not available (Why is that?)
• Impossibility of fast stable approximation of analytic functions from equispaced samples
• Title not available (Why is that?)
• On the Gibbs Phenomenon and Its Resolution
• Exponentially-convergent strategies for defeating the Runge phenomenon for the approximation of non-periodic functions. I: Single-interval schemes
• Divergence (Runge phenomenon) for least-squares polynomial approximation on an equispaced grid and mock-Chebyshev subset interpolation
• On the Fourier Extension of Nonperiodic Functions
• On the Gibbs phenomenon. I: Recovering exponential accuracy from the Fourier partial sum of a nonperiodic analytic function
• A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds
• High-order unconditionally stable FC-AD solvers for general smooth domains. I: Basic elements
• Accurate, high-order representation of complex three-dimensional surfaces via Fourier continuation analysis
• A spectral FC solver for the compressible Navier-Stokes equations in general domains. I: Explicit time-stepping
• High-order unconditionally stable FC-AD solvers for general smooth domains. II: Elliptic, parabolic and hyperbolic PDEs; theoretical considerations
• The Growth of Polynomials Bounded at Equally Spaced Points
• The prolate matrix
• Approximation error in regularized SVD-based Fourier continuations
• Fourier embedded domain methods: Extending a function defined on an irregular region to a rectangle so that the extension is spatially periodic and \(C^{\infty}\)
• Trouble with Gegenbauer reconstruction for defeating Gibbs' phenomenon: Runge phenomenon in the diagonal limit of Gegenbauer polynomial approximations
• A spectral embedding method applied to the advection-diffusion equation
• On the resolution power of Fourier extensions for oscillatory functions
• A fast algorithm for Fourier continuation
• The Future Fast Fourier Transform?
• Title not available (Why is that?)

Cited In (45)

• Frames and numerical approximation. II: Generalized sampling
• Subperiodic trigonometric subsampling: a numerical approach
• Numerical Properties of Fat Schemes with Special Support
• On the Fourier Extension of Nonperiodic Functions
• Two algorithms for periodic extension on uniform grids
• On the Convergence of the Quasi-Periodic Approximations on a Finite Interval
• Fast algorithms for the computation of Fourier extensions of arbitrary length
• A Hermite extension method for numerical differentiation
• Numerical differentiation by a Fourier extension method with super-order regularization
• Convergence analysis of oversampled collocation boundary element methods in 2D
• A mapped polynomial method for high-accuracy approximations on arbitrary grids
• Title not available (Why is that?)
• Discrete prolate spheroidal wave functions: further spectral analysis and some related applications
• Approximation error in regularized SVD-based Fourier continuations
• Infinite-dimensional \(\ell ^1\) minimization and function approximation from pointwise data
• An Adaptive Partition of Unity Method for Multivariate Chebyshev Polynomial Approximations
• Parameter selection and numerical approximation properties of Fourier extensions from fixed data
• Pointwise and uniform convergence of Fourier extensions
• A fast algorithm for the convolution of functions with compact support using Fourier extensions
• A Fourier Extension Based Numerical Integration Scheme for Fast and High-Order Approximation of Convolutions with Weakly Singular Kernels
• Accurate and efficient spectral methods for elliptic PDEs in complex domains
• Numerical differentiation for two-dimensional functions by a Fourier extension method
• On the resolution power of Fourier extensions for oscillatory functions
• Subperiodic trigonometric hyperinterpolation
• An efficient spectral method for elliptic PDEs in complex domains with circular embedding
• A Windowed Fourier Method for Approximation of Non-periodic Functions on Equispaced Nodes
• The Fourier approximation of smooth but non-periodic functions from unevenly spaced data
• A Super Order Regularization Scheme in Hilbert Scales under General Smoothing Conditions
• Oversampled collocation approximation method of functions via Jacobi frames
• Exponential tractability of \(L_2\)-approximation with function values
• The Fourier extension method and discrete orthogonal polynomials on an arc of the circle
• A radial basis function based frames strategy for bypassing the Runge phenomenon
• Two-dimensional Fourier continuation and applications
• AAA interpolation of equispaced data
• Fast and stable approximation of analytic functions from equispaced samples via polynomial frames
• Function approximation on arbitrary domains using Fourier extension frames
• Spectral methods in non-tensor geometry. II: Chebyshev versus Zernike polynomials, gridding strategies and spectral extension on squircle-bounded and perturbed-quadrifolium domains
• Efficient function approximation on general bounded domains using splines on a Cartesian grid
• Improved bounds for the eigenvalues of prolate spheroidal wave functions and discrete prolate spheroidal sequences
• A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds
• How exponentially ill-conditioned are contiguous submatrices of the Fourier matrix?
• Title not available (Why is that?)
• Computing with functions on domains with arbitrary shapes
• APPROXIMATING SMOOTH, MULTIVARIATE FUNCTIONS ON IRREGULAR DOMAINS
• Frames and numerical approximation

This page was built for publication: On the numerical stability of Fourier extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404262)