5
$\begingroup$

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?

  • 1
    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)$.2012-04-11

1 Answers 1

5

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...)