如何在Python中实现回代求解线性系统？

Question

我目前正在致力于实现一个回代函数，以解决由 Python 中的增广矩阵表示的线性系统。我一直在研究求解线性系统的算法，并且理解回代的概念，但我在实现细节上遇到了困难。这个带参数输入的函数是矩阵行梯形形式 3 x 3，其增广矩阵与线性系统中的 equals 堆叠。

# GRADED FUNCTION: back_substitution

def back_substitution(M):
    """
    Perform back substitution on an augmented matrix (with unique solution) in reduced row echelon form to find the solution to the linear system.

    Parameters:
    - M (numpy.array): The augmented matrix in row echelon form with unitary pivots (n x n+1).

    Returns:
    numpy.array: The solution vector of the linear system.
    """
    
    # Make a copy of the input matrix to avoid modifying the original
    M = M.copy()

    # Get the number of rows (and columns) in the matrix of coefficients
    num_rows = len(M)

    ### START CODE HERE ####
    
    # Iterate from bottom to top
    for row in range(num_rows): 
        # Get the substitution row. Remember now you must proceed from bottom to top, so you must start at the last row in the matrix.
        # The last row in matrix is in the index num_rows - 1, then you need to subtract the current index.
        substitution_row = M[row-1]

        # Iterate over the rows above the substitution_row
        for j in range(row + 1, num_rows): 

            # Get the row to be reduced. The indexing here is similar as above, with the row variable replaced by the j variable.
            row_to_reduce = M[j-1]
            # Get the index of the first non-zero element in the substitution row. This values does not depend on j!
            index = get_index_first_non_zero_value_from_row(substitution_row,row)

            # Get the value of the element at the found index
            value = row_to_reduce[index]

            # Perform the back substitution step using the formula row_to_reduce = None
            row_to_reduce = row_to_reduce - value*M[row]

            # Replace the updated row in the matrix, be careful with indexing!
            M[row] = row_to_reduce
            

    ### END CODE HERE ####

     # Extract the solution from the last column
    solution = M[:,-1]
    
    return solution

A = np.array([[1,-1,0.5],[0,1,1], [0,0,1]])
B = np.array([[0.5], [-1], [-1]])
back_substitution(row_echelon_form(A,B))

#Output
[-1,0,-1]

必须输出为[1,0,-1]

Answer 1

我建议不要将 A 和 B 放在同一个表达式中，将它们放在一起可能会导致代码阅读更加复杂/更频繁地出现意外错误。

一个更简洁的解决方案可能是，计算从末尾到开头的 x[i]，每个 x[i] 相当于 (b[i] - M[i] @ x) / M[i, i ].

def back_substitution(M, b):
    n = b.size
    x = np.zeros_like(b)

    for i in range(n-1, -1, -1):
        x[i] = (b[i] - M[i] @ x) / M[i, i]

    return x

M = np.array([[1, -1, 0.5],[0, 1, 1], [0, 0, 1]])
b = np.array([[0.5], [-1], [-1]])
back_substitution(M,b)

最后我得到输出：

array([[ 1.],
       [ 0.],
       [-1.]])