In linear algebra, a tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal, the subdiagonal/lower diagonal (the first diagonal below this), and the supradiagonal/upper diagonal (the first diagonal above the main diagonal). For example, the following matrix is tridiagonal:
The determinant of a tridiagonal matrix is given by the continuant of its elements.[1]
An orthogonal transformation of a symmetric (or Hermitian) matrix to tridiagonal form can be done with the Lanczos algorithm.
A tridiagonal matrix is a matrix that is both upper and lower Hessenberg matrix.[2] In particular, a tridiagonal matrix is a direct sum of p 1-by-1 and q 2-by-2 matrices such that p + q/2 = n — the dimension of the tridiagonal. Although a general tridiagonal matrix is not necessarily symmetric or Hermitian, many of those that arise when solving linear algebra problems have one of these properties. Furthermore, if a real tridiagonal matrix A satisfies ak,k+1 ak+1,k > 0 for all k, so that the signs of its entries are symmetric, then it is similar to a Hermitian matrix, by a diagonal change of basis matrix. Hence, its eigenvalues are real. If we replace the strict inequality by ak,k+1 ak+1,k ≥ 0, then by continuity, the eigenvalues are still guaranteed to be real, but the matrix need no longer be similar to a Hermitian matrix.[3]
The set of all n × n tridiagonal matrices forms a 3n-2 dimensional vector space.
Many linear algebra algorithms require significantly less computational effort when applied to diagonal matrices, and this improvement often carries over to tridiagonal matrices as well.
Main article: continuant (mathematics) |
The determinant of a tridiagonal matrix A of order n can be computed from a three-term recurrence relation.[4] Write f1 = |a1| = a1 (i.e., f1 is the determinant of the 1 by 1 matrix consisting only of a1), and let
The sequence (fi) is called the continuant and satisfies the recurrence relation
with initial values f0 = 1 and f−1 = 0. The cost of computing the determinant of a tridiagonal matrix using this formula is linear in n, while the cost is cubic for a general matrix.
The inverse of a non-singular tridiagonal matrix T
is given by
where the θi satisfy the recurrence relation
with initial conditions θ0 = 1, θ1 = a1 and the ϕi satisfy
with initial conditions ϕn+1 = 1 and ϕn = an.[5][6]
Closed form solutions can be computed for special cases such as symmetric matrices with all diagonal and off-diagonal elements equal[7] or Toeplitz matrices[8] and for the general case as well.[9][10]
In general, the inverse of a tridiagonal matrix is a semiseparable matrix and vice versa.[11]
Main article: tridiagonal matrix algorithm |
A system of equations Ax = b for can be solved by an efficient form of Gaussian elimination when A is tridiagonal called tridiagonal matrix algorithm, requiring O(n) operations.[12]
When a tridiagonal matrix is also Toeplitz, there is a simple closed-form solution for its eigenvalues, namely:[13][14]
A real symmetric tridiagonal matrix has real eigenvalues, and all the eigenvalues are distinct (simple) if all off-diagonal elements are nonzero.[15] Numerous methods exist for the numerical computation of the eigenvalues of a real symmetric tridiagonal matrix to arbitrary finite precision, typically requiring operations for a matrix of size , although fast algorithms exist which (without parallel computation) require only .[16]
As a side note, an unreduced symmetric tridiagonal matrix is a matrix containing non-zero off-diagonal elements of the tridiagonal, where the eigenvalues are distinct while the eigenvectors are unique up to a scale factor and are mutually orthogonal.[17]
For unsymmetric or nonsymmetric tridiagonal matrices one can compute the eigendecomposition using a similarity transformation. Given a real tridiagonal, nonsymmetric matrix
where . Assume that each product of off-diagonal entries is strictly positive and define a transformation matrix by
The similarity transformation yields a symmetric tridiagonal matrix by:[18]
Note that and have the same eigenvalues.
A transformation that reduces a general matrix to Hessenberg form will reduce a Hermitian matrix to tridiagonal form. So, many eigenvalue algorithms, when applied to a Hermitian matrix, reduce the input Hermitian matrix to (symmetric real) tridiagonal form as a first step.[19]
A tridiagonal matrix can also be stored more efficiently than a general matrix by using a special storage scheme. For instance, the LAPACK Fortran package stores an unsymmetric tridiagonal matrix of order n in three one-dimensional arrays, one of length n containing the diagonal elements, and two of length n − 1 containing the subdiagonal and superdiagonal elements.
The discretization in space of the one-dimensional diffusion or heat equation
using second order central finite differences results in
with discretization constant . The matrix is tridiagonal with and . Note: no boundary conditions are used here.