Guass Elimination Method

From the third row, we get,

From the second row, we get,

From the first row, we get,

In general, using a pivot, all the elements below that pivot in that column are made zeros. Alternately, at each stage of elimination, we may also make the pivot as 1, by dividing that particular row by the pivot.

Note :  When does the Gauss elimination method as described above fail? It fails when any one of the pivots is zero or it is a very small number, as the elimination progresses. If a pivot is zero, then division by it gives over flow error, since division by zero is not defined. If a pivot is a very small number, then division by it introduces large round-off errors and the solution may contain large errors.

For example, we may have the system

in which the first pivot is zero.

Pivoting Procedures: How do we avoid computational errors in Gauss elimination? To avoid computational errors, we follow the procedure of partial pivoting. In the first stage of elimination, the first column of the augmented matrix is searched for the largest element in magnitude and brought as the first pivot by interchanging the first row of the augmented matrix (first equation) with the row (equation) having the largest element in magnitude. In the second stage of elimination, the second column is searched for the largest element in magnitude among the n – 1 elements leaving the first element, and this element is brought as the second pivot by interchanging the second row of the augmented matrix with the later row having the largest element in magnitude. This procedure is continued until the upper triangular system is obtained. Therefore, partial pivoting is done after every stage of elimination. There is another procedure called complete pivoting. In this procedure, we search the entire matrix A in the augmented matrix for the largest element in magnitude and bring it as the first pivot This requires not only an interchange of the rows, but also an interchange of the positions of the variables. It is possible that the position of a variable is changed a number of times during this pivoting. We need to keep track of the positions of all the variables. Hence, the procedure is computationally expensive and is not used in any software.

Note: 

1. Gauss elimination method is a direct method. Therefore, it is possible to count the total number of operations, that is, additions, subtractions, divisions and multiplications. Without going into details, we mention that the total number of divisions and multiplications (division and multiplication take the same amount of computer time) is n (n² 3n – 1)/3. The total number of additions and subtractions (addition and subtraction take the same amount of computer time) is n (n – 1)(2n 5)/6.
2. When the system of algebraic equations is large, how do we conclude that it is consistent or not, using the Gauss elimination method? A way of determining the consistency is from the form of the reduced system (1.4). We know that if the system is inconsistent then rank (A) ≠ rank [A|b]. By checking the elements of the last rows, conclusion can be drawn about the consistency or inconsistency.

Suppose that in (1.4), a⁽²⁾₃₃ ≠ 0 and b⁽²⁾₃ ≠ 0. Then, rank (A) = rank [A|b] = 3. The system is consistent and has a unique solution. Suppose that we obtain the reduced system as

Then, rank (A) = 2, rank [A|b] = 3 and rank (A) ≠ rank [A|b]. Therefore, the system is inconsistent and has no solution. Suppose that we obtain the reduced system as

Then, rank (A) = rank [A|b] = 2 < 3. Therefore, the system has 3 – 2 = 1 parameter family of infinite number of solutions.