Gauss–Jordan-elimináció

Gauss-elimináció: legyen adott egy n ismeretlenes lineáris egyenletrendszer. Ha minden együttható és minden konstans nulla (azaz a bővített mátrix nullmátrix), akkor mindegyik egyenlet 0=0 alakú, és ezért minden szám-n-es megoldás. Ellenkező esetben az egyenletrendszert elemi átalakításokkal lépcsőssé alakíthatjuk.

Carl Friedrich Gauss és Wilhelm Jordan tiszteletére róluk nevezték el.

Mátrixok redukálása diagonális alakra

Ez egy viszonylag könnyen megérthető módszer. Nagyon hasonlít a Gauss-eliminációra, csak annyi az eltérés, hogy az adott oszlop kinullázása mind a főátló alatti, mind a főátló feletti elemeket érinti. 4x4-es mátrix esetén az A mátrix alakulása a következőképpen történik:

$A={\begin{bmatrix}a11&a12&a13&a14\\a21&a22&a23&a24\\a31&a32&a33&a34\\a41&a42&a43&a44\end{bmatrix}}.$

$A={\begin{bmatrix}a11&a12&a13&a14\\0&a22&a23&a24\\0&a32&a33&a34\\0&a42&a43&a44\end{bmatrix}}.$

$A={\begin{bmatrix}a11&0&a13&a14\\0&a22&a23&a24\\0&0&a33&a34\\0&0&a43&a44\end{bmatrix}}.$

$A={\begin{bmatrix}a11&0&0&a14\\0&a22&0&a24\\0&0&a33&a34\\0&0&0&a44\end{bmatrix}}.$

$A={\begin{bmatrix}a11&0&0&0\\0&a22&0&0\\0&0&a33&0\\0&0&0&a44\end{bmatrix}}.$

nxn-es mátrix esetén az általános transzformációs képlet a k. oszlop nullázásánál

$a_{ij}^{(k+1)}=a_{ij}^{(k)}-a_{ik}^{(k)}/a_{kk}^{(k)}*a_{kj}^{(k)}$

$b_{i}^{(k+1)}=b_{i}^{(k)}-a_{ik}^{(k)}/a_{kk}^{(k)}*b_{k}^{(k)}$

$k=i...n$; $i\neq k$; $j=k...n$

Abban az esetben ha nem csak az egyenletrendszer megoldása a kérdés, hanem az A mátrix inverze is érdekel minket, a módszer hatékonysága nem sokkal marad el a többi általános módszertől. Azonban ha a mátrix inverzére nincs szükségünk, a módszer lassúbb mint, a legjobb alternatív megoldás (Pl. az LU felbontás).

Egy lehetséges algoritmus a Gauss-Jordan kiküszöbölésre

function GaussJordan(inout(a_ij),(b_i) i,j=1...n)

  for k ← 1 to n do
     for i ← 1 to n do
        if (i != k) then
           l←aik / akk
           bi← bi-l*bk
           for j←k to n do
              aij←aij-l*akj
           end for
        end if
     end for
  end for
  return(aij),(bi)

Fontos még megjegyezni, hogy a Gauss-Jordan módszert sosem használjuk a főelem kiválasztás alkalmazása nélkül.

Inverzek megtalálásának módszere

Ha a Gauss-Jordan eliminációt négyzet mátrixhoz alkalmazzuk, akkor használható a mátrix inverzének kiszámításához. Ez megtehető a négyzet mátrixnak ugyanazon dimenziók megegyező mátrixaival való fokozásával, a következő mátrix műveleten keresztül:

$[AI]\Longrightarrow A^{-1}[AI]\Longrightarrow [IA^{-1}].$

Ha az eredeti négyzet mátrix A, $A$, megfelel a következő kifejezésnek:

$A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}.$

Azután az azonosság fokozásával a következő áll fenn:

$[AI]={\begin{bmatrix}2&-1&0&1&0&0\\-1&2&-1&0&1&0\\0&-1&2&0&0&1\end{bmatrix}}.$

Az alapvető számsorú műveletek végrehajtásával a mátrixon [AI] amíg A eléri a csökkentett számsorú lépcsős formát, a következő lesz a végső eredmény:

$[IA^{-1}]={\begin{bmatrix}1&0&0&{\frac {3}{4}}&{\frac {1}{2}}&{\frac {1}{4}}\\0&1&0&{\frac {1}{2}}&1&{\frac {1}{2}}\\0&0&1&{\frac {1}{4}}&{\frac {1}{2}}&{\frac {3}{4}}\end{bmatrix}}.$

A mátrix növelése/fokozása/szaporítása most már megszüntethető, amely a következőt adja:

$I={\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}}\qquad A^{-1}={\begin{bmatrix}{\frac {3}{4}}&{\frac {1}{2}}&{\frac {1}{4}}\\{\frac {1}{2}}&1&{\frac {1}{2}}\\{\frac {1}{4}}&{\frac {1}{2}}&{\frac {3}{4}}\end{bmatrix}}.$

A mátrix nem szinguláris (mely azt jelenti, hogy van inverz mátrixa), ha az azonos mátrix elérhető csak alapvető számsori műveletekkel.

Források

• Lipschutz, Seymour, and Lipson, Mark. "Schaum's Outlines: Linear Algebra". Tata McGraw-hill edition. Delhi 2001. pp. 69–80.
• Strang, Gilbert (2003). Introduction to Linear Algebra, 3rd edition, Wellesley, Massachusetts: Wellesley-Cambridge Press, 74-76.
• Szabó László: Bevezetés a lineáris algebrába; Polygon Kiadó; 2003