Fast and Stable Approximation of Analytic Functions from Equispaced Samples via Polynomial Frames

Abstract We consider approximating analytic functions on the interval $$[-1,1]$$ [ - 1 , 1 ] from their values at a set of $$m+1$$ 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$$ ϵ > 0 , which in practice can be chosen close to machine epsilon. The method is known as polynomial frame approximation or polynomial extensions. It uses algebraic polynomials of degree n on an extended interval $$[-\gamma ,\gamma ]$$ [ - γ , γ ] , $$\gamma > 1$$ γ > 1 , to construct an approximation on $$[-1,1]$$ [ - 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]$$ [ - 1 , 1 ] that is simultaneously bounded by one at a set of $$m+1$$ m + 1 equispaced nodes in $$[-1,1]$$ [ - 1 , 1 ] and $$1/\epsilon $$ 1 / ϵ on the extended interval $$[-\gamma ,\gamma ]$$ [ - γ , γ ] . We show that linear oversampling, i.e. $$m = c n \log (1/\epsilon ) / \sqrt{\gamma ^2-1}$$ m = c n log ( 1 / ϵ ) / γ 2 - 1 , is sufficient for uniform boundedness of any such polynomial on $$[-1,1]$$ [ - 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.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.