Rounding Errors and Error Analysis

Numerical computation in finite precision arithmetic accumulates errors through successive operations. Analyzing these errors is fundamental to assessing algorithm reliability and numerical stability.

DefinitionAbsolute and Relative Error

Let $x$ be the true value and $\tilde{x}$ be an approximation. The absolute error is: $E_{\text{abs}} = |x - \tilde{x}|$

The relative error is: $E_{\text{rel}} = \frac{|x - \tilde{x}|}{|x|}$ provided $x \neq 0$ . In floating point arithmetic, relative error is typically the more meaningful measure.

The fundamental model of floating point arithmetic assumes that each elementary operation $\circ \in \{+, -, \times, \div\}$ satisfies: $\text{fl}(x \circ y) = (x \circ y)(1 + \delta)$ where $|\delta| \leq \epsilon_{\text{mach}}$ . This leads to forward and backward error analysis frameworks.

DefinitionForward and Backward Error

Consider an algorithm computing $y = f(x)$ that produces $\tilde{y}$ :

Forward error: $\|y - \tilde{y}\|$ measures the error in the output
Backward error: $\|\tilde{x} - x\|$ where $\tilde{y} = f(\tilde{x})$ exactly

An algorithm is backward stable if the computed solution $\tilde{y}$ is the exact solution to a slightly perturbed problem, i.e., $\tilde{y} = f(x + \Delta x)$ where $\|\Delta x\| = O(\epsilon_{\text{mach}})\|x\|$ .

ExampleCatastrophic Cancellation

Computing $f(x) = \sqrt{x+1} - \sqrt{x}$ for large $x$ suffers from catastrophic cancellation. Direct evaluation: $\text{fl}(\sqrt{x+1} - \sqrt{x})$ subtracts two nearly equal numbers, losing precision.

Rationalizing the numerator: $f(x) = \frac{(\sqrt{x+1} - \sqrt{x})(\sqrt{x+1} + \sqrt{x})}{\sqrt{x+1} + \sqrt{x}} = \frac{1}{\sqrt{x+1} + \sqrt{x}}$ avoids cancellation and is numerically stable.

Remark

Condition Number: For a problem $y = f(x)$ , the relative condition number is: $\kappa = \lim_{\epsilon \to 0} \sup_{\|\Delta x\| \leq \epsilon\|x\|} \frac{\|f(x+\Delta x) - f(x)\|/\|f(x)\|}{\|\Delta x\|/\|x\|}$

For differentiable $f$ , this is approximately $\kappa \approx \|f'(x)\| \|x\|/\|f(x)\|$ . A problem is ill-conditioned if $\kappa \gg 1$ , meaning small input perturbations cause large output changes regardless of the algorithm used.

Error accumulation follows different patterns depending on whether errors compound additively or multiplicatively. For a sequence of operations, accumulated relative error typically grows as $O(n\epsilon_{\text{mach}})$ for $n$ operations under favorable conditions, but can be exponential for unstable algorithms. This distinction separates stable algorithms from unstable ones.

Understanding the interplay between problem conditioning and algorithmic stability is essential: even a stable algorithm applied to an ill-conditioned problem will produce inaccurate results, while an unstable algorithm applied to a well-conditioned problem may still fail.