Analysis of Algorithms : An Active Learning Approach

118 NUMERIC ALGORITHMS

The basic plan is to divide the first row by the value in the first column and

then subtract multiples of this new first row from each of the other rows. In

our example, the second row would have the new first row subtracted from it,

the third row would have 3 times the new first row subtracted from it, and the

fourth row would have 8 times the new first row subtracted from it. You should

recognize that this would create the proper first column. This new matrix is

We now repeat this process for the second row. After we divide each of the

values in this row by the number in the second column (1.5), we use the values

in the second column of the other rows to determine how much this row is

multiplied by for each subtraction. The new matrix is now (values shown are

rounded)

We now repeat this process, using the third row to clear out the third col-

umn and the fourth row to clear out the fourth column. This gives the next

two matrices:

1 3.5 0.5 2.5 35

0 1.5 2.5 –0.5 10

0 – 8.5 2.5 –6.5 – 72

027 – 117 – – 224

1 0 – 5.33 3.66 11.7

0 1 1.67 –0.33 6.67

0 0 16.7 –9.3 –15.3

0 0 46 – 26 – 44

1 0 0 0.68 6.76

0 1 0 0.6 8.2

0 0 1 – 0.56 –0.92

0 0 0 – 0.24 –1.68

10002

01004

00103

00017