On the possibility of fast stable approximation of analytic functions from equispaced samples via polynomial frames.

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 \textit{polynomial frame} approximation or \textit{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 possibility 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 = c n \log(1/\epsilon) / \sqrt{\gamma^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 the 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.