Optimal approximation order of piecewise constants on convex partitions

Abstract

We prove that the error of the best nonlinear $L_p$-approximation by piecewise constants on convex partitions is $\mathcal{O}\left(N^{-\frac{2}{d+1}}\right)$, where $N$ the number of cells, for all functions in the Sobolev space $W_q^2(\Omega )$ on a cube $\Omega \subset {\mathbb{R}}^d$, $d⩾2$, as soon as $\frac{2}{d+1}+\frac{1}{p}-\frac{1}{q}⩾0$. The approximation order $\mathcal{O}\left(N^{-\frac{2}{d+1}}\right)$ is achieved on a polyhedral partition obtained by anisotropic refinement of an adaptive dyadic partition. Further estimates of the approximation order from the above and below are given for various Sobolev and Sobolev-Slobodeckij spaces $W_q^r(\Omega )$ embedded in $L_p(\Omega )$, some of which also improve the standard estimate $\mathcal{O}\left(N^{-\frac{1}{d}}\right)$ known to be optimal on isotropic partitions.

References in corpus (1)

• Exact asymptotics of the optimal Lp-error of asymmetric linear spline approximation