3.1 Errors

Source: Numerical-error ideas from Computational Physics (Landau, Páez, Bordeianu), Chapter 3. Rewritten in original wording; the sine series and the four-digit $1/3$ identity are standard classroom calculations, not a transcription of the book.

A computer printout looks exact. It is not. Every number you get is some mix of what the mathematics asked for and what the machine and the algorithm could actually do. Before you trust a result — especially a long run — name the error families and estimate which one is in charge.

Bugs and sloppy algebra are still the first place to look. Once the program is the program you meant to write, three more families remain.

Random error

Uncontrolled physical events: a voltage hiccup, a cosmic-ray bit flip, someone pulling a plug. You do not choose when they happen. Their chance of showing up grows with wall-clock time. A twenty-second check can look rock solid; a week-long integration may need independent reruns before you believe it is reproducible.

That is the opposite of truncation and round-off, which (on the same binary and the same inputs) happen the same way every time.

Quiz

Random error

1 / 2

Why can a week-long run be less trustworthy than a 20-second one even if the code is unchanged?

Pick an answer to see if you are right.

Approximation (algorithmic) error

You almost never run the exact mathematics. Infinite series become finite sums, $dx$ becomes a step $h$, a function that varies is frozen as a constant for one slice. The gap between the true math and that finite recipe is approximation error — also called algorithmic error, because it lives in the method, not in the hardware.

The textbook example is the sine series, which is exact as an infinite sum and approximate once you stop at $N$ terms:

$$\begin{align*} \sin x &= \sum_{n=1}^{\infty} \frac{(-1)^{n-1} x^{2n-1}}{(2n-1)!} \\ &= \sum_{n=1}^{N} \frac{(-1)^{n-1} x^{2n-1}}{(2n-1)!} + \mathcal{E}(x,N). \end{align*}$$

$\mathcal{E}(x,N)$ is the ignored tail from $n=N+1$ onward. For a good algorithm that tail should shrink as $N$ grows and vanish as $N\to\infty$.

For this particular series the scale of $N$ is set by $x$: you need $N \gg |x|$. If $N$ and $|x|$ are comparable, the leftover is large even though the infinite series is perfect.

Theorem (truncation of a convergent scheme). If the discrete method is consistent with the mathematics, algorithmic error $\to 0$ as the discretization parameter $N\to\infty$. For the sine Taylor sum, that limit is useful in practice only when $N$ is much larger than $|x|$.

Quiz

Approximation error

1 / 3

Order the argument that a truncated sine series can still be accurate (top = start).

OrderDrag the handle to rearrange — top should be first.

1. ⋮⋮1The infinite sum equals $\sin x$ exactly
2. ⋮⋮2For this series the size of $N$ must be set by $x$: you need $N \gg |x|$
3. ⋮⋮3A good algorithm makes $\mathcal{E}\to 0$ as $N\to\infty$
4. ⋮⋮4The leftover $\mathcal{E}(x,N)$ is the tail from $N+1$ to $\infty$

Drag items into the correct order (or use ↑↓), then check.

Round-off error

Floating-point numbers keep finitely many digits. That is the same kind of limitation as a lab instrument with a finite number of significant figures: the value you store is close to the true value, not equal to it. Every extra arithmetic step is another chance to round, so the damage grows with the number of operations. Some methods amplify that noise and go unstable; when round-off is most of the answer, you are looking at garbage.

Toy machine with four digits after the decimal: $\frac{1}{3}$ becomes $0.3333$, $\frac{2}{3}$ becomes $0.6667$ (last digit rounded). Then

$$2\left(\frac{1}{3}\right) - \frac{2}{3} = 0.6666 - 0.6667 = -0.0001 \neq 0.$$

Mathematically the combination is zero. On that machine it is a tiny bias. Repeat the same pattern millions of times and the tiny bias is no longer tiny.

Quiz

Round-off error

1 / 2

On a 4-decimal toy machine, $2(1/3)-2/3$ fails to be 0 because…

Pick an answer to see if you are right.

How a float is stored

Write a large number in scientific notation so the exponent is a small integer and the mantissa carries the significant figures:

$$a = 9.8765432109876543 \times 10^{16}.$$

The exponent is cheap to keep exactly. The mantissa is not: any digits past what the format allows are thrown away (or rounded). Double precision keeps on the order of 15–16 decimal digits of $m$; a 6-digit toy word would keep only $9.87654$ and forget the rest. Relative error is $| \tilde a - a | / |a|$ — it falls as you keep more digits of $m$, and has nothing to do with how large $10^{e}$ is.

Slide the digit count in the chart. Watch the relative error drop, then flatten once you have kept everything the true value had.

Quiz

Stored floats and significant figures

1 / 2

Order how a large floating-point value is stored (top = first).

OrderDrag the handle to rearrange — top should be first.

1. ⋮⋮1Relative error is then |ã − a| / |a|, set by how many digits of m survived
2. ⋮⋮2Write a = m × 10^e so the exponent is a small integer
3. ⋮⋮3Digits of m beyond the format width are rounded or dropped
4. ⋮⋮4Store e at full precision (it is small)

