三对角矩阵算法

Template:NoteTA 三对角矩阵算法（Template:Lang-en），又称为托马斯算法（Template:Lang，名称源于英国数学家Template:Link-en）是数值线性代数中的一种算法，通过简化形式的高斯消元法求解三对角矩阵。包含n个未知数的三对角方程组可以写成

a_{i} x_{i - 1} + b_{i} x_{i} + c_{i} x_{i + 1} = d_{i},

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

[\begin{matrix} b_{1} & c_{1} & 0 \\ a_{2} & b_{2} & c_{2} \\ a_{3} & b_{3} & ⋱ \\ ⋱ & ⋱ & c_{n - 1} \\ 0 & a_{n} & b_{n} \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ ⋮ \\ x_{n} \end{matrix}] = [\begin{matrix} d_{1} \\ d_{2} \\ d_{3} \\ ⋮ \\ d_{n} \end{matrix}] .

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

方法

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

c'_{i} = {\begin{matrix} \begin{matrix} \frac{c_{i}}{b_{i}} & ; & i = 1 \\ \frac{c_{i}}{b_{i} - a_{i} c'_{i - 1}} & ; & i = 2, 3, \dots, n - 1 \end{matrix} \end{matrix}

以及

d'_{i} = {\begin{matrix} \begin{matrix} \frac{d_{i}}{b_{i}} & ; & i = 1 \\ \frac{d_{i} - a_{i} d'_{i - 1}}{b_{i} - a_{i} c'_{i - 1}} & ; & i = 2, 3, \dots, n . \end{matrix} \end{matrix}

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

x_{n} = d'_{n}

x_{i} = d'_{i} - c'_{i} x_{i + 1}; i = n - 1, n - 2, \dots, 1 .