# 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?

• Could you clarify what you mean, perhaps in a simple example such as $\sin x$ on $[-1, 1]$ with $d=1$? From what I understand you can compute any $p_n$ you like, but never the function directly, and you want to estimate $\lvert f-p_n\rvert$ for a suitable norm. If you have no control on how fast $p_n$ converges to $f$, then there is no way to estimate $\lvert p_n-f\rvert$ in general. – Bruno Le Floch Nov 23 '14 at 4:04
• @BrunoLeFloch: Just added some background, hopefully it clarifies the difficulty. – ANSI C Mastah Nov 23 '14 at 5:33
• Thanks. I'm not knowledgeable on the subject matter, but the question is clearer now. – Bruno Le Floch Nov 23 '14 at 21:52