A computed vector can nearly satisfy a system and still be far from its exact solution. There is no contradiction: a matrix may send a large change in one input direction to a very small change in the output. The residual measures a discrepancy in the equations; forward error measures the discrepancy in the answer. Backward error asks a different, useful question: how much would the input data have to change for the computed answer to be exact?
We work with real matrices and the Euclidean vector norm and its induced matrix norm, denoted by the same symbol. For a matrix , . Thus and . These properties are the only norm estimates needed for the perturbation proof. In this chapter all equalities and bounds concern exact quantities; a floating-point computation can introduce additional rounding when it evaluates them.
Residual versus forward error
Definition 6.1.1
(Residual and forward error)
Let be a nonsingular real matrix, , and . For a proposed answer , define the residual and forward error by
Theorem 6.1.2
(Residual bound on the forward error)
Let be a nonsingular real matrix, , and let have residual and forward error . Then . If , then also .
Proof
(Subtracting the exact equation)
Subtracting gives , so and
If , then . Since , dividing the preceding inequality yields
A small relative residual therefore controls relative forward error only to the extent that the condition number is moderate. This is an upper bound, not a prediction that the error must attain it. If , relative expressions divided by or are undefined; the absolute inequality still holds. For the zero right-hand side the exact solution is zero, but a computed vector need not be.
A normwise backward-error certificate
Theorem 6.1.3
(Normwise backward error of a computed solution)
Let , , and, when , . Then is the smallest for which there exist with , and .
Proof
(A lower bound and a rank-one perturbation that attains it)
Suppose the computed answer is to solve a nearby system . Let , and . When , define
This is not merely a convenient scale. It is exactly the smallest for which there are perturbations satisfying , , and . Indeed the latter equation is equivalent to . The triangle inequality gives , so every admissible is at least .
For the reverse inequality, if , choose
Then . The rank-at-most-one matrix has two-norm : Cauchy–Schwarz gives the upper bound, and the unit vector attains it. Consequently and . If and , then ; take and , attaining . If , nonsingularity gives and hence ; set because the unperturbed system is already satisfied.
Proof X-ray
The two halves of the backward-error proof
The lower bound uses nothing but the triangle inequality on . The key move is the construction: the required correction is split between and in the proportion , so that both norm constraints become tight at the same . The rank-one matrix is chosen because it sends exactly to a multiple of while having the smallest possible norm for that job; Cauchy–Schwarz shows its norm equals . The division by and by is why and are treated separately. The argument closes because the lower bound and the construction meet at .
This is a normwise certificate under simultaneous relative bounds on the two data objects. It is not automatically the smallest perturbation when only may change, nor a componentwise error bound. If only may change, the exact choice is , whose norm is . The distinction matters when individual entries have very different scales.
Concept lensGeometric
Backward error as a ball in the space of perturbations
Fix and consider the linear map from perturbation pairs to . The pairs allowed at level form the ball , , and solves the perturbed system exactly when . The proof shows that, for , maps this ball onto the closed Euclidean ball of radius about . Hence is the smallest whose image ball reaches : it measures in the unit .
Perturbing both matrix and right-hand side
Theorem 6.1.4
(Perturbation bound for both data objects)
Assume and . Write , and . If , then is nonsingular and
Proof
(Subtracting, bounding and absorbing the error term)
Assume and let solve . Define
Suppose . This condition also guarantees is nonsingular: , and makes the second factor invertible by the convergent Neumann series. It is a sufficient condition, not a necessary one.
Put . Subtracting from the perturbed equation gives . Therefore
Move the last term to the left and divide by . Since , we obtain
The denominator is positive precisely under the stated sufficient condition. As it approaches zero the bound becomes uninformative; that does not prove the actual error is large. If only changes, set , recovering a simpler bound. The condition number describes sensitivity of the mathematical problem, while backward error describes the fit of a particular answer to nearby data.
How to interpret a certificate
The normwise backward-error construction permits changes to both and . Its optimality follows because the lower bound and the explicit perturbations meet exactly. A different problem has a different answer: requiring certain entries of to remain zero, or requiring symmetry to be preserved, restricts the allowed perturbations. The constructed rank-at-most-one matrix need not respect either restriction. One should state the permitted changes before calling an error small. A common relative tolerance also treats and as two separate objects; it does not mean each individual entry has changed by at most that percentage.
The certificate can still be useful when the true solution is unknown. Computing requires only the original data and the proposed answer, while computing requires the exact answer. The equality explains the gap, but applying it in practice may be as difficult as solving the original system. A bound or estimate for can give a usable upper estimate instead; the conclusion inherits the reliability of that estimate and of the residual calculation.
Rescaling also deserves attention. If both and are multiplied by the same nonzero scalar, the exact solution and both relative measures, whenever defined, remain unchanged. The normwise backward error also remains unchanged because its numerator and denominator scale equally. Changing only one equation, however, may change a normwise measure even though the solution set remains the same. That is because the norm weights the equations differently after such a rescaling. In applications with physical units or sharply differing row scales, an appropriate scaling or a componentwise analysis may be needed; the normwise certificate above does not decide that choice.
The perturbation estimate is also one-sided. A large condition number says some direction can be sensitive; it does not force every right-hand side or every perturbation to exhibit the worst case. Similarly, if the bound exceeds one, it can still be correct but may give little practical information. Inspecting the actual residual and the direction of the perturbation often reveals more than quoting a single scalar. The singular-vector interpretation from the earlier chapter identifies directions of greatest and least stretching, but the inequality above does not require us to compute those vectors.
Normal equations, QR and what is not proved
For a real full-column-rank matrix , the singular values of are the squares of those of , so . If is thin QR with orthonormal columns, then for every , and has the same singular values as . Thus .
These are exact conditioning identities. They explain why explicitly forming the normal matrix can worsen the condition of the system being solved; they do not prove that every QR implementation is backward stable or quantify its floating-point error. Such a claim requires an algorithm and a separate rounding-error analysis. In practice the product also has to be computed, so its entries can incur rounding before the solve. We make no universal digit-loss prediction from the squared condition number alone.
Worked examples
Worked example 6.1.5
(Small residual, substantial forward error)
Take , and . Find the exact solution, relative residual, relative forward error and normwise backward error.
Solution. The exact solution is . The residual is , while . Hence
The first ratio is about , whereas the second is about . Here , and , so the residual bound permits the observed error. Since , the exact normwise backward error is
It is about : the proposed vector is an exact solution to suitably nearby data even though it is far from the exact answer for the original data. The small second singular value explains the amplification.
Worked example 6.1.6
(A perturbation bound and two factorizations)
Let , , and . Find the perturbed solution and compare its actual relative error with the bound. Also compare the two condition numbers relevant to normal equations and QR.
Solution. The original solution is . The second diagonal entry of is , so . Therefore . The norms give , , and . The bound is
which exceeds the actual relative error, as required. Moreover has condition number 400. The exact QR factorization , has . These exact comparisons do not measure the rounding error of a particular software implementation.
Worked example 6.1.7
(The zero candidate: a boundary case)
Let , and . The exact solution is , the residual is and the forward error is , so the relative forward error is . Here , and , so . The construction for takes and : indeed . Since , a relative change of one hundred percent in is needed, and no smaller relative change in both and makes exact.
Counterexample mode
A tiny relative residual does not give a small error
Claim: if , the relative forward error is below as well. This is false. Take , and . The exact solution is , the residual is , so , while and . The repaired statement is the residual bound: , and allows the observed error.
Common mistakes and subtle points
Common mistake
(Reading the condition-number bound as a prediction)
In the second worked example the bound is , while the actual relative error is . The bound is a guarantee of the form "at most", not an estimate of the error, and a large does not mean every right-hand side suffers the worst case.
Common mistake
(Dividing by a zero norm)
If the exact solution is zero and the relative quantities with or in the denominator are undefined; only the absolute bound remains. Likewise needs , and needs the separate treatment shown above.
Exercises
Quick check
(For , and , find and and compare with .)
The exact solution is easy to read off.
Solution · Answer
The exact solution is . Then and , so . Also and , so the bound holds with equality.
Quick check
(If only may be perturbed, what is the smallest that makes an exact solution of ?)
Solve for .
Solution · Answer
The equation forces , so the only choice, and hence the smallest, has norm .
Quick check
(With , and , is the perturbation theorem applicable, and what does it give?)
Check first.
Solution · Answer
, so is nonsingular and the bound is .