Page 24 - Matrix Analysis & Applied Linear Algebra

16 Chapter 1 Linear Equations

Solution: The sequence of operations is indicated in parentheses and the pivots
are circled.
   
2
1
2 6 4 R 1 /2 1 3 2
 2 1 7 6  −→  2 1 7 6  R 2 − 2R 1
−2 −6 −7 −1 −2 −6 −7 −1 R 3 +2R 1
   
1
1 3 2 1 1 3 2 R 1 − R 2
1
−→  0 −1 1 2  (−R 2 ) −→  0 −1 −2 
0 −4 −1 3 0 −4 −1 3 R 3 +4R 2
   
1 0 4 4 10 4 4 R 1 − 4R 3
1
−→  0 −1 −2  −→  01 −1 −2  R 2 + R 3
0 0 −5 −5 −R 3 /5 00 1
1
 
10 0 0
−→  01 0 −1  .
00 1
1
   
x 1 0
Therefore, the solution is  x 2  =  −1  .
x 3 1

On the surface it may seem that there is little difference between the Gauss–
Jordan method and Gaussian elimination with back substitution because elimi-
nating terms above the pivot with Gauss–Jordan seems equivalent to performing
back substitution. But this is not correct. Gauss–Jordan requires more arithmetic
than Gaussian elimination with back substitution.

Gauss–Jordan Operation Counts

For an n × n system, the Gauss–Jordan procedure requires

n 3 n 2
+ multiplications/divisions
2 2
and
n 3 n
− additions/subtractions.
2 2
3
In other words, the Gauss–Jordan method requires about n /2 multipli-
cations/divisions and about the same number of additions/subtractions.

Recall from the previous section that Gaussian elimination with back sub-
3
stitution requires only about n /3 multiplications/divisions and about the same