三对角矩阵算法

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

参考文献
*
*