Ask a different question about an approximate solution
Suppose a computed vector is intended to solve . Its forward error requires knowing the exact solution . The residual is usually easier to compute, but its size depends on units and scaling. Backward error asks: how much would the data need to change for to be an exact solution?
Definition 2.5.1
(Normwise backward error)
We first use real matrices and the Euclidean vector norm and induced matrix norm. Define
Both and may change. If one is exactly zero, its relative bound forces its perturbation to be zero as well.
This definition is a property of the given approximate vector and data, not a statement that a particular algorithm produced it stably.
An exact normwise formula
Theorem 2.5.2
(Exact normwise backward error)
Let . When ,
If , then and either or , so ; zero perturbations attain .
Proof
(Residual identity and a rank-one perturbation)
Exactness of the perturbed system is equivalent to . Thus every admissible perturbation obeys
This proves the lower bound. If , the zero perturbations attain it. Otherwise put and . When , put and choose
The rank-one matrix has induced 2-norm one, and . When , take and the same ; here and the equality still holds. Thus the infimum is attained in all cases.
Proof X-ray
Lower bound and construction are separate halves
The proof has two independent halves. The lower bound uses only the residual identity and the triangle inequality, so it holds for every admissible perturbation. The matching construction is the nonobvious move: both perturbations are made parallel to the residual direction , with acting through so that and . The signs ( on , on ) make the two contributions add up to instead of canceling, and the common spends the whole budget . The case needs separate treatment because is undefined; there the budget is alone. Without the construction one knows only that .
A stricter componentwise question
Normwise perturbations can move data between entries of very different scales.
Definition 2.5.3
(Componentwise backward error)
The componentwise backward error is the least for which there are with and
Theorem 2.5.4
(Exact componentwise backward error)
Let . The least such is
where a term is interpreted as zero.
Proof
(Row-by-row residual identity)
The convention is consistent: implies and for every , hence .
The residual identity implies row by row, giving the lower bound. For every row with , choose
For rows with , use zero perturbations. Since , these choices satisfy and meet the componentwise bounds with . The formula therefore gives the exact minimum. A zero entry of or stays zero under this model; a different perturbation model can give a different backward error.
Worked example 2.5.5
(Computing both backward errors)
Let , and . Then , , and , so and . For the componentwise formula, , so . The optimal componentwise perturbation touches only row : and . Check: , and row is already exact.
Worked example 2.5.6
(Zero approximate solution)
Let , and . Then and , so . The construction for takes and , giving : the whole right-hand side has to be removed. Componentwise, and , so the two ratios are and , and . The convention is used in the second row, where and .
A small normwise error can hide a bad component
Worked example 2.5.7
(Small normwise error, large componentwise error)
Take and
The exact solution is and . Since and ,
The normwise error tends to zero with , while the second equation has a 100% componentwise backward error and the relative forward error stays large. The 2-norm condition number of is ; the problem amplifies errors along the small-singular-value direction (here also the eigenvector for ).
Counterexample mode
A small residual does not settle forward accuracy
A tempting claim is that a small normwise backward error forces a small relative forward error. Take the diagonal example with . Then and , yet . The repair is the bound below: the factor multiplies the residual, so a forward-error conclusion needs information about and the scale of the exact solution, not only about .
For nonsingular , the elementary relation gives . Using , it also gives . Thus conditioning enters the forward-error conclusion; this is a separate bound from either backward-error formula. In actual floating-point work the residual itself is rounded; a rigorous certificate for exact data requires controlling that computation too.
Common mistake
(A normwise perturbation need not respect zeros)
The normwise minimizer is , a rank-one matrix that is generally dense. In the diagonal example and , so places a nonzero entry at position , where has a zero. If the zero pattern is meaningful, does not measure a legitimate perturbation; that is the role of .
Common mistake
(The residual divided by the norm of b is not the backward error)
The ratio is the smallest relative perturbation of alone. Because may change too, can be smaller. For , and we have and , but and , attained by and : then .
Practice with solutions
Quick check
(For , and , compute and .)
Start with .
Solution · Answer
and . Also , so . Each , so .
Quick check
(In the diagonal example above, compute the two denominators of the componentwise formula.)
Use .
Solution · Answer
and ; the residual entries are and , so the maximum ratio is .
Quick check
(If exactly solves , what are both backward errors?)
Then .
Solution · Answer
Both are zero, attained by zero perturbations.
Quick check
(Why does a zero entry of remain zero in the componentwise perturbation model?)
Look at the constraint on .
Solution · Answer
The constraint forces whenever .