Tridiagonal matrix

From Wikipedia, the free encyclopedia
(Redirected from Tridiagonal)

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.

Properties[edit]

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.

Determinant[edit]

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.

Inversion[edit]

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]

Solution of linear system[edit]

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]

Eigenvalues[edit]

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]

Similarity to symmetric tridiagonal matrix[edit]

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.

Computer programming[edit]

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.

Applications[edit]

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.

See also[edit]

Notes[edit]

  1. ^ Thomas Muir (1960). A treatise on the theory of determinants. Dover Publications. pp. 516–525.
  2. ^ Horn, Roger A.; Johnson, Charles R. (1985). Matrix Analysis. Cambridge University Press. p. 28. ISBN 0521386322.
  3. ^ Horn & Johnson, page 174
  4. ^ El-Mikkawy, M. E. A. (2004). "On the inverse of a general tridiagonal matrix". Applied Mathematics and Computation. 150 (3): 669–679. doi:10.1016/S0096-3003(03)00298-4.
  5. ^ Da Fonseca, C. M. (2007). "On the eigenvalues of some tridiagonal matrices". Journal of Computational and Applied Mathematics. 200: 283–286. doi:10.1016/j.cam.2005.08.047.
  6. ^ Usmani, R. A. (1994). "Inversion of a tridiagonal jacobi matrix". Linear Algebra and its Applications. 212–213: 413–414. doi:10.1016/0024-3795(94)90414-6.
  7. ^ Hu, G. Y.; O'Connell, R. F. (1996). "Analytical inversion of symmetric tridiagonal matrices". Journal of Physics A: Mathematical and General. 29 (7): 1511. doi:10.1088/0305-4470/29/7/020.
  8. ^ Huang, Y.; McColl, W. F. (1997). "Analytical inversion of general tridiagonal matrices". Journal of Physics A: Mathematical and General. 30 (22): 7919. doi:10.1088/0305-4470/30/22/026.
  9. ^ Mallik, R. K. (2001). "The inverse of a tridiagonal matrix". Linear Algebra and its Applications. 325: 109–139. doi:10.1016/S0024-3795(00)00262-7.
  10. ^ Kılıç, E. (2008). "Explicit formula for the inverse of a tridiagonal matrix by backward continued fractions". Applied Mathematics and Computation. 197: 345–357. doi:10.1016/j.amc.2007.07.046.
  11. ^ Raf Vandebril; Marc Van Barel; Nicola Mastronardi (2008). Matrix Computations and Semiseparable Matrices. Volume I: Linear Systems. JHU Press. Theorem 1.38, p. 41. ISBN 978-0-8018-8714-7.
  12. ^ Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed.). The Johns Hopkins University Press. ISBN 0-8018-5414-8.
  13. ^ Noschese, S.; Pasquini, L.; Reichel, L. (2013). "Tridiagonal Toeplitz matrices: Properties and novel applications". Numerical Linear Algebra with Applications. 20 (2): 302. doi:10.1002/nla.1811.
  14. ^ This can also be written as because , as is done in: Kulkarni, D.; Schmidt, D.; Tsui, S. K. (1999). "Eigenvalues of tridiagonal pseudo-Toeplitz matrices" (PDF). Linear Algebra and its Applications. 297: 63. doi:10.1016/S0024-3795(99)00114-7.
  15. ^ Parlett, B.N. (1980). The Symmetric Eigenvalue Problem. Prentice Hall, Inc.
  16. ^ Coakley, E.S.; Rokhlin, V. (2012). "A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices". Applied and Computational Harmonic Analysis. 34 (3): 379–414. doi:10.1016/j.acha.2012.06.003.
  17. ^ Dhillon, Inderjit Singh. A New O(n 2 ) Algorithm for the Symmetric Tridiagonal Eigenvalue/Eigenvector Problem (PDF). p. 8.
  18. ^ "www.math.hkbu.edu.hk math lecture" (PDF).
  19. ^ Eidelman, Yuli; Gohberg, Israel; Gemignani, Luca (2007-01-01). "On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms". Linear Algebra and its Applications. 420 (1): 86–101. doi:10.1016/j.laa.2006.06.028. ISSN 0024-3795.

External links[edit]