You deserve better than two-sided finite differences

In calc 101, the derivative is derived as df/dx = \lim_{\epsilon \rightarrow 0} (f(x+\epsilon)-f(x))/\epsilon. So, if you want to estimate a derivative, an easy way to do so would be to just pick some small \epsilon and estimate:

df/dx \approx \frac{1}{\epsilon} (f(x+\epsilon)-f(x))

This can work OK. Let’s look at an example of trying to calculate the derivative of \log (x), using a range of different \epsilon

log_0.1_1sided

What’s happening? Well, the result is true mathematically in the limit that \epsilon is small, so it’s natural to get errors for large \epsilon. However, with very small \epsilon you run into trouble because floating-point arithmetic can only represent finite precision. Let’s try again with a smaller value of x=.001

log_0.001_1sided

That’s somewhat concerning. We can still get a nearly correct value, but we have a limited range of steps that achieve it. This is very well-known in numerical analysis, and a common solution is to use two-sided differences, i.e. to estimate

df/dx \approx \frac{1}{2 \epsilon} (f(x+\epsilon)-f(x-\epsilon)).

If we try that, we indeed get better results:

log_0.001_2sided

What’s happening here? Basically, we are using more information about the function to make a higher-order approximation, so we can mathematically get away with using a larger value of \epsilon. This in turn isis helpful to avoid the numerical precision demons.

Great! But let’s go deeper. If we use x = 10^{-5}, we get:

log_1e-05_2sided

Huh. 1-sided differences totally fall apart, but we seem to be running into more trouble. But never fear, you can use “four-sided differences”!

df/dx \approx \frac{1}{12 \epsilon} (-f(x+2\epsilon)+8 f(x+\epsilon)-8 f(x+\epsilon)+ f(x-2 \epsilon)

Then, we get what you might expect:

log_1e-05_4sided

But what if we go deeper, with x=10^{-7}?log_1e-07_4sided

Or maybe we should go even deeper, with x = 10^{-9}?

log_1e-09_4sided

Even the four-sided differences have failed us. Now, you might take a lesson here that you shouldn’t be using numerical differences (and I sort of agree). Those of certain temperament, on the other hand, would say instead that what we need is power. OK then, how do six-sided differences sound to you? Sound good?

df/dx \approx \frac{1}{60 \epsilon}(- f(x-3 \epsilon)+9 f(x-2 \epsilon)-45 f(x-\epsilon)+45 f(x+\epsilon)-9 f(x+2\epsilon)+f(x+3 \epsilon))

log_1e-09_6sided

This is still tough, but there is at least some range of epsilon where you can calculate a reasonable derivative. There is, of course, a never-ended sequence of these higher-order derivative approximations. There’s even a calculator, for all your bespoke finite-difference stencil needs.

Now, you might think that the real solution here is to use automatic differentiation, and you’re mostly right. It takes more computation to sample the function at more points, and no number of samples will fundamentally stop the numerical demons from destroying your result.

However, there still remain cases where it’s worthwhile to manually compute a derivative. More importantly perhaps, when you’re implementing an automatic differentiation tool, you still need to test that it is actually correct! Here, numerically differences will probably forever remain useful. So, certainly for the cases of building a test suite for autodiff code, it certainly makes sense to use these higher-order derivatives.

(I originally intended to leave this as a comment on Tim Viera’s post on testing gradient implementations, but this kinda got out of control.)

Advertisements
This entry was posted in Uncategorized and tagged , . Bookmark the permalink.

One Response to You deserve better than two-sided finite differences

  1. Pingback: The Secret Guild of Silicon Valley · Two Sided Finite Differences

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s