9.3.2 Lineáris egyenletrendszerek numerikus megoldása

Ebben az alfejezetben nem adunk meg formulákat a megoldásokra, hanem jól használható eljárásokat ismertetünk. Az első eljárás célja, hogy ekvivalens átalakításokkal az egyenletrendszer mátrixából úgynevezett felső háromszög mátrixot kapjunk, mely segítségével az egyenletrendszer megoldása könnyedén, egyszerű behelyettesítésekkel megadható. Az eljárás Gauss elimináció néven vált ismertté.

Megjegyzés.

Tetszőleges

alakú lineáris egyenletrendszer, ahol ekvivalens a következő lineáris egyenletrendszerrel:

, ahol

A megjegyzésből következik, hogy a Gauss elimináció során elegendő olyan lineáris egyenletrendszerekkel foglalkozni, melyek mátrixa négyzetes.

Tekintsük a kiinduló egyenletrendszert, és lássuk el a következő jelöléssel:

,

majd hajtsuk végre a következő algoritmust, azaz minden 1 és n-1 közé eső i-re végezzük el a következőket:

Jelöljük -gyel az  egyenletrendszer j. sorát az i. lépésben.

Tegyük fel, hogy

Legyen minden -re, és minden -re.

Megjegyzés.

Az i. lépés előtt az egyenletrendszer a következő alakú:

 

,

 

azaz, az i. lépésben az i sorindexű egyenlet alatti egyenletek i. együtthatóját kell kinullázni. Ezt úgy érjük el, hogy az i. egyenlet megfelelő skalárszorosát kivonjuk minden i-nél nagyobb sorindexű egyenletből, így az változó együtthatója zérus lesz minden olyan egyenletben, melynek a sorindexe nagyobb mint i.

A megfelelő átalakítások elvégzése után a következő formájú egyenletrendszert kapjuk:

 

.

 

Az egyenletrendszer megoldását a következő képletbe történő egyszerű behelyettesítéssel kapjuk:

Feladat.

Oldjuk meg a következő egyenletrendszert Gauss eliminációval.

Első lépés:

Második lépés:

A megoldás behelyettesítéssel:

Vizsgáljuk meg a Gauss eliminációt! Jól látható, hogy csak az együtthatókat érintik a változások. Adódik a kérdés, hogy adható-e olyan változata a Gauss eliminációnak, melyben a számításokat csak az együtthatók és szabad tagok mátrixaival végezzük. Tekintsük az egyenletrendszer mátrixos alakját:

, ahol

, és

Ahogyan az előzőekben láttuk, az elimináció-, azaz kiküszöbölés-módszer lényege abban áll, hogy rendszerünket visszavezetjük 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. Ezt úgy is elérhetjük, hogy az egyenletrendszer mindkét oldalát reprezentáló mátrixokat megszorozzuk úgynevezett eliminációs mátrixokkal.

Eliminációs mátrixok

Az Mk eliminációs mátrix olyan négyzetes mátrix, amellyel balról beszorozva egy a vektort, a vektor k -adik eleme alatti elemek kinullázódnak, azaz

Az eliminációs mátrixokat a következő módon konstruáljuk meg:

az egységmátrix k-adik oszlopa. Az ak elemet szokás generáló elemnek nevezni.

Tekintsük az előző feladatot, azaz

Jelölje az A mátrix első oszlopát a1.

Az eliminációs mátrix konstrukciójából adódik, hogy az egységmátrixból valamint a generáló elem és kinullázandó elemek segítségével elő tudunk állítani egy alkalmas M1 mátrixot. Az M1 mátrixot úgy konstruáljuk meg, hogy az egységmátrix első oszlopában a kinullázandó elemeknek megfelelő helyre a hányadost írjuk, azaz:

Ekkor:

, valamint

Hasonlóan megkonstruálható M2:

Ekkor

Azaz az eredeti egyenletrendszer megoldása:

Ahonnan az egyenletrendszer megoldása egyszerű behelyettesítéssel - ahogyan azt az előzőekben megismertük - megadható.

Megjegyzés.

További eliminációs eljárások adhatók, mint például a Gauss-Jordan elimináció, melyek gyakorlatban például a Mátrixok inverzének meghatározásánál használhatók.