Page 420 - Matrix Analysis & Applied Linear Algebra

416 Chapter 5 Norms, Inner Products, and Orthogonality

Therefore, if A is well conditioned, then relatively small uncertainties in b can’t
produce relatively large uncertainties in x. But when A is ill conditioned, it’s
possible for relatively small uncertainties in b to have relatively large effects on
x, and it’s also possible for large uncertainties in b to have almost no effect on
x. Since the direction of e is almost always unknown, we must guard against the
worst case and proceed with caution when dealing with ill-conditioned matrices.
Problem: What if there are uncertainties in both sides of Ax = b?
Solution: Use calculus to analyze the situation by considering the entries of
A = A(t) and b = b(t)tobedifferentiable functions of a variable t, and
compute the relative size of the derivative of x = x(t)by differentiating b = Ax
to obtain b =(Ax) = A x + Ax (with denoting d /dt ), so

−1

−1
x = A −1 A x ≤ A −1
+ A A x

b
b − A

≤ A −1
b + A −1
A x .

Consequently,

−1
x A b

≤ + A −1
A

x x

b

A
≤ A A −1
+ A A −1

A x A

b A b A
≤ κ + κ = κ + .
b A b A
In other words, the relative sensitivity of the solution is the sum of the relative

sensitivities of A and b magnified by κ = A A −1
. A discrete analog of

the above inequality is developed in Exercise 5.12.12.
Conclusion: In all cases, the credibility of the solution to Ax = b in the face
of uncertainties must be gauged in relation to the condition of A.
As the next example shows, the condition number is pivotal also in deter-
mining whether or not the residual r = b − A˜ x is a reliable indicator of the
accuracy of an approximate solution ˜ x.
Example 5.12.2
Checking an Answer. Suppose that ˜ x is a computed (or otherwise approxi-
mate) solution for a nonsingular system Ax = b, and suppose the accuracy of
˜ x is “checked” by computing the residual r = b − A˜ x. If r = 0, exactly,
then ˜ x must be the exact solution. But if r is not exactly zero—say, r is
2
zero to t significant digits—are we guaranteed that ˜ x is accurate to roughly t
significant figures? This question was briefly examined in Example 1.6.3, but it’s
worth another look.
Problem: To what extent does the size of the residual reflect the accuracy of
an approximate solution?