三對角矩陣算法

三對角矩陣算法（英語：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）.