Tridiagonális mátrix

A matematika lineáris algebra nevű ágában tridiagonális mátrix (esetleg kontinuánsmátrix) a neve az olyan négyzetes mátrixnak, amelyben csak a főátlón és a mellette található két átló mentén vannak nullától különböző elemek.

Például a következő mátrix tridiagonális:

${\displaystyle {\begin{pmatrix}1&4&0&0\\3&4&1&0\\0&2&3&4\\0&0&1&3\\\end{pmatrix}}.}$

Matematikai nyelven úgy mondjuk, hogy a_ij = 0 minden olyan (i, j) esetén, melyekre teljesül az |i − j| > 1 feltétel.

A tridiagonális mátrix voltaképpen egy felső és alsó Hessenberg-mátrix.[1]

Ilyen mátrixok lépnek fel például a parciális differenciálegyenletek végeselem diszkretizációjánál.

Tulajdonságok

Determináns

Egy n-dimenziós tridiagonális T mátrix determinánsát

${\displaystyle f_{n}={\begin{vmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{vmatrix}}}$

a következő rekurzív képlet segítségével lehet kiszámítani:

${\displaystyle f_{n}=a_{n}f_{n-1}-c_{n-1}b_{n-1}f_{n-2}}$

ahol f₀ = 1 és f_-1 = 0.

Inverz

Egy adott T nem szinguláris tridiagonális mátrix

${\displaystyle T={\begin{pmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{pmatrix}}}$

inverzét a következőképpen lehet kiszámolni:

${\displaystyle (T^{-1})_{ij}={\begin{cases}(-1)^{i+j}b_{i}\cdots b_{j-1}\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ ha }}i\leq j\\(-1)^{i+j}c_{j}\cdots c_{i-1}\theta _{j-1}\phi _{i+1}/\theta _{n}&{\text{ ha }}i>j\\\end{cases}}}$

ahol θ_i teljesíti az alábbi rekurzív feltételt:

${\displaystyle \theta _{i}=a_{i}\theta _{i-1}-b_{i-1}c_{i-1}\theta _{i-2}\quad {\text{ , }}i=2,3,\ldots ,n}$

θ₀ = 1, θ₁ = a₁ kezdőállapottal. ϕ_i pedig teljesíti a

${\displaystyle \phi _{i}=a_{i}\phi _{i+1}-b_{i}c_{i}\phi _{i+2}\quad {\text{ , }}i=n-1,\ldots ,1}$

feltételt ϕ_n+1 = 1 és ϕ_n = a_n kezdőállapottal.[2][3]

Numerikus megoldás

Szemléletesen, legyen adott az alábbi egyenlet.

${\displaystyle {\begin{pmatrix}d_{1}&c_{1}&0&0&...&0&0&0\\e_{1}&d_{2}&c_{2}&0&...&0&0&0\\0&e_{2}&d_{3}&c_{3}&...&0&0&0\\...&...&...&...&...&...&...&...\\...&...&...&...&...&...&...&...\\0&0&0&0&...&e_{n-2}&d_{n-1}&c_{n-1}\\0&0&0&0&...&0&e_{n-1}&d_{n}\\\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\...\\x_{n-1}\\x_{n}\end{pmatrix}}={\begin{pmatrix}b_{1}\\b_{2}\\b_{3}\\...\\b_{n-1}\\b_{n}\end{pmatrix}}}$

Az ilyen típusú egyenletrendszereket legkönnyebb a Thomas-algoritmussal megoldani, ami tulajdonképpen a Gauss-kiküszöbölés tridiagonális mátrixra egyszerűsített változata. Először sorrendben eltüntetjük az átló alatti elemeket, és az átlón levő elemeket egységnyire normalizáljuk. Első lépésben: ${\displaystyle c_{1}^{\prime }={c_{1}}{\frac {c_{1}}{d_{1}}}\quad ;\quad b_{1}^{\prime }={\frac {b_{1}}{d_{1}}}}$. Ezután, a többi ${\displaystyle i={\overline {2,n}}}$ elemre végrehajtjuk a${\displaystyle c_{i}^{\prime }={\frac {c_{i}}{d_{i}-e_{i}c_{i-1}^{\prime }}}\quad ;\quad b_{i}^{\prime }={\frac {b_{i}-e_{i}b_{i-1}}{d_{i}-e_{i}c_{i-1}}}}$ transzformációkat. Ezek eredményeképpen a

