Gaussian Elimination in Python
The usage of linear and polynomial equations is prevalent across almost the entirety of the field of numerical simulation. However, its most obvious use can be found in the discipline of engineering that deals with the analysis of linear systems of equations. Linear systems are a broad category that includes many different subcategories, such as structures, elastic material, heat fluxes, electromagnetism, electrical circuits, and many more.
When modeling linear systems, mathematical equations of the sort Ax = b are generated. In these equations, x represents the input matrix, and b represents the response vector for the system being modeled. Independent of the input vector, A, also known as the matrix of coefficients, contains a reflection of the fundamental attributes of the system. The linear equation system that we want to evaluate will still include the exact coefficients matrix A, but it will have a different response vector if the input is altered.
b.
Methods of Solving Systems of Linear Equations
In addition to the iterative techniques, there are also so-called straightforward approaches, which we won’t go over here because they aren’t relevant to the topic at hand. Their common goal is to simplify the process of solving the source equations by converting them into a system that has the same features as the original system but is easier to solve.
This can be accomplished through the use of three major procedures.
transformation:
- The numeric value of A’s determinant flips sign when two lines of the matrix A are swapped;
- The numeric value of the determinant of A gets multiplied by the same scalar by which the row of the matrix A is multiplied;
- A’s determinant is left unaltered if we change a row of A by the one produced by appending that row to some other row scaled by a scalar;
These processes, of course, have no influence on the system’s solutions, which remain unaltered; but, they might have an impact on the coefficient matrix A and the determinant of that matrix.
The following is a compilation of the three most important direct routes to potential solutions.
table:
| Method | Initial form | Final form |
|---|---|---|
|
Gauss elimination |
Ax = b | Ux = c |
|
LU decomposition |
Ax = b | LUx = b |
|
Gauss-Jordan elimination |
Ax = b | Ix = c |
Gauss Elimination Method
Row reduction is another name for the statistical technique known as Gaussian elimination. A linear system of equations can be solved using this technique, which is based on linear algebra. A coefficients matrix goes through a number of processes, which are the heart of what happens. These are the activities that are being carried out.
involved:
- We can swap two rows
- Scaling a row by multiplying it with a scaler
- Adding a row to another row of the matrix
These steps are carried out for as long as is required to ensure that the lower left side of the coefficient matrix is filled with
zeros.
Gauss Elimination Algorithm in Python
In terms of the manual process, there are two alternative ways: the first is that the rows are converted by subtracting rather than by adding, and the second is that the converted rows are not substituted by the beginning rows of the matrix A, but rather by the components that are unique to an upper triangular matrix. Both of these techniques involve changing the way that the rows are converted. In point of fact, the computation of solutions is not in any way impacted by components that are not part of U. (the modified matrix). Code
-
# Python program to find a solution to a set of linear equations using the Gaussian Elimination method
-
-
# Creating a function to print the augmented matrix with the given set of linear equations
-
def
print_aug(mat):
-
no = len(mat)
-
for
i
in
range(
0
, no):
-
l = “”
-
for
k
in
range(
0
, n +
1
):
-
l += str(mat[i][k]) +
“\t”
-
if
j == no –
1
:
-
l +=
“| ”
-
print
(l)
-
print
(“”)
-
-
# Creating a function to perform gaussian elimination on the given matrix mat
-
def
gauss_elem(mat):
-
num = len(mat)
-
-
for
i
in
range(
0
, num):
-
# Searching the maximum value of a particular column
-
max_el = abs(mat[i][i])
-
# Row having the element of maximum value
-
max_row = i
-
for
k
in
range(i +
1
, num):
-
if
abs(mat[k][i]) > max_el:
-
max_el = abs(mat[k][i])
-
max_row = k
-
-
# Swapping the maximum row with the current row
-
for
k
in
range(i, n +
1
):
-
temp = mat[max_row][k]
-
mat[max_row][k] = mat[i][k]
-
mat[i][k] = temp
-
-
# Chaning the value of the rows below the current row to 0
-
for
k
in
range(i +
1
, n):
-
curr = -mat[k][i] / mat[i][i]
-
for
j
in
range(i, n +
1
):
-
if
i == j:
-
mat[k][j] =
0
-
else
:
-
mat[k][j] += curr * mat[i][j]
-
-
# Solving the equation Ax = b for the created upper triangular matrix mat
-
l = [
0
for
i
in
range(n)]
-
for
j
in
range(n –
1
, –
1
, –
1
):
-
l[j] = mat[j][n] / mat[j][j]
-
for
k
in
range(j –
1
, –
1
, –
1
):
-
mat[k][n] -= mat[k][j] * l[j]
-
return
l
-
-
-
if
__name__ ==
“__main__”
:
-
from
fractions
import
Fraction
-
-
n = int(input())
-
-
A_mat = [[
0
for
j
in
range(n +
1
)]
for
i
in
range(n)]
-
-
# Reading the input coefficients of the linear equations
-
for
j
in
range(
0
, n):
-
l = map(Fraction, input().split(
” ”
))
-
for
i, elem
in
enumerate(l):
-
A_mat[j][i] = elem
-
-
-
l = input().split(
” ”
)
-
print
(l)
-
last = list(map(Fraction, l))
-
for
j
in
range(
0
, n):
-
A_mat[j][n] = last[j]
-
-
# Printing the augmented matrix from the input data
-
print_aug(A_mat)
-
-
# Calculating the solution of the matrix
-
x = gauss_elem(A_mat)
-
-
# Printing the result
-
l =
“Result:\t”
-
for
j
in
range(
0
, n):
-
l += str(x[j]) +
“\t”
-
print
(l)
Output:
3 3 4 -1 5 -2 1 2 -2 1 8 4 1 ['8', '4', '1'] 3 | 4 | -1 | 8 | 5 | -2 | 1 | 4 | 2 | -2 | 1 | 1 | Result: 1 2 3
In the event that we provide an equation set that does not have a solution, the output will be as follows:
3 1 1 1 0 1 -3 2 1 5 2 1 0 ['2', '1', '0'] 1 | 1 | 1 | 2 | 0 | 1 | -3 | 1 | 2 | 1 | 5 | 0 | --------------------------------------------------------------------------- ZeroDivisionError Traceback (most recent call last)in 75 76 # Calculating the solution of the matrix ---> 77 x = gauss_elem(A_mat) 78 79 # Printing the result ________________________________________ 3 frames ________________________________________ /usr/lib/Python3.7/fractions.py in __new__(cls, numerator, denominator, _normalize) 176 177 if denominator == 0: --> 178 raise ZeroDivisionError('Fraction(%s, 0)' % numerator) 179 if _normalize: 180 if type(numerator) is int is type(denominator): ZeroDivisionError: Fraction(3, 0)