Fast and stable approximation of analytic functions from equispaced samples via polynomial frames

DOI10.1007/S00365-022-09593-2arXiv2110.03755MaRDI QIDQ6379727FDOQ6379727

A. Shadrin, Ben Adcock

Publication date: 7 October 2021

Abstract: We consider approximating analytic functions on the interval $[-1,1]$ from their values at a set of $m+1$ equispaced nodes. A result of Platte, Trefethen & Kuijlaars states that fast and stable approximation from equispaced samples is generally impossible. In particular, any method that converges exponentially fast must also be exponentially ill-conditioned. We prove a positive counterpart to this `impossibility' theorem. Our `possibility' theorem shows that there is a well-conditioned method that provides exponential decay of the error down to a finite, but user-controlled tolerance $epsilon>0$, which in practice can be chosen close to machine epsilon. The method is known as extit{polynomial frame} approximation or extit{polynomial extensions}. It uses algebraic polynomials of degree $n$ on an extended interval $[-gamma,gamma]$, $gamma>1$, to construct an approximation on $[-1,1]$ via a SVD-regularized least-squares fit. A key step in the proof of our main theorem is a new result on the maximal behaviour of a polynomial of degree $n$ on $[-1,1]$ that is simultaneously bounded by one at a set of $m+1$ equispaced nodes in $[-1,1]$ and $1/epsilon$ on the extended interval $[-gamma,gamma]$. We show that linear oversampling, i.e., $m=cnlog(1/epsilon)/sqrtgamm{a}^2-1$, is sufficient for uniform boundedness of any such polynomial on $[-1,1]$. This result aside, we also prove an extended impossibility theorem, which shows that such a possibility theorem (and consequently the method of polynomial frame approximation) is essentially optimal.

Mathematics Subject Classification ID

Approximation by polynomials (41A10) Inequalities in approximation (Bernstein, Jackson, Nikol'ski?-type inequalities) (41A17) Rate of convergence, degree of approximation (41A25)

This page was built for publication: Fast and stable approximation of analytic functions from equispaced samples via polynomial frames

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