14.4. THE CONDITION NUMBER∗ 341
Lemma 14.4.2 Let A,B be m× n matrices such that A−1 exists, and suppose ||B|| <1/∣∣∣∣A−1
∣∣∣∣ . Then (A+B)−1 exists and∥∥∥(A+B)−1∥∥∥≤ ∥∥A−1∥∥∣∣∣∣ 1
1−||A−1B||
∣∣∣∣ .The above formula makes sense because
∥∥A−1B∥∥< 1.
Proof: By Lemma 14.4.1,∥∥A−1B∥∥≤ ∥∥A−1∥∥∥B∥< ∥∥A−1∥∥ 1
∥A−1∥ = 1
Suppose (A+B)x = 0. Then 0 = A(I +A−1B
)x and so since A is one to one,(
I +A−1B)
x = 0.
Therefore,
0 =∥∥(I +A−1B
)x∥∥≥ ∥x∥−∥∥A−1Bx
∥∥≥ ∥x∥−
∥∥A−1B∥∥∥x∥= (1−∥∥A−1B
∥∥)∥x∥> 0
a contradiction. This also shows(I +A−1B
)is one to one. Therefore, both (A+B)−1 and(
I +A−1B)−1 exist. Hence
(A+B)−1 =(A(I +A−1B
))−1=(I +A−1B
)−1A−1
Now ifx =
(I +A−1B
)−1 y
for ∥y∥ ≤ 1, then (I +A−1B
)x = y
and so∥x∥
(1−∥∥A−1B
∥∥)≤ ∥∥x+A−1Bx∥∥≤ ∥y∥= 1
and so||x||=
∥∥∥(I +A−1B)−1 y
∥∥∥≤ 11−∥A−1B∥
Since ||y|| ≤ 1 is arbitrary, this shows∥∥∥(I +A−1B)−1∥∥∥≤ 1
1−∥A−1B∥
Therefore,∥∥∥(A+B)−1∥∥∥ =
∥∥∥(I +A−1B)−1
A−1∥∥∥
≤∥∥A−1∥∥∥∥∥(I +A−1B
)−1∥∥∥≤ ∥∥A−1∥∥ 1
1−∥A−1B∥■