Page 353 - Matrix Analysis & Applied Linear Algebra

5.7 Orthogonal Reduction 349

1 1/2 1/3
γ = n 1/2 2 3 4 ··· n 1/n−1 1/2 in magnitude. Since γ is a slow growing
function of n, the entries in U won’t greatly magnify the entries of E, so

˜
A ≈ A (using complete pivoting).

In other words, Gaussian elimination with complete pivoting is stable, but Gaus-
sian elimination with partial pivoting is not. Fortunately, in practical work it is
rare to encounter problems such as the matrix W n in which partial pivoting
fails to control the growth in the U factor, so scaled partial pivoting is generally
considered to be a “practically stable” algorithm.
Algorithms based on the Gram–Schmidt procedure are more complicated.
First, the Gram–Schmidt algorithms differ from Householder and Givens reduc-
tions in that the Gram–Schmidt procedures are not a sequential application of
elementary orthogonal transformations. Second, as an algorithm to produce the
QR factorization even the modified Gram–Schmidt technique can return a Q
factor that is far from being orthogonal, and the intuitive stability argument
used earlier is not valid. As an algorithm to return the QR factorization of A,
the modified Gram–Schmidt procedure has been proven to be unstable, but as
an algorithm used to solve the least squares problem (see Example 5.5.3), it is
stable—i.e., stability of modified Gram–Schmidt is problem dependent.

Summary of Numerical Stability

• Gaussian elimination with scaled partial pivoting is theoretically un-
stable, but it is “practically stable”—i.e., stable for most practical
problems.

• Complete pivoting makes Gaussian elimination unconditionally sta-
ble.
• For the QR factorization, the Gram–Schmidt procedure (classical
or modified) is not stable. However, the modified Gram–Schmidt
procedure is a stable algorithm for solving the least squares problem.
• Householder and Givens reductions are unconditionally stable algo-
rithms for computing the QR factorization.

For the algorithms under consideration, the number of multiplicative oper-
ations is about the same as the number of additive operations, so computational
effort is gauged by counting only multiplicative operations. For the sake of com-
parison, lower-order terms are not significant, and when they are neglected the
following approximations are obtained.