Page 431 - Matrix Analysis & Applied Linear Algebra

5.12 Singular Value Decomposition 427

5.12.11. Bound the relative uncertainty in the solution of a nonsingular system
Ax = b for which there is some uncertainty in A but not in b by

E < 1 for any matrix
showing that if (A−E)˜ x = b, where α = A −1

norm such that I =1, then
x − ˜ x κ E

≤ , where κ = A A −1
.
x 1 − α A
Note: If the 2-norm is used, then E <σ n insures α< 1.
2
Hint: If B = A −1 E, then A − E = A(I − B), and α = B < 1

k k
=⇒
B k
≤ B → 0 =⇒ B → 0, so the Neumann series
i
expansion (p. 126) yields (I − B) −1 = ∞ B .
i=0
5.12.12. Now bound the relative uncertainty in the solution of a nonsingular
system Ax = b for which there is some uncertainty in both A and b

E < 1 for any
by showing that if (A − E)˜ x = b − e, where α = A −1

matrix norm such that I =1, then

x − ˜ x κ e E
≤ + , where κ = A A −1
.

x 1 − κ E / A b A
Note: If the 2-norm is used, then E <σ n insures α< 1. This
2
exercise underscores the conclusion of Example 5.12.1 stating that if A
is well conditioned, and if the relative uncertainties in A and b are
small, then the relative uncertainty in x must be small.

−4 −2 −4 −2
5.12.13. Consider the matrix A = 2 −2 2 1 .
−4 1 −4 −2
(a) Use the URV factorization you computed in Exercise 5.11.8 to
determine A .
†
(b) Now use the URV factorization you obtained in Exercise 5.11.9
to determine A . Do your results agree with those of part (a)?
†
T
5.12.14. For matrix A in Exercise 5.11.8, and for b =( −12 3 −9) , find
the solution of Ax = b that has minimum euclidean norm.

5.12.15. Suppose A = URV T is a URV factorization (so it could be an SVD)
of an m × n matrix of rank r, and suppose U is partitioned as U =
T
†
U 1 | U 2 , where U 1 is m × r. Prove that P = U 1 U = AA is the
1
T
projector onto R (A) along N A . In this case, P is said to be an or-
thogonal projector because its range is orthogonal to its nullspace. What
T
is the orthogonal projector onto N A along R (A)? (Orthogonal
projectors are discussed in more detail on p. 429.)