Gaussian elimination is an algorithm that allows to transform a system of linear equations into an equivalent system (i.e., a system having the same solutions as the original one) in row echelon form. Elementary row operations are performed on the system until the system is in row echelon form. Then, it can be easily solved by back-substitution.
Before reading this lecture, you should be familiar with:
the concept of equivalent system;
the row echelon form.
We are given a linear system of equations in unknowns that can be represented in matrix form aswhere is the matrix of coefficients, is the vector of constants and is the vector of unknowns.
The aim is to reduce it to an equivalent system in row echelon form, that is, an equivalent system whose coefficient matrix has the following characteristics:
zero-rows (if there are any) are preceded by non-zero rows;
all non-zero rows contain an element, called pivot, that is non-zero and has only zero entries below it and to its left.
The aim is achieved by repeatedly performing two elementary row operations:
interchanging the order of two equations;
adding a multiple of one equation to another equation.
Note: for the sake of simplicity, we are going to denote the coefficient matrix of the system by both before and after performing an elementary row operation, even if strictly speaking they are two different matrices.
We first present the steps of the Gaussian elimination algorithm in a rigorous manner, by listing them as if we were writing a computer program. We then explain them carefully.
The steps are as follows:
Start from and .
Increment by one unit.
Increment by one unit.
Stop the algorithm if . Else proceed to the next step.
If for , return to step 3. Else proceed to the next step.
Interchange the -th equation with any equation (with ) such that (if there is no need to perform an interchange).
For , add times the -th equation to the -th equation.
If , return to step 2. Else stop the algorithm.
In order to better understand the algorithm, note the following things:
we loop over the rows of the matrix; we start from the first row ( after steps 1 and 2); then, we move downwards by one row at a time ( when we reach step 8 and return to step 2);
we try to create a pivot on the current row (the -th), at the intersection with the -th column; we start from the first column ( after steps 1 and 3); then, we increment by one unit:
when we fail to create a pivot in the current column; in this case, the column is a non-basic column; we remain on the same row and look for a pivot in the next column (we go from step 5 to step 3, and we increment only );
when we manage to create a pivot in the current column; in this case, the column is a basic column; we move to the next row (we go from step 8 to step 2 and 3; and we increment both and );
we want a pivot at the intersection of the -th column and the -th row (called pivotal position) and a pivot must be non-zero; therefore, if , we interchange the rows (step 6) so as to bring a non-zero entry in position ; this operation fails if for ; this is the reason why we search for a non-zero entry in step 5 and we move to the next column if we do not find any;
once we have a non-zero entry in position , we perform elementary row operations aimed at making all the entries below it equal to zero (step 7); that the elements below it and to its left are zero is ensured by the fact that either they were made equal to zero in previous iterations (for basic columns) or they were already equal to zero (for non-basic columns);
the algorithm ends either when we reach the penultimate row (step 8) or when there are no more columns to scan for pivots (step 4);
we do not go to the last row because there are no rows below it on which we can perform elementary row operations (nothing to do in steps 6 and 7).
We now present several examples to show how Gaussian elimination works in practice.
Throughout this section, we will use augmented matrices to parsimoniously represent systems of linear equations. If you are not familiar with the concept of augmented matrix, you should revise it before reading the examples.
Example Consider the system of three equations in three unknownsThe augmented matrix of the system isWe start from row and column . We have , so we do not need to interchange rows. We add times the first row to the second, and obtainWe addtimes the first row to the third, and getWe now go to row and column . We have . However, , so we interchange the second row with the third:The only entry below is already zero, so we do not need to perform row additions. We are done with the penultimate row, so the Gaussian elimination algorithm stops. The matrix of coefficients (to the left of the vertical line) is in row echelon form because all of its rows have a pivot. The pivots are , and .
Example Consider the system of three equations in four unknownsThe augmented matrix of the system isWe start from row and column . We have , so we do not need to interchange rows. We add times the first row to the second, and obtainAll of the entries below are zero, so we are done with the first column. We now go to row and column . We have that and all of the entries below it are zero. Therefore, we cannot perform any row operation. Thus, the second column is a non-basic column and we need to go to the next column, without changing row. So, and . We have that , so there is no need to interchange rows. We add times the second row to the third, and obtainWe are done with the penultimate row, so the Gaussian elimination algorithm stops. The matrix of coefficients is in row echelon form because all of its rows have a pivot. The pivots are , and .
Note that in step 6 of the Gaussian elimination algorithm we have not specified a criterion for choosing which row to interchange with the current row (in case there is more than one possibility).
When we implement the Gaussian elimination algorithm on a computer, the criterion we usually follow is to choose the interchange that moves the largest element (in absolute value) to the pivotal position. This is done to improve the numerical stability of the algorithm: since in step 7 we compute the ratio , we want to be as far from zero as possible (to avoid division by zero problems caused by numerical round-off); as a consequence, we choose the row interchange so as to make the absolute value of as large as possible.
This method of choosing the pivot is called partial pivoting.
Another version of the algorithm is the so-called Gaussian elimination with complete pivoting, in which the absolute value of the pivot is maximized not only by exchanging rows, but also by exchanging columns (i.e., by changing the order of the unknowns). In step 6 of this algorithm we search all the quadrant of the coefficient matrix below and to the right of the pivotal position for the element that has the largest absolute value and then we move that element to the pivotal position with a row and a column interchange.
Below you can find some exercises with explained solutions.
Use the Gaussian elimination algorithm with partial pivoting to reduce the systemto row echelon form.
We start from row and column . The largest element in the first column is . So, we interchange the fourth row with the first:We add times the first row to the fourth row:We move to row and column . The largest element in the second column is . So, we interchange the third row with the second:We add times the second row to the third row:We add times the second row to the fourth row:The system is now in row echelon form: it last row is zero; all the rows above it are non-zero and have a pivot.
Most of the learning materials found on this website are now available in a traditional textbook format.