The Best Step Size

Finite-Difference Derivatives get better as $h$ shrinks, so why not take $h = 10^{-15}$? Because $f(x + h)$ and $f(x)$ become nearly equal, and subtracting them is Round-Off and Cancellation. Each stored value of $f$ has a rounding error of size about $\varepsilon|f|$ (with $\varepsilon \approx 10^{-16}$), and dividing their difference by a tiny $h$ magnifies that error.

For the forward difference (with $|f| \approx 1$ and $|f''| \le M$) the two errors add up to about $$E(h) = \underbrace{\frac{M}{2}h}_{\text{truncation}} + \underbrace{\frac{2\varepsilon}{h}}_{\text{round-off}}.$$ The first term falls as $h$ shrinks; the second grows.

Key idea

The total error is smallest at a moderate $h$. For the forward difference, $h^{*} = 2\sqrt{\varepsilon/M} \approx 10^{-8}$ and the best error is about $10^{-8}$: only half the digits survive. For the central difference, $h^{*} \approx (3\varepsilon/M)^{1/3} \approx 10^{-5}$ and the best error is about $\varepsilon^{2/3} \approx 10^{-11}$.

Why it works

Minimize $E(h) = \frac{M}{2}h + \frac{2\varepsilon}{h}$: $E'(h) = \frac{M}{2} - \frac{2\varepsilon}{h^{2}} = 0$ gives $h^{*} = 2\sqrt{\varepsilon/M}$, and then $E(h^{*}) = 2\sqrt{M\varepsilon}$, where the two parts are equal. For the central difference, $E(h) = \frac{M}{6}h^{2} + \frac{\varepsilon}{h}$ (now $M$ bounds $|f'''|$), and $E'(h) = \frac{M}{3}h - \frac{\varepsilon}{h^{2}} = 0$ gives $h^{*} = (3\varepsilon/M)^{1/3}$. A higher-order formula lets you stop at a larger $h$, before round-off has grown much.

The error of difference formulas for sin x at x = 1, over twelve decades of h. On the right, truncation falls with slope 1 or 2; on the left, round-off rises like ε/h.

Worked example: The best h for a forward difference

With $M = 1$ and $\varepsilon = 10^{-16}$, find $h^{*}$ and the best possible error.

$h^{*} = 2\sqrt{10^{-16}/1} = 2 \times 10^{-8}$.
$E(h^{*}) = 2\sqrt{1 \times 10^{-16}} = 2 \times 10^{-8}$.
So about 8 correct digits at best, however much effort goes in.

Answer: $h^{*} = 2 \times 10^{-8}$, error about $2 \times 10^{-8}$

Worked example: Real numbers

Forward and central differences for $f(x) = \sin x$ at $x = 1$ in double precision gave these errors. What do they show?

Forward: $h = 10^{-2}$: $4.2 \times 10^{-3}$; $10^{-4}$: $4.2 \times 10^{-5}$; $10^{-6}$: $4.2 \times 10^{-7}$; $10^{-8}$: $3 \times 10^{-9}$; $10^{-10}$: $6 \times 10^{-8}$; $10^{-12}$: $4 \times 10^{-5}$.
Central: $h = 10^{-2}$: $9 \times 10^{-6}$; $10^{-4}$: $9 \times 10^{-10}$; $10^{-6}$: $3 \times 10^{-11}$; then it grows again.
Down to $h = 10^{-6}$ the forward error falls by 100 per factor-of-100 step in $h$ (order 1). Below $10^{-8}$ it rises: at $h = 10^{-12}$ it is as bad as at $h = 10^{-4}$. The central difference bottoms out lower, near $h = 10^{-5}$ or $10^{-6}$.

Answer: a V shape, with its bottom near the predicted best h

Worked example: Round-off alone

How big is the round-off part $\frac{2\varepsilon}{h}$ at $h = 10^{-12}$?

$\frac{2 \times 10^{-16}}{10^{-12}} = 2 \times 10^{-4}$.
That matches the size of the observed error: at tiny $h$, almost everything you compute is round-off.

Answer: about $2 \times 10^{-4}$

Common mistake

Making $h$ as small as possible. Below the best $h$, the round-off error grows like $\varepsilon/h$ and swamps the answer; at $h = 10^{-15}$ the forward difference may have no correct digits at all. Check by trying a few values of $h$ a factor of 10 apart: if the answers stop agreeing as $h$ shrinks, you have passed the bottom of the V.

Sources and further reading

Tobin A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation (University of Delaware, free online edition): chapter "Piecewise interpolation", section "Convergence of finite differences" (round-off error)

MIT OpenCourseWare 18.330, Introduction to Numerical Analysis: lecture notes on numerical differentiation and round-off

The Best Step Size

Practice

Builds on

Leads to

Sources and further reading