Page 36 - Matrix Analysis & Applied Linear Algebra

28 Chapter 1 Linear Equations

Experience has shown that the following strategy for combining row scaling
with column scaling usually works reasonably well.

Practical Scaling Strategy

1. Choose units that are natural to the problem and do not dis-
tort the relationships between the sizes of things. These natural
units are usually self-evident, and further column scaling past
this point is not ordinarily attempted.
2. Row scale the system [A|b] so that the coefficient of maximum
magnitude in each row of A is equal to 1. That is, divide each
equation by the coefficient of maximum magnitude.
Partial pivoting together with the scaling strategy described above
makes Gaussian elimination with back substitution an extremely effec-
tive tool. Over the course of time, this technique has proven to be reliable
for solving a majority of linear systems encountered in practical work.

Although it is not extensively used, there is an extension of partial pivoting
known as complete pivoting which, in some special cases, can be more effective
than partial pivoting in helping to control the effects of roundoff error.

Complete Pivoting
If [A|b] is the augmented matrix at the k th step of Gaussian elimina-
tion, then search the pivotal position together with every position in A
that is below or to the right of the pivotal position for the coefficient
of maximum magnitude. If necessary, perform the appropriate row and
column interchanges to bring the coefficient of maximum magnitude into
the pivotal position. Shown below is the third step in a typical situation:
 
∗∗ ∗ ∗ ∗ ∗
 0 ∗ ∗ ∗ ∗ ∗ 
 
 00 S S ∗ 
S
00 S S S ∗
 
00 S S S ∗
Search the positions marked “ S ” for the coefficient of maximal magni-
tude. If necessary, interchange rows and columns to bring this maximal
coefficient into the circled pivotal position. Recall from Exercise 1.2.13
that the effect of a column interchange in A is equivalent to permuting
(or renaming) the associated unknowns.