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.