Page 352 - Matrix Analysis & Applied Linear Algebra

348 Chapter 5 Norms, Inner Products, and Orthogonality

during the process. To see this from a heuristic point of view, consider the LU
factorization of A = LU, and suppose that floating-point Gaussian elimination
with no pivoting returns matrices L + E and U + F that are the exact LU
factors of a somewhat different matrix
˜
A =(L + E)(U + F)= LU + LF + EU + EF = A + LF + EU + EF.

If E and F account for the roundoff errors, and if their entries are small relative
to those in A, then the entries in EF are negligible, and

˜
A ≈ A + LF + EU (using no pivoting).
However, if L or U contains entries that are large relative to those in A
(and this is certainly possible), then LF or EU can contain entries that are
significant. In other words, Gaussian elimination with no pivoting can return the
˜
LU factorization of a matrix A that is not very close to the original matrix
A, and this is what it means to say that an algorithm is unstable. We saw on
p. 26 that if partial pivoting is employed, then no multiplier can exceed 1 in
magnitude, and hence no entry of L can be greater than 1 in magnitude (recall
that the subdiagonal entries of L are in fact the multipliers). Consequently,
L cannot greatly magnify the entries of F, so, if the rows of A have been
reordered according to the partial pivoting strategy, then

˜
A ≈ A + EU (using partial pivoting).
˜
Numerical stability requires that A ≈ A, so the issue boils down to the degree
to which U magnifies the entries in E —i.e., the issue rests on the magnitude of
the entries in U. Unfortunately, partial pivoting may not be enough to control
the growth of all entries in U. For example, when Gaussian elimination with
partial pivoting is applied to

 
1 0 0 ··· 0 0 1
 −1 1 0 ··· 0 0 1 
 . 
 . 
 −1 −1 1 . 0 0 1 
 . . . . . . . 
W n =  . . . . . . . . . . . . .  ,
 . 
 . . 
−1 −1 −1 1 0 1
 . 
 
−1 −1 −1 ··· −1 1 1
 
−1 −1 −1 ··· −1 −11
the largest entry in U is u nn =2 n−1 . However, if complete pivoting is used on
W n , then no entry in the process exceeds 2 in magnitude (Exercises 1.5.7 and
1.5.8). In general, it has been proven that if complete pivoting is used on a well-
scaled matrix A n×n for which max |a ij | =1, then no entry of U can exceed