3.1: Gaussian Elimination
- Page ID
- 96045
The standard numerical algorithm to solve a system of linear equations is called Gaussian Elimination. We can illustrate this algorithm by example.
Consider the system of equations
\[\begin{aligned} &-3 x_{1}+2 x_{2}-x_{3}=-1 \\ &6 x_{1}-6 x_{2}+7 x_{3}=-7 \\ &3 x_{1}-4 x_{2}+4 x_{3}=-6 \end{aligned} \nonumber \]
To perform Gaussian elimination, we form an Augmented Matrix by combining the matrix \(A\) with the column vector \(b\) :
\[\left(\begin{array}{rrrr} -3 & 2 & -1 & -1 \\ 6 & -6 & 7 & -7 \\ 3 & -4 & 4 & -6 \end{array}\right) \nonumber \]
Row reduction is then performed on this matrix. Allowed operations are (1) multiply any row by a constant, (2) add multiple of one row to another row, (3) interchange the order of any rows. The goal is to convert the original matrix into an upper-triangular matrix
We start with the first row of the matrix and work our way down as follows. First we multiply the first row by 2 and add it to the second row, and add the first row to the third row:
\[\left(\begin{array}{rrrr} -3 & 2 & -1 & -1 \\ 0 & -2 & 5 & -9 \\ 0 & -2 & 3 & -7 \end{array}\right) \nonumber \]
We then go to the second row. We multiply this row by \(-1\) and add it to the third row:
\[\left(\begin{array}{rrrr} -3 & 2 & -1 & -1 \\ 0 & -2 & 5 & -9 \\ 0 & 0 & -2 & 2 \end{array}\right) \nonumber \]
The resulting equations can be determined from the matrix and are given by
\[\begin{aligned} -3 x_{1}+2 x_{2}-x_{3} &=-1 \\ -2 x_{2}+5 x_{3} &=-9 \\ -2 x_{3} &=2 \end{aligned} \nonumber \]
These equations can be solved by backward substitution, starting from the last equation and working backwards. We have
\[\begin{aligned} &-2 x_{3}=2 \rightarrow x_{3}=-1 \\ &-2 x_{2}=-9-5 x_{3}=-4 \rightarrow x_{2}=2 \\ &-3 x_{1}=-1-2 x_{2}+x_{3}=-6 \rightarrow x_{1}=2 \end{aligned} \nonumber \]
Therefore,
\[\left(\begin{array}{l} x_{1} \\ x_{2} \\ x_{3} \end{array}\right)=\left(\begin{array}{r} 2 \\ 2 \\ -1 \end{array}\right) \nonumber \]