Gaussian Elimination stands as a foundational and powerful method in linear algebra, offering a systematic approach to solving systems of linear equations. In this article, we will discuss Gaussian Elimination to Solve Linear Equations.

We all are aware of linear equations. It is a group of linear equations with various unknown factors. The unknown factors exist in multiple equations, and we need to solve a linear equation to find those unknown constants. One such method to solve a system of linear equations is Gaussian elimination.

Before proceeding further, let's first understand the concept of Gaussian elimination.

Let's explore how the gaussian elimination method helps us find the solutions to the linear equations.

Gaussian elimination

The gaussian elimination is an algorithm in linear algebra that lets you find the solutions to a linear system.

The central concept of this algorithm is to add multiples of one (smallest) equation to the others to remove a variable and to keep doing so until there is only one variable remaining. The value of this last variable is determined and then substituted back into the other equations to evaluate the different unknown values. Hence gaussian elimination method is a step‐by‐step elimination of the variables.

To apply gaussian elimination, you can algebraically operate on the columns and rows of a matrix in the given three ways:

You can interchange two rows.

You can multiply a row by any non-zero constant.

You can also add a row to another row to form an upper triangular matrix.

Augmented Matrix

To find the values of the unknowns in gaussian elimination, we convert the augmented matrix into the row echelon form and carry out the backward substitution. This method, also known as row reduction, contains two steps: back substitution and forward elimination.

Row Echelon Form

All rows with at least one non-zero element are above all-zero rows.

Each row's leading coefficient(first non-zero element) should be one.

The matrix is in an upper triangular matrix.

Solving a linear system with an augmented matrix using Gaussian elimination is a structured, organized, and quite efficient method.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Gauss Elimination Method with Example

Gaussian Elimination, a fundamental technique in linear algebra, provides a systematic approach to solving systems of linear equations. Let's explore this method through an illustrative example.

Consider the system:

2x+y−z = 8 −3x−y+2z = -11 −2x+y+2z = -3

The goal is to transform this system into an equivalent, simpler system with a unique solution through a series of elementary row operations.

Step 1: Augmented Matrix

2 1 -1 | 8

-3 -1 2 | -11

-2 1 2 | -3

Step 2: Row Operations

R_{2}=R_{2 }+ 3/2R_{1} R_{3}= R_{3} + R_{1}

2 1 -1 | 8

0 -½ ½| 1

0 2 1 | 5

Step 3: Row Operations

R_{3}= R_{3} - 4R_{2}

2 1 -1 | 8

0 -½ ½| 1

0 0 -1 | 1

Step 4: Back Substitution

z=−1

Substitute back into the second equation to find y:

-½y + ½(-1) = 1

Finally, substitute back into the first equation to find x:

2x+ 2 -1= 8

x=3

The solution to the system of linear equations is x=3, y=2, and z=-1. Gaussian Elimination has successfully transformed the system into a simplified form, revealing the unique solution to the given set of equations.

Gauss Elimination Problems

Find the unknown variables using the Gaussian elimination method for the given linear equations.

Input

Enter the no. of equations: 3

Enter the augmented matrix:

2 1 1 10

3 2 3 18

1 4 9 16

Output

The unknown values for the above equations are:

7

-9.00001

5

Explanation

The given input forms the matrix having n rows and n+1 columns depending on the number of unknown constants(n). The input matrix represents the following equations-

2X + Y + Z = 10

3X + 2Y + 3Z = 18

X + 4Y + 9Z = 16

Algorithm

First, we will define the number of rows(n) and columns(n+1) or the number of equations.

The second step is to read the number of unknown variables(n).

Read augmented matrix of n X n+1 Size

For i = 0 to n
For j = 0 to n+1
Read matrix[i][j]
Next j
Next i

Transform Augmented Matrix (A) by performing the shifting operations and applying gaussian elimination to form an upper triangular matrix.

Applying Gauss Elimination on input matrix:

For i = 0 to n-1
If matrix[i][j] = 0
Print "Error"
Stop
End If
For j = i+1 to n
Ratio = matrix[j],i/matrix[i],i
For k = 0 to n+1
matrix[i][k] = matrix[j][k] - Ratio * matrix[i][k]
Next k
Next j
Next i

The next step is to obtain a solution by Back Substitution.

Xn = matrix[n],n+1/matrix[n],n
For i = n-1 to 1
Xi = matrix[i],n+1
For j = i+1 to n
Xi = Xi - matrix[i][j] * Xj
Next j
Xi = Xi/matrix[i],i
Next i

Now we can see the output in the console.

The implementation of the above algorithm is given below.

Implementation in C++

C++

C++

#include<iostream> #include<math.h>

using namespace std;

int main() { int i, j, k, n;

cout << "\nEnter the no. of equations: "; cin >> n;

// Here size of the augmented matrix will be n*n+1 float matrix[n][n + 1];

/* we will store the n unknown constants of n equations in array 'result' */ float result[n];

cout << "\nEnter the augmented matrix: "; for (i = 0; i < n; i++) { for (j = 0; j < n + 1; j++) { cin >> matrix[i][j]; } }

for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if (abs(matrix[i][i]) < abs(matrix[j][i])) { for (k = 0; k < n + 1; k++) {

/* we will swap the matrix[i][k] and matrix[j][k] to get the lowest element on top */ matrix[i][k] = matrix[i][k] + matrix[j][k]; matrix[j][k] = matrix[i][k] - matrix[j][k]; matrix[i][k] = matrix[i][k] - matrix[j][k]; } } } }

/* Using Gaussian elimination to form upper triangular matrix */ for (i = 0; i < n - 1; i++) { for (j = i + 1; j < n; j++) { float f = matrix[j][i] / matrix[i][i]; for (k = 0; k < n + 1; k++) { matrix[j][k] = matrix[j][k] - f * matrix[i][k]; } } }

/* Using backward substitution to find the unknown values */ for (i = n - 1; i >= 0; i--) { result[i] = matrix[i][n];

for (j = i + 1; j < n; j++) { if (i != j) { result[i] = result[i] - matrix[i][j] * result[j]; } } result[i] = result[i] / matrix[i][i]; }

cout << "\nThe unknown values for the above equations are:\n"; for (i = 0; i < n; i++) { cout << result[i] << "\n"; } return 0; }

Output

Time Complexity

The time complexity for the above code will be O(n)*(O(n)*O(n)) = O(n3) because for each pivot, we will traverse the part to its right for each row below it. Whereas the space complexity is O(n^2).

Implementation in Java

Java

Java

import java.util.Scanner;

public class Main { public void solveMatrix(double[][] A, double[] B) { int N = B.length; for (int k = 0; k < N; k++) { /** find pivot row **/ int max = k; for (int i = k + 1; i < N; i++) if (Math.abs(A[i][k]) > Math.abs(A[max][k])) max = i;

/** swap row in A matrix **/ double[] temp = A[k]; A[k] = A[max]; A[max] = temp;

/** swap corresponding values in constants matrix **/ double t = B[k]; B[k] = B[max]; B[max] = t;

/** pivot within A and B **/ for (int i = k + 1; i < N; i++) { double factor = A[i][k] / A[k][k]; B[i] -= factor * B[k]; for (int j = k; j < N; j++) A[i][j] -= factor * A[k][j]; } }

/* Using back substitution to find unknown variables*/ double[] solution = new double[N]; for (int i = N - 1; i >= 0; i--) { double sum = 0.0; for (int j = i + 1; j < N; j++) sum += A[i][j] * solution[j]; solution[i] = (B[i] - sum) / A[i][i]; } /** Print solution **/ printSolution(solution); }

/* function to print solution */ public void printSolution(double[] sol) { int N = sol.length; System.out.println("\n The unknown values for the above equations are: "); for (int i = 0; i < N; i++) System.out.printf("%.3f ", sol[i]); System.out.println(); }

/** Main function **/ public static void main (String[] args) { Scanner scan = new Scanner(System.in); /** Make an object of Main class **/ Main ge = new Main();

System.out.println("\nEnter the no. of equations:"); int N = scan.nextInt();

double[] B = new double[N]; double[][] A = new double[N][N];

System.out.println("\nEnter the augmented matrix:"); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) A[i][j] = scan.nextDouble();

System.out.println("\nEnter "+ N +" solutions"); for (int i = 0; i < N; i++) B[i] = scan.nextDouble(); ge.solveMatrix(A,B); } }

Output

Time Complexity

The time complexity for the above code will be O(n)*(O(n)*O(n)) = O(n3) because for each pivot, we will traverse the part to its right for each row below it. Whereas the space complexity is O(n^2).

Implementation in Python

Python

Python

# Importing NumPy Library import numpy as np import sys

n = int(input('Enter number of equations: '))

# Making numpy array of n x n+1 size and initializing # to zero for storing augmented matrix matrix = np.zeros((n,n+1))

# Making numpy array of n size and initializing # to zero for storing solution vector x = np.zeros(n)

# Reading augmented matrix coefficients print('Enter the augmented matrix:') for i in range(n): for j in range(n+1): matrix[i][j] = float(input( 'matrix['+str(i)+']['+ str(j)+']='))

# Applying Gauss Elimination for i in range(n): if matrix[i][i] == 0.0: sys.exit('Error! division by zero detected!')

for j in range(i+1, n): ratio = matrix[j][i]/matrix[i][i]

for k in range(n+1): matrix[j][k] = matrix[j][k] - ratio * matrix[i][k]

# Back Substitution x[n-1] = matrix[n-1][n]/matrix[n-1][n-1]

for i in range(n-2,-1,-1): x[i] = matrix[i][n]

for j in range(i+1,n): x[i] = x[i] - matrix[i][j]*x[j]

x[i] = x[i]/matrix[i][i]

# Displaying solution print('\nThe unknown values for the above equations are:') for i in range(n): print('X%d = %0.2f' %(i,x[i]), end = '\t')

Output

Time Complexity

The time complexity for the above code will be O(n)*(O(n)*O(n)) = O(n3) because for each pivot, we will traverse the part to its right for each row below it.

Now it’s time for some frequently asked questions.

Frequently Asked Questions

What are the rules for Gaussian elimination?

The rules for Gaussian elimination is to perform elementary row operations: interchange rows, multiply a row by a non-zero constant, and add or subtract a multiple of one row from another.

Why is it called Gaussian elimination?

It is named after Carl Friedrich Gauss, it's a method for transforming a matrix to its row-echelon form.

What is Gaussian elimination method disadvantages?

Gaussian elimination method disadvantages are sensitivity to round-off errors and computational complexity for large systems.

Can you divide in Gaussian elimination?

Division is involved when scaling rows but not when performing basic row operations.

Conclusion

In the above article, we have learned to calculate the value of unknown variables in linear equations using the gaussian elimination method. We have discussed the approach using java, python, and CPP languages. To enhance your knowledge of gaussian algorithms, check out these articles-

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences for placement preparations.