三对角矩阵算法

三对角矩阵算法（英语：tridiagonal matrix algorithm），又称为托马斯算法（Thomas algorithm，名称源于英国数学家卢埃林·托马斯（英语：Llewellyn Thomas））是数值线性代数中的一种算法，通过简化形式的高斯消元法求解三对角矩阵。包含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）.