Question
Let $x \in [-1, 1]^d \subset \mathbb{R}^d$ be a $d$-dimensional variable and assume that -- given $n$ -- I have a way of computing a polynomial $p_n(x)$ of degree $n$ that approximates a smooth function $f(x)$ over that standard box. Assuming $d$ might be quite high, what would be a good and practical way to estimate the approximation error?
I am rather flexible when it comes to the metric used to measure the error, but the method should be (hopefully) fast and preferably deterministic.
Background
The need to estimate approximation error arises in an adaptive code: I am trying to construct a piecewise-polynomial approximation to a given $f(x)$. I am assuming that $f(x)$ is smooth and can be (at least) evaluated pointwise, but one could make stronger assumptions if that would help (e.g., requiring the ability to evaluate an arbitrary partial derivative of $f(x)$).
The method is $h$-adaptive, meaning that if the error over a box is judged to be too high, the box is divided into subboxes. Through profiling I found that the slowest part of my code -- also the one that has the highest chance of being optimized -- is the error estimation, thus the question: what would be a good way to do that?
The standard estimate of $|f(x)-p_n(x)|$ is useful for theoretical estimates, but does not work in practice as the number of partial derivatives of order $n+1$ is very high. One may instead attempt to find minimum/maximum of $g(x) = f(x) - p_n(x)$, but $g(x)$ has either lots of local extrema or has other nasty properties. Simply evaluating $|f(x)-p_n(x)|$ at some points is problematic, especially as the dimension $d$ increases.
Proposed solution and alternative question. One solution to my question is to use the approach used by some adaptive methods, such as the Runge-Kutta-Fehlenberg methods. We compute two approximations to $f(x)$, namely $p_{n-1}(x)$ and $p_n(x)$. Letting $q(x) = p_n(x) - p_{n-1}(x)$, a bound on $|q(x)|$ over the box $[-1, 1]^d$ yields an estimate of $|f(x) - p_n(x)|$. Is this a decent approach? If so, could you recommend an upper bound on the absolute value of a polynomial?
