Gaussian Elimination

Gaussian elimination is a direct method, solving for the “exact” solution in one pass through the equations.

Given the matrix form of a system of equations:

$$\left[\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right]=\left\{\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right\}=\left\{\begin{array}{c}{b}_1\\ b_2\\ b_3\end{array}\right\}$$

Forward Elimination

First, we eliminate $x_1$ by multiplying the first row by $a_{21}/a_{11}$ so that it is:

$$a_{21}{x}_1+\frac{a_{21}}{a_{11}}{a}_{12}{x}_2+\frac{a_{21}}{a_{11}}{a}_{13}{x}_3=\frac{a_{21}}{a_{11}}{b}_1$$

This means that it can now be subtracted from the second row to get:

$$\left(a_{22}-\frac{a_{21}}{a_{11}}\right)a_{22}{x}_2+\left(a_{23}-\frac{a_{21}}{a_{11}}\right)a_{23}{x}_3=b_2-\frac{a_{21}}{a_{11}}{b}_1$$

or

$$a_{22}^{\prime }{x}_2+a_{23}^{\prime }{x}_3=b_2^{\prime }$$

where the prime indicates that the value has been changed.

We can then also repeat the procedure for row 3, where:

$$\text{Row \#3}=\text{Row \#3}-\left(\frac{a_{31}}{a_{11}}\right)\text{Row \#1}$$

At this point our matrix will be:

$$\left[\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ 0& a_{22}^{\prime }& a_{23}^{\prime }\\ 0& a_{32}^{\prime }& a_{33}^{\prime }\end{array}\right]\left\{\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right\}=\left\{\begin{array}{c}{b}_1\\ b_2^{\prime }\\ b_3^{\prime }\end{array}\right\}$$

We then eliminate $x_2$ by doing:

$$\text{Row \#3}=\text{Row \#3}-\left(\frac{a_{32}^{\prime }}{a_{22}^{\prime }}\right)\text{Row \#2}$$

such that our matrix is:

$$\left[\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ 0& a_{22}^{\prime }& a_{23}^{\prime }\\ 0& 0& a_{33}^{\prime \prime }\end{array}\right]\left\{\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right\}=\left\{\begin{array}{c}{b}_1\\ b_2^{\prime }\\ b_3^{\prime \prime }\end{array}\right\}$$

Here the double prime on $a_{33}^{\prime \prime }$ and $b_3^{\prime \prime }$ indicates that they have been changed twice.

Forward Elimination Completion Criteria

Forward elimination is complete when terms below the diagonal in $A$ are $0$, such as

$$\left[\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ 0& a_{22}^{\prime }& a_{23}^{\prime }\\ 0& 0& a_{33}^{\prime \prime }\end{array}\right]$$

Backward substitution

Starting at the bottom, we can solve $b_3$ using:

$$\begin{array}{r}{a}_{33}^{\prime \prime }{x}_3=b_{33}^{\prime \prime }\\ x_3=\frac{b_3^{\prime \prime }}{a_{33}^{\prime \prime }}\end{array}$$

Then, we can move up to row 2 to solve $x_2$ by subbing in our solved $x_3$ value:

$$a_{22}^{\prime }{x}_2+a_{23}^{\prime }{x}_3=b_2^{\prime }$$

Then we can continue moving up and sub in $x_2$ and $x_3$ to solve for $x_1$:

$$a_{11}{x}_1+a_{12}{x}_2+a_{13}{x}_3=b_1$$

Notes

The above approach is called Naïve Gaussian Elimination, because we are not
checking for a divide by zero. For example, if we have

$$\text{Row \#2}=\text{Row \#2}-\left(\frac{a_{21}}{a_{11}}\right)\text{Row \#1}$$

if the term on the diagonal $a_{11}$ is $0$, we will have a division by zero.

Benefits:

• We achieve the exact solution in one pass
• Straightforward algorithm

Challenges:

• Not very efficient (many calculations needed)
• Divide by zero is possibility (if there is zero on diagonal)
• Round-off Error for Gaussian Elimination