三对角矩阵算法

三对角矩阵算法（英语：tridiagonal matrix algorithm），又称为托马斯算法（Thomas algorithm，名称源于英国数学家卢埃林·托马斯）是数值线性代数中的一种算法，通过简化形式的高斯消元法求解三对角矩阵。包含n个未知数的三对角方程组可以写成

$a_{i}x_{i-1}+b_{i}x_{i}+c_{i}x_{i+1}=d_{i},\,\!$

其中$a_{1}=0\,$、 $c_{n}=0\,$。写成矩阵形式则为

${\begin{bmatrix}{b_{1}}&{c_{1}}&{}&{}&{0}\\{a_{2}}&{b_{2}}&{c_{2}}&{}&{}\\{}&{a_{3}}&{b_{3}}&\ddots &{}\\{}&{}&\ddots &\ddots &{c_{n-1}}\\{0}&{}&{}&{a_{n}}&{b_{n}}\\\end{bmatrix}}{\begin{bmatrix}{x_{1}}\\{x_{2}}\\{x_{3}}\\\vdots \\{x_{n}}\\\end{bmatrix}}={\begin{bmatrix}{d_{1}}\\{d_{2}}\\{d_{3}}\\\vdots \\{d_{n}}\\\end{bmatrix}}.$

高斯消元法在求解一般线性方程组时需要$O(n^{3})$时间复杂度，但对于三对角系统则只需$O(n)$复杂度。

方法

三对角矩阵算法可分为如下两步进行。第一步求解系数$c_{i}'$和$d_{i}'$：

$c'_{i}={\begin{cases}{\begin{array}{lcl}{\cfrac {c_{i}}{b_{i}}}&;&i=1\\{\cfrac {c_{i}}{b_{i}-a_{i}c'_{i-1}}}&;&i=2,3,\dots ,n-1\\\end{array}}\end{cases}}\,$

以及

$d'_{i}={\begin{cases}{\begin{array}{lcl}{\cfrac {d_{i}}{b_{i}}}&;&i=1\\{\cfrac {d_{i}-a_{i}d'_{i-1}}{b_{i}-a_{i}c'_{i-1}}}&;&i=2,3,\dots ,n.\\\end{array}}\end{cases}}\,$

第二步通过回代得到最终结果：

$x_{n}=d'_{n}\,$

$x_{i}=d'_{i}-c'_{i}x_{i+1}\qquad ;\ i=n-1,n-2,\ldots ,1.$

参考文献

• Conte, S.D., and deBoor, C. Elementary Numerical Analysis. McGraw-Hill, New York. 1972. ISBN 0070124469. 
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP. Section 2.4. Numerical Recipes: The Art of Scientific Computing 3rd. New York: Cambridge University Press. 2007 [2015-02-13]. ISBN 978-0-521-88068-8. （原始内容存档于2016-03-04）.