5.2 Cost of Solving a System of Linear Equations Using Gauss-Jordan Elimination

Now we will solve the same 3 x 3 example using Gauss-Jordan Elimination.

To calculate the cost of Gauss-Jordan Elimination, we begin by counting the number of arithmetic operations necessary to convert the coefficient matrix of the original system to a diagonal matrix.

In the first step, we introduced zeros in the first column beginning in row 2. We performed exactly the same operations that we used when we applied Gaussian Elimination to the problem. So the calculations require 4(2) multiplications and 3(2) additions.

For the second step, we needed to eliminate the second element in the third row and the second element in the first row. This step required 3 multiplications and 2 additions on each of 2 rows. For the third step, we needed to eliminate the third elements from the first and second rows. This step requires 2 multiplications and 1 addition on each of the 2 rows.

We can write the total operation count so far as

Once the matrix was in diagonal form, we divided the diagonal element and the right-hand-side element of each row by the that row's diagonal element. This last step required 3 multiplications. Hence the total operation count for Gauss-Jordan on our 3 x 3 example is 21 multiplications and 12 additions. (Recall that Gaussian Elimination required 17 multiplications and 11 additions.)

Now let us consider solving a general n x n system using Gauss-Jordan Elimination.

Step 1: Introduce zeros in the first column.

Step 2: Introduce zeros in the second column.

We continue eliminating elements below and above the diagonals for columns three through n-1. The last step is to introduce zeros above the diagonal element in the the n^th column of the matrix. Once this step is complete we have a diagonal matrix.

Step n: Introduce zeros in the n^th column.

At this point, column (n+1) of the augmented matrix is the solution of the system of equations. Adding together all of the operations required for Gauss-Jordan Elimination for a general system of n linear equations, we find that there are

As before, we can use the expression for the sum of the first n integers to rewrite the number of multiplications required for Gauss-Jordan Elimination as