2. 列主元高斯消去法(Gaussian Elimination with Partial Pivoting)

下面是使用Python实现列主元高斯消去法(Gaussian Elimination with Partial Pivoting)求解线性方程组的代码。该实现包含前向消去和回代两个步骤,并在每一步选择当前列的绝对值最大的元素作为主元。

import numpy as np

def gaussian_elimination_with_partial_pivoting(A, b):
    """
    Solve the system of linear equations Ax = b using Gaussian Elimination with Partial Pivoting.

    Parameters:
    A : 2D list or numpy array
        Coefficient matrix
    b : 1D list or numpy array
        Right-hand side vector

    Returns:
    x : numpy array
        Solution vector
    """
    n = len(b)
    A = A.astype(float)  # Ensure the matrix is of type float
    b = b.astype(float)  # Ensure the vector is of type float
    
    # Forward elimination with partial pivoting
    for i in range(n):
        # Pivoting: find the row with the largest element in the current column
        max_row_index = np.argmax(np.abs(A[i:n, i])) + i
        if A[max_row_index, i] == 0:
            raise ValueError("Matrix is singular or nearly singular")

        # Swap the current row with the max_row_index row
        A[[i, max_row_index]] = A[[max_row_index, i]]
        b[[i, max_row_index]] = b[[max_row_index, i]]

        # Make the diagonal element 1 and eliminate the column below
        pivot = A[i, i]
        A[i] = A[i] / pivot
        b[i] = b[i] / pivot

        for j in range(i + 1, n):
            factor = A[j, i]
            A[j] = A[j] - factor * A[i]
            b[j] = b[j] - factor * b[i]

    # Backward substitution
    x = np.zeros(n)
    for i in range(n - 1, -1, -1):
        x[i] = b[i] - np.dot(A[i, i + 1:], x[i + 1:])
    
    return x

# Example usage
A = np.array([[2, -1, 1],
              [3, 3, 9],
              [3, 3, 5]], dtype=float)
b = np.array([2, -1, 2], dtype=float)

x = gaussian_elimination_with_partial_pivoting(A, b)
print("Solution:", x)

代码说明

  1. 输入参数

    • A:系数矩阵,可以是二维列表或NumPy数组。

    • b:右端向量,可以是一维列表或NumPy数组。

  2. 前向消去(Forward Elimination with Partial Pivoting)

    • 对于每一列,从当前行到最后一行中选择绝对值最大的元素作为主元。

    • 交换当前行和主元所在行。

    • 将当前行的主元归一化。

    • 对当前行以下的每一行进行消去操作,使得该列元素变为零。

  3. 回代(Backward Substitution)

    • 从最后一行开始,逐步向上回代,求解每一个未知数。

示例

给定系数矩阵 (A) 和右端向量 (b):

A = [[2, -1, 1],
     [3, 3, 9],
     [3, 3, 5]]
b = [2, -1, 2]

运行上述代码,求解线性方程组 (Ax = b),可以得到解向量 x

注意事项

  • 该实现假设矩阵 (A) 是非奇异的,即有唯一解。

  • 该实现通过交换行操作避免了数值不稳定的问题,适用于更广泛的情况。

Last updated