Python/linear_algebra/gaussian_elimination.py at master · TheAlgorithms/Python · GitHub

Name: Python/linear_algebra/gaussian_elimination.py at master · TheAlgorithms/Python · GitHub
Rating: 4.9 (1927 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
"""
| Gaussian elimination method for solving a system of linear equations.
| Gaussian elimination - https://en.wikipedia.org/wiki/Gaussian_elimination
"""

importnumpyasnp
fromnumpyimportfloat64
fromnumpy.typingimportNDArray


defretroactive_resolution(
coefficients: NDArray[float64], vector: NDArray[float64]
) ->NDArray[float64]:
"""
 This function performs a retroactive linear system resolution
 for triangular matrix

 Examples:
 1.
 * 2x1 + 2x2 - 1x3 = 5
 * 0x1 - 2x2 - 1x3 = -7
 * 0x1 + 0x2 + 5x3 = 15
 2.
 * 2x1 + 2x2 = -1
 * 0x1 - 2x2 = -1

 >>> gaussian_elimination([[2, 2, -1], [0, -2, -1], [0, 0, 5]], [[5], [-7], [15]])
 array([[2.],
 [2.],
 [3.]])
 >>> gaussian_elimination([[2, 2], [0, -2]], [[-1], [-1]])
 array([[-1. ],
 [ 0.5]])
 """

rows, columns=np.shape(coefficients)

x: NDArray[float64] =np.zeros((rows, 1), dtype=float)
forrowinreversed(range(rows)):
total=np.dot(coefficients[row, row+1 :], x[row+1 :])
x[row, 0] = (vector[row][0] -total[0]) /coefficients[row, row]

returnx


defgaussian_elimination(
coefficients: NDArray[float64], vector: NDArray[float64]
) ->NDArray[float64]:
"""
 This function performs Gaussian elimination method

 Examples:
 1.
 * 1x1 - 4x2 - 2x3 = -2
 * 5x1 + 2x2 - 2x3 = -3
 * 1x1 - 1x2 + 0x3 = 4
 2.
 * 1x1 + 2x2 = 5
 * 5x1 + 2x2 = 5

 >>> gaussian_elimination([[1, -4, -2], [5, 2, -2], [1, -1, 0]], [[-2], [-3], [4]])
 array([[ 2.3 ],
 [-1.7 ],
 [ 5.55]])
 >>> gaussian_elimination([[1, 2], [5, 2]], [[5], [5]])
 array([[0. ],
 [2.5]])
 """
# coefficients must to be a square matrix so we need to check first
rows, columns=np.shape(coefficients)
ifrows!=columns:
returnnp.array((), dtype=float)

# augmented matrix
augmented_mat: NDArray[float64] =np.concatenate((coefficients, vector), axis=1)
augmented_mat=augmented_mat.astype("float64")

# scale the matrix leaving it triangular
forrowinrange(rows-1):
pivot=augmented_mat[row, row]
forcolinrange(row+1, columns):
factor=augmented_mat[col, row] /pivot
augmented_mat[col, :] -=factor*augmented_mat[row, :]

x=retroactive_resolution(
augmented_mat[:, 0:columns], augmented_mat[:, columns : columns+1]
 )

returnx


if__name__=="__main__":
importdoctest

doctest.testmod()