2.4.3 Gaussian Elimination

Gaussian Elimination is considered the workhorse of computational science for the solution of a system of linear equations. Karl Friedrich Gauss, a great 19^th century mathematician, suggested this elimination method as a part of his proof of a particular theorem. Computational scientists use this “proof” as a direct computational method.

Gaussian Elimination is a systematic application of elementary row operations to a system of linear equations in order to convert the system to upper triangular form. Once the coefficient matrix is in upper triangular form, we use back substitution to find a solution.

The general procedure for Gaussian Elimination can be summarized in the following steps:

Gaussian Elimination Steps

Write the augmented matrix for the system of linear equations.

Use elementary row operations on the augmented matrix [A|b] to transform A into upper triangular form. If a zero is located on the diagonal, switch the rows until a nonzero is in that place. If you are unable to do so, stop; the system has either infinite or no solutions.

Use back substitution to find the solution of the problem.

An Example.

We will illustrate each step of Gaussian Elimination with a system of three linear equations in three variables, using the compact notation of augmented matrices. As we go through the steps of Gaussian Elimination with our 3 x 3 example system, keep in mind that although the numbers in the augmented matrix may change significantly after each elementary row operation, our solution set has not changed.

1. Write the augmented matrix for the system of linear equations.

We use the symbol to indicate that the matrix preceding the arrow will be changed using the operation specified; the matrix following the arrow displays the result of that change. Let r1, r2, and r3 denote rows 1, 2, and 3, respectively. We will also use a shorthand to represent the particular elementary row operations used to change an intermediate augmented matrix. For example,

written to the right of row three of an augmented matrix means: Replace row three with four times row three plus negative one-third times row two. Note that computational scientists usually denote multiplication with an asterisk, so you will see u*v rather than u·v or u x v when u and v are to be multiplied.

2. Use elementary row operations on the augmented matrix [A|b] to transform A into upper triangular form.

Since all of the nonzero elements are now located in the “upper triangle” of the matrix, we have completed the first phase of solving a system of linear equations using Gaussian Elimination.

Notice that our original coefficient matrix had a “0” on the diagonal in row 1. Since we needed to use multiples of that diagonal element to eliminate the elements below it, we switched two rows in order to move a nonzero element into that position. We can use the same technique when a “0” appears on the diagonal as a result of calculation. If it is not possible to move a nonzero onto the diagonal by interchanging rows, then the system has either infinitely many solutions or no solution, and the coefficient matrix is said to be singular.

The second and final phase of Gaussian Elimination is back substitution. During this phase, we solve for the values of the unknowns, working our way up from the bottom row.

3. Use back substitution to find the solution of the problem.

The last row in the augmented matrix represents the equation

. The second row of the augmented matrix represents the equation

2y + z = 4.

Substituting the value of z into this equation and solving for y gives us:

Finally, the first row of the augmented matrix represents the equation

x + y + 2z = 6.

Substituting the values of y and z into the first equation yields:

Send comments on material to Cynthia Lanius

These pages are maintained by Hilena Vargas (hvargas@rice.edu)
Updated: February 20, 2009