三对角矩阵算法

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

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

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

${\displaystyle {\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}}.}$

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

方法

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

${\displaystyle 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}}\,}$ 

以及

${\displaystyle 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}}\,}$ 

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

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

${\displaystyle 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）.