If an algorithm is stable, will it always give an accurate answer?

No. A backward-stable algorithm guarantees only that its answer is exact for a nearby problem; if the problem itself is ill-conditioned, that nearby problem can have a very different solution, so the forward error may still be large.

What is unit roundoff?

Unit roundoff is the maximum relative error incurred when a real number is rounded to the nearest floating-point number; it sets the granularity of floating-point arithmetic and appears in essentially every stability bound.

Conditioning and Numerical Stability

Conditioning measures how sensitive a problem's solution is to perturbations in its data, while stability measures how much error a particular algorithm adds in finite-precision arithmetic; together they determine the accuracy of a computed result.

Definition

Conditioning is an intrinsic property of a problem describing how its exact solution responds to perturbations of the input, whereas numerical stability is a property of an algorithm describing how faithfully it solves the problem despite rounding errors.

Scope

This topic covers floating-point arithmetic and unit roundoff, the condition number of problems such as solving linear systems and evaluating functions, forward and backward error, the rule of thumb that forward error is bounded by condition number times backward error, and the definitions of backward and forward stability.

Core questions

How is floating-point arithmetic modelled, and what is the role of unit roundoff?
What does the condition number of a problem quantify, and how is it defined for linear systems and for function evaluation?
How are forward error, backward error, and conditioning related?
What distinguishes a backward-stable algorithm from a forward-stable one, and why is backward stability the usual target?

Key theories

Condition number: The condition number is the factor by which relative perturbations in the data can be amplified in the solution; for a linear system it equals the matrix norm times the norm of the inverse, and it sets a limit on achievable accuracy independent of the algorithm.
Backward error analysis: Rather than bounding the error in the answer directly, one shows that the computed result is the exact answer to a nearby problem; an algorithm is backward stable when this nearby problem differs from the original by an amount of order unit roundoff.
Forward error equals condition number times backward error: The central rule of thumb of numerical analysis states that the forward (solution) error is bounded approximately by the problem's condition number multiplied by the backward error, cleanly separating the contributions of the problem and the algorithm.

Mechanisms

Floating-point numbers represent reals with finite precision, so each elementary operation incurs a relative error bounded by unit roundoff. Backward error analysis tracks these errors by attributing them to perturbations of the data rather than the result, producing bounds of the form: computed answer equals exact answer of a perturbed input. Combining a backward error bound with the problem's condition number yields a forward error estimate, which explains why a stable algorithm can still lose accuracy on an ill-conditioned problem.

Clinical relevance

Understanding conditioning and stability is essential whenever computed results must be trusted: it explains why some least-squares formulations lose accuracy, guides the choice of stable algorithms and well-posed formulations across simulation and data analysis, and warns when an ill-conditioned model cannot yield a reliable answer regardless of the method used.

History

The conceptual framework was established by Wilkinson, whose backward error analysis in the 1960s explained the practical reliability of Gaussian elimination, and was later systematized and extended across the whole field by Higham; the IEEE 754 floating-point standard subsequently put rounding behaviour on a firm and portable footing.

Key figures

James H. Wilkinson
Nicholas J. Higham
Lloyd N. Trefethen
William Kahan

Seminal works

trefethen1997
higham2002

Frequently asked questions

If an algorithm is stable, will it always give an accurate answer?: No. A backward-stable algorithm guarantees only that its answer is exact for a nearby problem; if the problem itself is ill-conditioned, that nearby problem can have a very different solution, so the forward error may still be large.
What is unit roundoff?: Unit roundoff is the maximum relative error incurred when a real number is rounded to the nearest floating-point number; it sets the granularity of floating-point arithmetic and appears in essentially every stability bound.