Page 32 - Matrix Analysis & Applied Linear Algebra

24 Chapter 1 Linear Equations

may not buy you very much because there are many cases for which an increase
in precision does not produce a comparable decrease in the accumulated roundoff
error. Given any particular precision (say, t ), it is not difficult to provide exam-
ples of linear systems for which the computed t-digit solution is just as bad as
the one in our 3-digit example above.
Although the effects of rounding can almost never be eliminated, there are
some simple techniques that can help to minimize these machine induced errors.

Partial Pivoting

At each step, search the positions on and below the pivotal position for
the coefficient of maximum magnitude. If necessary perform the appro-
priate row interchange to bring this maximal coefficient into the pivotal
position. Illustrated below is the third step in a typical case:

 
∗ ∗ ∗ ∗ ∗ ∗
 0 ∗ ∗ ∗ ∗ ∗ 
 
S
 00 ∗∗ ∗  .
00 S ∗∗ ∗
 
00 S ∗∗ ∗
Search the positions in the third column marked “ S ” for the coefficient
of maximal magnitude and, if necessary, interchange rows to bring this
coefficient into the circled pivotal position. Simply stated, the strategy
is to maximize the magnitude of the pivot at each step by using only
row interchanges.

On the surface, it is probably not apparent why partial pivoting should
make a difference. The following example not only shows that partial pivoting
can indeed make a great deal of difference, but it also indicates what makes this
strategy effective.
Example 1.5.1
It is easy to verify that the exact solution to the system

−10 −4 x + y =1,
x + y =2,

is given by
1 1.0002
x = and y = .
1.0001 1.0001
If 3-digit arithmetic without partial pivoting is used, then the result is