Gaussian Elimination in Linear Equations

Gaussian Elimination is a powerful algorithm used to solve systems of linear equations. It’s widely used in programming for applications like machine learning, physics simulations, and optimization problems. In this blog, we’ll explain how Gaussian Elimination works, provide practical examples, and include Python code snippets to help you implement it.

---

What is Gaussian Elimination?

Gaussian Elimination is a method for solving systems of linear equations by transforming the matrix of coefficients into an upper triangular form (row echelon form). Once the matrix is in this form, we can solve for the variables using back substitution.

Key Concepts

• Row Echelon Form (REF): A matrix where:

  • The first non-zero element in each row (called the pivot) is 1.
  • Each pivot is to the right of the pivot in the row above.
  • Rows with all zeros are at the bottom.

• Reduced Row Echelon Form (RREF): A matrix in REF where:

  • Each pivot is the only non-zero entry in its column.

Example Problem

Given the following system of equations:

3.0X1 + 2.0X2 - 4.0X3 =  3.0
2.0X1 + 3.0X2 + 3.0X3 = 15.0
5.0X1 - 3.0X2 +    X3 = 14.0

We represent it as an augmented matrix:

mat = [[3.0, 2.0, -4.0, 3.0],
       [2.0, 3.0, 3.0, 15.0],
       [5.0, -3.0, 1.0, 14.0]]

The solution to this system is:

X1 = 3.0, X2 = 1.0, X3 = 2.0

---

How Does Gaussian Elimination Work?

The process involves two main steps:

1. Forward Elimination: Convert the matrix into row echelon form.
2. Back Substitution: Solve for the variables starting from the last row.

Steps in Forward Elimination

1. Find the largest absolute value in the current column (partial pivoting).
2. Swap rows to bring the largest value to the pivot position.
3. Use the pivot to eliminate values below it in the same column.

Steps in Back Substitution

1. Start from the last row and solve for the variable.
2. Substitute the solved values into the previous rows to find the remaining variables.

---

Python Implementation

Here’s how you can implement Gaussian Elimination in Python:

# Function to perform Gaussian Elimination
def gaussian_elimination(mat):
    n = len(mat)

    # Forward elimination
    for i in range(n):
        # Partial pivoting: Find the row with the largest pivot
        max_row = i
        for k in range(i + 1, n):
            if abs(mat[k][i]) > abs(mat[max_row][i]):
                max_row = k

        # Swap the current row with the max_row
        mat[i], mat[max_row] = mat[max_row], mat[i]

        # Eliminate all entries below the pivot
        for k in range(i + 1, n):
            factor = mat[k][i] / mat[i][i]
            for j in range(i, n + 1):
                mat[k][j] -= factor * mat[i][j]

    # Back substitution
    x = [0] * n
    for i in range(n - 1, -1, -1):
        x[i] = mat[i][n] / mat[i][i]
        for k in range(i - 1, -1, -1):
            mat[k][n] -= mat[k][i] * x[i]

    return x


# Example usage
if __name__ == "__main__":
    # Augmented matrix for the system of equations
    mat = [
        [3.0, 2.0, -4.0, 3.0],
        [2.0, 3.0, 3.0, 15.0],
        [5.0, -3.0, 1.0, 14.0]
    ]

    # Solve the system
    solution = gaussian_elimination(mat)
    print("Solution for the system:")
    for i, val in enumerate(solution):
        print(f"X{i + 1} = {val:.6f}")

Output

Solution for the system:
X1 = 3.000000
X2 = 1.000000
X3 = 2.000000

---

Applications in Programming

Gaussian Elimination is used in various fields:

1. Machine Learning: Solving linear regression problems.
2. Graphics: Transforming 3D objects in computer graphics.
3. Physics Simulations: Modeling physical systems.
4. Optimization: Solving linear programming problems.

---

Time Complexity

The time complexity of Gaussian Elimination is O(N³) for an N x N matrix. This is because:

• Forward elimination involves iterating over rows and columns.
• Back substitution involves solving for each variable.

---

Conclusion

Gaussian Elimination is a fundamental algorithm for solving systems of linear equations. By implementing it programmatically, you can efficiently handle real-world problems in fields like machine learning and physics simulations.

For more content, follow me at — https://linktr.ee/shlokkumar2303