三对角

在线性代数中，一个三对角矩阵是矩阵的一种，它“几乎”是一个对角矩阵。准确来说：一个三对角矩阵的非零系数在主对角线上，或比主对角线低一行的对角线上，或比主对角线高一行的对角线上。例如，下面的是三对角矩阵：由三对角矩阵得来的行列式，也被称为一个 continuant。三对角矩阵是海森堡矩阵。尽管一般的三对角矩阵不一定是对称或埃尔米特矩阵，许多解线性代数问题时出现的矩阵却往往有这些性质。进一步如果一个实三对角矩阵 A 满足 ak,k+1 ak+1,k > 0，所以它元素的符号都为正，从而相似于一个埃尔米特矩阵，这样特征值都是实数。后一个推论如果我们将条件 ak,k+1 ak+1,k > 0 换为 ak,k+1 ak+1,k ≥ 0，结论仍然成立。所有 n × n 三对角矩阵的集合组成一个 3n-2 维向量空间。许多线性代数算法应用于对角矩阵时所需计算量特别少，这种改进也经常被三对角矩阵继承。譬如，一个 n 阶三对角矩阵 A 的行列式能用 continuant（Continuant）的递归公式计算：这里 det [ A ] { 1 , … , k } {displaystyle det_{{1,ldots ,k}}} 是第 k 个主子式，即 [ A ] { 1 , … , k } {displaystyle _{{1,ldots ,k}}} 是由 A 最开始的 k 行 k 列组成的子矩阵。用此方法计算三对角矩阵所需计算量是线性 n ，然而对于一般的矩阵复杂度是 n 的 3 次方。一个将一般矩阵变成海森堡型的变换，将厄密特矩阵变成三对角矩阵。从而，许多特征值算法运用到厄密特矩阵上，第一步将输入的厄密特矩阵变成三对角矩阵。一个三对角矩阵利用特定的存储方案比一般矩阵所用的存储空间也少得多。例如，LAPACK Fortran包将一个 n-维非对称三对角矩阵存为三个 1-维数列，其中一个长 n 包含对角元素，其它两个长为 n− 1 包含下对角线和上对角线元素。三对角矩阵方程 A x = b , b ∈ R n {displaystyle Ax=b,,bin mathbb {R} ^{n}} ，能用一种需要 O(n)次操作的特殊的算法解出来（Golub and Van Loan）。