Foundations of numerical computing · Lecture 4

Errors and Their Propagation

Every numerical answer is wrong by some amount. We learn to measure that amount, predict how it grows, and avoid the one operation that destroys accuracy: subtracting nearly equal numbers.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Today's goals

Compute absolute, relative and percentage errors and count correct significant digits
Distinguish round-off error from truncation error, with examples of each
Use the error propagation rules for $+,-,\times,\div$ and the general formula
Recognise catastrophic cancellation and rewrite formulas to avoid it
Find the best step size when truncation and round-off errors compete

Last time

Round-off: relative error up to $10^{-16}$ per number (L2). Truncation: the first neglected Taylor term, $O(h^p)$ (L3).

Today

How do those tiny errors, plus the errors of stopping a method early, combine and grow through a calculation?

Foundations of numerical computing · you are here

L1 · Why Numerical Methods?→L2 · Floating-Point Numbers→L3 · Taylor Series and Order of Accuracy→L4 · Errors and Their Propagation→L5 · Conditioning and Stability

Builds on: L2, L3

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

2 / 17

Start here

The idea in one picture

Every numerical answer has two kinds of error.Truncation: we stopped a process early. A smaller step helps.Round-off: the computer keeps limited digits. A smaller step hurts.What we actually get is the red V: the bigger of the two.So "smaller h" is not always better: there is a best step size.

In plain words

Every computed answer is a little wrong: the question is how much
Two causes: stopping early (truncation) and limited digits (round-off)
Making one smaller can make the other bigger

New words today

absolute error: |true − approximate|
relative error: absolute error ÷ |true value|
significant digits: digits that carry real information
cancellation: losing digits when subtracting nearly equal numbers

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

3 / 17

Measuring error

True value $x$ , approximation $x^{*}$ .

Absolute error

E_a = |x - x^{*}|

Relative error

E_r = \dfrac{|x - x^{*}|}{|x|}

Percentage error

E_p = 100 \times E_r \,\%

Relative error is scale-free: an error of 1 cm in 1 km ( $10^{-5}$ ) is far better than 1 cm in 10 cm ( $10^{-1}$ ). Numerical analysts almost always report relative error.

Approximation of $\pi$	$E_a$	$E_r$
3.14	0.0015927	$5.07\times10^{-4}$
22/7 = 3.142857	0.0012645	$4.02\times10^{-4}$
3.1416	0.0000073	$2.34\times10^{-6}$

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

4 / 17

How many significant digits are correct?

Rule

x^{*} \text{ is correct to } n \text{ significant digits if } \; E_r \le \tfrac{1}{2}\times 10^{1-n}

Decimal places

x^{*} \text{ is correct to } d \text{ decimal places if } \; E_a \le \tfrac{1}{2}\times10^{-d}

$3.14$ : $E_r = 5.07\times10^{-4} \le 0.5\times10^{-2}$ ✓ but $> 0.5\times10^{-3}$ ✗: 3 significant digits
$3.1416$ : $E_a = 7.3\times10^{-6} \le 0.5\times10^{-4}$ : correct to 4 decimal places
Double precision: $E_r \le 1.1\times10^{-16}$ gives about 16
Iterations: stop when $|x_{k+1}-x_k| < \tfrac12\times10^{-d}$ for $d$ decimal places (Lecture 1)

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

5 / 17

Two sources of error in every computation

Lecture 2

Round-off error

From storing numbers with finitely many digits
Example: $\tfrac{2}{3} \to 0.6667$ , $\;0.1 \to 0.1000000000000000055\ldots$
Grows slowly with the number of operations
Reduced by higher precision (double, not float)

+

this course

Truncation error

From replacing an infinite or exact process by a finite one
Example: $e = 1 + 1 + \tfrac{1}{2!} + \tfrac{1}{3!} + \tfrac{1}{4!} = 2.708333$ , error $0.009948$
Stopping an iteration, a finite step $h$ , a cut series
Reduced by more terms, smaller $h$ , more iterations

Total error = round-off + truncation. Making $h$ smaller cuts truncation error but adds round-off error: a balance we measure later in this lecture and meet again in Lecture 19 (numerical differentiation).

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

6 / 17

How errors propagate through arithmetic

Inputs $x \pm \Delta x$ and $y \pm \Delta y$ . Worst-case (maximum) error of the result:

Sum and difference: absolute errors add

\Delta(x \pm y) \le \Delta x + \Delta y

Product and quotient: relative errors add

\frac{\Delta(xy)}{|xy|} \approx \frac{\Delta x}{|x|} + \frac{\Delta y}{|y|}, \qquad \frac{\Delta(x/y)}{|x/y|} \approx \frac{\Delta x}{|x|} + \frac{\Delta y}{|y|}

