Numerical stability is the property of a numerical algorithm that controls how errors introduced during computation affect its results. It is a central concern of numerical analysis, especially when calculations use floating-point arithmetic. Stability concerns the computational method, whereas conditioning concerns the underlying mathematical problem. A stable method avoids introducing substantially more error than the problem’s inherent sensitivity and the working precision warrant; it does not guarantee an accurate answer to every problem. (cs.cornell.edu)
Finite precision and error propagation
Computers represent only a finite subset of the real numbers. Intermediate results therefore usually require rounding. A standard model for a basic arithmetic operation is
[ \operatorname{fl}(a\circ b)=(a\circ b)(1+\delta), \qquad |\delta|\leq u, ]
where (\circ) denotes addition, subtraction, multiplication, or division, and (u) is the unit roundoff. This relative-error model applies under appropriate assumptions, notably that overflow and problematic underflow do not occur. Each operation may introduce a small error, but the accumulated effect depends on how subsequent operations propagate it. (cs.cornell.edu)
Errors also arise from inaccurate input data and from approximating a continuous problem by a finite computation. These sources are conceptually distinct from rounding error. Stability analysis examines error propagation rather than simply counting arithmetic operations: mathematically equivalent expressions can behave differently in finite precision. (netlib.org)
Conditioning versus stability
The condition number measures how sensitive a problem’s exact answer is to perturbations in its input. For a differentiable scalar function (f), a local relative condition number is
[ \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|, ]
when the expression is defined. The derivative determines local sensitivity, independently of the algorithm used to evaluate the function. A large condition number indicates that small relative input changes can produce large relative output changes. (netlib.org)
An ill-conditioned problem can yield an inaccurate answer even with a stable algorithm. Conversely, an unstable algorithm may lose accuracy on a well-conditioned problem by creating sensitive intermediate calculations. This distinction separates unavoidable amplification associated with the problem from avoidable amplification associated with its implementation. (netlib.org)
Forward, backward, and mixed error
Suppose the exact answer is (y=f(x)) and the computed answer is (\widehat y). Forward error measures their difference, either absolutely or relatively:
[ |\widehat y-y|, \qquad \frac{|\widehat y-y|}{|y|}. ]
Here the norm specifies how vector or matrix errors are measured; relative error requires a nonzero denominator. (cs.cornell.edu)
Backward error instead asks how much the input must change to make the computed answer exact. An algorithm is backward stable if its output satisfies
[ \widehat y=f(x+\Delta x) ]
with a small perturbation (\Delta x), typically bounded by a modest, dimension-dependent multiple of (u). Mixed stability permits both a small input perturbation and a small output discrepancy. For sufficiently small perturbations, the central relationship is approximately
[ \text{relative forward error} \lesssim \text{condition number}\times \text{relative backward error}. ]
Backward stability therefore provides an interpretation of the answer as the exact solution of a nearby problem. (netlib.org)
Normwise stability bounds the overall size of a perturbation. Componentwise stability bounds individual entries relative to their magnitudes and can be more informative when data contain very small or zero entries. A small normwise error need not imply small relative changes in every component. (netlib.org)
Cancellation and algebraic reformulation
Catastrophic cancellation occurs when subtracting nearby approximate quantities exposes errors that were small relative to the operands but large relative to their difference. The subtraction itself can even be exact; the damaging errors may already be present in its inputs. (cs.cornell.edu)
For small positive (z), consider
[ f(z)=1-\sqrt{1-z}. ]
Direct evaluation subtracts quantities close to one. Rationalizing gives the equivalent expression
[ f(z)=\frac{z}{1+\sqrt{1-z}}, ]
which avoids that subtraction. The function is relatively well-conditioned near zero, but the direct expression can lose much of its relative accuracy. This illustrates why algebraic equivalence does not imply numerical equivalence. (cs.cornell.edu)
Summation supplies another distinction between stability and accuracy. Ordinary sequential summation has a backward-error bound proportional to the number of terms times (u). Nevertheless, its relative forward error can be large when positive and negative terms nearly cancel, because the summation problem itself is then ill-conditioned. (cs.cornell.edu)
Linear algebra and statistical computation
In numerical linear algebra, solving a system of linear equations (Ax=b) involves both algorithmic error and sensitivity associated with the matrix (A). A backward-stable solver produces (\widehat x) satisfying
[ (A+\Delta A)\widehat x=b+\Delta b ]
for small perturbations. The residual (b-A\widehat x) helps assess backward error, but a small residual alone does not establish small forward error when the system is ill-conditioned. (netlib.org)
For full-column-rank least-squares problems, forming the normal equations introduces (A^{T}A), whose spectral condition number is (\kappa_2(A)^2). Algorithms based on QR decomposition avoid explicitly forming this matrix and thereby avoid that particular source of accuracy loss. Computational cost, precision, and conditioning all influence the comparison. (netlib.org)
In machine learning, evaluating the softmax function directly can overflow because of its exponentials. For finite inputs, the equivalent formula
[ p_i=\frac{\exp(x_i-m)}{\sum_j\exp(x_j-m)}, \qquad m=\max_j x_j, ]
keeps exponential arguments nonpositive. The corresponding log-sum-exp formula is (m+\log\sum_j\exp(x_j-m)). These transformations avoid exponential overflow, although rounding and underflow still require analysis. (doi.org)
Stability in time-stepping methods
For numerical solutions of differential equations, stability also describes the propagation of perturbations across time steps. Applied to (y'=\lambda y), the forward Euler method gives
[ y_{n+1}=(1+h\lambda)y_n. ]
For a decaying exact solution, numerical perturbations are non-amplifying when (|1+h\lambda|\leq1). With real negative (\lambda), this requires (h\leq2/|\lambda|). Such step-size restrictions concern the discrete evolution itself, not merely floating-point rounding. (math.mit.edu)