使用追赶法求解三对角方程组

三对角方程组是指系数形如

$$\boldsymbol{A}= \begin{pmatrix} b_1 & c_1 & & & \\ a_2 & b_2 & c_2 & & \\ & \ddots & \ddots & \ddots & \\ & & a_{n-1} & b_{n-1} & c_{n-1} \\ & & & a_n & b_n \end{pmatrix}$$

的方程组。当系数矩阵是严格对角占优矩阵时，即满足

$$\begin{aligned} &|b_1| > |c_1| > 0 \\ &|b_i| > |c_i| + |a_i| \\ &|b_n| > |a_n| > 0 \end{aligned}$$

时，可以使用追赶法求解方程组，计算量很小。

追赶法的核心算法是矩阵分析中常用的LU分解，对于给定方程组$\boldsymbol{A}\boldsymbol{x}=\boldsymbol{d}$，其系数矩阵为三对角矩阵，可以利用LU分解得到如下形式

$$\begin{pmatrix} b_1 & c_1 & & & \\ a_2 & b_2 & c_2 & & \\ & \ddots & \ddots & \ddots & \\ & & a_{n-1} & b_{n-1} & c_{n-1} \\ & & & a_n & b_n \end{pmatrix} = \begin{pmatrix} \alpha_1 & & & & \\ \gamma_2 & \alpha_2 & & & \\ & \ddots & \ddots & & \\ & & \gamma_{n-1} & \alpha_{n-1} & \\ & & & \gamma_n & \alpha_n \end{pmatrix} \begin{pmatrix} 1 & \beta_1 & & & \\ & 1 & \beta_2 & & \\ & & \ddots & \ddots & \\ & & & 1 & \beta_{n-1} \\ & & & & 1 \end{pmatrix}$$

其中

$$\boldsymbol{L}= \begin{pmatrix} \alpha_1 & & & & \\ \gamma_2 & \alpha_2 & & & \\ & \ddots & \ddots & & \\ & & \gamma_{n-1} & \alpha_{n-1} & \\ & & & \gamma_n & \alpha_n \end{pmatrix}, \boldsymbol{U}= \begin{pmatrix} 1 & \beta_1 & & & \\ & 1 & \beta_2 & & \\ & & \ddots & \ddots & \\ & & & 1 & \beta_{n-1} \\ & & & & 1 \end{pmatrix}$$

因此有下述等式

$$\begin{aligned} \begin{cases} \alpha_1 = b_1 \\ \gamma_i = a_i, & i=1,2,...,n \\ \alpha_i + \gamma_i \beta_{i-1} = b_i, & i=2,3,...,n \\ \alpha_i \beta_i = c_i, & i=1,2,...,n \end{cases} \end{aligned}$$

现已知$a_i,b_i,c_i$，由$\gamma_i = a_i$可求得$\gamma_i$。观察到，由$\alpha_i \beta_i = c_i$有，若知$\alpha_i$可求得$\beta_i$，由$\alpha_i + \gamma_i \beta_{i-1} = b_i$有，若知$\beta_i$可求得$\alpha_{i+1}$。而由$\alpha_1 = b_1$可求得$\alpha_1$，从而可以依次求出$\alpha_i$和$\beta_i$。

要想求解$\boldsymbol{A}\boldsymbol{x}=\boldsymbol{d}$，只需要求解$\boldsymbol{L}\boldsymbol{y}=\boldsymbol{d}$和$\boldsymbol{U}\boldsymbol{x}=\boldsymbol{y}$。

对于$\boldsymbol{L}\boldsymbol{y}=\boldsymbol{d}$，有

$$\begin{pmatrix} \alpha_1 & & & & \\ \gamma_2 & \alpha_2 & & & \\ & \ddots & \ddots & & \\ & & \gamma_{n-1} & \alpha_{n-1} & \\ & & & \gamma_n & \alpha_n \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_{n-1} \\ y_n \end{pmatrix} = \begin{pmatrix} d_1 \\ d_2 \\ \vdots \\ d_{n-1} \\ d_n \end{pmatrix}$$

从而有下述等式

$$\begin{aligned} \begin{cases} \alpha_1 y_1 = d_1 \\ \gamma_i y_{i-1} + \alpha_i y_i = d_i, & i=2,3,...,n \end{cases} \end{aligned}$$

可以依次求出$y_1,y_2,…,y_n$。

对于$\boldsymbol{U}\boldsymbol{x}=\boldsymbol{y}$，有

$$\begin{pmatrix} 1 & \beta_1 & & & \\ & 1 & \beta_2 & & \\ & & \ddots & \ddots & \\ & & & 1 & \beta_{n-1} \\ & & & & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_{n-1} \\ x_n \end{pmatrix} = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_{n-1} \\ y_n \end{pmatrix}$$

从而有下述等式

$$\begin{aligned} \begin{cases} x_i + \beta_i x_{i+1} = y_i, & i=1,2,...,n-1 \\ x_n = y_n \end{cases} \end{aligned}$$

可以依次求出$x_n,x_{n-1},…,x_1$。

这样，就求出了方程组$\boldsymbol{A}\boldsymbol{x}=\boldsymbol{d}$的解。这样的，先依次正向求出$y_1,y_2,…,y_n$（追），再依次逆向求出$x_n,x_{n-1},…,x_1$（赶）的方法称为追赶法。