Gauss-elimináció

A Wikipédiából, a szabad enciklopédiából

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-dik 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 megintcsak magától érthető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élda[szerkesztés]

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:

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ó

Jegyzetek[szerkesztés]

  1. Az eljárással meghatározható mátrixok rangja és determinánsa is.