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:

$\left(\begin{array}{cccc}1& 4& 0& 0\\ 3& 4& 1& 0\\ 0& 2& 3& 4\\ 0& 0& 1& 3\\ \end{array}\right).$

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

$f_n=\left|\begin{array}{cc}{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{array}\right|$

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=\left(\begin{array}{cc}{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{array}\right)$

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

$(T^{-1}{)}_{ij}=\{\begin{array}{ll}(-1{)}^{i+j}{b}_i\cdots b_{j-1}{\theta }_{i-1}{\varphi }_{j+1}/{\theta }_n& \text{ ha }i\le j\\ (-1{)}^{i+j}{c}_j\cdots c_{i-1}{\theta }_{j-1}{\varphi }_{i+1}/{\theta }_n& \text{ ha }i>j\\ \end{array}$

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}\text{ , }i=2,3,\dots ,n$

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

${\varphi }_i=a_i{\varphi }_{i+1}-b_i{c}_i{\varphi }_{i+2}\text{ , }i=n-1,\dots ,1$

feltételt ϕ_n+1 = 1 és ϕ_n = a_n kezdőállapottal.

Numerikus megoldás

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

$\left(\begin{array}{cccccccc}{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{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ ...\\ x_{n-1}\\ x_n\end{array}\right)=\left(\begin{array}{c}{b}_1\\ b_2\\ b_3\\ ...\\ b_{n-1}\\ b_n\end{array}\right)$

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};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 }};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

$\left(\begin{array}{cccccccc}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{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ ...\\ x_{n-1}\\ x_n\end{array}\right)=\left(\begin{array}{c}{b}_1^{\prime }\\ b_2^{\prime }\\ b_3^{\prime }\\ ...\\ b_{n-1}^{\prime }\\ b_n^{\prime }\end{array}\right)$

rendszert kapjuk, melyet hátulról előre haladva könnyen megoldhatunk: $x_n=b_n^{\prime };x_i=b_i^{\prime }-x_{i+1}{c}_i^{\prime }(i=\overline{n-1,1})$ . Ha figyelembe vesszük, hogy a mátrixban elfoglalt helyek alapján $d_i=a_{ii};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.

Példa

Példaképpen tekintsük a

$\left(\begin{array}{ccccc}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{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\\ \end{array}\right)=\left(\begin{array}{c}1\\ 1\\ 2\\ 3\\ 2\\ \end{array}\right)$

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

$\left(\begin{array}{ccccc}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{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\\ \end{array}\right)=\left(\begin{array}{c}0.0833\\ 0.1429\\ 0.7317\\ 2.325\\ 0.2625\\ \end{array}\right)$

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

$x=\left(\begin{array}{c}0.1535\\ -0.2806\\ 0.5558\\ 0.1718\\ 0.2626\\ \end{array}\right)$

é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ó, Kolozsvár, 2008) ISBN 978 973 610 763 4