Tridiagonal matrix: Difference between revisions

Revision as of 06:08, 29 August 2024

Latest revision as of 01:19, 26 May 2025

(2 intermediate revisions by 2 users not shown)

Line 21:

===Determinant===

{{Main|continuantContinuant (mathematics)}}

The [[determinant]] of a tridiagonal matrix ''A'' of order ''n'' can be computed from a three-term [[recurrence relation]].<ref>{{Cite journal | last1 = El-Mikkawy | first1 = M. E. A. | title = On the inverse of a general tridiagonal matrix | doi = 10.1016/S0096-3003(03)00298-4 | journal = Applied Mathematics and Computation | volume = 150 | issue = 3 | pages = 669–679 | year = 2004 }}</ref> Write ''f''₁&nbsp;=&nbsp;|''a''₁|&nbsp;=&nbsp;''a''₁ (i.e., ''f''₁ is the determinant of the 1 by 1 matrix consisting only of ''a''₁), and let

Line 70:

:<math>\phi_i = a_i \phi_{i+1} - b_i c_i \phi_{i+2} \qquad i=n-1,\ldots,1</math>

with initial conditions ''ϕ''_''n''+1&nbsp;=&nbsp;1 and ''ϕ''_''n''&nbsp;=&nbsp;''a_n''.<ref>{{Cite journal | last1 = Da Fonseca | first1 = C. M. | doi = 10.1016/j.cam.2005.08.047 | title = On the eigenvalues of some tridiagonal matrices | journal = Journal of Computational and Applied Mathematics | volume = 200 | pages = 283–286 | year = 2007 | doi-access = free }}</ref><ref>{{Cite journal | last1 = Usmani | first1 = R. A. | doi = 10.1016/0024-3795(94)90414-6 | title = Inversion of a tridiagonal jacobi matrix | journal = Linear Algebra and itsIts Applications | volume = 212-213 | pages = 413–414 | year = 1994 | doi-access = free }}</ref>

