A Gauss-elimináció a lineáris algebra egy lineáris egyenletrendszerek megoldására használatos algoritmusa. Az eljárás Carl Friedrich Gauss nevét viseli, aki maga is leírt a lineáris egyenletrendszerek megoldására szolgáló általános eljárást, azonban ez az eljárás már Gauss előtt is ismert volt.

Az eljárás célja és előnyei

szerkesztés

Legyen adott a következő lineáris egyenletrendszer:

 
 
 
 

Az eljárás során az egyenletrendszer megoldásait keressük, ahol megoldás alatt olyan   értendő, amely az   ismeretlenek helyére behelyettesítve mind az m egyenletet kielégíti.[1]

Az elimináció-, azaz kiküszöbölés-módszer lényege abban áll, hogy rendszerünket visszavezetjük vagy valamely háromszög- vagy átlós mátrixszal reprezentálható alakra. Ezt sorozatos, jobb és bal oldalon egyaránt alkalmazott, lineáris transzformációk segítségével érjük el.
Az egyenletrendszert felfoghatjuk így:

 

Első lépésben a T1 mátrixszal szorozzuk mindkét oldalt:

 

Majd T2 transzformációnak vetjük alá:

 

Az m-edik lépés után az egyenletünk:

 

amely numerikus megoldása közvetlen módon kivitelezhető.
Azt is megtehetjük, hogy az A,b → A',b' transzformáció helyett A,x → A',x' típusú alakítást végzünk:

 

Szemben az előbbi esettel, itt szükséges számontartanunk a végzett transzformációkat, mivel a megoldást nem a végső x', hanem az eredeti x = Q1 · Q2 · ... Qm · x' vektorra akarjuk meghatározni. A gyakorlatban a Ti és Qi gyöktartó transzformációkat egyidejűleg végezzük. Feladatunk ezek azonosítása, illetve egymás utáni alkalmazásuk algoritmizálása.
Célunk az A mátrix bizonyos elemeinek a kinullázása a lehető legkisebb kerekítési hiba mellett. A következő egyszerű műveleteket használjuk:

  • Felcserélve A bármely két sorát és a megfelelő sorokat b-ben , nem módosul az x megoldásvektor. Ez nyilvánvalóvá válik, ha észrevesszük, hogy a művelet az eredeti egyenletrendszer két egyenletének triviális felcserélését jelenti.
  • Hasonlóképpen, ha bármelyik sort A-ban helyettesítjük önmaga és bármely másik sor lineáris kombinációjával, nem módosul a megoldás, ha azonos műveletet végzünk el b vektoron is. Az egyenletrendszer szintjén ez megint csak magától értetődik, tudniillik két egyenlet összeadása nem módosítja a megoldást.
  • Két oszlop cseréje az A-ban a megfelelő együtthatók felcserélését teszik szükségessé az x megoldásvektorban. Az egyes egyenletek szintjén ez az összeadás kommutativitásának kihasználását jelenti.

A mátrix-szorzások n3-bel arányos számítási költségének elkerülése érdekében kihasználjuk azt a tényt, hogy a fenti műveleteknek megfelelő transzformációs mátrixokban csak n elem különbözik nullától. Ezért a sorok és oszlopok módosítását közvetlenül elvégezhetjük n-nel arányos művelettel.

Megengedett módszerek

szerkesztés

A Gauss-elimináció szerint az egyenletrendszereket csak a következő megengedett lépésekkel szabad megoldani:

  • két egyenlet felcserélése,
  • egyenlet számmal szorzása,
  • egyik egyenlethez a másik skalárszorosának hozzáadása.

Az egyenletrendszer rendezése

szerkesztés

 

 

 

 

Ekkor tegyük fel, hogy  . (Ez az állapot az egyenletek sorrendjének felcserélésével elérhető.) Ekkor vonjuk ki az i. egyenletből (ahol  ) az első egyenlet   – szeresét. Az   átló menti elemet, amellyel osztunk, főelemnek nevezzük. A következő egyenletrendszert kapjuk:

 

 

 

 

Ezután az   egyenletekből vonjuk ki a második egyenlet  –szeresét. Ekkor a

 

 

 

 

