Back to the on-screen lesson ·
Why the total error of a difference formula falls, bottoms out and climbs, and how to find the step where it is smallest.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to say which error dominates at a given step size, find the step that balances truncation against rounding, state the best accuracy a formula of a given order can reach in a given arithmetic, and recognise a run that has gone past the optimum.
You know that a difference formula's truncation error is proportional to a power of the step, and you know that subtracting nearly equal numbers destroys significant digits. This lesson is what happens when those two facts are applied to the same formula at the same time.
The truncation error comes from the formula and falls as the step falls. The rounding error comes from the arithmetic and, in a difference formula, rises as the step falls, because the subtraction cancels more digits. The optimal step is where the two are equal, and the achievable accuracy is the total error there.
A difference formula's total error has two parts pulling opposite ways. The truncation error of an order-$p$ formula is about $Ch^{p}$ and falls with $h$. The rounding error is about $\dfrac{\varepsilon|f|}{h}$ and rises as $h$ falls, because the formula subtracts two function values that agree in ever more digits and then divides by an ever smaller number. So the total error traces a U: it falls, bottoms out, and climbs. Setting the two equal gives the optimum $h \approx \varepsilon^{1/(p+1)}$, at which the total error is about $\varepsilon^{p/(p+1)}$. For a first-order formula in double precision that is $h \approx 10^{-8}$ and about eight correct digits — half the precision, spent on the method. For a second-order formula it is $h \approx 10^{-5}$ and about eleven digits: a larger step and a better answer, which is what pays for the extra evaluation. The practical recipe is to compute the optimum, then check it: halve the step once, and if the answer does not improve you were already past the bottom of the U.
Another way: picture
Plot the logarithm of the total error against the logarithm of the step. You see two straight lines meeting in a V — one of slope $p$ coming down from the right, one of slope $-1$ going up on the left — and the answer is the point of the V. Everything to the left of it is noise being divided by a small number.
Another way: steps
Shrinking the step shrinks the truncation error and grows the rounding error, so the total error falls, flattens and then climbs. A method that is more accurate on paper as the step goes to zero is describing a limit the arithmetic never reaches. The symptom is a routine that gets less accurate the harder it is asked to work, which reads as a bug and is not one. The test that distinguishes the two: recompute at a larger step. If the answer improves, nothing is broken and the step was past the optimum.
A forward difference has $p = 1$ and $\varepsilon \approx 10^{-16}$.
Balance $h$ against $10^{-16}/h$.
$h^{2} = 10^{-16}$, so $h \approx 10^{-8}$.
The optimal step.
The total error there is about $10^{-8}$: eight of the sixteen digits, and no smaller step recovers any of the rest.
Half the precision is the price.
A derivative estimate at $h = 10^{-12}$ disagrees with the one at $h = 10^{-6}$ in its third digit.
Which is wrong?
Recompute at $h = 10^{-8}$: it agrees with the $10^{-6}$ answer to eight digits.
The tiny step was the bad one.
The $10^{-12}$ run was dividing rounding noise by $10^{-12}$, and was the most careful and the least accurate of the three.
Effort spent past the optimum is spent backwards.
Balance $h^{4}$ against $10^{-15}/h$, so $h^{5} = 10^{-15}$.
That gives $h = 10^{-3}$.
And the error there is $h^{4} = 10^{-12}$: twelve of the fifteen digits, from a step a hundred thousand times larger than the first-order one.
A first-order difference formula has truncation error about $h$ and rounding error about $\dfrac{10^{-14}}{h}$. For each step size $h = 10^{-k}$ below, give the exponent $n$ for which the total error is about $10^{n}$.
| Value of k | Exponent of the total error | |
|---|---|---|
| A large step | 3 | |
| The balanced step | 7 | |
| A tiny step | 11 |
A forward difference is being used with $h = 10^{-4}$ and the answer is not accurate enough. Is taking $h$ very much smaller a good idea?
A difference formula is used at four different step sizes, or in four different settings. Match each to what limits its accuracy.
| Truncation error: the formula's own approximation | Rounding error: cancellation divided by a tiny step | The smallest total error this arithmetic allows | Nothing but truncation, so smaller really is better | |
|---|---|---|---|---|
| A step of about $10^{-1}$ | ||||
| A step of about $10^{-10}$ | ||||
| The step where the two errors are equal | ||||
| The same formula evaluated in exact arithmetic |
You must choose a step size for a difference formula in an arithmetic with about $13$ significant digits. Put the five steps into order.
Number the steps in order (write the number in the box):
A centred difference has truncation error about $h^{2}$ and rounding error about $\dfrac{10^{-15}}{h}$. The best step is $h = 10^{-k}$ and the smallest total error is about $10^{n}$. Give $k$ and $n$.
$k = $ k and $n = $ n
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A first-order formula has truncation error about $h$ and rounding error about $\dfrac{10^{-14}}{h}$. The best step is $h = 10^{-k}$. What is $k$?
Answer:
You can balance the two errors, find the optimal step and say what accuracy it buys. Say in your own words why a difference estimate can get worse when the step is made smaller.
8. Your turn: the optimal step for a fourth-order formula at $\varepsilon = 10^{-15}$, step 3