General function

\Delta f \approx \left|\frac{\partial f}{\partial x}\right|\Delta x + \left|\frac{\partial f}{\partial y}\right|\Delta y + \cdots

Powers: $\dfrac{\Delta(x^n)}{|x^n|} \approx |n|\,\dfrac{\Delta x}{|x|}$
The general formula comes from the first-order Taylor expansion (Lecture 3)
Danger: in $x - y$ the absolute error stays, but if $x - y$ is tiny the relative error explodes

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

7 / 17

Problem 1: relative error of a formula

Problem 1If

u = \dfrac{4x^2y^3}{z^4}

and the errors in

x, y, z

are each

0.001

, find the maximum relative error in

u

at

x = y = z = 1

.

1

Take logarithms:

\ln u = \ln 4 + 2\ln x + 3\ln y - 4\ln z

2

Differentiate:

\dfrac{\Delta u}{u} = 2\dfrac{\Delta x}{x} + 3\dfrac{\Delta y}{y} - 4\dfrac{\Delta z}{z}

3

Worst case: all terms add:

\left|\dfrac{\Delta u}{u}\right|_{\max} = 2\dfrac{0.001}{1} + 3\dfrac{0.001}{1} + 4\dfrac{0.001}{1}

4

= (2 + 3 + 4)\times 0.001 = 0.009

Maximum relative error

= 0.009

(0.9%). The powers multiply the relative errors:

z^4

contributes the most.

Second example

Rectangle area

$l = 10.0 \pm 0.05$ cm, $w = 5.0 \pm 0.05$ cm.
$A = 50$ cm²; $\Delta A \approx w\,\Delta l + l\,\Delta w = 0.25 + 0.5 = 0.75$ cm².
Relative: $0.5\% + 1\% = 1.5\%$ .

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

8 / 17

Catastrophic cancellation

Subtracting two nearly equal numbers cancels their leading digits; only the noisy trailing digits survive.

4-digit arithmetic: $\sqrt{1001} - \sqrt{1000} = 31.64 - 31.62 = 0.02$
True value $0.0158074$ : relative error 26.5%, from inputs accurate to 0.02%!
Rewrite (multiply by the conjugate): $\dfrac{1}{\sqrt{1001}+\sqrt{1000}} = \dfrac{1}{63.26} = 0.01581$ (error 0.01%)
The subtraction itself is exact; it exposes the earlier rounding errors

Digit view

31.6385…
− 31.6228…
= 00.0157…

In 4 digits: 31.64 − 31.62: the two shared digits "31.6" cancel, leaving one digit of noise.

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

9 / 17

Explore: naive vs rewritten formulas

$\dfrac{1-\cos x}{x^2}$ should be ≈ 0.5 for small $x$
Move $x$ towards $10^{-8}$ : the naive formula returns 0 (100% error)
Rewritten $\dfrac{2\sin^2(x/2)}{x^2}$ stays accurate
Try the other two expressions in the menu

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

10 / 17

Fixing the quadratic formula

Problem 2Solve

x^2 + 10^{8}x + 1 = 0

. The roots are about

-10^{8}

and

-10^{-8}

.

1

Naive small root:

x_1 = \dfrac{-10^8 + \sqrt{10^{16} - 4}}{2}

: two numbers that agree in about 16 digits are subtracted

2

Double precision gives

x_1 = -7.4506\times10^{-9}

: 25% wrong

3

Use

x_1 x_2 = c/a = 1

: compute the large root safely,

x_2 = \dfrac{-10^8 - \sqrt{10^{16}-4}}{2}

(no cancellation)

4

Then

x_1 = \dfrac{c}{a\,x_2} = \dfrac{2c}{-b - \sqrt{b^2-4ac}} = -1.0000\times10^{-8}

✓

Rule: compute the root where

-b

and

\pm\sqrt{b^2-4ac}

have the same sign, then the other from

x_1x_2 = c/a

.

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

11 / 17

Truncation and round-off together: $e^{-20}$ by Taylor series

$e^{x} = \sum x^n/n!$ converges for every $x$ (no truncation problem with enough terms)
For $x = -20$ the terms reach $4.3\times10^{7}$ with alternating signs: huge cancellation
The sum comes out wrong in every digit, even negative!
Cure: compute $1/e^{20}$ (all terms positive)

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

12 / 17

Truncation meets round-off: the best step size