egyenletrendszert kapjuk. Hasonló módon folytatva az eljárást a következő egyenletrendszerhez jutunk:

 

 

 

 

 

 

 

Így az egyenletrendszer kibővített mátrixából elemi átalakításokkal eljutottunk a következő mátrixhoz:

 

Következmények

szerkesztés

Ha a   mindegyike egyenlő 0-val, akkor az egyenletrendszer megoldható (ekkor az egyenletrendszer mátrixának rangja megegyezik a kibővített mátrixának rangjával).

Ha ezen elemek valamelyike nem 0 akkor az egyenletrendszer nem oldható meg. (ekkor az egyenletrendszer mátrixának rangja kisebb a kibővített mátrixénál.)

Tehát egy egyenletrendszer akkor és csak akkor oldható meg, ha mátrixának rangja egyenlő kibővített mátrixának rangjával.

Ha az egyenletek száma nem pontosan r akkor az egyenletrendszer megoldása nem egyértelmű. Egy lineáris egyenletrendszer akkor és csak akkor oldható meg egyértelműen, ha mátrixának és kibővített mátrixának rangja egyaránt megegyezik az egyenletben szereplő ismeretlenek számával.

Algoritmus

szerkesztés

Miután kinullázzuk a megfelelő elemeket, a rendszerünk ilyen alakú lesz:

 


az (1), (2)... (n) felső indexek az egyes lépéseket jelölik.

A Gauss-módszer algoritmusa a következőképpen képzelhető el:

function   inout:   (az A mátrixot és a b vektort „helyben” módosítjuk)

for   to   do
for   to   do
 
 
for   to   do
 
end for
end for
end for
return  

end function

Ebben az algoritmusban feltételeztük, hogy az   feltétel minden esetben teljesül. Az algoritmus megvalósításánál azonban ezt a tesztelést célszerű a kódba beépíteni.

A kapott rendszer mátrixa egy felső-háromszög mátrix. Amennyiben az utolsó egyenletre is érvényes az   feltétel, akkor a rendszert egyszerűen megoldhatjuk.

A kiküszöbölés vezető rendben   műveletet tesz szükségessé, tehát a visszahelyettesítés   műveletigénye elhanyagolható nagy rendszerek megoldása esetén.

Példaképpen tekintsük át a módszer lépéseit egy konkrét 3 x 3-as mátrixszal leírható egyenletrendszer esetén:

    =   (főelem: 1) →

    =   (főelem: -7) →

    =  

A megoldások:  

Ritka mátrixok

szerkesztés

A ritka mátrixok Gauss-eliminációja során fellépő jelenséget, hogy olyan helyeken keletkezik nemzérus elem, ahol eredetileg nulla állt, feltöltődésnek nevezik. Mivel a ritka mátrixokban a nulla elemeket általában helytakarékosan tárolják, ezért a feltöltődésre ügyelni kell: helyet kell szerezni az újonnan keletkezett elemeknek. Ha külön nem foglalkoznak vele, a feltöltődés nagymértékű is lehet; egy eliminációs lépés alatt akár az egész mátrix feltöltődhet.[2]

A minimális feltöltődés (minimum fill-in) elérése kívánatos cél, a szükséges számítási bonyolultságról még kevés tanulmány született;[3] általában segíthet, ha a problémát okozó sorokat, oszlopokat a Gauss-elimináció végén kezeljük, amit a minimális fokszám algoritmus (az elimináció k-adik lépésében azt a főátlóbeli elemet választjuk főelemnek, amelynek az i index fokszáma minimális) valósít meg.

Hivatkozások

szerkesztés
  • Stoyan Gisbert-Takó Galina: Numerikus módszerek I.
  • Lázár Zsolt, Lázár József, Járai-Szabó Ferenc: Numerikus módszerek
  • A. G. Kuros: Felsőbb algebra, Tankönyvkiadó
  1. Az eljárással meghatározható mátrixok rangja és determinánsa is.
  2. Stoyan Gisbert-Takó Galina: Numerikus módszerek I.
  3. Yixin Cao, R. B. Sandeep: Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds