Gauss Elimination Method

In this method, we first change the coefficient matrix $A$ into an upper triangular matrix using elimination. Then we find out the unknowns via back substitution.

Interactive calculator

This section demonstrates an interactive calculator for solving a linear system using the Gauss-elimination method with partial pivoting.

System size--System size---12345678

$x_{1}+$

$x_{2}+$

$x_{3}=$

$x_{1}+$

$x_{2}+$

$x_{3}=$

$x_{1}+$

$x_{2}+$

$x_{3}=$

Solution,

The above system can be represented in matrix notation as:

$$\begin{bmatrix}7 & 5 & 3 \\ 2 & 1 & 6 \\ 1 & 2 & 3\end{bmatrix}\begin{bmatrix}x_{1} \\ x_{2} \\ x_{3}\end{bmatrix}=\begin{bmatrix}1 \\ 2 \\ 3\end{bmatrix}$$

Step 1

Take $R_{1}$ as pivot row, $a_{11}=7$ as pivot element, and eliminate $x_{1}$ from $R_{2}, R_{3}$ by applying

$$R_{2}\leftarrow R_{2}-\frac{2}{7}R_{1}, R_{3}\leftarrow R_{3}-\frac{1}{7}R_{1}$$

$$\begin{bmatrix}7 & 5 & 3 \\ 0 & -0.4 & 5.14 \\ 0 & 1.3 & 2.57\end{bmatrix}\begin{bmatrix}x_{1} \\ x_{2} \\ x_{3}\end{bmatrix}=\begin{bmatrix}1 \\ 1.7143 \\ 2.8571\end{bmatrix}$$

Step 2

Take $R_{2}$ as pivot row, $a_{22}=-0.4286$ as pivot element, and eliminate $x_{2}$ from $R_{3}$ by applying

$$R_{3}\leftarrow R_{3}+\frac{1.2857}{0.4286}R_{2}$$

$$\begin{bmatrix}7 & 5 & 3 \\ 0 & -0.4 & 5.14 \\ 0 & 0 & 18\end{bmatrix}\begin{bmatrix}x_{1} \\ x_{2} \\ x_{3}\end{bmatrix}=\begin{bmatrix}1 \\ 1.7143 \\ 8\end{bmatrix}$$

We can clearly see that the coefficient matrix has been turned into an upper triangular matrix. Now we can proceed with back substitution as follow:

$$7x_{1}+5x_{2}+3x_{3}=1\ \ ...... \ (1) \\ -0.4286x_{2}+5.1429x_{3}=1.7143\ \ ...... \ (2) \\ 18x_{3}=8\ \ ...... \ (3) \\$$

From $eq^n(3),\ x_3=\frac{8}{18}=0.4444$

From $eq^n(2),\ x_2=\frac{1.7143-5.1429x_{3}}{-0.4286}=\frac{1.7143-5.1429\times0.4444}{-0.4286}=\frac{-0.5714}{-0.4286}=1.3333$

From $eq^n(1),\ x_1=\frac{1-5x_{2}-3x_{3}}{7}=\frac{1-5\times1.3333-3\times0.4444}{7}=\frac{-7}{7}=-1$

Hence the solution for the system is:

$$x_{1}=-1,\ x_{2}=1.3333,\ x_{3}=0.4444$$

Algorithm

Following represents the algorithm for the basic Gauss-Elimination method without pivoting. This section is represented in mathematical notations.

1. Start
2. Declare and read the size of the system $N$
3. Declare variable for system, $S$ as a 2D array of size $N\times (N+1)$. Such that $S_{i,j}$ represents the element at $i^{th}$ row and $j^{th}$ column.
4. For each elements of $S$ input a value from user
5. Start from $k=1$
6. Take $R_{k}$ as pivot row and then eliminate $x_{k}$ from the rows $R_{i}$ for $i=(k+1),...,N$ by applying $R_{i}\leftarrow R_{i}- \frac{S_{i,k}}{S_{k,k}}R_{k}$ modifying $S$
7. Increase $k$ by $1$. Goto step 6 if $k \text{<} N$
8. Find $x_{j}=\frac{S_{j,N+1}-\sum_{i=j+1}^{N}x_{i}S_{j,i}}{S_{j,j}}$ for $j=N,N-1,...,1$
9. Stop

Pseudo Code

The pseudo-code for the basic Gauss-Elimination method can be written as:

Read N
Declare S = Array(N, N+1)

-- Read the input
for i=1:N
  for j=1:N+1
    Read S[i][j]
  endfor
endfor

-- Perform elimination
for k=1:N-1
  for i=k+1:N
    factor = S[i][k]/S[k][k]
    for j=k+1:N+1
      S[i][j] = S[i][j] - factor * S[k][j]
    end
  end
end

-- Perform back substitution
for k=N:1
  sum = 0
  for i=k+1:N
    sum += S[k][i]
  end
  Print x[k] = (S[k][N+1]-sum)/S[k][k]
end

Programs

C

/*
 * Basic Gauss Elimination Method in C
*/

#include <stdio.h>
#define MAX_SYSTEM_SIZE 20

int main()
{
  // The size of linear system
  int N = 3;

  // Preallocate enough memory for the system
  double S[MS][MS+1];
  double X[MS];

  // Get the size of the system
  printf("Enter the size of linear system: ");
  scanf("%d", &N);

  // Limit the max system size
  if (N >= MS)
  {
    printf("Please enter size below %d", MS);
    return -1;
  }
  
  // Ask for the system
  printf("\nEnter the matrix in augmented matrix form:\n");
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < N + 1; j++)
    {
      printf("Enter S[%d][%d] = ", i + 1, j + 1);
      scanf("%lf", &S[i][j]);
    }
  }

  // Perform Elimination
  for (int k = 0; k < N - 1; k++)
  {
    for (int i = k + 1; i < N; i++)
    {
      // Precalculate factor as S[i][k] will 
      // change in the following loop
      double factor = S[i][k] / S[k][k];
      for (int j = k; j < N + 1; j++)
      {
        S[i][j] = S[i][j] - factor * S[k][j];
      }
    }
  }

  // Perform Back substitution
  for (int k = N - 1; k >= 0; k--)
  {
    double sum = 0;
    for (int i = k + 1; i < N; i++)
    {
      sum += S[k][i] * X[i];
    }
    X[k] = (S[k][N] - sum) / S[k][k];
  }

  printf("\nSolution for the system is: \n");
  for (int i = 0; i < N; i++)
  {
    printf("x%d=%lf\n", i + 1, X[i]);
  }

  return 0;
}

Python

#
# Basic Gauss Elimination Method
#

N = int(input("Enter the size of the system "))
S = [[0]*(N+1) for _ in range(N)]
X = [0]*N

# Ask for input
print("Enter the system in augmented matrix form:")
for i in range(N):
  for j in range(N+1):
    S[i][j] = float(input(f"Enter S[{i+1}][{j+1}] = "))

# Perform elimination
for k in range(N-1):
  for i in range(k+1, N):
    # Precalculate factor as S[i][k] will change in the following loop
    factor = S[i][k]/S[k][k]
    for j in range(k, N+1):
      S[i][j] = S[i][j] - factor*S[k][j]

# Perform back substitution
for k in reversed(range(0, N)):
  sum = 0
  for i in range(k+1, N):
    sum += S[k][i]*X[i]
  
  X[k] = (S[k][N]-sum)/S[k][k]

# Print the solution
for i in range(N):
  print(f"x{i+1} = {X[i]}")

Complexity

The time complexity of the basic Gauss Elimination method is $O(N^3)$ where $N$ is the size of the system. The elimination step requires 3 nested loops which gives the time complexity to be $O(N^3)$. Similarly, the space complexity is $O(N^2)$ which comes due to the matrix used to represent the system.

Advantages

1. The Gauss Elimination method is one of the fastest direct methods of solving linear systems.

Disadvantages

1. The basic Gauss Elimination method can't deal with zero pivot elements.