$f'(x) \approx \dfrac{f(x+h) - f(x)}{h}$ (Lecture 3): truncation error ∝ $h$ (right side of the V)
But $f(x+h) - f(x)$ cancels: round-off error ≈ $\varepsilon / h$ grows as $h$ shrinks (left side)
Best forward $h \approx \sqrt{\varepsilon} \approx 10^{-8}$ ; best central $h \approx \varepsilon^{1/3} \approx 10^{-5}$
Smallest possible error: about $10^{-8}$ (forward), $10^{-11}$ (central)

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

13 / 17

Beyond the classroom

Where this shows up in CSE and machine learning

📊

Variance in one pass

$\sigma^2 = \overline{x^2} - \bar{x}^2$ cancels badly when the mean is large: data near $10^8$ give 22.0 instead of 22.5, and near $10^9$ the result is pure noise (it can even be negative). Libraries subtract the mean first (two passes) or use Welford's method.

🧠

Log-sum-exp and softmax

$\log\sum e^{z_i}$ is computed as $m + \log\sum e^{z_i - m}$ with $m = \max z_i$ : no overflow, no loss of digits.

🔊

Audio in decibels

Speech energy in dB uses $10\log_{10}(E + \epsilon)$ ; the small $\epsilon$ stops $\log 0$ on silent frames.

💰

Money

Banks never store taka as binary floats: 0.1 is inexact. They use integers (paisa) or decimal arithmetic.

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

14 / 17

Practice

Practice problem

Problem 3(a) Define absolute, relative and percentage errors. (b) If

\pi

is approximated by

3.14

, find the three errors. (c) Explain, with an example, why the subtraction of two nearly equal numbers causes loss of significant digits and how it can be avoided.

How to write a complete answer

Write each definition as a formula with a one-line meaning
Show substitution: $E_a = |3.1415927 - 3.14| = 0.0015927$ , $E_r = 0.0015927/3.1415927 = 5.07\times10^{-4}$ , $E_p = 0.0507\%$
Cancellation: use the 4-digit $\sqrt{1001} - \sqrt{1000}$ example; give both the wrong and the rewritten result
State the cure in general: rewrite with conjugates, trig identities, or series for small arguments

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

15 / 17

Checkpoint

Checkpoint · think, then discuss with your neighbourWhich expression is computed accurately in double precision for

x = 10^{-10}

?

A

\sqrt{1+x} - 1

B

\dfrac{x}{\sqrt{1+x} + 1}

C

(1+x) - 1

D

\dfrac{e^{x} - 1}{x}

B. It equals A exactly (multiply by the conjugate) but has no subtraction of nearly equal numbers. A, C and D all subtract 1 from a number very close to 1.

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

16 / 17

Summary

Key points

$E_a = |x - x^*|$ , $E_r = E_a/|x|$ , $E_p = 100E_r$ ; correct to $n$ significant digits if $E_r \le \tfrac12 10^{1-n}$
Round-off: finite digits. Truncation: finite process. Total error is both
Absolute errors add in $\pm$ ; relative errors add in $\times, \div$ ; powers multiply them
Subtracting nearly equal numbers destroys relative accuracy: rewrite the formula
Total error = truncation + round-off: a V shape in $h$ ; best $h \approx \sqrt{\varepsilon}$ (forward) or $\varepsilon^{1/3}$ (central)

Homework

Find $E_a$ , $E_r$ and $E_p$ when $\sqrt{2}$ is approximated by 1.414. How many significant digits are correct?
If $V = \pi r^2 h$ with $r = 2.0 \pm 0.01$ and $h = 5.0 \pm 0.02$ , find the maximum relative error in $V$ .
Rewrite $\ln(x+1) - \ln x$ for large $x$ to avoid cancellation. Test both forms in Python for $x = 10^{12}$ .
Lab: run the variance program and explain why the one-pass formula fails.

Next lecture

Conditioning and stability. Why some problems amplify every small error (and no algorithm can help), while some algorithms ruin perfectly good problems.

Md Mahbub E Noor

Lecture 4: Errors and Their Propagation

University of Barishal

17 / 17

Errors and Their Propagation

Today's goals

The idea in one picture

Measuring error

How many significant digits are correct?

Two sources of error in every computation

Round-off error

Truncation error

How errors propagate through arithmetic

Problem 1: relative error of a formula

Rectangle area

Catastrophic cancellation

Explore: naive vs rewritten formulas

Fixing the quadratic formula

Truncation and round-off together: e−20e^{-20}e−20 by Taylor series

Truncation meets round-off: the best step size

Where this shows up in CSE and machine learning

Variance in one pass

Log-sum-exp and softmax

Audio in decibels

Money

Practice problem

Checkpoint

Summary

Truncation and round-off together: $e^{-20}$ by Taylor series