Page 133 - Matrix Analysis & Applied Linear Algebra

3.8 Inverses of Sums and Sensitivity127

essentially the same conclusion from (3.8.4) when only a single entry is perturbed
and from Exercise 3.8.2 when a single column is perturbed.
This discussion resolves, at least in part, an issue raised in §1.6—namely,
“What mechanism determines the extent to which a nonsingular system Ax = b
is ill-conditioned?” To see how, an aggregate measure of the magnitude of the
entries in A is needed, and one common measure is

A = max |a ij | = the maximum absolute row sum. (3.8.7)
i
j
This is one example of a matrix norm, a detailed discussion of which is given in
§5.1. Theoretical properties specific to (3.8.7) are developed on pp. 280 and 283,
and one property established there is the fact that XY ≤ X Y for all
conformable matrices X and Y. But let’s keep things on an intuitive level for
the time being and defer the details. Using the norm (3.8.7), the approximation
(3.8.6) insures that if B is sufficiently small, then

$ −1 $ $ −1 $ $ $ $ $
$
$
$ A − (A + B) −1 $ ≈ A BA −1 $ ≤ A −1 $ B A −1 $ ,
$
so, if we interpret x < y to mean that x is bounded above by something not
∼
far from y, we can write
$ −1 $ % &
$ A − (A + B) −1$ $ $ $ $ B
< $ A −1 $ B = A −1 $ A .
$
A −1 ∼ A
The term on the left is the relative change in the inverse, and B / A is the
$ $
relative change in A. The number κ = A −1$ A is therefore the “magnifi-
$
cation factor” that dictates how much the relative change in A is magnified.
This magnification factor κ is called a condition number for A. In other
words, if κ is small relative to 1 (i.e., if A is well conditioned), then a small
relative change (or error) in A cannot produce a large relative change (or error)
in the inverse, but if κ is large (i.e., if A is ill conditioned), then a small rela-
tive change (or error) in A can possibly (but not necessarily) result in a large
relative change (or error) in the inverse.
The situation for linear systems is similar. If the coefficients in a nonsingular
system Ax = b are slightly perturbed to produce the system (A + B)˜ x = b,
then x = A −1 b and ˜ x =(A + B) −1 b so that (3.8.6) implies

x − ˜ x = A −1 b − (A + B) −1 b ≈ A −1 b − A −1 − A −1 BA −1 b = A −1 Bx.
For column vectors, (3.8.7) reduces to x = max i |x i |, and we have

$ $
x − ˜ x < $ A −1 $ B x ,
∼