Back to the on-screen lesson ·
Why subtracting nearly equal numbers destroys the leading digits, how to count what is lost, and the rewrites that stop it happening.
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 spot a subtraction of nearly equal quantities, count the significant digits it destroys, and rewrite the expression — by conjugate, identity or factorisation — into a form that keeps them.
You know that the errors of a difference add absolutely while the difference itself can be tiny, so the relative error of a difference can be enormous even when both inputs are accurate. This lesson gives that its name and its cure.
Cancellation is what happens when a subtraction removes the leading digits two numbers share; it is catastrophic when the digits removed are most of the ones there were. A conjugate is the factor that turns a difference of square roots into a difference of their squares. An expression is stable here when no step of it subtracts two nearly equal quantities.
Subtracting two nearly equal numbers is the one floating-point operation that can turn a small relative error into a large one. Every operation is correct to within half an epsilon relative to its own result, and that promise is worthless when the result is far smaller than the operands. If $\hat{a}$ and $\hat{b}$ carry $d$ correct digits and agree in their first $k$, then $\hat{a} - \hat{b}$ carries about $d - k$: the shared digits subtract to zero, and the rounding noise that was sitting harmlessly in the last places is promoted into the leading ones. Nothing announces this. The answer prints with a full set of digits and most of them are fiction. The cure is algebraic, not arithmetic: find a form of the same quantity that never subtracts near-equals — a conjugate for $\sqrt{x+1} - \sqrt{x}$, an identity for $1 - \cos x$, the product of the roots for the small root of a quadratic, a purpose-written library routine for $e^{x} - 1$ and $\ln(1 + x)$. Where no such form exists, the only remaining option is to carry $k$ extra digits from the start.
Another way: steps
Another way: example
$x^{2} - 10^{8}x + 1 = 0$. The formula gives the small root as $\dfrac{10^{8} - \sqrt{10^{16} - 4}}{2}$, and the two terms agree in about sixteen digits, so in double precision it returns $0$. Compute the large root — no cancellation there — and use $x_1 x_2 = 1$: the small root is $10^{-8}$, to full precision.
It is tempting to think that because each operation is accurate to within an epsilon, a short chain of accurate operations must give an accurate answer. It does not follow. The guarantee is relative to each result, and a subtraction that produces a tiny result has a correspondingly tiny guarantee attached to it, while the errors it inherited from its operands are the size of their results. That is the whole of catastrophic cancellation, and it is why counting operations tells you nothing about accuracy.
With $x = 10^{8}$, $\sqrt{x + 1}$ and $\sqrt{x}$ agree to about eight digits.
The subtraction will cost those eight.
Sixteen stored digits less eight agreeing digits leaves about eight correct digits in the difference.
Half the precision, gone in one line.
Computing $\dfrac{1}{\sqrt{x+1} + \sqrt{x}}$ instead gives the same number with all sixteen.
The conjugate removes the subtraction.
The derivative estimate $\dfrac{f(x + h) - f(x)}{h}$ subtracts two values that agree more closely the smaller $h$ is.
Cancellation built into the formula.
No identity removes it, because the difference is what is being asked for.
The problem itself is the subtraction.
So $h$ cannot be taken to zero: past a point the cancellation grows faster than the formula improves.
This is the subject of a later lesson.
$\cos x$ is about $1 - 5 \times 10^{-9}$, so it agrees with $1$ in about eight digits.
Eight digits will cancel.
From sixteen stored digits that leaves about eight in the answer.
Writing it as $2\sin^{2}(x/2)$ squares a small accurate number instead, and keeps all sixteen.
Three pairs of numbers are each stored to $16$ significant digits. Each pair agrees in the number of leading digits shown. How many significant digits does each difference carry?
| Leading digits they agree on | Significant digits left | |
|---|---|---|
| Pair A | 1 | |
| Pair B | 6 | |
| Pair C | 7 |
For $x = 10^{7}$, the expressions $\sqrt{x + 1} - \sqrt{x}$ and $\dfrac{1}{\sqrt{x + 1} + \sqrt{x}}$ are equal as real numbers. What is true of them as computations?
Each expression below cancels badly at the size shown. Match it to the form that does not.
| $\dfrac{1}{\sqrt{x + 1} + \sqrt{x}}$, by the conjugate | $2\sin^{2}(x/2)$, by a half-angle identity | the library routine that takes $x$ and never forms the difference | the product of the roots, divided by the large root | |
|---|---|---|---|---|
| $\sqrt{x + 1} - \sqrt{x}$ for $x$ near $10^{12}$ | ||||
| $1 - \cos x$ for very small $x$ | ||||
| $e^{x} - 1$ for very small $x$ | ||||
| the small root of $x^{2} - bx + c$ with $b$ huge |
Here is a computation of $\sqrt{x + 1} - \sqrt{x}$ at $x = 10^{11}$, line by line. Mark the line at which the significant digits are lost.
This task has no paper form; do it on a device.
At $x = 10^{11}$ you compute $\sqrt{x + 1} - \sqrt{x}$ as $\dfrac{1}{\sqrt{x + 1} + \sqrt{x}}$ instead. How many significant digits does this second form lose to cancellation?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
You need the difference of two quantities that agree in their first $9$ significant digits, and you need that difference to $4$ correct significant digits. To how many significant digits must the two inputs be computed?
Answer:
You can find the cancelling subtraction in an expression, say how many digits it costs, and give a form that avoids it. Say in your own words why an error bound that holds for every single operation does not bound the error of the answer.
8. Your turn: $1 - \cos x$ at $x = 10^{-4}$, step 3