09. Solution of Linear System of Equations (Gaussian Elimination Method)
Dated: 16-08-2025
The solution of the system of equations gives \(n\) unknown values \(x_1, x_2, \ldots, x_n\), which satisfy the system simultaneously. If \(m > n\), the system usually will have an infinite number of solutions.
If \(|A| \ne 0\) then the system has a unique solution, otherwise, there is no solution.
Under elimination methods, we consider
Gaussian elimination Gauss-Jordan elimination
Crout’s reduction also known as Cholesky’s reduction is considered under decomposition methods.
Gaussian Elimination Method
Stages
- The given system of equations is reduced to an equivalent
upper triangular form using elementary transformations.
- the
upper triangular system is solved using back substitution procedure.
\[
\begin{aligned}
a_{11}x_1 + a_{12}x_2 + &\cdots + a_{1n}x_n = b_1 \\
a_{21}x_1 + a_{22}x_2 + &\cdots + a_{2n}x_n = b_2 \\
&\vdots \\
a_{n1}x_1 + a_{n2}x_2 + &\cdots + a_{nn}x_n = b_n \\
\end{aligned}
\]
Stage 1
Substituting the value of \(x_1\) from first equation into the rest
\[
\begin{aligned}
x_1 + a_{12}^\prime x_2 + &\cdots + a_{1n}^\prime x_n = b_1^\prime \\
a_{22}^\prime x_2 + &\cdots + a_{2n}^\prime x_n = b_2^\prime \\
&\vdots \\
a_{n2}^\prime x_2 + &\cdots + a_{nn}^\prime x_n = b_n^\prime \\
\end{aligned}
\]
Now, \(x_1\) is eliminated for \((n - 1)^{th}\) equations, making them independent of \(x_1\).
Repeat the same process for \(x_2, x_3, \ldots, x_{n - 1}\).
This will get us the following upper triangular form.
\[
\left.
\begin{aligned}
c_{11} x_1 + c_{12} x_2 + \cdots c_{1n} x_n &= d_1 \\
c_{22} x_2 + \cdots c_{2n} x_n &= d_2 \\
&\vdots \\
c_{nn} x_n &= d_n
\end{aligned}
\right\}
\]
Stage 2
The values of the unknowns are determined by backward substitution. First \(x_n\) is found from the last equation and then substitution this value of \(x_n\) in the preceding equation will give the value of \(x_{n-1}\). Continuing this way, we can find the values of all other unknowns
Example
Solve the following system of equations using Gaussian elimination method
\[
\begin{aligned}
2x + 3y - z &= 5 \\
4x + 4y - 3z &= 3 \\
-2x + 3y - z &= 1
\end{aligned}
\]
Solution
Stage 1
\[
\begin{aligned}
2x + 3y - z &= 5 \\
4x + 4y - 3z &= 3 \\
-2x + 3y - z &= 1
\end{aligned}
\]
\[
\left \downarrow
\begin{aligned}
\text{eq}_2 = \text{eq}_2 - \frac{\text{eq}_1}{2} \\
\text{eq}_3 = \text{eq}_3 - \frac{\text{eq}_1}{2} \\
\end{aligned}
\right.
\]
\[
\begin{aligned}
x + \frac 3 2 y - \frac z 2 &= \frac 5 2\\
3x + \frac 5 2 y - \frac 5 2 z &= \frac 1 2 \\
-3x + \frac 3 2 y - \frac z 2 &= -\frac 3 2
\end{aligned}
\]
\[
\left \downarrow
\begin{aligned}
\text{eq}_2 = \text{eq}_2 - 3 \times \text{eq}_1\\
\text{eq}_3 = \text{eq}_3 + 3 \times \text{eq}_1 \\
\end{aligned}
\right.
\]
\[
\left.
\begin{aligned}
x + \frac 3 2 y - \frac z 2 &= \frac 5 2\\
- 2 y - z &= -7 \\
6 y - 2 z &= 6
\end{aligned}
\right\}
\]
\[
\left \downarrow
\begin{aligned}
\text{eq}_2 = \frac {\text{eq}_2}{-2}\\
\end{aligned}
\right.
\]
\[
\begin{aligned}
x + \frac 3 2 y - \frac z 2 &= \frac 5 2\\
y + \frac z 2 &= \frac 7 2 \\
6 y - 2 z &= 6
\end{aligned}
\]
\[
\left \downarrow
\begin{aligned}
\text{eq}_3 = \text{eq}_3 - 6 \times \text{eq}_2\\
\end{aligned}
\right.
\]
\[
\left.
\begin{aligned}
x + \frac 3 2 y - \frac z 2 &= \frac 5 2\\
y + \frac z 2 &= \frac 7 2 \\
5 z &= -15
\end{aligned}
\right\}
\]
Stage 2
\[z = 3\]
\[\implies y = \frac{7}{2} - \frac{3}{2} = 2\]
\[\implies x = \frac{5}{2} + \frac{3}{2} - 3 = 1\]
Therefore, solution is \((1, 2, 3)\).
Partial and Full Pivoting
The Gaussian elimination method fails if any one of the pivot elements becomes zero. In such a situation, we rewrite the equations in a different order to avoid zero pivots. Changing the order of equations is called pivoting.
In partial pivoting, only the rows are interchanged but in full pivoting, rows and columns are interchanged.
A linear system of \(m\) equations can be written as \(n\) unknowns \(x_1, x_2, \ldots, x_n\).
\[
A = \begin{bmatrix}
a_{11} & a_{12} & a_{13} & \dots & a_{1n} \\
a_{21} & a_{22} & a_{23} & \dots & a_{2n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & a_{m3} & \dots & a_{mn}
\end{bmatrix} \\
\begin{bmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n
\end{bmatrix} \\
=
\begin{bmatrix}
b_1 \\
b_2 \\
\vdots \\
b_m
\end{bmatrix} \\
\]
Example
Solve the system of equations by Gaussian elimination method with partial pivoting.
\[
\begin{aligned}
x+y+z &= 7 \\
3x+3y+4z &= 24 \\
2x+y+3z &= 16
\end{aligned}
\]
\[
\begin{bmatrix}
1 & 1 & 1 \\
3 & 3 & 4 \\
2 & 1 & 3
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
z
\end{bmatrix}
=
\begin{bmatrix}
7 \\
24 \\
16
\end{bmatrix}
\]
However, a glance at the first column reveals that the numerically largest element is \(3\) which is in second row.
Interchanging first 2 rows, we have.
\[
\begin{bmatrix}
3 & 3 & 4 \\
1 & 1 & 1 \\
2 & 1 & 3
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
z
\end{bmatrix}
=
\begin{bmatrix}
24 \\
7 \\
16
\end{bmatrix}
\]
Stage 1
\[
\begin{bmatrix}
1 & 1 & \frac{4}{3} \\
0 & -1 & \frac{1}{3} \\
0 & 0 & -\frac{1}{3}
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
z
\end{bmatrix}
=
\begin{bmatrix}
8 \\
0 \\
-1
\end{bmatrix}
\]
Stage 2
\[z = 3\]
\[\implies y = 1\]
\[\implies x = 3\]
References
Read more about notations and symbols.