Article directory
- 1. Basic theory
-
- 1. System of linear equations
- 2. Detailed steps of Gauss elimination method
- 3. Precautions
- 2. Specific calculation process
-
- 1. Use Gauss elimination method to find the LU decomposition of A, and solve the system of equations Ax =b from this
-
- a. Perform LU decomposition of A.
- b. Use LU decomposition to solve the system of equations Ax=b
- 3. Code implementation
-
- 1. Python code implementation
- 2. C language code implementation
Gauss elimination method, also known as Gauss elimination method or Gauss-Jordan elimination method, is a numerical method used to solve systems of linear equations. It was developed by German mathematician Carl Friedrich Gauss in the late 18th century.
The basic idea of the Gauss elimination method is to transform a system of linear equations into an upper triangular system of equations through a series of row transformations, and then solve the solution of the system of equations through a back substitution process.
1. Basic theory
1. System of linear equations
A system of linear equations is a set of equations composed of a set of linear equations. Every linear equation can be expressed in the form of “a?x? + a?x? + … + a?x? = b”, where a?, a?, …, a? are known constants, x?, x?, …, x? are unknown variables, and b is a known constant. Each term in the equation is the product of a variable raised to a power and a constant, and there is no multiplication operator connecting the variables.
A system of linear equations can contain multiple linear equations that together describe the relationship between a set of variables. Solving a system of linear equations is to find the values of variables that satisfy all equations so that all equations are true. The goal of solving a system of linear equations is to find the values of a set of variables such that every equation in the system is satisfied.
A system of linear equations can have multiple or no solutions. A system of equations has a solution if there is at least one combination of variable values that satisfies all equations. If no such combination of variable values exists, then the system of equations has no solution.
Methods for solving linear equations include Gaussian elimination method, matrix method, Clem’s rule, etc. These methods can be used to solve systems of linear equations of different sizes and forms. Linear equations are widely used in mathematics, physics, engineering and other fields to describe and solve various practical problems.
2. Detailed steps of Gauss elimination method
- Write the system of linear equations in augmented matrix form, that is, combine the coefficient matrix and the constant vector.
- Select the equation whose coefficient of the first unknown is not zero as the principal component equation. If there is no such equation, swap the two rows or columns so that the principal component coefficient is not zero.
- Divide the coefficient of the pivot equation by the pivot coefficient so that the pivot coefficient becomes 1.
- Multiply the coefficients of the pivot equation by the pivot coefficients of the other equations and subtract the result from the corresponding equation to eliminate the pivot coefficients in the other equations.
- Repeat steps 2 to 4 until all coefficients of the unknown variables are in the form of upper triangular matrices.
- Perform a back-substitution process, starting from the last row and solving for the value of each unknown in turn. The process of back substitution is to solve for the value of the unknown by substituting the known unknown into the equation.
3. Notes
&emps; &emps;The advantage of the Gauss elimination method is that it can accurately solve a system of linear equations and is suitable for any number of unknowns and equations. It is widely used in the fields of numerical calculation and scientific engineering. However, it There are also some limitations and caveats:
-
If the coefficient matrix of the system of equations is singular (that is, the determinant is zero), it cannot be solved using Gaussian elimination.
-
During the elimination process, you need to pay attention to avoid dividing by zero. If you encounter a situation where the pivot coefficient is zero, you need to perform row exchange or column exchange.
-
If the coefficient matrix of the system of equations is large, the calculation amount of elimination will be large and may require a long calculation time.
2. Specific calculation process
1. Use Gauss elimination method to find the LU decomposition of A, and solve the system of equations Ax =b
A
=
[
[
1
,
2
,
1
,
?
2
]
,
[
2
,
5
,
3
,
?
2
]
,
[
?
2
,
?
2
,
3
,
5
]
,
[
1
,
3
,
2
,
3
]
]
A=[ [1, 2, 1, -2], [2, 5, 3, -2], [-2, -2, 3, 5], [1, 3, 2, 3] ]
A=[[1,2,1,?2],[2,5,3,?2],[?2,?2,3,5],[1,3,2,3]]
b
=
[
2
,
8
,
4
,
9
]
b=[2, 8, 4, 9]
b=[2,8,4,9]
a. Perform LU decomposition of A.
-
Select the equation whose coefficient of the first unknown is not zero as the principal component equation, that is, the element in row 1 and column 1 is not zero, so select row 1 as the principal component equation.
-
Divide the coefficients of the pivot equation by the pivot coefficient, that is, divide all the elements in row 1 by 1 to get:
1 2 1 -2 2 5 3 -2 -2 -2 3 5 1 3 2 3
- Multiply the coefficients of the pivot equation by the pivot coefficients of the other equations and subtract the result from the corresponding equation to eliminate the pivot coefficients in the other equations. Eliminate rows 2, 3, and 4:
1 2 1 -2 0 1 1 2 0 4 4 1 0 1 1 5
-
Select the equation whose coefficient of the second unknown is not zero as the principal component equation, that is, the elements in row 2 and column 2 are not zero, so select row 2 as the principal component equation.
-
Divide the coefficients of the pivot equation by the pivot coefficient, that is, divide all the elements in row 2 by 1 to get:
1 2 1 -2 0 1 1 2 0 4 4 1 0 1 1 5
- Multiply the coefficients of the pivot equation by the pivot coefficients of the other equations and subtract the result from the corresponding equation to eliminate the pivot coefficients in the other equations. Eliminate rows 3 and 4:
1 2 1 -2 0 1 1 2 0 0 0 -7 0 0 0 3
Now, we get the upper triangular matrix U and the lower triangular matrix L:
U = 1 2 1 -2 0 1 1 2 0 0 0 -7 0 0 0 3 L = 1 0 0 0 2 1 0 0 -2 -4 1 0 1 -1 -1 1
b. Use LU decomposition to solve the system of equations Ax=b
- First, according to LU decomposition, we can get Ly=b, where y is a new unknown vector.
1 0 0 0 | y1 = 2 2 1 0 0 | y2 = 8 -2 -4 1 0 | y3 = 4 1 -1 -1 1 | y4 = 9
Through the forward substitution method, we can solve for the value of y:
y1 = 2 y2 = 8 - 2y1 = 8 - 2(2) = 4 y3 = 4 - 2y1 + 4y2 = 4 - 2(2) + 4(4) = 18 y4 = 9 - y1 + y2 - y3 = 9 - 2 + 4 - 18 = -7
- Then, according to LU decomposition, we can get Ux=y, where x is the unknown vector we want to solve for.
1 2 1 -2 | x1 = y1 0 1 1 2 | x2 = y2 0 0 0 -7 | x3 = y3 0 0 0 3 | x4 = y4
Through back substitution, we can solve for the value of x:
x1 = y1 = 2 x2 = y2 - x1 = 4 - 2 = 2 x3 = y3 / (-7) = 18 / (-7) ≈ -2.571 x4 = y4 / 3 = (-7) / 3 ≈ -2.333
Therefore, the solution of the system of equations Ax=b is x = [2, 2, -2.571, -2.333].
3. Code implementation
1. Python code implementation
import numpy as np
A = np.array([[1, 2, 1, -2],
[2, 5, 3, -2],
[-2, -2, 3, 5],
[1, 3, 2, 3]])
b = np.array([2, 8, 4, 9])
def gauss_elimination(A, b):
n = len(A)
for i in range(n-1):
for j in range(i + 1, n):
factor = A[j, i] / A[i, i]
A[j, i:] -= factor * A[i, i:]
b[j] -= factor * b[i]
return A, b
def back_substitution(U, y):
n = len(U)
x = np.zeros(n)
x[-1] = y[-1] / U[-1, -1]
for i in range(n-2, -1, -1):
x[i] = (y[i] - np.dot(U[i, i + 1:], x[i + 1:])) / U[i, i]
return x
def solve_linear_equations(A, b):
U, y = gauss_elimination(A, b)
x = back_substitution(U, y)
return x
x = solve_linear_equations(A, b)
print("Solution x:", x)