${\displaystyle {\begin{pmatrix}1&c_{1}^{\prime }&0&0&...&0&0&\\0&1&c_{2}^{\prime }&0&...&0&0&\\0&0&1&c_{3}^{\prime }&...&0&0&\\...&...&...&...&...&...&...\\...&...&...&...&...&...&...\\0&0&0&0&...&1&c_{n-1}^{\prime }\\0&0&0&0&...&0&1\\\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\...\\x_{n-1}\\x_{n}\end{pmatrix}}={\begin{pmatrix}b_{1}^{\prime }\\b_{2}^{\prime }\\b_{3}^{\prime }\\...\\b_{n-1}^{\prime }\\b_{n}^{\prime }\end{pmatrix}}}$

rendszert kapjuk, melyet hátulról előre haladva könnyen megoldhatunk: ${\displaystyle x_{n}=b_{n}^{\prime }\quad ;\quad x_{i}=b_{i}^{\prime }-x_{i+1}c_{i}^{\prime }\quad (i={\overline {n-1,1}})}$ .

Ha figyelembe vesszük, hogy a mátrixban elfoglalt helyek alapján ${\displaystyle d_{i}=a_{ii}\quad ;\quad e_{i}=a_{ii-1}}$ és ${\displaystyle c_{i}=a_{ii+1}}$, akkor a fenti módszert a következő algoritmussal valósíthatjuk meg:

 1: function Thomas( in: (aij ),(bi) out: (xi) i, j = 1, n )
 2:   a12 ← a12/a11
 3:   b1 ← b1/a11
 4:   for i ← 2 to n − 1 do
 5:      aii+1 ← aii+1 / (aii − aii−1 ai-1i)
 6:      bi ← (bi − aii−1 bi−1)/(aii − aii−1 ai−1i)
 7:      aii−1 ← 0
 8:   end for
 9:   bn ← (bn − ann−1 bn−1)/(ann − ann−1 an−1n)
10:   xn ← bn
11:   for i ← n − 1 to 1 do
12:       xi = bi − xi+1 aii+1
13:   end for
14:   return (xi)
15: end function

Memóriakihasználás szempontjából természetesen célszerűbb, ha nem az egész mátrixot, hanem csak a nemnulla c, d és e elemeket tároljuk. Ebben az esetben az algoritmus a következőképpen alakul:

 1: function THOMAS2( in: (ci),(di),(ei),(bi) out: (xi) i, j = 1, n )
 2:   c1 ← c1/d1
 3:   b1 ← b1/d1
 4:   for i ← 2 to n do
 5:     ci ← ci/(di − ei ci−1)
 6:     bi ← (bi − ei bi−1)/(di − ei ci−1)
 7:   end for
 8:   xn ← bn
 9:   for i ← n − 1 to 1 do
10:     xi = bi − xi+1 ci
11:   end for
12:   return (xi)
13: end function

Megjegyezzük, hogy a Thomas-algoritmus könnyen általánosítható szélesebb sávos mátrixokra is.

Példa

Példaképpen tekintsük a

${\displaystyle {\begin{pmatrix}12&3&0&0&0\\3&6&4&0&0\\0&4&5&2&0\\0&0&1&2&8\\0&0&0&4&5\\\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\\\end{pmatrix}}={\begin{pmatrix}1\\1\\2\\3\\2\\\end{pmatrix}}}$

tridiagonális rendszert. A Thomas-algoritmus alkalmazásával átalakíthatjuk ezt egy

${\displaystyle {\begin{pmatrix}1&0.25&0&0&0\\0&1&0.7619&0&0\\0&0&1&1.0244&0\\0&0&0&1&8.2\\0&0&0&0&1\\\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\\\end{pmatrix}}={\begin{pmatrix}0.0833\\0.1429\\0.7317\\2.325\\0.2625\\\end{pmatrix}}}$

egyszerűen megoldható rendszerré. A visszahelyettesítések alapján megoldásnak az

${\displaystyle x={\begin{pmatrix}0.1535\\-0.2806\\0.5558\\0.1718\\0.2626\\\end{pmatrix}}}$

értékeket kapjuk.

Jegyzetek

1. Matrix Analysis. Cambridge University Press, 28. o. (1985). ISBN 0521386322 
2. da Fonseca, C.M. (2007. március 1.). „On the eigenvalues of some tridiagonal matrices” (angol nyelven). Journal of Computational and Applied Mathematics 200 (1), 283–286. o. DOI:10.1016/j.cam.2005.08.047. 
3. Usmani, Riaz A. (1994. november 1.). „Inversion of a tridiagonal jacobi matrix” (angol nyelven). Linear Algebra and its Applications 212-213, 413–414. o. DOI:10.1016/0024-3795(94)90414-6. 

Források

• Lázár Zsolt – Lázár József – Járai-Szabó Ferenc: Numerikus módszerek (Kolozsvári Egyetemi Kiadó, Kolozsvár, 2008) ISBN 978 973 610 763 4