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=\left[\begin{array}{cccc}a11& a12& a13& a14\\ a21& a22& a23& a24\\ a31& a32& a33& a34\\ a41& a42& a43& a44\end{array}\right].$

$A=\left[\begin{array}{cccc}a11& a12& a13& a14\\ 0& a22& a23& a24\\ 0& a32& a33& a34\\ 0& a42& a43& a44\end{array}\right].$

$A=\left[\begin{array}{cccc}a11& 0& a13& a14\\ 0& a22& a23& a24\\ 0& 0& a33& a34\\ 0& 0& a43& a44\end{array}\right].$

$A=\left[\begin{array}{cccc}a11& 0& 0& a14\\ 0& a22& 0& a24\\ 0& 0& a33& a34\\ 0& 0& 0& a44\end{array}\right].$

$A=\left[\begin{array}{cccc}a11& 0& 0& 0\\ 0& a22& 0& 0\\ 0& 0& a33& 0\\ 0& 0& 0& a44\end{array}\right].$

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\ne 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]⟹A^{-1}[AI]⟹[I{A}^{-1}].$

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

$A=\left[\begin{array}{ccc}2& -1& 0\\ -1& 2& -1\\ 0& -1& 2\end{array}\right].$

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

$[AI]=\left[\begin{array}{cccccc}2& -1& 0& 1& 0& 0\\ -1& 2& -1& 0& 1& 0\\ 0& -1& 2& 0& 0& 1\end{array}\right].$

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:

$[I{A}^{-1}]=\left[\begin{array}{cccccc}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{array}\right].$

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

$I=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]A^{-1}=\left[\begin{array}{ccc}\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{array}\right].$

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