Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

When using numerical analysis, I often find that I am required to estimate a derivative (e.g. when using Newton Iteration for finding roots). To estimate the first derivative of a function $f(x)$ at a point $x_0$ (assuming that $f(x)$ is continuous at $x_0$), one can use the slightly-modified (to avoid bias to one side) first principles formula for derivatives, shown below.

For small $h$:

$$f'(x_0)\approx\frac{f(x+h)-f(x-h)}{2h}\tag{1}$$

Using this method, we can estimate $f^{(n)}(x)$ recursively with, for sufficiently small $h$:

$$f^{(n)}(x_0)\approx\frac{f^{(n-1)}(x+h)-f^{(n-1)}(x-h)}{2h}\tag{2}$$

The problem I have with $(2)$ is that each recursion produces a loss of accuracy that builds up. As well, to estimate $f^{(n)}(x_0)$, the function $f(x)$ is required to be computed $2^n$ times.

Is $(2)$ the best method for approximating the $n^{th}$ derivative of $f(x_0)$ numerically or are there more efficient methods?

share|improve this question
3  
2  
This is related to William's suggestion. The standard method is, more or less, to fix the same $h$ and use it for all of the derivatives. If nothing else, this means that you only have to compute $f$ at $O(n)$ points, since there will be a lot of redundancies. Likewise, doing the computation theoretically (with formulas) and then plugging in the resulting formula yields a drastic speedup in computational speed. –  Charles Staats Apr 10 '12 at 22:47
1  
The formula you gave requires $2n+1$ function evaluations to estimate $f^{(n)}(x)$, not $2^n$. –  copper.hat Apr 10 '12 at 23:44
    
In fact, only $n+1$ evaluations are required. Induction gives: $f^{(n)}(x)\approx \frac{1}{(2h)^n} \sum_{k=0}^n \binom{n}{k} (-1)^k f(x+(n-2k)h)$. –  copper.hat Apr 11 '12 at 5:38
add comment

1 Answer 1

up vote 3 down vote accepted

Yes, there are much better methods for computing $n$-th derivatives than simple-minded finite differences. I mentioned some of them in this MO answer.

Briefly: one could pick from

  1. Richardson extrapolation of a suitable sequence of finite difference estimates (discussed in these two papers).
  2. Cauchy's differentiation formula: $$f^{(n)}(a)=\frac{n!}{2\pi i}\oint_\gamma \frac{f(z)}{(z-a)^{n+1}}\mathrm dz $$
  3. Lanczos's formula: $$f^{(n)}(a)=\lim_{h\to 0}\frac{(2n+1)!}{2^{n+1}n!h^n}\int_{-1}^1 f(a+hu)P_n(u)\mathrm du$$

where $P_n(x)$ is a Legendre polynomial.


Even simple-minded finite differences can be saved somewhat; for instance, in the case of the first derivative, when one uses central differences

$$f^\prime (x)\approx\frac{f(x+h)-f(x-h)}{2h}$$

one good choice of $h$, due to Nash, takes $h=\sqrt{\varepsilon}\left(|x|+\sqrt{\varepsilon}\right)$ where $\varepsilon$ is machine epsilon. (I had previously mentioned this in one of OP's previous questions...)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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