342 CHAPTER 14. NUMERICAL SOLUTIONS OF LINEAR SYSTEMS
Proposition 14.4.3 Suppose A is invertible, b ̸= 0, Ax = b, and A1x1 = b1 where
∥A−A1∥< 1/∥∥A−1∥∥
Then
∥x1−x∥∥x∥
≤ 1(1−∥A−1 (A1−A)∥)
∥A∥∥∥A−1∥∥(∥A1−A∥
∥A∥+∥b−b1∥∥b∥
). (14.11)
Proof: It follows from the assumptions that
Ax−A1x+A1x−A1x1 = b−b1.
HenceA1 (x−x1) = (A1−A)x+b−b1.
Now A1 = (A+(A1−A)) and so by the above lemma, A−11 exists and so
(x−x1) = A−11 (A1−A)x+A−1
1 (b−b1)
= (A+(A1−A))−1 (A1−A)x+(A+(A1−A))−1 (b−b1) .
By the estimate in Lemma 14.4.2,
∥x−x1∥ ≤∥∥A−1
∥∥1−∥A−1 (A1−A)∥
(∥A1−A∥∥x∥+∥b−b1∥) .
Dividing by ∥x∥ ,
∥x−x1∥∥x∥
≤∥∥A−1
∥∥1−∥A−1 (A1−A)∥
(∥A1−A∥+ ∥b−b1∥
∥x∥
)(14.12)
Now b = Ax = A(A−1b
)and so ∥b∥ ≤ ∥A∥
∥∥A−1b∥∥ and so
∥x∥=∥∥A−1b
∥∥≥ ∥b∥/∥A∥ .Therefore, from 14.12,
∥x−x1∥∥x∥
≤∥∥A−1
∥∥1−∥A−1 (A1−A)∥
(∥A∥∥A1−A∥∥A∥
+∥A∥∥b−b1∥∥b∥
)≤
∥∥A−1∥∥∥A∥
1−∥A−1 (A1−A)∥
(∥A1−A∥∥A∥
+∥b−b1∥∥b∥
)■
This shows that the number,∥∥A−1
∥∥∥A∥ , controls how sensitive the relative change inthe solution of Ax = b is to small changes in A and b. This number is called the conditionnumber. It is bad when it is large because a small relative change in b, for example, couldyield a large relative change in x.