1 Gaussian elimination

Recall from HELM booklet  8 that the basic idea with Gaussian (or Gauss) elimination is to replace the matrix of coefficients with a matrix that is easier to deal with. Usually the nicer matrix is of upper triangular form which allows us to find the solution by back substitution . For example, suppose we have

which we can abbreviate using an augmented matrix to

$\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 3\hfill & \hfill -5\hfill & \hfill 2\hfill \\ \hfill 3\hfill & \hfill 11\hfill & \hfill -9\hfill & \hfill 4\hfill \\ \hfill -1\hfill & \hfill 1\hfill & \hfill 6\hfill & \hfill 5\hfill \end{array}\right].$

We use the boxed element to eliminate any non-zeros below it. This involves the following row operations

$\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 3\hfill & \hfill -5\hfill & \hfill 2\hfill \\ \hfill 3\hfill & \hfill 11\hfill & \hfill -9\hfill & \hfill 4\hfill \\ \hfill -1\hfill & \hfill 1\hfill & \hfill 6\hfill & \hfill 5\hfill \end{array}\right]\begin{array}{c}\hfill \\ R2-3\times R1\hfill \\ R3+R1\hfill \end{array}\Rightarrow \left[\begin{array}{cccc}\hfill 1\hfill & \hfill 3\hfill & \hfill -5\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 2\hfill & \hfill 6\hfill & \hfill -2\hfill \\ \hfill 0\hfill & \hfill 4\hfill & \hfill 1\hfill & \hfill 7\hfill \end{array}\right].$

And the next step is to use the 2 to eliminate the non-zero below it . This requires the final row operation

$\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 3\hfill & \hfill -5\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 2\hfill & \hfill 6\hfill & \hfill -2\hfill \\ \hfill 0\hfill & \hfill 4\hfill & \hfill 1\hfill & \hfill 7\hfill \end{array}\right]\begin{array}{c}\hfill \\ \hfill \\ R3-2\times R2\hfill \end{array}\Rightarrow \left[\begin{array}{cccc}\hfill 1\hfill & \hfill 3\hfill & \hfill -5\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 2\hfill & \hfill 6\hfill & \hfill -2\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -11\hfill & \hfill 11\hfill \end{array}\right].$

This is the augmented form for an upper triangular system, writing the system in extended form we have

which is easy to solve from the bottom up, by back substitution .

Example 5

Solve the system

Solution

The bottom equation implies that $x_3=-1$ . The middle equation then gives us that

$2x_2=-2-6x_3=-2+6=4\therefore x_2=2$

and finally, from the top equation,

$x_1=2-3x_2+5x_3=2-6-5=-9.$

Therefore the solution to the problem stated at the beginning of this Section is

$\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -9\hfill \\ \hfill 2\hfill \\ \hfill -1\hfill \end{array}\right].$

The following Task will act as useful revision of the Gaussian elimination procedure.

Task!

Carry out row operations to reduce the matrix

$\left[\begin{array}{ccc}\hfill 2\hfill & \hfill -1\hfill & \hfill 4\hfill \\ \hfill 4\hfill & \hfill 3\hfill & \hfill -1\hfill \\ \hfill -6\hfill & \hfill 8\hfill & \hfill -2\hfill \end{array}\right]$

into upper triangular form.

Answer