Backward stability and perturbation bounds

For Ax=b and a candidate solution xhat, define the residual as b−Axhat. The forward error is xhat−x, where x is the unknown exact solution. For nonsingular A, the error equals minus A inverse times the residual. Consequently a small residual can coexist with a large solution error when the inverse amplifies its direction strongly. Residuals are attractive because they can be computed without knowing x, but evaluating them in the same working precision as the solve can hide cancellation or rounding. Higher-precision residual accumulation can make a diagnostic more trustworthy.

If only b may change while A stays fixed, xhat exactly solves Axhat=b+δb for the unique perturbation δb=−r. Its relative backward error is therefore the residual norm divided by the norm of b, assuming b is nonzero. Allowing perturbations to A as well gives a different, often smaller, backward error. Componentwise restrictions produce another measure again. A statement that a solution has tiny backward error is incomplete unless it says which inputs may change and how those changes are scaled.

Suppose the perturbed system is (A+δA)(x+δx)=b+δb. Rearranging and bounding the inverse of I+A inverse δA produces a finite perturbation estimate. The essential condition is that κ(A) times the relative matrix perturbation is less than one. A Neumann-series argument then guarantees that A+δA remains invertible and bounds the inverse correction. The denominator is meaningful: when the perturbation can approach a singular matrix, a uniform small forward-error guarantee can disappear.

Let εA be the matrix perturbation norm divided by the matrix norm, and εb the right-hand-side perturbation norm divided by the right-hand-side norm. The displayed bound uses the inequality between b, A, and x, so it may be conservative for a particular problem. It is not legitimate to use the formula after its denominator becomes zero or negative. Nor should a first-order slogan about condition times backward error replace the finite bound when that product is no longer small. Sensitivity estimates have an operating regime just as iterative methods do.

An algorithm is normwise backward stable when its result is the exact solution of an allowed nearby problem with perturbations bounded by a modest dimension-dependent multiple of unit roundoff, under its stated assumptions. That guarantee is about the algorithm. A problem can still be ill conditioned, producing substantial forward uncertainty from that tiny perturbation. Conversely, a well-conditioned problem can be solved inaccurately by an unstable algorithm. Assessing both properties avoids blaming intrinsic data sensitivity on a reliable factorization or excusing a poor computation because the equations are difficult.

Iterative refinement combines these ideas operationally. Compute a residual, approximately solve for a correction using existing factors, and update the candidate. A more accurate residual can improve the final answer even when the factors were obtained in lower precision. Success depends on the correction quality, conditioning, scaling, and arithmetic; it is not automatic for arbitrary factors. Report a scaled residual alongside a suitable condition estimate and, when possible, an error bound. Preserve structure in the backward model if the original physical or statistical problem requires it.