Lower bounds for finite difference formulas

Question

I'm interested in approximating higher derivatives of a function via values of the function only. I guess the following question has been studied, but I haven't been able to find a reference. I know that one can, via repeated application of the finite difference formula $$f'(x)\approx \frac{f(x+\delta)-f(x)}{\delta}$$ approximate the higher derivatives using equally spaced nodes as $$f^{(k)}(x)\approx \frac{1}{\delta^k}\left(\sum_{i=0}^k(-1)^i{k\choose i}f(x+(k-i)\delta)\right)$$

and that under appropriate assumptions on $f$ this can be made provably close to the actual $f^{(k)}(x)$ in a quantitative way (depending on $\delta$) (of course, without assumptions, the derivative can be made to be anything we want by Hermite interpolation).

But is there a place discussing the need for $\Omega(k)$ calls to $f$, or providing some sort of lower bound?

Answer 1

I believe you are asking the following:

What is the minimum number of evaluations of $f$ required to approximate $f^{(k)}$ to order of accuracy $p$?

In fact, this is a homework problem I often give during the first week of a numerical analysis course. The answer is that generically you need $k-p+1$ evaluations; as @VorKir mentions, this can be seen by considering the system of equations that the coefficients of the finite difference formula must satisfy (which is a Vandermonde system).

There is one caveat: if your evaluation points are symmetric about some value $x_0$, then your approximation to $f^{(k)}$ at $x_0$ can be of one order higher.