Chapter 14

Analysis Of Linear Transformations14.1 The Condition Number

Let A ∈L (X ,X) be a linear transformation where X is a finite dimensional vector spaceand consider the problem Ax = b where it is assumed there is a unique solution to thisproblem. How does the solution change if A is changed a little bit and if b is changed alittle bit? This is clearly an interesting question because you often do not know A and bexactly. If a small change in these quantities results in a large change in the solution, x,then it seems clear this would be undesirable. In what follows ||·|| when applied to a lineartransformation will always refer to the operator norm. Recall the following property of theoperator norm in Theorem 10.7.3.

Lemma 14.1.1 Let A,B ∈L (X ,X) where X is a normed vector space as above. Then for||·|| denoting the operator norm, ||AB|| ≤ ||A|| ||B|| .

Lemma 14.1.2 Let A,B ∈L (X ,X) ,A−1 ∈L (X ,X) , and suppose

||B||< 1/∣∣∣∣A−1∣∣∣∣ .

Then (A+B)−1 ,(I +A−1B

)−1 exists and∥∥∥(I +A−1B)−1∥∥∥≤ (1− ∣∣∣∣A−1B

∣∣∣∣)−1(14.1)

∥∥∥(A+B)−1∥∥∥≤ ∣∣∣∣A−1∣∣∣∣ ∣∣∣∣ 1

1−||A−1B||

∣∣∣∣ . (14.2)

The above formula makes sense because∣∣∣∣A−1B

∣∣∣∣< 1.

Proof: By Lemma 10.7.3,∥∥A−1B∥∥≤ ∣∣∣∣A−1∣∣∣∣ ||B||< ∣∣∣∣A−1∣∣∣∣ 1

||A−1|| = 1 (14.3)

Then from the triangle inequality,∥∥(I +A−1B)

x∥∥ ≥ ||x||−

∣∣∣∣A−1Bx∣∣∣∣

≥ ||x||−∥∥A−1B

∥∥ ||x||= (1−∥∥A−1B∥∥) ||x||

It follows that I + A−1B is one to one because from 14.3, 1−∣∣∣∣A−1B

∣∣∣∣ > 0. Thus if(I +A−1B

)x = 0, then x = 0. Thus I +A−1B is also onto, taking a basis to a basis. Then a

generic y ∈ X is of the form y =(I +A−1B

)x and the above shows that∥∥∥(I +A−1B

)−1y∥∥∥≤ (1− ∣∣∣∣A−1B

∣∣∣∣)−1 ∥y∥

which verifies 14.1. Thus (A+B) =A(I +A−1B

)is one to one and this with Lemma 10.7.3

implies 14.2. ■

389