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:

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

Tridiagonális mátrixok a numerikus analízis ágában. Matematikai nyelven úgy mondjuk, hogy a_ij = 0 minden olyan (ij) esetén, melyekre teljesül a |i − j| > 1 feltétel. Szemléletesen, adott az alábbi egyenlet. Ilyen mátrixok lépnek fel például a parciális diferenciálegyenletek végeselem diszkretizációjánál:

${\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: $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 $i={\overline {2,n}}$ elemre végrehajtjuk a$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 ${\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: $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 $d_{i}=a_{ii}\quad ;\quad e_{i}=a_{ii-1}$ és $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.

Tulajdonságok

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

Determináns

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

$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:

$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

$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:

$(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:

$\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

$\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.

Példák

Példaképpen tekintsük a ${\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 ${\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 $x={\begin{pmatrix}0.1535\\-0.2806\\0.5558\\0.1718\\0.2626\\\end{pmatrix}}$ értékeket kapjuk.

Források

• Lázár Zsolt, Lázár József, Járai-Szabó Ferenc – Numerikus módszerek (Kolozsvári Egyetemi Kiadó, 2008)