Page 418 - Matrix Analysis & Applied Linear Algebra

414 Chapter 5 Norms, Inner Products, and Orthogonality

Image of the Unit Sphere

Fora nonsingular A n×n having singular values σ 1 ≥ σ 2 ≥· · · ≥ σ n
and an SVD A = UDV T with D = diag (σ 1 ,σ 2 ,...,σ n ) , the image
of the unit 2-sphere is an ellipsoid whose k th semiaxis is given by σ k U ∗k
(see Figure 5.12.1). Furthermore, V ∗k is a point on the unit sphere such
that AV ∗k = σ k U ∗k . In particular,

• σ 1 = AV ∗1 2 = max Ax 2 = A 2 , (5.12.4)
x 2 =1
• σ n = AV ∗n 2 = min Ax 2 =1/ A −1 2 . (5.12.5)
x 2 =1
The degree of distortion of the unit sphere under transformation by A
is measured by the 2-norm condition number
σ 1
• κ 2 = = A 2
A −1
2 ≥ 1. (5.12.6)
σ n
Notice that κ 2 =1 if and only if A is an orthogonal matrix.

The amount of distortion of the unit sphere under transformation by A
determines the degree to which uncertainties in a linear system Ax = b can be
magnified. This is explained in the following example.
Example 5.12.1
Uncertainties in Linear Systems. Systems of linear equations Ax = b aris-
ing in practical work almost always come with built-in uncertainties due to mod-
eling errors (because assumptions are almost always necessary), data collection
errors (because infinitely precise gauges don’t exist), and data entry errors (be-
√
cause numbers like 2,π, and 2/3 can’t be entered exactly). In addition,
roundoff error in floating-point computation is a prevalent source of uncertainty.
In all cases it’s important to estimate the degree of uncertainty in the solution
of Ax = b. This is not difficult when A is known exactly and all uncertainty
resides in the right-hand side. Even if this is not the case, it’s sometimes possible
to aggregate uncertainties and shift all of them to the right-hand side.
Problem: Let Ax = b be a nonsingular system in which A is known exactly
˜
but b is subject to an uncertainty e, and consider A˜ x = b − e = b. Estimate
58
the relative uncertainty x − ˜ x / x in x in terms of the relative uncertainty
˜
b − b / b = e / b in b. Use any vector norm and its induced matrix
norm (p. 280).
58
Knowing the absolute uncertainty x − ˜ x by itself may not be meaningful. For example, an
absolute uncertainty of a half of an inch might be fine when measuring the distance between
the earth and the moon, but it’s not good in the practice of eye surgery.