1. Sources of Error

In scientific computing, errors arise from multiple sources. Understanding these sources is the first step toward controlling them.

Definition 1.1: Types of Errors

Model Error: Simplifications made when creating a mathematical model of a physical problem.
Measurement Error: Imprecision in measuring physical quantities or input data.
Truncation Error: Error from approximating an infinite process with a finite one (e.g., truncating a Taylor series).
Rounding Error: Error from representing real numbers with finite precision (floating-point representation).

Example: Truncation vs Rounding Error

Consider computing $e^x$ using the Taylor series:

e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots

Truncation error: Stopping after n terms introduces error from the omitted terms.
Rounding error: Each arithmetic operation introduces small errors due to finite precision.

2. Absolute and Relative Error

Definition 1.2: Absolute Error

Let $x$ be the exact value and $\hat{x}$ be an approximation. The absolute error is:

e = \hat{x} - x

The absolute error bound (or error limit) $\varepsilon$ satisfies $|e| = |\hat{x} - x| \leq \varepsilon$ .

Definition 1.3: Relative Error

The relative error is the ratio of absolute error to the exact value:

e_r = \frac{\hat{x} - x}{x} = \frac{e}{x}, \quad x \neq 0

In practice, since $x$ is unknown, we often use $e_r \approx \frac{\hat{x} - x}{\hat{x}}$ when the error is small.

Example: Computing Errors

Problem: If $x = \pi$ and $\hat{x} = 3.14$ , find the errors.

Solution:

Absolute error: $e = 3.14 - 3.14159... = -0.00159...$

Relative error: $e_r = \frac{-0.00159}{3.14159} \approx -0.000507 \approx -0.05\%$

Remark:

Relative error is often more meaningful than absolute error. An absolute error of 1 meter is negligible when measuring the distance to the Moon, but catastrophic when measuring the width of a human hair.

3. Significant Digits

Definition 1.4: Significant Digits

A digit in a number is significant if its error bound is at most half a unit in that digit position. The significant digits are counted from the first non-zero digit to the last reliable digit.

Equivalently, if $\hat{x}$ is written in scientific notation as $\hat{x} = \pm d_1.d_2d_3...d_n \times 10^m$ where $d_1 \neq 0$ , then $\hat{x}$ has n significant digits if:

|\hat{x} - x| \leq \frac{1}{2} \times 10^{m-n+1}

Example: Counting Significant Digits

$123.45$ has 5 significant digits