Drag items into the correct order (or use ↑↓), then check.

Those discarded least-significant digits are not a curiosity. Once a word has a fixed width, every later arithmetic step works with a slightly wrong mantissa. Subtract two such words and you can throw away the accurate part on purpose.

3.1.1 Courting disaster: subtractive cancellation

A stored float is the exact value times $(1+\epsilon_x)$ with $|\epsilon_x|$ of order machine precision. Feed that model through a close subtraction $a=b-c$, then through a single quotient $b/c$. Walk each identity — at each step pick the matching equation (lookalikes included).

Theorem. If you subtract two large numbers and the result is small, that small number is less significant than either of the large ones.

You already met this in the sine series for large $x$: $x-x^3/3!+\cdots$ is a pile of big alternating terms whose true sum is only $\sin x\in[-1,1]$. The same trap sits in $e^{-x}\simeq 1-x+x^2/2!-\cdots$. A rewrite removes the cancellation: compute $e^{x}$ (all terms positive) and take the reciprocal. Round-off is still there; you just stopped manufacturing a tiny answer out of two giants.

Quiz

Subtractive cancellation

1 / 3

Order why a small difference of two large floats is untrustworthy (top = start).

OrderDrag the handle to rearrange — top should be first.

1. ⋮⋮1When $b\simeq c$, the leading digits cancel and $a$ is small
2. ⋮⋮2The leftover $a$ is assembled from the least-significant bits
3. ⋮⋮3The factor $b/a$ multiplies whatever relative noise did not cancel
4. ⋮⋮4Each stored value is $x_c\simeq x(1+\epsilon_x)$

Drag items into the correct order (or use ↑↓), then check.

3.1.2 Subtractive-cancellation labs

Quadratic formula

$ax^{2}+bx+c=0$ has two algebraically equal closed forms. When $b^{2}\gg 4ac$, $\sqrt{\Delta}\approx|b|$, so one of the $\pm$ textbook roots cancels. Walk which form subtracts and how Vieta recovers the tiny root — pick among lookalikes.

A clean test family is $a=1$, $b=1$, $c=10^{-n}$ as $n$ grows.

Activity: Stable quadratic roots

Input: three floats a b c (two distinct real roots). Print the smaller-magnitude root in scientific notation with 6 digits after the decimal (:.6e). Use a method that still works when $b^{2}\gg 4ac$.

The chart below is the log–log picture the $S^{(1)}$ vs $S^{(3)}$ lab is after: relative error versus $N$, with $S^{(3)}$ as the reference. A straight stretch means the error is a power of $N$. The vertical coordinate is (minus) a count of surviving significant figures.

Adding $1/n$ upward dumps small terms into a mantissa that is already full; downward parks the large terms last. That is why $S^{\mathrm{down}}$ is usually the more precise of the two, even though the sums are identical on paper.

3.1.3 Round-off in one product, quotient, or function

The guide above already walked the product/quotient worst-case sum $|\epsilon_b|+|\epsilon_c|$. Multiplication obeys the same rule: add the relative uncertainties.

For a smooth $f$, the gap between $f(x)$ and $f(x_c)$ is first-order

$$\mathcal{E}\simeq\frac{f'(x)}{f(x)}(x-x_c).$$

On $f(x)=\sqrt{1+x}$ that is $\mathcal{E}\simeq (x-x_c)/(2(1+x))$. Near $x=\pi/4$ a fourth-place error in $x$ stays a fourth-place error in $f$ — the derivative is not an amplifier here.

Quiz

Propagating round-off

1 / 2

Worst-case relative error in $b/c$ or $bc$ is…

Pick an answer to see if you are right.

3.1.4 Round-off error accumulation

One rounding event is a tiny step of length $\epsilon_m$. After $N$ steps, if those steps point in random directions, the typical net displacement of a random walk is

$$R\simeq\sqrt{N}\,r \qquad\Rightarrow\qquad \epsilon_{\mathrm{ro}}\simeq\sqrt{N}\,\epsilon_m.$$

If the errors refuse to cancel, a sober backup is the coherent bound $N\epsilon_m$. Worse: some upward recurrences (spherical Bessel functions are the usual exhibit) let the error grow like $N!$. Those need a separate analysis — the $\sqrt{N}$ cartoon does not apply.

Quiz

Accumulating round-off

1 / 2

If each step’s rounding error is a random ±ε_m, the typical relative error after N steps scales as…

Pick an answer to see if you are right.

Which family is it?

Same program can carry all three. Name the dominant one before you “fix” the wrong knob.

Quiz

Checking a numerical result

1 / 1

Order a sane check of a long numerical job (top = first).

OrderDrag the handle to rearrange — top should be first.

1. ⋮⋮1If the method uses a cutoff N or step h, raise N (or cut h) and see the answer settle
2. ⋮⋮2If the job ran a long time, rerun it and compare (random error)
3. ⋮⋮3Estimate whether the operation count could have let round-off take over
4. ⋮⋮4Separate bugs from numerical error: is this even the intended algorithm?

Drag items into the correct order (or use ↑↓), then check.

Next: 3.2 Experimental error investigation.