Page 37 - Matrix Analysis & Applied Linear Algebra

1.5 Making Gaussian Elimination Work 29

You should be able to see that complete pivoting should be at least as effec-
tive as partial pivoting. Moreover, it is possible to construct specialized exam-
ples where complete pivoting is superior to partial pivoting—a famous example
is presented in Exercise 1.5.7. However, one rarely encounters systems of this
nature in practice. A deeper comparison between no pivoting, partial pivoting,
and complete pivoting is given on p. 348.
Example 1.5.3

Problem: Use 3-digit arithmetic together with complete pivoting to solve the
following system:

x − y = −2,
−9x +10y =12.

Solution: Since 10 is the coefficient of maximal magnitude that lies in the
search pattern, interchange the first and second rows and then interchange the
first and second columns:

1 −1 −2 −9 10 12
−→
−9 10 12 1 −1 −2

10 −9 12 10 −9 12
−→ −→ .
−1 1 −2 0 .1 −.8
The effect of the column interchange is to rename the unknowns to ˆx and ˆy,
where ˆx = y and ˆ = x. Back substitution yields ˆ = −8 and ˆx = −6 so that
y
y
x =ˆ = −8 and y =ˆx = −6.
y

In this case, the 3-digit solution and the exact solution agree. If only partial
pivoting is used, the 3-digit solution will not be as accurate. However, if scaled
partial pivoting is used, the result is the same as when complete pivoting is used.

If the cost of using complete pivoting was nearly the same as the cost of using
partial pivoting, we would always use complete pivoting. However, it is not diffi-
cult to show that complete pivoting approximately doubles the cost over straight
Gaussian elimination, whereas partial pivoting adds only a negligible amount.
Couple this with the fact that it is extremely rare to encounter a practical system
where scaled partial pivoting is not adequate while complete pivoting is, and it
is easy to understand why complete pivoting is seldom used in practice. Gaus-
sian elimination with scaled partial pivoting is the preferred method for dense
systems (i.e., not a lot of zeros) of moderate size.