【算法 | Python】高斯消元法

末蓝、 2022-12-03 05:22 187阅读 0赞

--------------------

程序来源：[Gaussian Elimination][]

--------------------

### Arithmetic Analysis ###

*   *   *  原理说明
         *  源代码
         *  代码说明

### 原理说明 ###

*  [高斯消元法(Gauss Elimination)【超详解&模板】][Gauss Elimination]
 *  [高斯消元法-百度百科][-]

### 源代码 ###

""" Gaussian elimination method for solving a system of linear equations. Gaussian elimination - https://en.wikipedia.org/wiki/Gaussian_elimination 高斯消元法，是线性代数中的一个算法，可用来求解线性方程组，并可以求出矩阵的秩，以及求出可逆方阵的逆矩阵。 高斯消元法的原理是：若用初等行变换将增广矩阵 化为 ，则AX = B与CX = D是同解方程组。 详细说明见 http://www.mamicode.com/info-detail-1813820.html """
    
    
    import numpy as np
    
    
    def retroactive_resolution(coefficients: np.matrix, vector: np.array) -> np.array:
        """ 此函数对三角矩阵执行追溯线性系统解析 This function performs a retroactive linear system resolution for triangular matrix """
    
        rows, columns = np.shape(coefficients)
    
        x = np.zeros((rows, 1), dtype=float)
        for row in reversed(range(rows)):
            sum = 0
            for col in range(row + 1, columns):
                sum += coefficients[row, col] * x[col]
    
            x[row, 0] = (vector[row] - sum) / coefficients[row, row]
    
        return x
    
    
    def gaussian_elimination(coefficients: np.matrix, vector: np.array) -> np.array:
        """ 此函数执行高斯消去法 This function performs Gaussian elimination method Examples: 1x1 - 4x2 - 2x3 = -2 1x1 + 2x2 = 5 5x1 + 2x2 - 2x3 = -3 5x1 + 2x2 = 5 1x1 - 1x2 + 0x3 = 4 >>> 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)
        if rows != columns:
            return []
    
        # augmented matrix
        # 增广矩阵
        augmented_mat = np.concatenate((coefficients, vector), axis=1)
        augmented_mat = augmented_mat.astype("float64")
    
        # scale the matrix leaving it triangular
        # 缩放矩阵，让它变成三角形
        for row in range(rows - 1):
            pivot = augmented_mat[row, row]
            for col in range(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]
        )
    
        return x
    
    
    if __name__ == "__main__":
        import doctest
    
        doctest.testmod()

### 代码说明 ###

*  在运行代码前需安装numpy库，安装方法如下：`用管理员身份打开cmd，输入 python -m pip install numpy`
 *  代码 `gaussian_elimination(coefficients: np.matrix, vector: np.array) -> np.array` 中的冒号与箭头作用为：**提示其他人变量类型**（非强制），详情见[**Python函数参数中的冒号与箭头**][Python]
 *  [**Python doctest模块：文档测试（超级详细）**][Python doctest]

[Gaussian Elimination]: https://github.com/TheAlgorithms/Python/blob/master/arithmetic_analysis/gaussian_elimination.py
[Gauss Elimination]: http://www.mamicode.com/info-detail-1813820.html
[-]: https://baike.baidu.com/item/%E9%AB%98%E6%96%AF%E6%B6%88%E5%85%83%E6%B3%95/619561?fr=aladdin
[Python]: https://www.cnblogs.com/ArsenalfanInECNU/p/10724203.html
[Python doctest]: http://c.biancheng.net/view/2676.html