Closed form solutions can be computed for special cases such as [[symmetric matrix|symmetric matrices]] with all diagonal and off-diagonal elements equal<ref>{{Cite journal | last1 = Hu | first1 = G. Y. | last2 = O'Connell | first2 = R. F. | doi = 10.1088/0305-4470/29/7/020 | title = Analytical inversion of symmetric tridiagonal matrices | journal = Journal of Physics A: Mathematical and General | volume = 29 | issue = 7 | pages = 1511 | year = 1996 | bibcode = 1996JPhA...29.1511H }}</ref> or [[Toeplitz matrices]]<ref>{{Cite journal | last1 = Huang | first1 = Y. | last2 = McColl | first2 = W. F. | doi = 10.1088/0305-4470/30/22/026 | title = Analytical inversion of general tridiagonal matrices | journal = Journal of Physics A: Mathematical and General | volume = 30 | issue = 22 | pages = 7919 | year = 1997 | bibcode = 1997JPhA...30.7919H }}</ref> and for the general case as well.<ref>{{Cite journal | last1 = Mallik | first1 = R. K. | doi = 10.1016/S0024-3795(00)00262-7 | title = The inverse of a tridiagonal matrix | journal = Linear Algebra and itsIts Applications | volume = 325 | pages = 109–139 | year = 2001 | issue = 1–3 | doi-access = free }}</ref><ref>{{Cite journal | last1 = Kılıç | first1 = E. | doi = 10.1016/j.amc.2007.07.046 | title = Explicit formula for the inverse of a tridiagonal matrix by backward continued fractions | journal = Applied Mathematics and Computation | volume = 197 | pages = 345–357 | year = 2008 }}</ref>

In general, the inverse of a tridiagonal matrix is a [[semiseparable matrix]] and vice versa.<ref name="VandebrilBarel2008">{{cite book|author1=Raf Vandebril|author2=Marc Van Barel|author3=Nicola Mastronardi|title=Matrix Computations and Semiseparable Matrices. Volume I: Linear Systems|year=2008|publisher=JHU Press|isbn=978-0-8018-8714-7|at=Theorem 1.38, p. 41}}</ref> The inverse of a symmetric tridiagonal matrix can be written as a [[single-pair matrix]] (a.k.a. ''generator-representable semiseparable matrix'') of the form<ref name="Meurant1992">{{cite journal |last1=Meurant |first1=Gerard |title=A review on the inverse of symmetric tridiagonal and block tridiagonal matrices |journal=SIAM Journal on Matrix Analysis and Applications |date=1992 |volume=13 |issue=3 |pages=707-728707–728 |doi=10.1137/0613045 |url=https://doi.org/10.1137/0613045|url-access=subscription }}</ref><ref>{{cite journal |last1=Bossu |first1=Sebastien |title=Tridiagonal and single-pair matrices and the inverse sum of two single-pair matrices |journal=Linear Algebra and itsIts Applications |date=2024 |volume=699 |pages=129-158129–158 |doi=10.1016/j.laa.2024.06.018 |url=https://authors.elsevier.com/a/1jOTP5YnCtZEc|arxiv=2304.06100 }}</ref>

<math>\begin{pmatrix}

Line 109:

===Eigenvalues===

When a tridiagonal matrix is also [[Toeplitz matrix|Toeplitz]], there is a simple closed-form solution for its eigenvalues, namely:<ref>{{Cite journal | doi = 10.1002/nla.1811| title = Tridiagonal Toeplitz matrices: Properties and novel applications| journal = Numerical Linear Algebra with Applications| volume = 20| issue = 2| pages = 302| year = 2013| last1 = Noschese | first1 = S. | last2 = Pasquini | first2 = L. | last3 = Reichel | first3 = L. }}</ref><ref>This can also be written as <math> a + 2 \sqrt{bc} \cos(k \pi / {(n+1)}) </math> because <math> \cos(x) = -\cos(\pi-x) </math>, as is done in: {{Cite journal | last1 = Kulkarni | first1 = D. | last2 = Schmidt | first2 = D. | last3 = Tsui | first3 = S. K. | title = Eigenvalues of tridiagonal pseudo-Toeplitz matrices | doi = 10.1016/S0024-3795(99)00114-7 | journal = Linear Algebra and itsIts Applications | volume = 297 | pages = 6363–80 | year = 1999 | issue = 1–3 | url = https://hal.archives-ouvertes.fr/hal-01461924/file/KST.pdf }}</ref>

:<math> a - 2 \sqrt{bc} \cos \left (\frac{k\pi}{n+1} \right ), \qquad k=1, \ldots, n. </math>

Line 130:

</math>

where <math>b_i \neq c_i </math>.

Assume that each product of off-diagonal entries is {{em|strictly}} positive <math>b_i c_i > 0 </math> and define a transformation matrix <math>D</math> by<ref name=kreer_operator>{{Cite journal | last1 = Kreer | first1 = M. | title = Analytic birth-death processes: a Hilbert space approach | doi = 10.1016/0304-4149(94)90112-0 | journal = Stochastic Processes and theirTheir Applications | volume = 49 | issue = 1 | pages = 65–74 | year = 1994 }}</ref>

:<math>

D := \operatorname{diag}(\delta_1 , \dots, \delta_n)

Line 156:

==Computer programming==

A transformation that reduces a general matrix to Hessenberg form will reduce a Hermitian matrix to tridiagonal form. So, many [[eigenvalue algorithm]]s, when applied to a Hermitian matrix, reduce the input Hermitian matrix to (symmetric real) tridiagonal form as a first step.<ref>{{Cite journal |lastlast1=Eidelman |firstfirst1=Yuli |last2=Gohberg |first2=Israel |last3=Gemignani |first3=Luca |date=2007-01-01 |title=On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms |url=https://www.sciencedirect.com/science/article/pii/S0024379506003041 |journal=Linear Algebra and itsIts Applications |language=en |volume=420 |issue=1 |pages=86–101 |doi=10.1016/j.laa.2006.06.028 |issn=0024-3795|doi-access=free }}</ref>

A tridiagonal matrix can also be stored more efficiently than a general matrix by using a special [[matrix representation|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'' &minus; 1 containing the [[subdiagonal]] and [[superdiagonal]] elements.

Line 197:

==External links==

* [http://www.netlib.org/lapack/lug/node125.html Tridiagonal and Bidiagonal Matrices] in the LAPACK manual.

* {{cite journal |author=Moawwad El-Mikkawy, Abdelrahman Karawia |title=Inversion of general tridiagonal matrices |journal=Applied Mathematics Letters |volume=19 |issue=8 |year=2006 |pages=712–720 |doi=10.1016/j.aml.2005.11.012 |url=http://app2.mans.edu.eg/eulc/Libraries/itemsAttach/IssueArticle/1037592/papermik.pdf |url-status=dead |archive-url=https://web.archive.org/web/20110720131242/http://app2.mans.edu.eg/eulc/Libraries/itemsAttach/IssueArticle/1037592/papermik.pdf |archive-date=2011-07-20 |doi-access=free }}

* [http://www.cs.utexas.edu/users/flame/pubs/flawn53.pdf High performance algorithms] for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form

* [https://web.archive.org/web/20140310122757/http://michal.is/projects/tridiagonal-system-solver-sor-c/ Tridiagonal linear system solver] in C++