Page 44 - Matrix Analysis & Applied Linear Algebra

36 Chapter 1 Linear Equations

then the numbers

for i =1, 2,...,n
r i = a i1 ξ 1 + a i2 ξ 2 + ··· + a in ξ n − b i
are called the residuals. Suppose that you compute a solution x c and substitute
it back to find that all the residuals are relatively small. Does this guarantee that
x c is close to the exact solution? Surprisingly, the answer is a resounding “no!”
whenever the system is ill-conditioned.
Example 1.6.3
For the ill-conditioned system given in Example 1.6.1, suppose that somehow
you compute a solution to be

ξ 1 = −666 and ξ 2 = 834.
If you attempt to “check the error” in this computed solution by substituting it
back into the original system, then you find—using exact arithmetic—that the
residuals are
r 1 = .835ξ 1 + .667ξ 2 − .168 = 0,
r 2 = .333ξ 1 + .266ξ 2 − .067 = −.001.

That is, the computed solution (−666, 834) exactly satisfies the first equation
and comes very close to satisfying the second. On the surface, this might seem to
suggest that the computed solution should be very close to the exact solution. In
fact a naive person could probably be seduced into believing that the computed
solution is within ±.001 of the exact solution. Obviously, this is nowhere close
to being true since the exact solution is

x = 1 and y = −1.

This is always a shock to a student seeing this illustrated for the first time because
it is counter to a novice’s intuition. Unfortunately, many students leave school
believing that they can always “check” the accuracy of their computations by
simply substituting them back into the original equations—it is good to know
that you’re not among them.

This raises the question, “How can I check a computed solution for accu-
racy?” Fortunately, if the system is well-conditioned, then the residuals do indeed
provide a more effective measure of accuracy (a rigorous proof along with more
insight appears in Example 5.12.2 on p. 416). But this means that you must be
able to answer some additional questions. For example, how can one tell before-
hand if a given system is ill-conditioned? How can one measure the extent of
ill-conditioning in a linear system?
One technique to determine the extent of ill-conditioning might be to exper-
iment by slightly perturbing selected coefficients and observing how the solution