Linear Algebra and Analysis

15.1 The Condition Number

Let A ∈ℒ

be a linear transformation where X is a finite dimensional vector space and consider the problem Ax = b where it is assumed there is a unique solution to this problem. How does the solution change if A is changed a little bit and if b is changed a little bit? This is clearly an interesting question because you often do not know A and b exactly. 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 linear transformation will always refer to the operator norm. Recall the following property of the operator norm in Theorem 11.6.3.

Proof: By Lemma 11.6.3,

||||A −1B|||| ≤ ||||A −1||||||B || < ||||A−1||||-1--= 1 (15.3) ||A− 1||

(15.3)

Then from the triangle inequality,

It follows that I + A⁻¹B is one to one because from 15.3, 1 − > 0. Thus if x = 0, then x = 0. Thus I + A⁻¹B is also onto, taking a basis to a basis. Then a generic y ∈ X is of the form y = x and the above shows that

∥∥( −1 )−1 ∥∥ ( |||| −1 ||||)−1 ∥ I + A B y∥ ≤ 1− A B ∥y∥

which verifies 15.1. Thus

= A is one to one and this with Lemma 11.6.3 implies 15.2. ■

Proof: This follows from the above lemma.

because A⁻¹b∕ is a unit vector. Now multiply and divide by . Then

This shows that the number,

, controls how sensitive the relative change in the solution of Ax = b is to small changes in A and b. This number is called the condition number. It is bad when this number is large because a small relative change in b, for example could yield a large relative change in x.

Recall that for A an n × n matrix,

₂ = σ₁ where σ₁ is the largest singular value. The largest singular value of A⁻¹ is therefore, 1/σ_n where σ_n is the smallest singular value of A. Therefore, the condition number is controlled by σ₁∕σ_n, the ratio of the largest to the smallest singular value of A provided the norm is the usual Euclidean norm.