Alexei Shadrin

Ben Adcock, Anders C. Hansen, Alexei Shadrin

We prove that any stable method for resolving the Gibbs phenomenon - that is, recovering high-order accuracy from the first $m$ Fourier coefficients of an analytic and nonperiodic function - can converge at best root-exponentially fast in $m$. Any method with faster convergence must also be unstable, and in particular, exponential convergence implies exponential ill-conditioning. This result is analogous to a recent theorem of Platte, Trefethen & Kuijlaars concerning recovery from pointwise function values on an equispaced $m$-grid. The main step in our proof is an estimate for the maximal behaviour of a polynomial of degree $n$ with bounded $m$-term Fourier series, which is related to a conjecture of Hrycak & Groechenig. In the second part of the paper we discuss the implications of our main theorem to polynomial-based interpolation and least-squares approaches for overcoming the Gibbs phenomenon. Finally, we consider the use of so-called Fourier extensions as an attractive alternative for this problem. We present numerical results demonstrating rapid convergence in a stable manner.

Ben Adcock, Rodrigo Platte, Alexei Shadrin

We consider the problem of approximating an analytic function on a compact interval from its values at $M+1$ distinct points. When the points are equispaced, a recent result (the so-called impossibility theorem) has shown that the best possible convergence rate of a stable method is root-exponential in $M$, and that any method with faster exponential convergence must also be exponentially ill-conditioned at a certain rate. This result hinges on a classical theorem of Coppersmith & Rivlin concerning the maximal behaviour of polynomials bounded on an equispaced grid. In this paper, we first generalize this theorem to arbitrary point distributions. We then present an extension of the impossibility theorem valid for general nonequispaced points, and apply it to the case of points that are equidistributed with respect to (modified) Jacobi weight functions. This leads to a necessary sampling rate for stable approximation from such points. We prove that this rate is also sufficient, and therefore exactly quantify (up to constants) the precise sampling rate for approximating analytic functions from such node distributions with stable methods. Numerical results -- based on computing the maximal polynomial via a variant of the classical Remez algorithm -- confirm our main theorems. Finally, we discuss the implications of our results for polynomial least-squares approximations. In particular, we theoretically confirm the well-known heuristic that stable least-squares approximation using polynomials of degree $N < M$ is possible only once $M$ is sufficiently large for there to be a subset of $N$ of the nodes that mimic the behaviour of the $N$th set of Chebyshev nodes.

Alexei Shadrin

The Landau-Kolmogorov problem consists of finding the upper bound $M_k$ for the norm of intermediate derivative $|f^{(k)}|$, when the bounds $|f| \le M_0$ and $|f^{(n)}| \le M_n$, for the norms of the function and of its higher derivative, are given. Here, we consider the case of a finite interval, and when all the norms are the max-norms. Our interest to that particular case is motivated by the fact that there are good chances to add this case to a short list of Landau--Kolmogorov inequalities where a complete solution exists, i.e., a solution that covers all values of $n,k\in\N$ (and, for a finite interval, all values of $σ= M_n/M_0$). The main guideline here is Karlin's conjecture that says that, for all $n,k\in\N$ and all $σ>0$, the maximum of $|f^{(k)}|$ is attained by a certain Chebyshev or Zolotarev spline. So far, it has been proved only for small $n \ge 4$ with all $σ$, and for all $n$ with particular $σ= σ_n$. Here, we prove Karlin's conjecture in several further subcases: 1) all $n,k\in\N$ and all $0 < σ\le σ_n$ 2) all $n \in \N$, all $σ> 0$, with $k=1,2$ 3) all $σ> 0$, with $n < 10$ and $0 < k < n$.

Geno Nikolov, Alexei Shadrin

We are continuing out studies of the so-called Markov inequalities with a majorant. Inequalities of this type provide a bound for the $k$-th derivative of an algebraic polynomial when the latter is bounded by a certain curved majorant $μ$. A conjecture is that the upper bound is attained by the so-called snake-polynomial which oscillates most between $\pm μ$, but it turned out to be a rather difficult question. In the previous paper, we proved that this is true in the case of symmetric majorant provided the snake-polynomial has a positive Chebyshev expansion. In this paper, we show that that the conjecture is valid under the condition of positive expansion only, hence for non-symmetric majorants as well.