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?

  • 3
    $\begingroup$ Are you trying to create a procedure for generating finite difference formula for arbitrary order of accuracy? The lower bounds come from considering a linear system which represent approximation conditions for a linear combination of values of $f$ with unknown coefficients. Your question reduces then to the question when the system has at least one solution. In simplest case of uniform mesh and arbitrary smooth $f$, $\Omega(k) \geq k + 1$ if you want at least 1st order of approximation. $\endgroup$ – VorKir Feb 7 '17 at 1:05

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.