Contents
The Naive Gauss Elimination Method
Naive Gauss elimination method is one of the numerical method to solve a system of linear equations.
This method is similiar to Cramer's, with generalization to solve $n$ number of equations.
It's called "naive" because it does not avoid division by zero. Should we encounter one,
pivoting of the matrices are required.
Naive Gauss elimination consists of two steps, namely the forward elimination and the back substitution.
Consider the following system of linear equations,
$$ \begin{cases} {}
a_{11}x_1+a_{12}x_2+a_{13}x_3 = b_1 \\
a_{21}x_1+a_{22}x_2+a_{23}x_3 = b_2 \\
a_{31}x_1+a_{32}x_2+a_{33}x_3 = b_3,
\end{cases} $$
which expressed as a matrices system of $[A][X]=[B]$ as
$$ \begin{bmatrix}
a_{11} & a_{12} & a_{13} \\
a_{21} & a_{22} & a_{23} \\
a_{n1} & a_{n2} & a_{33}
\end{bmatrix} \begin{bmatrix}
x_{1} \\ x_{2} \\ x_{3}
\end{bmatrix} = \begin{bmatrix}
b_{1} \\ b_{2} \\ b_{3}
\end{bmatrix}.$$
We now introduce $M$ as the augmented form of $A$ with elements of $B$ as
$$ M = \begin{bmatrix}
a_{11} & a_{12} & a_{13} &\bigm| & b_{1} \\
a_{21} & a_{22} & a_{23} &\bigm| & b_{2} \\
a_{31} & a_{32} & a_{33} &\bigm| & b_{3}
\end{bmatrix}. $$
Forward Elimination
To perform the forward elimination step,
first substract every element in $a_{2n}$ (row 2) in $M$ by
$$\begin{equation}
a_{2n}-\frac{a_{21}}{a_{11}}a_{1n}, \tag{1.1}
\end{equation}$$
resulting in the matrix $M$
$$ M = \begin{bmatrix}
a_{11} & a_{12} & a_{13} &\bigm| & b_{1} \\
& a_{22}' & a_{23}' &\bigm| & b_{2}' \\
a_{n1} & a_{32} & a_{33} &\bigm| & b_{3}
\end{bmatrix}. $$
Then, substract every element in $a_{3n}$ (row 3) in $M$ by
$$\begin{equation}
a_{3n}-\frac{a_{31}}{a_{11}}a_{1n}, \tag{1.2}
\end{equation}$$
which results in
$$ M = \begin{bmatrix}
a_{11} & a_{12} & a_{13} &\bigm| & b_{1} \\
& a_{22}' & a_{23}' &\bigm| & b_{2}' \\
& a_{32}' & a_{33}' &\bigm| & b_{3}'
\end{bmatrix}. $$
Finally, we substract every element in $a_{3n}$ (row 3) in $M$ by
$$\begin{equation}
a_{3n}'-\frac{a_{32}'}{a_{22}'}a_{2n}', \tag{1.3}
\end{equation}$$
and we got the augmented upper triangle matrix $M'$ as
$$ M' = \begin{bmatrix}
a_{11} & a_{12} & a_{13} &\bigm| & b_{1} \\
& a_{22}' & a_{23}' &\bigm| & b_{2}' \\
& & a_{33}'' &\bigm| & b_{3}''
\end{bmatrix}. $$
Backward Substitution
To perform the backward substitution step, we multiply $M'$ by $X$ and solve for $x_3$ first.
Notice that for the last row of the matrix, we would get the equation
$$\begin{align}a_{33}''x_3 &= b_{3}'' \notag \\
x_3 &= \frac{b_{3}''}{a_{33}''}. \tag{1.4}\end{align}$$
Then, for $x_2$ we get
$$a_{22}'x_2+a_{23}'x_3 = b_{2}'$$
$$x_2 = \frac{b_{2}'- a_{23}x_2}{a_{22}'}. \tag{1.5}$$
Finally, for $x_1$ we get
$$a_{11}x_1+a_{12}x_2+a_{13}x_3 = b_{1}$$
$$x_1 = \frac{b_{1} - a_{12}x_2 - a_{13}x_3}{a_{11}}. \tag{1.6}$$
Example 1.1
Solve the following system of linear equations!
$$\begin{cases}{}
3x_1 - 0.1x_2 - 0.2x_3 = 7.85 \\
0.1x_1 + 7x_2 - 0.3x_3 = -19.3 \\
0.3x_1 - 0.2x_2 + 10x_3 = 71.4
\end{cases}$$
Solution
We begin by constructing the augmented matrix $M$ from the system,
$$ M = \begin{bmatrix}
3 & -0.1 & -0.2 &\bigm| & 7.85 \\
0.1 & 7 & -0.3 &\bigm| & -19.3 \\
0.3 & -0.2 & 10 &\bigm| & 71.4
\end{bmatrix}. $$
First, we perform the forward elimination step by substracting $M$ using Eq. 1.1
$$\begin{equation}
a_{2n}-\frac{0.1}{3}a_{1n}, \notag
\end{equation}$$
and Eq. 1.2
$$\begin{equation}
a_{3n}-\frac{0.3}{3}a_{1n}, \notag
\end{equation}$$
resulting in $M$
$$ M = \begin{bmatrix}
3 & -0.1 & -0.2 &\bigm| & 7.85 \\
0 & 7.033 & -0.293 &\bigm| & -19.562 \\
0 & -0.190 & 10.020 &\bigm| & 70.615
\end{bmatrix}. $$
Then, using Eq. 1.3,
$$\begin{equation}
a_{3n}-\frac{-0.190}{7.033}a_{2n}, \notag
\end{equation}$$
we obtain the matrix $M'$
$$ M' = \begin{bmatrix}
3 & -0.1 & -0.2 &\bigm| & 7.85 \\
0 & 7.033 & -0.293 &\bigm| & -19.562 \\
0 & 0 & 10.012 &\bigm| & 70.084
\end{bmatrix}. $$
We now perform the backward substitution step using Eq. 1.4, 1.5, and 1.6.
For $x_3$, we get
$$\begin{align}
x_3 &= \frac{70.084}{10.012} \notag \\
&= 7.01. \notag
\end{align}$$
For $x_2$, we get
$$\begin{align}
x_2 &= \frac{-19.562-(-0.293(7.01))}{7.033} \notag \\
&= -2.51. \notag
\end{align}$$
Finally, for $x_1$, we get
$$\begin{align}
x_2 &= \frac{7.85-(-0.1(-2.51)-0.2(7.01))}{3} \notag \\
&= 3. \notag
\end{align}$$
Thus, the solutions to the system were
$$x_1, x_2, x_3 = \{3, -2.51, 7.01\}. \tag*{$\Box$}$$
Generalization of The Naive Gauss Elimination Method
We will show now the generalized naive Gauss elimination for $n$ number of equations.
Consider the following system,
$$ \begin{cases} {}
&a_{11}x_1+\ldots+a_{13}x_3 = b_1 \tag{2.1a, 2.1b, 2.1c}\\
&a_{21}x_1+\ldots+a_{23}x_3 = b_2 \\
& \vdots \notag \\
&a_{31}x_1+\ldots+a_{33}x_3 = b_3.
\end{cases} $$
By the same manner as previously, we will construct an augmented matrix $M$ as follows,
$$ M = \begin{bmatrix}
a_{11} & a_{12} & \ldots & a_{1n} &\bigm| & b_{1} \\
a_{21} & a_{22} & \ldots & a_{2n} &\bigm| & b_{2} \\
& & \vdots & &\bigm| &\vdots \\
a_{n1} & a_{n2} & \ldots & a_{nn} &\bigm| & b_{n}
\end{bmatrix}. $$
Next, we perform the forward elimination step by multiplying Eq. (2.1a) by $a_{21}/a_{11}$ to give
$$ a_{21}x_1+\frac{a_{21}}{a_{11}}a_{12}x_2+\ldots+\frac{a_{21}}{a_{11}}a_{1n}x_n=\frac{a_{21}}{a_{11}}b_n.
\tag{2.2}$$
Then, substract Eq. (2.1b) by this equation to give
$$ \left(a_{22}-\frac{a_{21}}{a_{11}}a_{12}\right)x_2+\ldots+\left(a_{2n}-\frac{a_{21}}{a_{11}}a_{1n}\right)x_n
= b_2-\frac{a_{21}}{a_{11}}b_1$$
or rewritten as
$$a_{22}'x_2+\ldots+a_{2n}'x_n=b_2'.$$
We repeat the same procedure for the remaining equations until we change the former system of equations into an
upper triangular form such as
$$\begin{align}
a_{11}x_1+a_{12}x_2+a_{12}x_3+\ldots+a_{1n}x_n&=b_1 \tag{2.3}\\
a_{22}'x_2+a_{23}'x_3+\ldots+a_{2n}'x_n&=b_2 \tag{2.4}\\
a_{33}''x_3+\ldots+a_{3n}''x_n&=b_3 \tag{2.5}\\
&\vdots \notag\\
a_{nn}^{(n-1)}x_n&=b_n^{(n-1)}. \tag{2.6}
\end{align}$$
We then now begin the back substitution step by solving Eq. (2.6) for $x_n$,
$$ x_n = \frac{b_n^{(n-1)}}{a_{nn}^{(n-1)}}. \tag{2.7}$$
The result from Eq. (2.7) could be substituted to the previous equation to solve for $x_{n-1}$.
Thus, the rest of the unknowns $x$-s can be solved by the Eq. (2.8) below,
$$ x_i = \frac{b_i^{n-1}-\displaystyle\sum_{j=i+1}^{n}a_{ij}^{i-1}x_j}{a_{ii}^{i-1}} \tag{2.8}$$
Programming Exercises
Exercise 1.1
Solve the following system of linear equations using the naive Gauss elimination. $$ \begin{cases} x_1+2x_2=10 \\ 1.1x_1+2x_2=4 \end{cases}$$Solution
The above equations can be written in the augmented matrix form
$$ \begin{bmatrix} 1 & 2 & \bigm| & 10 \\ 1.1 & 2 & \bigm| & 4 \end{bmatrix}.$$
We can now begin to write program to solve this system.
# Array storing the variables
array = [[1, 2, 10],
[1.1, 2, 10.4]]
n = len(array)
# Array storing the solutions
solution = [0 for i in range(n)]
# Forward Elimination Step
for i in range(n):
for j in range(i+1, n):
ratio = array[j][i]/array[i][i]
for k in range(n+1):
array[j][k] = array[j][k]-ratio*array[i][k]
# Back Substitution Step
solution[n-1] = array[n-1][n]/array[n-1][n-1]
for i in range(n-2,-1,-1):
solution[i] = array[i][n]
for j in range(i+1,n):
solution[i] = solution[i]-array[i][j]*solution[j]
solution[i] = solution[i]/array[i][i]
print("Numerical solutions:\n", solution)
Loading PyScript..
Exercise 1.2
Solve the following system of linear equations using the naive Gauss elimination. $$ \begin{cases} 8x_1+2x_2-x_3=-2 \\ 10x_1+2x_2+4x_3=4 \\ 12x_1+2x_2+2x_3=6\end{cases}$$Solution
The above equations contain division by zero when left as it is. Pivotting the equations resulted in the augmented matrix
$$ \begin{bmatrix} 2 & 8 & -1 & \bigm| & -2 \\ 2 & 10 & 4 & \bigm| & 4
\\ 2 & 12 & 2 & \bigm| & 6 \end{bmatrix}.$$
We can now begin to the write program to solve this system.
# Array storing the variables
array = [[2, 8, -2, -2],
[2, 10, 4, 4],
[2, 12, 2, 6]]
n = len(array)
# Array storing the solutions
solution = [0 for i in range(n)]
# Forward Elimination Step
for i in range(n):
for j in range(i+1, n):
ratio = array[j][i]/array[i][i]
for k in range(n+1):
array[j][k] = array[j][k]-ratio*array[i][k]
# Back Substitution Step
solution[n-1] = array[n-1][n]/array[n-1][n-1]
for i in range(n-2,-1,-1):
solution[i] = array[i][n]
for j in range(i+1,n):
solution[i] = solution[i]-array[i][j]*solution[j]
solution[i] = solution[i]/array[i][i]
print("Numerical solutions:\n", solution)
Loading PyScript...
Exercise 1.3
Solve the following system of linear equations using the naive Gauss elimination. $$ \begin{cases} 2x_1+x_2-x_3+2x_4=5 \\ 4x_1+5x_2-3x_3+6x_4=9 \\ -2x_1+5x_2-2x_3+6x_4=4 \\ 4x_1+11x_2-4x_3+8x_4=2\end{cases}$$Solution
The above equations can be written in the augmented matrix form
$$ \begin{bmatrix} 2 & 1 & -1 & 2 & \bigm| & 5 \\ 4 & 5 & -3 & 6 & \bigm| & 9
\\ -2 & 5 & -2 & 6 & \bigm| & 4 \\ 4 & 11 & -4 & 8 & \bigm| & 2 \end{bmatrix}.$$
We can now begin to write the program to solve this system.
# Array storing the variables
array = [[2, 1, -1, 2, 5],
[4, 5, -3, 6, 9],
[-2, 5, -2, 6, 4],
[4, 11, -4, 8, 2]]
n = len(array)
# Array storing the solutions
solution = [0 for i in range(n)]
# Forward Elimination Step
for i in range(n):
for j in range(i+1, n):
ratio = array[j][i]/array[i][i]
for k in range(n+1):
array[j][k] = array[j][k]-ratio*array[i][k]
# Back Substitution Step
solution[n-1] = array[n-1][n]/array[n-1][n-1]
for i in range(n-2,-1,-1):
solution[i] = array[i][n]
for j in range(i+1,n):
solution[i] = solution[i]-array[i][j]*solution[j]
solution[i] = solution[i]/array[i][i]
print("Numerical solutions:\n", solution)
Loading PyScript...
Exercise 1.4
Solve the following system of linear equations using the naive Gauss elimination. $$ \begin{cases} 2x_1+x_2+4x_3+x_4-x_5=7 \\ -x_1+3x_2-2x_3-x_4+2x_5=1 \\ 5x_1+x_2+3x_3-4x_4+x_5=33 \\ 3x_1-2x_2-2x_3-2x_4+x_5=24 \\ -4x_1-x_2-5x_3+3x_4-4x_5=-49\end{cases}$$Solution
The above equations can be written in the augmented matrix form
$$ \begin{bmatrix} 2 & 1 & 4 & 1 & -1 & \bigm| & 7 \\ -1 & 3 & -2 & -1 & 2 & \bigm| & 1
\\ 5 & 1 & 3 & -4 & 1 & \bigm| & 33 \\ 3 & -2 & -2 & -2 & 3 & \bigm| & 24 \\ -4 & -1 & -5 & 3 & -4 & \bigm| & -49\end{bmatrix}.$$
We can now begin to write the program to solve this system.
# Array storing the variables
array = np.array([[2, 1, 4, 1, -1, 7],
[-1, 3, -2, -1, 2, 1],
[5, 1, 3, -4, 1, 33],
[3, -2, -2, -2, 3, 24],
[-4, -1, -5, 3, -4, -49]])
n = len(array)
# Array storing the solutions
solution = [0 for i in range(n)]
# Forward Elimination Step
for i in range(n):
for j in range(i+1, n):
ratio = array[j][i]/array[i][i]
for k in range(n+1):
array[j][k] = array[j][k]-ratio*array[i][k]
# Back Substitution Step
solution[n-1] = array[n-1][n]/array[n-1][n-1]
for i in range(n-2,-1,-1):
solution[i] = array[i][n]
for j in range(i+1,n):
solution[i] = solution[i]-array[i][j]*solution[j]
solution[i] = solution[i]/array[i][i]
print("Numerical solutions:\n", solution)
Loading PyScript...
References
Chapra, S.C, & Canale, R.P. (2014). Numerical Methods for Engineers, 7th Edition. McGraw Hill.
© 2023 Geophysics Wiki