Gauss-elimináció

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

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

$a_{11}{x}_1+a_{12}{x}_2+\dots +a_{1n}{x}_n=b_1$

$a_{21}{x}_1+a_{22}{x}_2+\dots +a_{2n}{x}_n=b_2$

$\dots$

$a_{m1}{x}_1+a_{m2}{x}_2+\dots +a_{mn}{x}_n=b_m$

Az eljárás során az egyenletrendszer megoldásait keressük, ahol megoldás alatt olyan $k_1,k_2,\dots ,k_n$ értendő, amely az $x_1,x_2,\dots ,x_n$ ismeretlenek helyére behelyettesítve mind az m egyenletet kielégíti.

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:

$Ax=b$

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

$T_{1}Ax=T_{1}b$

Majd T₂ transzformációnak vetjük alá:

$T_2{T}_{1}Ax=T_2{T}_{1}b$

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

$A^{\prime }x=b^{\prime }$

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:

$(A{Q}_1)(Q_1^{-1}x)=b\dots$

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 = Q₁ · Q₂ · ... Q_m · x' vektorra akarjuk meghatározni. A gyakorlatban a T_i és Q_i 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 n³-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

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

$a_{11}{x}_1+a_{12}{x}_2+\dots +a_{1n}{x}_n=b_1$

$a_{21}{x}_1+a_{22}{x}_2+\dots +a_{2n}{x}_n=b_2$

$\dots$

$a_{m1}{x}_1+a_{m2}{x}_2+\dots +a_{mn}{x}_n=b_m$

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

$a_{11}^{,}{x}_1+a_{12}^{,}{x}_2+\dots +a_{1n}^{,}{x}_n=b_1^{,}$

$0+a_{22}^{,}{x}_2+\dots +a_{2n}^{,}{x}_n=b_2^{,}$

$\dots$

$0+a_{m2}^{,}{x}_2+\dots +a_{mn}^{,}{x}_n=b_m^{,}$

Ezután az $i\ne 2$ egyenletekből vonjuk ki a második egyenlet $\frac{a_{i2}}{a_{22}}$–szeresét. Ekkor a

$a_{11}^{,,}{x}_1+0+\dots +a_{1n}^{,,}{x}_n=b_1^{,,}$

$0+a_{22}^{,,}{x}_2+\dots +a_{2n}^{,,}{x}_n=b_2^{,,}$

$\dots$

$0+0+\dots +a_{mn}^{,,}{x}_n=b_m^{,,}$

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

$a_{11}^{*}{x}_1+0+\dots +a_{1r+1}^{*}{x}_{r+1}+\dots +a_{1n}{x}_n=b_1^{*}$

$0+a_{22}^{*}{x}_2+\dots +a_{2r+1}^{*}{x}_{r+1}+\dots +a_{2n}^{*}{x}_n=b_2^{*}$

$\dots$

$0+0+\dots +a_{rr}^{*}{x}_r+a_{rr+1}^{*}{x}_{r+1}+\dots +a_{rn}^{*}{x}_n=b_r^{*}$

$0=b_{r+1}^{*}$

$\dots$

$0=b_m^{*}$

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

$\left[\begin{array}{cccccccc}{a}_{11}^{*}& 0& \dots & 0& a_{1r+1}^{*}& \dots & a_{1n}^{*}& b_1^{*}\\ 0& a_{22}^{*}& \dots & 0& a_{2r+1}^{*}& \dots & a_{2n}^{*}& b_2^{*}\\ ⋮& & \ddots & & ⋮& & ⋮& ⋮\\ 0& 0& \dots & a_{rr}^{*}& a_{rr+1}^{*}& \dots & a_{rn}^{*}& b_r^{*}\\ 0& ⋮& & & & & 0& b_{r+1}^{*}\\ ⋮& & & & & & ⋮& ⋮\\ 0& \dots & & & & & 0& b_n^{*}\end{array}\right]$

Következmények

Ha a $b_{r+1}^{*}\dots b_m^{*}$ 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

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

$\left(\begin{array}{cccc}{a}_{11}^{(1)}& a_{12}^{(1)}& \cdots & a_{1n}^{(1)}\\ 0& a_{22}^{(2)}& \cdots & a_{2n}^{(2)}\\ ⋮& \cdots & ⋮\\ 0& 0& \cdots & a_{nn}^{(n)}\end{array}\right)\cdot \left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right)=\left(\begin{array}{c}{b}_1^{(1)}\\ b_2^{(2)}\\ \cdot \\ b_n^{(n)}\end{array}\right)$

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 $Gauss$ inout: $(a_{ij}),(b_i)i,j=1..n$ (az A mátrixot és a b vektort „helyben” módosítjuk)

for $k\leftarrow 1$ to $n-1$ do

for $i\leftarrow k+1$ to $n$ do

$l\leftarrow a_{ik}/a_{kk}$

$b_i\leftarrow b_i-l{b}_k$

for $j\leftarrow k$ to $n$ do

$a_{ij}\leftarrow a_{ij}-l{a}_{kj}$

end for

end for

end for

return $(a_{ij}),(b_i)$

end function

Ebben az algoritmusban feltételeztük, hogy az $a_{kk}^{(k)}\ne 0$ 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 $a_{nn}^{(n)}\ne 0$ feltétel, akkor a rendszert egyszerűen megoldhatjuk.

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

Példa

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:

$\left(\begin{array}{ccc}1& 5& -2\\ 2& 3& 1\\ 2& 4& -3\end{array}\right)$ $\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)$ = $\left(\begin{array}{c}2\\ 5\\ 2\end{array}\right)$ (főelem: 1) →

$\left(\begin{array}{ccc}1& 5& -2\\ 0& -7& 5\\ 0& -6& 1\end{array}\right)$ $\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)$ = $\left(\begin{array}{c}2\\ 1\\ -2\end{array}\right)$ (főelem: -7) →

$\left(\begin{array}{ccc}1& 5& -2\\ 0& -7& 5\\ 0& 0& \frac{-23}{7}\end{array}\right)$ $\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)$ = $\left(\begin{array}{c}2\\ 1\\ \frac{-20}{7}\end{array}\right)$

A megoldások: $x_1=\frac{31}{23},x_2=\frac{11}{23},x_3=\frac{20}{23}$

Ritka mátrixok

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.

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; á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

• 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ó