Page 350 - Matrix Analysis & Applied Linear Algebra

346 Chapter 5 Norms, Inner Products, and Orthogonality
Example 5.7.3

Orthogonal Reduction and Least Squares. Orthogonal reduction can be
used to solve the least squares problem associated with an inconsistent system
m×n
Ax = b in which A ∈ and m ≥ n (the most common case). If ε
denotes the difference ε = Ax − b, then, as described on p. 226, the general
least squares problem is to find a vector x that minimizes the quantity
m
2 T 2
ε = ε ε = ε ,
i
i=1
where is the standard euclidean vector norm. Suppose that A is reduced
to an upper-trapezoidal matrix T by an orthogonal matrix P, and write

R n×n c n×1
PA = T = and Pb =
0 d
in which R is an upper-triangular matrix. An orthogonal matrix is an isometry—
recall (5.6.1)—so that

2

2
2
2
2
ε = Pε = P(Ax − b) =
R x − c
=
Rx − c

0 d

d
2 2
= Rx − c + d .
2 2
Consequently, ε is minimized when x is a vector such that Rx − c is
minimal or, in other words, x is a least squares solution for Ax = b if and only
if x is a least squares solution for Rx = c.
Full-Rank Case. In a majority of applications the coefficient matrix A has
linearly independent columns so rank (A m×n )= n. Because multiplication by
a nonsingular matrix P does not change the rank,
n = rank (A)= rank (PA)= rank (T)= rank (R n×n ).
Thus R is nonsingular, and we have established the following fact.
• If A has linearly independent columns, then the (unique) least squares so-
lution for Ax = b is obtained by solving the nonsingular triangular system
Rx = c for x.
T
As pointed out in Example 4.5.1, computing the matrix product A A is to be
avoided when floating-point computation is used because of the possible loss of
significant information. Notice that the method based on orthogonal reduction
T
T
sidesteps this potential problem because the normal equations A Ax = A b
T
are avoided and the product A A is never explicitly computed. Householder
reduction (or Givens reduction for sparse problems) is a numerically stable algo-
rithm (see the discussion following this example) for solving the full-rank least
squares problem, and, if the computations are properly ordered, it is an attrac-
tive alternative to the method of Example 5.5.3 that is based on the modified
Gram–Schmidt procedure.