Page 317 - Matrix Analysis & Applied Linear Algebra

5.5 Gram–Schmidt Procedure 313

While the LU and QR factors can be used in more or less the same way to
solve nonsingular systems, things are different for singular and rectangular cases
because Ax = b might be inconsistent, in which case a least squares solution
as described in §4.6, (p. 223) may be desired. Unfortunately, the LU factors of
A don’t exist when A is rectangular. And even if A is square and has an
LU factorization, the LU factors of A are not much help in solving the system
T
T
of normal equations A Ax = A b that produces least squares solutions. But
the QR factors of A m×n always exist as long as A has linearly independent
columns, and, as demonstrated in the following example, the QR factors provide
the least squares solution of an inconsistent system in exactly the same way as
they provide the solution of a consistent system.
Example 5.5.3
Application to the Least Squares Problem. If Ax = b is a possibly in-
consistent (real) system, then, as discussed on p. 226, the set of all least squares
solutions is the set of solutions to the system of normal equations
T
T
A Ax = A b. (5.5.5)
T
T
But computing A A and then performing an LU factorization of A A to solve
(5.5.5) is generally not advisable. First, it’s inefficient and, second, as pointed
T
out in Example 4.5.1, computing A A with floating-point arithmetic can result
in a loss of significant information. The QR approach doesn’t suffer from either
of these objections. Suppose that rank (A m×n )= n (so that there is a unique
least squares solution), and let A = QR be the QR factorization. Because the
T
columns of Q are an orthonormal set, it follows that Q Q = I n , so
T
T
T
T
T
A A =(QR) (QR)= R Q QR = R R. (5.5.6)
Consequently, the normal equations (5.5.5) can be written as
T
T
T
R Rx = R Q b. (5.5.7)
But R T is nonsingular (it is triangular with positive diagonal entries), so (5.5.7)
simplifies to become
T
Rx = Q b. (5.5.8)
This is just an upper-triangular system that is efficiently solved by back substi-
tution. In other words, most of the work involved in solving the least squares
problem is in computing the QR factorization of A. Finally, notice that

T
T
T
x = R −1 Q b = A A −1 A b
is the solution of Ax = b when the system is consistent as well as the least
squares solution when the system is inconsistent (see p. 214). That is, with the
QR approach, it makes no difference whether or not Ax = b is consistent
because in both cases things boil down to solving the same equation—namely,
(5.5.8). Below is a formal summary.