Automatic approximation using asymptotically optimal adaptive interpolation

We present an asymptotic analysis of adaptive methods for Lp approximation of functions f ∈ Cr([a, b]), where 1≤p≤+∞. The methods rely on piecewise polynomial interpolation of degree r − 1 with adaptive strategy of selecting m subintervals. The optimal speed of convergence is in this case of order m−r and it is already achieved by the uniform (nonadaptive) subdivision of the initial interval; however, the asymptotic constant crucially depends on the chosen strategy. We derive asymptotically best adaptive strategies and show their applicability to automatic Lp approximation with a given accuracy ε.