Page 421 - Matrix Analysis & Applied Linear Algebra

5.12 Singular Value Decomposition 417

Solution: Without realizing it, we answered this question in Example 5.12.1.
To bound the accuracy of ˜ x relative to the exact solution x, write r = b − A˜ x
as A˜ x = b − r, and apply (5.12.8) with e = r to obtain

κ −1 r 2 ≤ x − ˜ x ≤ κ r 2 , where κ = A 2
A −1
2 . (5.12.9)

b x b
2 2
Therefore, for a well-conditioned A, the residual r is relatively small if and
only if ˜ x is relatively accurate. However, as demonstrated in Example 5.12.1,
equality on either side of (5.12.9) is possible, so, when A is ill conditioned, a
very inaccurate approximation ˜ x can produce a small residual r, and a very
accurate approximation can produce a large residual.
Conclusion: Residuals are reliable indicators of accuracy only when A is well
conditioned—if A is ill conditioned, residuals are nearly meaningless.
In addition to measuring the distortion of the unit sphere and gauging the
sensitivity of linear systems, singular values provide a measure of how close A
is to a matrix of lower rank.

Distance to Lower-Rank Matrices
If σ 1 ≥ σ 2 ≥ ··· ≥ σ r are the nonzero singular values of A m×n , then
for each k< r, the distance from A to the closest matrix of rank k is

σ k+1 = min A − B 2 . (5.12.10)
rank(B)=k

D 0
Proof. Suppose rank (B m×n )= k, and let A = U V T be an SVD
0 0
for A with D = diag (σ 1 ,σ 2 ,...,σ r ) . Define S = diag (σ 1 ,...,σ k+1 ), and

partition V = F n×k+1 | G . Since rank (BF) ≤ rank (B)= k (by (4.5.2)),
dim N (BF)= k+1−rank (BF) ≥ 1, so there is an x ∈ N (BF) with x 2 =1.
Consequently, BFx = 0 and
     
S00 x Sx
D 0 T
AFx = U V Fx = U  0 0    = U  0  .
0
0 0
0 0 0 0 0
Since A − B = max y 2 =1 (A − B)y , and since Fx 2 = x 2 =1
2 2
(recall (5.2.4), p. 280, and (5.2.13), p. 283),
k+1 k+1
2 2 2 2 2
2
2
2
A − B ≥ (A − B)Fx = Sx = σ x ≥ σ x = σ .
2 2 2 i i k+1 i k+1
i=1 i=1
0
Equality holds for B k = U D k V T with D k = diag (σ 1 ,...,σ k ), and thus
0 0
(5.12.10) is proven.