„Tridiagonális mátrix” változatai közötti eltérés

numerikus analizis
(numerikus analizis)
 
0 & 0 & 1 & 3 \\
\end{pmatrix}.</math>
:Tridiagonális mátrixok a [[numerikus analízis]] ágában. Matematikai nyelven úgy mondjuk, hogy a<sub>ij</sub> = 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:
:<math>\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}</math>
:Az ilyen típusú egyenletrendszereket legkönnyebb a '''Thomas algoritmus'''sal 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: <math>c_1^\prime={c_1}\frac{c_1}{d_1} \quad;\quad b_1^\prime = \frac{b_1}{d_1}</math>. Ezután, a többi <math>i=\overline{2,n}</math> elemre végrehajtjuk a<math>c_i^\prime=\frac{c_i}{d_i-e_ic_{i-1}^\prime}\quad;\quad b_i^\prime=\frac{b_i-e_ib_{i-1}}{d_i-e_ic_{i-1}}</math> transzformációkat. Ezek eredményeképpen a <math>\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}</math> rendszert kapjuk, melyet hátulról előre haladva könnyen megoldhatunk: <math>x_n=b_n^\prime \quad;\quad x_i=b_i^\prime -x_{i+1}c_i^\prime \quad (i=\overline{n-1,1})</math> .
:Ha figyelembe vesszük, hogy a mátrixban elfoglalt helyek alapján <math>d_i=a_{ii}\quad;\quad e_i=a_{ii-1}</math> és <math>c_i=a_{ii+1}</math>, akkor a fenti módszert a következő algoritmussal valósíthatjuk meg:
:<syntaxhighlight>
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
</syntaxhighlight>'''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:<syntaxhighlight>
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
 
</syntaxhighlight>Megjegyezzük, hogy a '''Thomas-algoritmus''' könnyen általánosítható szélesebb sávos mátrixokra is.
:
 
== Tulajdonságok ==
::<math>\phi_i = a_i \phi_{i+1} - b_i c_i \phi_{i+2} \quad \text{ , } i=n-1,\ldots,1</math>
feltételt ''ϕ''<sub>''n''+1</sub>&nbsp;=&nbsp;1 és ''ϕ''<sub>''n''</sub>&nbsp;=&nbsp;''a''<sub>''n''</sub> kezdőállapottal.<ref>{{cite doi|10.1016/j.cam.2005.08.047}}</ref><ref>{{cite doi|10.1016/0024-3795(94)90414-6}}</ref>
 
== Példák ==
Példaképpen tekintsük a <math>\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}</math> tridiagonális rendszert. A Thomas-algoritmus alkalmazásával átalakíthatjuk ezt egy <math>\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}</math> egyszerűen megoldható rendszerré. A visszahelyettesítések alapján megoldásnak az <math>x=
\begin{pmatrix}
0.1535 \\
-0.2806 \\
0.5558 \\
0.1718 \\
0.2626 \\
\end{pmatrix}</math> értékeket kapjuk.
 
== Források ==
<references />
 
* Lázár Zsolt, Lázár József, Járai-Szabó Ferenc – ''Numerikus módszerek'' ([[Kolozsvári Egyetemi Kiadó]], 2008)
 
[[Kategória:Lineáris algebra]]
[[Kategória:Numerikus analízis]]
1

szerkesztés