查看“︁三对角矩阵算法”︁的源代码

{{NoteTA
|G1 = Math
}}
'''三对角矩阵算法'''（{{lang-en|tridiagonal matrix algorithm}}），又称为'''托马斯算法'''（{{lang|en|Thomas algorithm}}，名称源于英国数学家{{link-en|卢埃林·托马斯|Llewellyn Thomas}}）是[[数值线性代数]]中的一种算法，通过简化形式的[[高斯消元法]]求解[[三对角矩阵|三对角矩阵]]。包含''n''个未知数的三对角方程组可以写成
:<math>
a_i x_{i - 1}  + b_i x_i  + c_i x_{i + 1}  = d_i , \,\!</math>
其中<math> a_1  = 0\, </math>、 <math> c_n = 0\, </math>。写成矩阵形式则为

:<math>
\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}
.
</math>

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

== 方法 ==
三对角矩阵算法可分为如下两步进行。第一步求解系数<math>c_i'</math>和<math>d_i'</math>：
:<math>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}
\,</math>
以及
:<math>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}
\,</math>

第二步通过回代得到最终结果：
:<math>x_n = d'_n\,</math>

:<math>x_i = d'_i - c'_i x_{i + 1} \qquad ; \ i = n - 1, n - 2, \ldots, 1.</math>

== 参考文献 ==
*{{cite book|author=Conte, S.D., and deBoor, C.|year=1972|title=Elementary Numerical Analysis|publisher= McGraw-Hill, New York|isbn= 0070124469}}
*{{Cite book|last1=Press|first1=WH|last2=Teukolsky|first2=SA|last3=Vetterling|first3=WT|last4=Flannery|first4=BP|year=2007|title=Numerical Recipes: The Art of Scientific Computing|edition=3rd|publisher=Cambridge University Press|publication-place=New York|isbn=978-0-521-88068-8|chapter=Section 2.4|chapter-url=http://apps.nrbook.com/empanel/index.html?pg=56|access-date=2015-02-13|archive-date=2016-03-04|archive-url=https://web.archive.org/web/20160304052339/http://apps.nrbook.com/empanel/index.html?pg=56|dead-url=no}}

[[Category:数值线性代数]]