5. 追赶法（Thomas Algorithm）

追赶法（Thomas Algorithm）是一种高效的算法，专门用于解决三对角矩阵的线性方程组。三对角矩阵是指在主对角线、上对角线和下对角线之外的元素全为零的矩阵。

实现步骤

1. 前向消去（Forward Elimination）：修改系数矩阵和右端向量，使其变为上三角形式。

2. 回代（Backward Substitution）：求解未知数。

代码实现

import numpy as np

def thomas_algorithm(a, b, c, d):
    """
    Solve the system of linear equations Ax = d for a tridiagonal matrix A using the Thomas algorithm.

    Parameters:
    a : list or numpy array
        Sub-diagonal (a_1, ..., a_{n-1}) of the tridiagonal matrix A
    b : list or numpy array
        Main diagonal (b_0, ..., b_{n-1}) of the tridiagonal matrix A
    c : list or numpy array
        Super-diagonal (c_0, ..., c_{n-2}) of the tridiagonal matrix A
    d : list or numpy array
        Right-hand side vector

    Returns:
    x : numpy array
        Solution vector
    """
    n = len(d)
    
    # Allocate space for the modified coefficients
    c_prime = np.zeros(n - 1)
    d_prime = np.zeros(n)

    # Modify the coefficients
    c_prime[0] = c[0] / b[0]
    d_prime[0] = d[0] / b[0]

    for i in range(1, n):
        denom = b[i] - a[i - 1] * c_prime[i - 1]
        if i < n - 1:
            c_prime[i] = c[i] / denom
        d_prime[i] = (d[i] - a[i - 1] * d_prime[i - 1]) / denom

    # Backward substitution
    x = np.zeros(n)
    x[-1] = d_prime[-1]

    for i in range(n - 2, -1, -1):
        x[i] = d_prime[i] - c_prime[i] * x[i + 1]

    return x

# Example usage
a = np.array([1, 1, 1], dtype=float)  # Sub-diagonal (n-1 elements)
b = np.array([4, 4, 4, 4], dtype=float)  # Main diagonal (n elements)
c = np.array([1, 1, 1], dtype=float)  # Super-diagonal (n-1 elements)
d = np.array([5, 6, 6, 5], dtype=float)  # Right-hand side vector (n elements)

x = thomas_algorithm(a, b, c, d)
print("Solution:", x)

代码说明

1. 输入参数：

   • a：下对角线元素（长度为 ( n-1 ) 的数组）。

   • b：主对角线元素（长度为 ( n ) 的数组）。

   • c：上对角线元素（长度为 ( n-1 ) 的数组）。

   • d：右端向量（长度为 ( n ) 的数组）。

2. 前向消去（Forward Elimination）：

   • 计算修正后的上对角线元素 ( c' ) 和右端向量 ( d' )。

   • 修改后的上对角线和右端向量用来构造一个新的等价的上三角矩阵。

3. 回代（Backward Substitution）：

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

示例

给定三对角矩阵的下对角线元素 (a)，主对角线元素 (b)，上对角线元素 (c)，以及右端向量 (d)：

a = [1, 1, 1]
b = [4, 4, 4, 4]
c = [1, 1, 1]
d = [5, 6, 6, 5]

运行上述代码，求解三对角线性方程组 (Ax = d)，可以得到解向量 x。