Page 419 - Matrix Analysis & Applied Linear Algebra

5.12 Singular Value Decomposition 415

Solution: Use b = Ax ≤ A x with x − ˜ x = A −1 e to write

e

x − ˜ x
A −1
A A −1
e e
= ≤ = κ , (5.12.7)
x x b b

where κ = A A −1
is a condition number as discussed earlier (κ = σ 1 /σ n

if the 2-norm is used). Furthermore, e = A(x − ˜ x) ≤ A (x − ˜ x) and

x ≤ A −1
b imply

x − ˜ x e e 1 e
≥ ≥ = .
x A x A A −1 b κ b
This with (5.12.7) yields the following bounds on the relative uncertainty:

κ −1 e ≤ x − ˜ x ≤ κ e , where κ = A A −1
. (5.12.8)

b x b
In other words, when A is well conditioned (i.e., when κ is small—see the rule
of thumb in Example 3.8.2 to get a feeling of what “small” and “large” might
mean), (5.12.8) insures that small relative uncertainties in b cannot greatly
affect the solution, but when A is ill conditioned (i.e., when κ is large), a
relatively small uncertainty in b might result in a relatively large uncertainty
in x. To be more sure, the following problem needs to be addressed.
Problem: Can equality be realized in each bound in (5.12.8) for every nonsin-
gular A, and if so, how?

Solution: Use the 2-norm, and let A = UDV T be an SVD so AV ∗k = σ k U ∗k
for each k. If b and e are directed along left-hand singular vectors associated
with σ 1 and σ n , respectively—say, b = βU ∗1 and e = U ∗n , then

x = A −1 b = A −1 (βU ∗1 )= βV ∗1 and x−˜ x = A −1 e = A −1 ( U ∗n )= V ∗n ,
σ 1 σ n
so

x − ˜ x σ 1 | | e
2 = = κ 2 2 when b = βU ∗1 and e = U ∗n .
x σ n |β| b
2 2
Thus the upper bound (the worst case) in (5.12.8) is attainable for all A. The
lower bound (the best case) is realized in the opposite situation when b and e
are directed along U ∗n and U ∗1 , respectively. If b = βU ∗n and e = U ∗1 ,
then the same argument yields x = σ −1 βV ∗n and x − ˜ x = σ 1 −1 V ∗1 , so
n

x − ˜ x σ n | | e
2 = = κ −1 2 when b = βU ∗n and e = U ∗1 .
x σ 1 |β| 2 b
2 2