追赶法
专门用于求解对角占优的三对角方程组的直接法，是LU分解在三对角矩阵上的高效应用。
对于三对角线性方程组：
\[
Ax=d
\]
式中：
\[
A = \begin{pmatrix}
b_1 & c_1 & & & 0 \\
a_2 & b_2 & c_2 & & \\
& a_3 & b_3 & c_3 & \\
& & \ddots & \ddots & \ddots \\
& & & a_n & b_n
\end{pmatrix}
\]
并且满足：
\[
\begin{cases}
\left\vert b_1\right\vert > \left\vert c_1 \right\vert > 0 \\
\left\vert b_i \right\vert \geq \left\vert a_i \right\vert + \left\vert c_i \right\vert, \quad i = 2,3,\cdots,n-1 \\
\left\vert b_n \right\vert > \left\vert a_n \right\vert > 0
\end{cases}
\]
且 \(a_i \neq 0\), \(c_i \neq 0\)，则称 \(A\) 为对角占优的三对角线矩阵。\(\rightarrow\) 即满足对角线非零，对角线元素大于等于左右元素。
两种分解方法： - Doolittle分解：\(L\) 的对角线元素为1 - Crout分解：\(U\) 的对角线元素为1
求解步骤（Crout分解）
-
矩阵分解：\(A=LU\),其中： $$ L = \begin{pmatrix} l_1 & & & \ a_2 & l_2 & & \ & a_3 & l_3 & \ & & \ddots & \ddots \ & & & a_n & l_n \end{pmatrix}, \quad U = \begin{pmatrix} 1 & u_1 & & \ & 1 & u_2 & \ & & 1 & \ddots \ & & & \ddots & u_{n-1} \ & & & & 1 \end{pmatrix} $$ 观察发现我们要求的只有两条线。
-
“追”过程（分解与前代）：
- \(l_1\times 1 = b_1\)
- \(u_i = c_i / l_i \quad (i=1,\cdots,n-1)\)
- \(l_{i+1} = b_{i+1} - a_{i+1} u_i\)
- \(y_1 = d_1 / l_1, \quad y_i = (d_i - a_i y_{i-1}) / l_i \quad (i=2,\cdots,n)\)，重复过程
- “赶”过程（回代）：令 \(Ux=y\), 即 \(Ly=d\)，简单的带入求解：
- \(x_n = y_n\)
- \(x_i = y_i - u_i x_{i+1} \quad (i=n-1,\cdots,1)\)