Page 31 - Matrix Analysis & Applied Linear Algebra

1.5 Making Gaussian Elimination Work 23

Since

2
fl fl(m)fl(47) = fl(1.89 × 47) = .888 × 10 =88.8,

2
fl fl(m)fl(28) = fl(1.89 × 28) = .529 × 10 =52.9,

2
fl fl(m)fl(19) = fl(1.89 × 19) = .359 × 10 =35.9,
the first step of 3-digit Gaussian elimination is as shown below:

47 28 19
fl(89 − 88.8) fl(53 − 52.9) fl(36 − 35.9)

47 28 19
= .
.2
.1 .1
The goal is to triangularize the system—to produce a zero in the circled
(2,1)-position—but this cannot be accomplished with 3-digit arithmetic. Unless
the circled value is replaced by 0, back substitution cannot be executed.
.2
Henceforth, we will agree simply to enter 0 in the position that we are trying
to annihilate, regardless of the value of the floating-point number that might
actually appear. The value of the position being annihilated is generally not
even computed. For example, don’t even bother computing

fl 89 − fl fl(m)fl(47) = fl(89 − 88.8) = .2
in the above example. Hence the result of 3-digit Gaussian elimination for this
example is

47 28 19
.
0 .1 .1
Apply 3-digit back substitution to obtain the 3-digit floating-point solution

.1
y = fl =1,
.1

19 − 28 −9
x = fl = fl = −.191.
47 47
The vast discrepancy between the exact solution (1, −1) and the 3-digit
solution (−.191, 1) illustrates some of the problems we can expect to encounter
while trying to solve linear systems with floating-point arithmetic. Sometimes
using a higher precision may help, but this is not always possible because on
all machines there are natural limits that make extended precision arithmetic
impractical past a certain point. Even if it is possible to increase the precision, it