线性方程组与本征值问题(03)：三对角矩阵

所谓 三对角矩阵, 是指形如 \[ \mathbf{A}=\begin{pmatrix} a_1 & c_1 \\ b_2 & a_2 & c_2 \\ & \ddots & \ddots & \ddots \\ & & b_{n-1} & a_{n-1} & c_{n-1} \\ & & & b_n & a_n \end{pmatrix} \] 的矩阵\(\mathbf{A}\). 它同样可以进行 LU 分解, 但分解后的矩阵比较特殊: $$ \[\begin{aligned} \mathbf{L}&=\begin{pmatrix} 1 & \\ \beta_2 & 1 \\ & \ddots & \ddots \\ & & \beta_n & 1 \end{pmatrix} \\ \mathbf{U}&=\begin{pmatrix} \alpha_1 & c_1 \\ & \ddots & \ddots \\ & & \alpha_{n-1} & c_{n-1} \\ & & & \alpha_n \end{pmatrix} \end{aligned}\]

$$

它可以简便地写作矩阵元形式

\[ l_{jj}=1,\ l_{j,j-1}=\beta_j,\ u_{jj}=\alpha_j,\ u_{j,j+1}=c_j \]

根据矩阵元形式计算

\[ a_{jk}=\sum_{m=1}^nl_{jm}u_{mk}=(\alpha_j+\beta_jc_{j-1})\delta_{jk}+c_j\delta_{j,k-1}+\alpha_{j-1}\beta_j\delta_{j, k + 1} \]

与矩阵\(\mathbf{A}\)进行比对, 就可得到

\[ \begin{align} \alpha_1 &= a_1 \\ \beta_j&=\frac{b_j}{\alpha_{j-1}} \\ \alpha_j&=a_j-\beta_jc_{j-1} \\(j&=2,3,\cdots,n) \end{align} \]

这就是三对角矩阵的 Thomas 算法. 它的计算量约为\(8n-7\), 分解本身为\(3n-3\), 如果还需解线性方程组, 还要多\(5n-4\).