From the free course Numerical Analysis and Computational Methods on Lykke
Mathematical Foundations and Error Analysis
Key concepts: Floating-Point Arithmetic · Truncation Error · Rounding Error · Absolute vs. Relative Error
Exploration of how computers represent numbers and the various types of errors that arise during numerical calculations.
Mathematical Foundations and Error Analysis
Numerical analysis is the bridge between the infinite precision of theoretical mathematics and the finite constraints of physical hardware. While a mathematician might comfortably work with the transcendental number $\pi$ or the infinite series for $e^x$, a computer scientist must grapple with the reality that a CPU can only represent a sliver of the real number line. This section explores the fundamental limitations of digital computation, the taxonomy of errors that arise during calculation, and the rigorous mathematical frameworks used to bound these errors.
Floating-Point Arithmetic
At the core of modern computing lies the Floating-Point Representation. Unlike fixed-point arithmetic, which allocates a set number of digits for the integer and fractional parts, floating-point arithmetic allows the "point" to move, providing a wide dynamic range that can represent both the diameter of an atom and the distance to a distant galaxy using the same number of bits.
The IEEE 754 Standard
Most modern systems adhere to the IEEE 754 standard, which defines how floating-point numbers are stored in binary. A number $x$ is typically represented in the form:
Definition: Floating-Point Normalized Form $$x = \pm (1.f) \times 2^{E - bias}$$ Where:
- $s$ (Sign bit): Determines if the number is positive (0) or negative (1).
- $f$ (Fraction/Mantissa): The fractional part of the significand. The "1." is implicit in normalized numbers to save a bit.
- $E$ (Exponent): An unsigned integer that is shifted by a bias to allow for negative exponents.
| Feature | Single Precision (32-bit) | Double Precision (64-bit) |
|---|---|---|
| Sign Bit | 1 bit | 1 bit |
| Exponent | 8 bits | 11 bits |
| Mantissa | 23 bits | 52 bits |
| Bias | 127 | 1023 |
| Approx. Range | $10^{-38}$ to $10^{38}$ | $10^{-308}$ to $10^{308}$ |
| Decimal Digits | ~7 | ~15-17 |
Machine Epsilon ($\epsilon_{mach}$)
The most critical constant in numerical analysis is Machine Epsilon. It represents the upper bound on the relative error due to rounding in floating-point arithmetic.
Theorem: Machine Epsilon Machine epsilon is the smallest positive number $\epsilon$ such that $1 + \epsilon \neq 1$ in the computer's floating-point representation. For a system with $t$ bits in the mantissa, $\epsilon_{mach} \approx 2^{-t}$.
In Python, which uses double precision (64-bit) by default for floats, $\epsilon_{mach}$ is approximately $2.22 \times 10^{-16}$. This means that any calculation involving numbers of vastly different scales (e.g., adding $10^{16}$ and $1$) will result in the smaller number being "swallowed" by the larger one.
# Demonstrating Machine Epsilon in Python
x = 1.0
epsilon = 1.0
while 1.0 + epsilon != 1.0:
last_epsilon = epsilon
epsilon /= 2.0
print(f"Calculated Machine Epsilon: {last_epsilon}")
# Output: 2.220446049250313e-16
Rounding Error and Precision Limits
Rounding Error occurs because the set of representable floating-point numbers is discrete and finite. When a real number $x$ cannot be represented exactly, the system must choose a nearby representable number $fl(x)$.
Mechanisms of Rounding
There are two primary ways a system handles numbers it cannot represent exactly:
- Chopping (Truncation): Simply discarding all bits beyond the available precision. This is computationally cheap but introduces a significant bias.
- Rounding to Nearest: Choosing the representable value closest to the true value. This is the default behavior for IEEE 754.
| Method | Mathematical Logic | Maximum Error |
|---|---|---|
| Chopping | $fl(x) = x$ truncated | $\epsilon_{mach}$ |
| Rounding | $fl(x) = \text{nearest } \hat{x}$ | $\frac{1}{2}\epsilon_{mach}$ |
Catastrophic Cancellation
One of the most dangerous forms of rounding error is Loss of Significance, often called Catastrophic Cancellation. This occurs when subtracting two nearly equal numbers. Because the leading digits of both numbers match, they cancel out, leaving only the "garbage" digits (the rounding errors) in the result.
Worked Example: Quadratic Formula Consider solving $ax^2 + bx + c = 0$ where $b^2 \gg 4ac$. If $b = 1000.000$ and $4ac = 0.0001$, then $\sqrt{b^2 - 4ac}$ is very close to $b$. Subtracting $-b + \sqrt{b^2 - 4ac}$ will lead to a massive loss of precision. Numerical software often uses an alternative form: $$x_1 = \frac{-2c}{b + \sqrt{b^2 - 4ac}}$$ to avoid this subtraction.
Truncation Error and Taylor Series
While rounding error is a byproduct of hardware, Truncation Error is a byproduct of the algorithm. It is the error introduced by approximating a continuous mathematical process with a finite one.
The Taylor Series Foundation
Most numerical methods (differentiation, integration, root-finding) are derived from the Taylor Series Expansion.
Taylor's Theorem If a function $f(x)$ is $n+1$ times continuously differentiable on an interval containing $a$, then for any $x$ in the interval: $$f(x) = \sum_{k=0}^{n} \frac{f^{(k)}(a)}{k!}(x-a)^k + R_n(x)$$ where $R_n(x)$ is the Remainder Term (the truncation error): $$R_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}(x-a)^{n+1}$$ for some $\xi$ between $a$ and $x$.
Big O Notation and Convergence
We quantify truncation error using Big O Notation, which describes how the error scales as the step size $h$ (where $h = x - a$) approaches zero.
- If $Error \approx Ch^k$, we say the method is $k$-th order accurate, written as $O(h^k)$.
- A higher order means the error drops much faster as we increase the resolution (decrease $h$).
| Method | Order | Error Scaling |
|---|---|---|
| Forward Difference | $O(h)$ | Halving $h$ halves error |
| Central Difference | $O(h^2)$ | Halving $h$ quarters error |
| Simpson's Rule | $O(h^4)$ | Halving $h$ reduces error by $1/16$ |
import math
def taylor_exp(x, n):
"""Approximate e^x using n terms of Taylor series."""
approximation = sum([(x**i) / math.factorial(i) for i in range(n)])
return approximation
true_val = math.exp(1.0)
approx_val = taylor_exp(1.0, 5)
truncation_error = abs(true_val - approx_val)
print(f"True e: {true_val}")
print(f"Approx (5 terms): {approx_val}")
print(f"Truncation Error: {truncation_error}")
Absolute vs. Relative Error
To discuss error meaningfully, we must distinguish between the magnitude of the mistake and its significance relative to the scale of the problem.
Definitions
Let $x$ be the true value and $\hat{x}$ be the approximation.
-
Absolute Error ($E_{abs}$): $$E_{abs} = |x - \hat{x}|$$ Use case: When the physical units of the error matter (e.g., "the bridge is off by 2 centimeters").
-
Relative Error ($E_{rel}$): $$E_{rel} = \frac{|x - \hat{x}|}{|x|}, \quad x \neq 0$$ Use case: When the scale of the value matters. An error of 1 meter is catastrophic when measuring a room, but negligible when measuring the distance to the moon.
Comparison Table
| Scenario | True Value ($x$) | Approx ($\hat{x}$) | Abs Error | Rel Error |
|---|---|---|---|---|
| Small Scale | 0.001 | 0.0009 | 0.0001 | 10% |
| Large Scale | 1,000,000 | 999,999 | 1.0 | 0.0001% |
| Precision Limit | $\pi$ | 3.14159 | $2.65 \times 10^{-6}$ | $8.4 \times 10^{-7}$ |
Insight: Significant Digits A common rule of thumb is that if the relative error is approximately $10^{-d}$, the approximation $\hat{x}$ has roughly $d$ correct significant decimal digits.
Stability and Error Propagation
Numerical analysis is rarely a single step. It is usually a pipeline where the output of one function becomes the input of the next. Error Propagation is the study of how errors grow or shrink through these steps.
Forward vs. Backward Error
- Forward Error: The difference between the calculated result and the true result ($|f(x) - \hat{f}(x)|$).
- Backward Error: The smallest change to the input $x$ that would make the calculated result "correct" for that modified input ($|x - \hat{x}|$ such that $\hat{f}(x) = f(\hat{x})$).
Condition Numbers
The Condition Number ($\kappa$) of a function measures how sensitive the output is to small changes in the input.
$$ \kappa = \left| \frac{x f'(x)}{f(x)} \right| $$
- Well-conditioned: $\kappa$ is small (near 1). Small changes in input lead to small changes in output.
- Ill-conditioned: $\kappa$ is large. Small input errors (like rounding) are magnified into massive output errors.
| Condition Number ($\kappa$) | Interpretation |
|---|---|
| $\kappa \approx 1$ | Stable; error does not grow. |
| $\kappa \approx 10^k$ | You may lose $k$ digits of precision. |
| $\kappa \to \infty$ | Singular problem; unsolvable numerically. |
Stability of Algorithms
An algorithm is Stable if the errors generated during the calculation do not grow uncontrollably. A classic example is the evaluation of a polynomial. Using the standard form $a_n x^n + \dots + a_0$ can be unstable for high degrees, whereas Horner’s Method reduces the number of multiplications and additions, leading to better numerical stability.
def horner_eval(coeffs, x):
"""
Evaluates a polynomial using Horner's Method.
coeffs: [a_n, a_{n-1}, ..., a_0]
"""
result = 0
for c in coeffs:
result = result * x + c
return result
# Evaluating P(x) = 3x^2 + 2x + 1 at x=2
# Standard: 3*(2^2) + 2*(2) + 1 = 12 + 4 + 1 = 17
# Horner: ((3*2) + 2)*2 + 1 = (8)*2 + 1 = 17
Common Pitfalls in Numerical Computing
- Testing for Equality: Never use
if x == 0.3:when dealing with floats. Instead, use a tolerance:if abs(x - 0.3) < 1e-9:. - Summing Series: When summing a long list of numbers, sum from smallest to largest. Adding a tiny number to a large running sum results in the tiny number being rounded away.
- Overflow and Underflow:
- Overflow: The result is too large to be represented (becomes
inf). - Underflow: The result is too small (closer to zero than the smallest representable normalized number), often resulting in it being flushed to
0.0.
- Overflow: The result is too large to be represented (becomes
- The "Hidden" Truncation: Using a library function (like
sin(x)) assumes you trust its internal Taylor expansion or CORDIC algorithm. Always check the documentation for the precision guarantees of third-party libraries.
Summary of Error Sources
| Error Source | Origin | Mitigation Strategy |
|---|---|---|
| Modeling Error | Simplifications in the physics/math | Use more complex models. |
| Data Error | Measurement noise in inputs | Use statistical filtering/smoothing. |
| Rounding Error | Finite bit representation | Use higher precision (Double/Quad). |
| Truncation Error | Finite approximation of infinite series | Increase number of terms or decrease step size. |
| Propagation Error | Sensitivity of the algorithm | Use well-conditioned algorithms. |

Source Materials
Study Numerical Analysis and Computational Methods on Lykke
This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.
Add the free extensionSign in to open every sectionAll sections of Numerical Analysis and Computational Methods · Browse more course pages