JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Backward Stability: The Best You Can Hope For

You cannot ask an algorithm to give the exact answer to your problem — floating-point forbids it. But you can ask for the next best thing: the exact answer to a problem indistinguishable from yours. That promise is backward stability, the gold standard of numerical computing, and this guide unpacks exactly what it does and does not buy you.

The ideal courier

The previous guide split error into two faces: forward error, how far your answer sits from the truth, and backward error, how small a change to the input would make your answer exactly right. Backward error turned out to be the one you can usually measure, because it never asks you to know the true answer. This guide takes the next step and asks: what is the strongest, most honest demand you can place on an algorithm? The answer is backward stability, and it is built entirely out of backward error.

Picture hiring a courier. You cannot demand delivery to your exact GPS point down to the millimetre — the world is not that precise, and neither is the address you wrote down. What you can reasonably demand is delivery to a point indistinguishable, given the noise already in your address, from where you meant. A backward-stable algorithm is that ideal courier. It does not return the exact answer to YOUR problem; it returns the exact answer to a problem that differs from yours by no more than a sliver — a perturbation on the order of the unit roundoff u, about 10^-16 in double precision.

Why settle for the answer to a nearby problem rather than yours? Because your problem was never exact to begin with. Its data came from measurements, or from rounding real numbers into floating-point the moment they were stored. If the algorithm's perturbation is smaller than the uncertainty already living in your inputs, then you genuinely cannot tell its answer apart from the answer to the 'real' problem you wished you had. The algorithm has hidden its rounding inside the noise you could not avoid — and that is the most any finite-precision method can ever promise.

What the definition actually says

Let us state it cleanly. An algorithm that is supposed to compute y = f(x) is backward stable if, for every input x, the value y-hat it actually computes equals f(x + delta-x) EXACTLY, for some perturbation delta-x whose relative size ||delta-x|| / ||x|| is of order u. Read that twice. There is an equals sign, not an approximation: the computed y-hat is the perfect, mathematically exact output of f — just fed a slightly nudged input. All the messy rounding that happened across thousands of floating-point operations gets accounted for at once, by being repackaged as a single tiny change to the data.

computed answer    y-hat
backward-stable :  y-hat = f(x + delta-x)   EXACTLY,
                   with  ||delta-x|| / ||x||  =  O(u)

good news:  you can often bound delta-x WITHOUT knowing the true y
the rule :  forward error  <=  kappa(problem) * backward error
                              =  kappa(problem) * O(u)
Backward stability in one box, and the rule that turns it into accuracy.

This is not an abstract ideal that nothing achieves. A surprising number of the workhorse algorithms you will lean on are provably backward stable: Gaussian elimination with partial pivoting (the standard way to do LU factorization and solve A x = b), QR factorization built from Householder reflections, and the polished routines inside LAPACK that nearly every scientific library calls underneath. When you type a backslash to solve a linear system in your favourite environment, you are almost certainly running a backward-stable method without having to think about it.

Why backward error, not forward error, is the right thing to prove

Backward stability is not just a clever definition; it is the survivor of a historical battle. Before the 1950s, analysing rounding meant chasing each tiny error FORWARD through a calculation, watching the worst-case bound balloon step after step until it predicted disaster for computations that, in practice, ran perfectly. The forward bounds were honest but useless — far too pessimistic to tell a good method from a bad one. James H. Wilkinson, working on early machines at the UK's National Physical Laboratory, flipped the question and gave the field its modern shape.

His move, now called backward error analysis, is to stop tracking how errors pile up in the answer and instead prove a single statement: the computed y-hat is the EXACT answer to f(x + delta-x), with delta-x bounded by a modest multiple of u. The genius is that this cleanly separates two things the old forward analysis hopelessly tangled together — the quality of the ALGORITHM (its backward error) and the difficulty of the PROBLEM (its condition number). Each becomes tractable on its own; multiply them and you recover the forward error you actually care about. This reframing won Wilkinson the 1970 Turing Award.

The catch everyone misses: stable is not the same as accurate

Here is the single most important thing to carry out of this guide, and the one most often misunderstood: backward stability does NOT promise a small forward error. It promises only a small backward error. Whether that translates into an accurate answer depends entirely on the condition number of the problem, through the master rule from the previous guide: forward error is at most the condition number times the backward error. For a backward-stable method the backward error is about u, so the forward error is about (condition number) times u — no smaller.

Walk the arithmetic on a single example to feel it. You solve A x = b with a backward-stable LU solver, so the backward error is around 10^-16. If the matrix condition number kappa(A) is about 10^8, the forward error is roughly 10^8 times 10^-16 = 10^-8: you get about 8 correct significant digits out of 16. Hand the same flawless solver a matrix with kappa(A) about 10^13 and the forward error becomes 10^13 times 10^-16 = 10^-3: only about 3 trustworthy digits. The solver did precisely the same thing both times. The difference in accuracy came entirely from the problem.

  1. Your answer looks wrong. Resist blaming the code first.
  2. Estimate the backward error (or the residual, which reports it). If it is around u, your algorithm is doing its job — it is backward stable.
  3. Estimate the condition number kappa of the problem (for a linear system, ask your library for kappa(A)).
  4. Multiply: forward error is about kappa times u. If kappa is huge, the lost digits are the problem's fault, and switching algorithms will not save you — only reformulating the problem or carrying more precision can.

So backward stability is exactly the right thing to demand of a method, and it is also the ceiling: it has done everything an algorithm CAN do. On a well-conditioned problem that translates into a beautifully accurate answer; on an ill-conditioned one it translates into a large forward error that is not the algorithm's fault. This is precisely why the title says 'the best you can hope for' — you can hope for backward stability and get it, but you cannot hope to beat the problem's own conditioning.

A gentler cousin: mixed forward-backward stability

Pure backward stability is a demanding promise — an EXACT answer to a nearby problem, with zero wobble allowed in the output. Some perfectly trustworthy algorithms cannot quite make that promise, and for them there is a slightly relaxed standard called mixed forward-backward stability. It says the computed y-hat is NEARLY the exact answer to a NEARBY problem: a small wobble is permitted at both ends, on the input and on the output. Formally, y-hat + delta-y = f(x + delta-x) where both relative perturbations ||delta-y|| / ||y|| and ||delta-x|| / ||x|| are of order u.

The reassuring fact is that mixed stability buys you the SAME practical accuracy bound: forward error of order (condition number times u), identical to the backward-stable case. So for the purpose of trusting an answer, a mixed-stable algorithm is essentially as good as a backward-stable one — the relaxation gives the analyst breathing room without costing accuracy. Many real algorithms, including standard eigenvalue routines, are mixed stable rather than purely backward stable, and you would never notice the difference in your results.

What to carry forward

Backward stability reframes the whole goal of a numerical method. You stop asking the impossible — 'give me the exact answer' — and start asking the achievable: 'be the exact answer to a problem within rounding distance of mine'. When a method meets that bar, you have a clean division of responsibility. The algorithm has discharged its duty; any remaining inaccuracy belongs to the problem's conditioning, and you address it on that side of the ledger, by reformulating or by spending more precision.

The next and final guide of this rung makes the partnership explicit with the slogan accuracy = conditioning times stability. You now hold both halves: this guide gave you stability as the gold standard an algorithm can reach, and the earlier guides gave you conditioning as the immovable property of the problem. Put them together and you can finally answer, for any computation you run, the only question that matters — how many of my digits can I actually trust?