$0.00456$ has 3 significant digits (leading zeros don't count)

$1.200$ has 4 significant digits (trailing zeros after decimal count)

$1200$ has 2, 3, or 4 significant digits (ambiguous without context)

Theorem 1.1: Significant Digits and Relative Error

If $\hat{x}$ approximates $x$ with n significant digits, then the relative error satisfies:

|e_r| \leq \frac{1}{2} \times 10^{-(n-1)}

4. Error Propagation

When we perform arithmetic operations on approximate numbers, errors propagate. Understanding this propagation is essential for error analysis.

Theorem 1.2: Error Propagation in Arithmetic

Let $\hat{x}$ and $\hat{y}$ be approximations with absolute errors $\Delta x$ and $\Delta y$ . Using differential analysis:

Addition/Subtraction: $\Delta(x \pm y) = \Delta x \pm \Delta y$

Multiplication: $\Delta(xy) \approx y \Delta x + x \Delta y$

Division: $\Delta(x/y) \approx \frac{y \Delta x - x \Delta y}{y^2}$

Theorem 1.3: Relative Error Propagation

For relative errors $\delta_x$ and $\delta_y$ :

Addition: $\delta_{x+y} \approx \frac{|x|\delta_x + |y|\delta_y}{|x+y|}$

Subtraction: $\delta_{x-y} \approx \frac{|x|\delta_x + |y|\delta_y}{|x-y|}$ (can be large!)

Multiplication/Division: $\delta_{xy} \approx \delta_{x/y} \approx \delta_x + \delta_y$

Note:

For subtraction of nearly equal numbers, $|x-y|$ is small, making the relative error potentially very large. This is called catastrophic cancellation.

Theorem 1.4: Function Evaluation Error

For a function $f(x)$ with input error $\Delta x$ :

\Delta f(x) \approx f'(x) \Delta x

The relative error is:

\delta_f = \frac{\Delta f}{f} \approx \frac{xf'(x)}{f(x)} \cdot \delta_x

The factor $\frac{xf'(x)}{f(x)}$ is called the condition number of the function.

5. Machine Precision and Floating-Point

Definition 1.5: Machine Epsilon

Machine epsilon ( $\varepsilon_{mach}$ ) is the smallest positive number such that $1 + \varepsilon_{mach} \neq 1$ in floating-point arithmetic.

For IEEE 754 double precision: $\varepsilon_{mach} \approx 2.22 \times 10^{-16}$

Example: Floating-Point Representation

In IEEE 754 double precision (64 bits):

1 bit for sign
11 bits for exponent (range roughly $10^{-308}$ to $10^{308}$ )
52 bits for mantissa (about 15-16 decimal digits of precision)

Remark:

The relative error in representing any real number x as a floating-point number fl(x) satisfies $|fl(x) - x|/|x| \leq \varepsilon_{mach}$ .

6. Techniques to Reduce Errors

1. Avoid Subtracting Nearly Equal Numbers

Reformulate expressions to avoid catastrophic cancellation.

Example: Instead of $\sqrt{1+x} - 1$ for small x, use $\frac{x}{\sqrt{1+x} + 1}$

2. Prevent Large Numbers from Swamping Small Numbers

When summing numbers of vastly different magnitudes, sum from smallest to largest.

Example: Computing $\sum_{i=1}^{n} a_i$ where $a_1 \ll a_n$

3. Reduce the Number of Operations

Each operation introduces rounding error. Use efficient algorithms.

Example: Horner's method for polynomials: $P(x) = ((a_n x + a_{n-1})x + \cdots)x + a_0$

4. Avoid Division by Small Numbers

Division by a small number amplifies errors. Rearrange formulas when possible.

5. Use Stable Formulas

Choose mathematically equivalent formulas that are numerically more stable.

Example: For the quadratic formula with $b^2 \gg 4ac$ , use $x_1 = \frac{-b - \text{sign}(b)\sqrt{b^2-4ac}}{2a}$ , then $x_2 = \frac{c}{ax_1}$

7. Numerical Stability

Definition 1.6: Numerical Stability

A numerical algorithm is stable if small perturbations in the input (or rounding errors during computation) produce only small changes in the output.

An algorithm is unstable if small errors can grow exponentially during computation.

Example: Stable vs Unstable Recurrence

Consider computing $I_n = \int_0^1 x^n e^x dx$ using the recurrence:

I_n = e - n I_{n-1}

Forward recurrence (starting from $I_0 = e-1$ ):

Errors grow because we multiply the error by n at each step. Unstable!

Backward recurrence (starting from large n):

I_{n-1} = \frac{e - I_n}{n}

Errors shrink because we divide by n at each step. Stable!

Remark:

A good numerical algorithm should be both efficient and stable. Sometimes there is a trade-off between the two, and stability should usually take priority.

Practice Quiz

Error Analysis Quiz

10

Questions

0

Correct

0%

Accuracy

1

If the exact value is

x = 3.14159

and the approximation is

\hat{x} = 3.14

, what is the absolute error?

Easy

Not attempted

2

The relative error of approximating

\pi \approx 3.14

is approximately:

Easy

Not attempted

3

The number

0.003456

has how many significant digits?

Easy

Not attempted

4

When subtracting two nearly equal numbers, the primary concern is:

Medium

Not attempted

5

If

f(x) = x^2

and

x

has relative error

\epsilon_r

, what is the approximate relative error in

f(x)

?

Medium

Not attempted

6

Machine epsilon for IEEE double precision is approximately:

Medium

Not attempted

7

To compute

\sqrt{1+x} - 1

for small

x

with better numerical stability, one should use:

Hard

Not attempted

8

A numerical algorithm is called stable if:

Medium

Not attempted

9

When computing

e^x - 1

for small

x

, the direct computation suffers from:

Hard

Not attempted

10

If

\epsilon(x)

is the absolute error in

x

and

\epsilon(y)

is the absolute error in

y

, the absolute error in

x \cdot y

is approximately:

Hard

Not attempted

Frequently Asked Questions

What's the difference between truncation error and rounding error?

Truncation error comes from approximating a mathematical process (like using a finite number of terms in a series). It exists even with infinite precision.

Rounding error comes from representing numbers with finite precision. It's inherent to computer arithmetic.

How do I know if my algorithm is numerically stable?

Test your algorithm with:

Slightly perturbed inputs - do outputs change only slightly?
Compare results at different precisions (float vs double)
Check if the backward error is small (is the computed solution exact for a nearby problem?)

Why is subtraction more dangerous than addition?

When subtracting nearly equal numbers, the leading significant digits cancel, leaving only the less significant (more error-prone) digits. This "catastrophic cancellation" can cause huge relative errors even when absolute errors are small.

What is the condition number of a problem?

The condition number measures how sensitive a problem's output is to small changes in the input. A problem with large condition number is ill-conditioned.

For a function $f(x)$ , the condition number is approximately $|xf'(x)/f(x)|$ .

How many significant digits should I report?

Report only the digits you're confident about. If your computation has relative error of about $10^{-6}$ , you should report about 6 significant digits. Reporting more implies false precision.

Error Analysis and Numerical Stability

1. Sources of Error

Definition 1.1: Types of Errors

Example: Truncation vs Rounding Error

2. Absolute and Relative Error

Definition 1.2: Absolute Error

Definition 1.3: Relative Error

Example: Computing Errors

Remark:

3. Significant Digits

Definition 1.4: Significant Digits

Example: Counting Significant Digits

Theorem 1.1: Significant Digits and Relative Error

4. Error Propagation

Theorem 1.2: Error Propagation in Arithmetic

Theorem 1.3: Relative Error Propagation

Note:

Theorem 1.4: Function Evaluation Error

5. Machine Precision and Floating-Point

Definition 1.5: Machine Epsilon

Example: Floating-Point Representation

Remark:

6. Techniques to Reduce Errors

1. Avoid Subtracting Nearly Equal Numbers

2. Prevent Large Numbers from Swamping Small Numbers

3. Reduce the Number of Operations

4. Avoid Division by Small Numbers

5. Use Stable Formulas

7. Numerical Stability

Definition 1.6: Numerical Stability

Example: Stable vs Unstable Recurrence

Remark:

Practice Quiz

Frequently Asked Questions

What's the difference between truncation error and rounding error?

How do I know if my algorithm is numerically stable?

Why is subtraction more dangerous than addition?

What is the condition number of a problem?

How many significant digits should I report?