1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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
    Commented Feb 7, 2017 at 1:05

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .