1 Error bound basics

1.1 Definition and purpose

An error bound is a quantity—often a function of problem data and algorithm parameters—that limits the discrepancy between an exact value and an approximation. If \(x\) is the true value and \(\tilde{x}\) is computed from a method, an error bound states that \(\| \tilde{x}-x \|\le B\) (or, in probabilistic settings, that this inequality holds with a specified confidence). Error bounds serve two closely related purposes: they quantify uncertainty and they enable controlled selection of method parameters such as step sizes or tolerances.

1.2 Absolute vs relative error bounds

Absolute error bounds bound the difference directly, typically in a chosen norm: \(\|\tilde{x}-x\|\le B\). Relative error bounds control the discrepancy relative to the size of the true quantity, for example \(\|\tilde{x}-x\|/ \|x\| \le \varepsilon\) when \(x\neq 0\). Relative bounds are often more meaningful across varying magnitudes, while absolute bounds are simpler to interpret when the target scale is fixed or known to be nonzero.

1.3 Deterministic vs probabilistic error bounds

Deterministic (guaranteed) error bounds hold for all admissible inputs or for all outcomes consistent with the stated assumptions. Probabilistic (confidence-based) bounds instead provide guarantees under modeled randomness—for example, when measurement noise is treated as a random variable or when stochastic approximation is used. Probabilistic bounds usually express the bound as holding “with probability at least \(1-\delta\)” or in terms of expected error and tail behavior.

1.4 Local vs global error bounds

Local error bounds describe the error produced over a single step or local operation (e.g., one update of a differential equation solver). Global error bounds refer to the accumulated error after many steps or over the full computation. Methods in numerical analysis often provide local estimates that, via summation or inequality tools, yield global behavior.

2 Sources of error in approximations

2.1 Truncation (model/discretization) error

Truncation error arises when an exact model is replaced by a simplified one, or when an infinite process is approximated by a finite one. Common cases include discretizing an integral into a quadrature rule, discretizing a differential equation into a step-by-step scheme, or truncating a Taylor series after finitely many terms. This error typically depends on discretization parameters such as mesh size or step length.

2.2 Rounding error (floating-point effects)

Rounding error comes from representing real numbers in finite precision arithmetic. Arithmetic operations in floating-point can introduce small relative perturbations at each step. In algorithms that perform many operations, these perturbations may combine in nontrivial ways, sometimes scaling with the number of operations and sensitivity of the computation.

2.3 Measurement and input uncertainty

If inputs are measured or otherwise obtained with noise—such as sensor readings or fitted parameters—then the approximation inherits uncertainty from those data. Error bounds can incorporate input perturbations using perturbation theory, often producing a relation between the size of input errors and the resulting output error.

2.4 Accumulated error in iterative methods

Iterative methods repeatedly apply update formulas, so errors from each iteration may persist, amplify, or dissipate depending on the iteration’s structure. In some settings, contraction-like behavior ensures that earlier errors decay, while in others, the process can magnify disturbances and make bounds depend strongly on the number of iterations.

Stability describes how sensitively an algorithm’s output responds to perturbations in inputs or intermediate computations. Even if each step has small error, an unstable method can turn small perturbations into larger final errors. Error bounds therefore often involve stability measures such as condition numbers or Lipschitz constants that quantify sensitivity.

3 Bounding techniques

3.1 Norm-based error estimates

Norm-based techniques bound errors in a chosen vector or function norm, such as \(L^\infty\), \(L^2\), or an induced matrix norm. By choosing norms compatible with the problem’s structure, analysts can obtain clean inequalities that propagate through computations.

3.1.1 Use of vector and operator norms

For vectors, norms quantify sizes of errors directly. For linear operators, bounds often use submultiplicativity (e.g., \(\|A v\|\le \|A\|\,\|v\|\)) and triangle inequalities to combine contributions. This framework is central to analyzing linear systems and the behavior of iterative linear solvers.

3.1.2 Matrix norm bounds and induced inequalities

Induced matrix norms are defined so they interact naturally with vector norms, producing inequalities that are straightforward to apply in practice. Such bounds can estimate how perturbations in inputs propagate through a sequence of matrix-vector multiplications, and they can also relate to error growth over time steps in discretized dynamics.

3.2 Lipschitz and contraction-based bounds

Lipschitz continuity assumptions provide a general mechanism for bounding how changes in inputs affect changes in outputs. When a mapping is a contraction—its Lipschitz constant is less than one—errors tend to shrink under iteration.

3.2.1 Lipschitz continuity assumptions

If a function \(f\) satisfies \(\|f(u)-f(v)\|\le L\|u-v\|\), then deviations introduced at intermediate stages can be controlled by multiplying by \(L\) repeatedly. Such assumptions are common in the analysis of ordinary differential equations and nonlinear fixed-point iterations.

3.2.2 Grönwall-type inequalities

Grönwall-type inequalities convert a differential or integral inequality into an explicit bound, often producing exponential dependence on time or step count. They are frequently used to transform local estimates into global ones for systems governed by differential equations.

3.3 Taylor-series remainder bounds

Taylor expansions approximate a function near a point; the remainder term quantifies the truncation error. Bounding that remainder typically requires assumptions on derivatives of the function.

3.3.1 Mean value theorem and remainder forms

Using mean value theorem variants, one can express the remainder in forms involving some intermediate point where derivatives are evaluated. While the intermediate point may be unknown, bounds on derivatives over an interval allow replacing the remainder expression with a computable upper bound.

3.3.2 Derivative bounds and smoothness assumptions

If derivatives up to a certain order are bounded (e.g., \(\|f^{(k)}\|\le M\) on a region), then remainder terms can be bounded by \(M\) times a power of the step size. Smoothness assumptions therefore play a direct role in turning abstract expansions into concrete numeric error estimates.

3.4 Integral remainder bounds

Some truncation errors can be represented as integrals of derivatives, allowing bounds via estimates of those derivatives and standard inequalities. Integral remainder bounds are often convenient for functions that are easier to bound through global derivative estimates rather than pointwise evaluations.

3.5 Bounding with convexity and monotonicity

Convexity and monotonicity provide inequalities that constrain approximation error without requiring high-order derivative information. For example, monotone function properties can yield sign information about remainders, and convexity can bound deviations between function values and secant or tangent approximations.

4 Error bounds in numerical methods

4.1 Root-finding

Root-finding aims to solve \(f(x)=0\). Error bounds in this context relate the distance from the current iterate to the true root, often using derivative information and local behavior.

4.1.1 Bisection error bounds

Bisection maintains an interval \([a,b]\) containing a root and halves it each step. The resulting error bound is typically proportional to the interval length; after \(n\) steps, the uncertainty is bounded by \((b-a)/2^n\). This yields guaranteed convergence under continuity and sign-change assumptions.

4.1.2 Newton and secant error estimates

Newton’s method uses tangent-line updates and can converge rapidly when the derivative at the root is nonzero and the initial guess is sufficiently close. Error bounds often involve higher derivatives or local Lipschitz-type constants. Secant methods similarly rely on local smoothness but generally require less derivative information; their bounds connect the iterate errors to previous errors through a nonlinear recurrence.

4.2 Interpolation and approximation

Interpolation approximates a function using values at selected points. Error bounds quantify how far the interpolation can deviate from the original function.

4.2.1 Interpolation remainder (Lagrange form)

For polynomial interpolation, the remainder can be expressed in terms of the \((n+1)\)-st derivative evaluated at an intermediate point, multiplied by a product involving the distances to the nodes. With derivative bounds, this leads to explicit error estimates.

4.2.2 Best approximation and projection errors

In spaces with inner products or norms, best approximation problems measure the smallest achievable error among all candidates in a chosen subspace. Projection methods introduce orthogonality or quasi-orthogonality properties that can be used to derive bounds in terms of neglected modes or approximation spaces.

4.3 Numerical integration

Quadrature rules approximate an integral \(\int_a^b f(x)\,dx\) using weighted sums. Error bounds depend on derivatives of \(f\) and on the specific rule.

4.3.1 Trapezoidal rule error

The trapezoidal rule error can be bounded using second derivatives, often producing dependence on the step size squared for sufficiently smooth functions. With uniform spacing, the bound typically simplifies to a constant times \(h^2\) times an estimate of \(\|f''\|\).

4.3.2 Simpson’s rule error

Simpson’s rule, using polynomial approximation on subintervals, yields error bounds tied to fourth derivatives. Under smoothness assumptions, the error decreases more quickly with step size than lower-order rules, commonly reflecting the method’s higher-order accuracy.

4.4 Differential equations

For ordinary differential equations, error bounds describe how numerical trajectories deviate from exact solutions.

4.4.1 Local truncation error (one-step methods)

Local truncation error measures the defect when the exact solution is substituted into the one-step update formula. For one-step methods, this defect is often expressed in powers of the step size \(h\), with the order determined by the method’s design.

4.4.2 Global error and step-size dependence

Global error accumulates local errors over many steps. Using stability tools (such as Grönwall inequalities or Lipschitz assumptions), one can bound the final error after time \(T\), often obtaining a rate like \(O(h^p)\) where \(p\) relates to method order.

4.5 Linear algebra computations

Many numerical tasks reduce to linear algebra operations, where error behavior depends on sensitivity of the underlying problem.

The condition number measures how relative output changes can be amplified by relative input perturbations. High condition numbers signal that even accurate arithmetic may yield large relative errors in the result. Error bounds often separate algorithmic error from conditioning effects.

4.5.2 Backward vs forward error

Backward error interprets the computed result as the exact solution to a slightly perturbed problem. Forward error measures the difference between computed and true solutions. Backward error can be easier to bound in floating-point arithmetic, while forward error bounds often follow by combining backward estimates with conditioning.

5 Error bounds and conditioning

5.1 Conditioning of problems vs stability of algorithms

Conditioning is a property of the problem itself—how sensitive the exact solution is to perturbations—whereas stability is a property of the algorithm—how it handles perturbations introduced during computation. A problem can be ill-conditioned yet still produce meaningful results with careful algorithms, but error bounds must account for both aspects.

5.2 Sensitivity analysis using perturbation bounds

Perturbation bounds relate changes in outputs to changes in inputs and operators. They provide a systematic way to convert known perturbation magnitudes into output uncertainty, which is essential for interpreting computed solutions in practical contexts.

5.3 Forward error bounds derived from perturbations

Forward error bounds typically estimate \(\|\tilde{x}-x\|\) based on perturbation size and on sensitivity characteristics. These bounds are frequently expressed using norms, with scaling that depends on whether the measure is absolute or relative.

5.4 Backward error bounds and interpretation

Backward error bounds state that the computed output solves a nearby problem. This interpretation is particularly useful in floating-point contexts: if the backward perturbation is small relative to the problem data, then forward error can be bounded in terms of conditioning.

6 Selecting step sizes and tolerances

6.1 Using bounds to choose discretization parameters

Error estimates provide guidance on selecting step size \(h\) or discretization resolution. By inverting a bound like \(B(h)\), one can choose \(h\) so that the predicted error stays below a desired tolerance. This supports cost–accuracy trade-offs in large computations.

6.2 Error budget allocation across algorithm components

Complex computations may involve multiple sources of error, such as discretization error, linear solver residual error, and rounding error. Allocating an “error budget” helps ensure that no single component dominates the final uncertainty, allowing efficient allocation of computational effort.

6.3 Stopping criteria based on error estimates

Iterative methods often terminate when the residual or an estimated error falls below a threshold. When error bounds relate residual size to actual solution error, these criteria become reliability tools rather than heuristics.

6.4 Adaptive refinement guided by bounds

Adaptive algorithms adjust the discretization dynamically based on error estimates. A posteriori bounds can indicate where the approximation is weak (e.g., regions with large local truncation error), prompting refinement until the global uncertainty target is satisfied.

7 Practical computation of error bounds

7.1 A priori vs a posteriori error bounds

A priori bounds are computed before performing the full computation, relying on assumptions like smoothness and bounds on derivatives. A posteriori bounds are computed after obtaining an approximation, using information derived from the computed solution (or from residuals) to estimate the true error.

7.1.1 A posteriori estimation strategies

Common strategies include residual-based estimators, dual-weighted methods (in partial differential equation contexts), and recovery techniques that compare approximations at different resolutions. The goal is to produce a bound that is both computable and representative of actual error.

7.2 Residual-based error estimation

Residuals measure how well an approximation satisfies the governing equations. Under appropriate conditions, a norm of the residual can be converted into an error bound, often multiplied by stability or inverse-type factors reflecting how strongly the operator enforces correctness.

7.2.1 Norm of the residual as a bound input

Residual norms serve as inputs to error estimators, frequently through inequalities of the form \(\|e\|\le C\|r\|\), where \(e\) is the error and \(r\) is the residual. Determining or estimating the constant \(C\) is a key part of making the bound effective.

7.3 Interval arithmetic and guaranteed bounds

Interval arithmetic propagates ranges rather than single floating-point values. By enclosing exact quantities within intervals and using outward rounding, one can produce guaranteed error bounds for computations. This approach can be computationally expensive but offers strong correctness guarantees.

7.4 Empirical error vs theoretical bounds

Theoretical bounds are sometimes conservative. Empirical validation—comparing computed approximations against higher-accuracy references—can indicate whether bounds are realistic or overly pessimistic. Good practice involves understanding assumptions behind theoretical bounds and checking their relevance to observed behavior.

8 Common theorems and reference formulas

8.1 Standard inequalities used in error analysis

Error analysis relies heavily on general inequalities such as triangle inequalities, Hölder and Cauchy–Schwarz inequalities, and inequalities controlling sums of sequences. These tools convert local estimates into global bounds and allow expressions to be simplified into usable forms.

8.2 Typical remainder bounds by smoothness class

Remainder bounds often depend on which derivatives exist and how they are bounded. A “smoothness class” (e.g., functions with bounded \(k\)-th derivative) determines the order of approximation and the polynomial power of step size appearing in the bound.

8.3 Big-O interpretations of error bounds

Many error bounds can be expressed asymptotically as \(O(h^p)\) or \(O(\varepsilon^q)\), capturing dominant behavior as parameters shrink. Big-O notation abstracts constants away, helping compare convergence rates across methods while recognizing that practical accuracy also depends on hidden factors.

8.4 Linking convergence rates to error bounds

Convergence rates describe how quickly approximations improve as discretization refines. Linking rates to error bounds involves showing that the error decreases no slower than a specified function of the refinement parameter, often using method order and stability estimates.

9 Worked examples and templates

9.1 Bounding a truncation error in a Taylor approximation

A standard template begins with expanding a function around a point using a Taylor series up to order \(n\), then bounding the remainder using a known bound on the \((n+1)\)-st derivative. The final estimate typically has the form \(R_{n}(h)\le Mh^{n+1}/(n+1)!\), where \(M\) bounds the derivative magnitude on the interval.

9.2 Error bound for numerical integration of a smooth function

For a chosen quadrature rule, one writes the remainder term in terms of a derivative of specific order (second for trapezoidal, fourth for Simpson in many classical settings). Substituting an estimate for the relevant derivative norm yields an explicit bound as a constant times a power of the step size, scaled by the interval length.

9.3 Error bound for an iterative update with contraction

If an update mapping \(G\) satisfies \(\|G(u)-G(v)\|\le L\|u-v\|\) with \(L<1\), then the error after \(k\) steps can be bounded by a geometric series. A typical template gives \(\|u_k-u^\*\|\le L^k\|u_0-u^\*\|\), and with additional per-step perturbations, the bound extends using a summation that yields an overall finite radius of uncertainty.

9.4 Putting bounds together for an end-to-end computation

An end-to-end template combines multiple contributors: discretization error, solver tolerance, and rounding effects. One sets each component so that its bound contributes at most a designated fraction of the total tolerance, then uses triangle inequality or problem-specific composition rules to combine them into a final estimate of total error.

10 Limitations and pitfalls

10.1 Overly pessimistic bounds

Some bounds are intentionally conservative to guarantee correctness under broad assumptions. While useful for certification, they can drive inefficient parameter choices if they are far from tight in the actual regime of the computation.

10.2 Misuse of norms or inconsistent units

Bounds derived under one norm may not translate directly to another. Similarly, mixing dimensionful quantities without consistent scaling can lead to incorrect interpretations. Choosing a norm compatible with the method and the problem’s units is essential for meaningful results.

10.3 Hidden assumptions (smoothness, bounded derivatives)

Many remainder bounds require smoothness and derivative boundedness on a region containing the iterates or the domain of approximation. If the function is less regular than assumed—or if iterates leave the region where bounds hold—the theoretical guarantees may fail.

10.4 Dependence on problem scaling and conditioning

Error bounds often include constants that depend on scaling or conditioning. Two mathematically equivalent formulations can yield very different numerical sensitivity, so comparing bounds across formulations requires attention to how the constants change under scaling.

10.5 Probabilistic bounds requiring distributional assumptions

Probabilistic error bounds depend on assumptions about the underlying randomness, such as noise distributions, independence, or tail behavior. If those assumptions do not match the actual data-generation process, the claimed confidence levels may be unreliable.