> For the complete documentation index, see [llms.txt](https://laus-organization.gitbook.io/numerical-analysis-implementations-in-python/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://laus-organization.gitbook.io/numerical-analysis-implementations-in-python/zhi-jie-qiu-jie-xian-xing-fang-cheng-zu/5.-zhui-gan-fa-thomas-algorithm.md).

# 5. 追赶法（Thomas Algorithm）

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

#### 实现步骤

1. **前向消去（Forward Elimination）**：修改系数矩阵和右端向量，使其变为上三角形式。
2. **回代（Backward Substitution）**：求解未知数。

#### 代码实现

```python
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)：

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

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