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:

${\displaystyle a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}=b_{1}}$

${\displaystyle a_{21}x_{1}+a_{22}x_{2}+\dots +a_{2n}x_{n}=b_{2}}$

${\displaystyle \dots }$

${\displaystyle 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 ${\displaystyle k_{1},k_{2},\dots ,k_{n}}$ értendő, amely az ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ 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:

${\displaystyle Ax=b\,}$

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

${\displaystyle T_{1}Ax=T_{1}b\,}$

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

${\displaystyle T_{2}T_{1}Ax=T_{2}T_{1}b\,}$

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

${\displaystyle A'x=b'\,}$

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:

${\displaystyle (AQ_{1})(Q_{1}^{-1}x)=b\ldots \,}$

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

${\displaystyle a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}=b_{1}}$

${\displaystyle a_{21}x_{1}+a_{22}x_{2}+\dots +a_{2n}x_{n}=b_{2}}$

${\displaystyle \dots }$

${\displaystyle a_{m1}x_{1}+a_{m2}x_{2}+\dots +a_{mn}x_{n}=b_{m}}$

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

${\displaystyle a_{11}^{,}x_{1}+a_{12}^{,}x_{2}+\dots +a_{1n}^{,}x_{n}=b_{1}^{,}}$

${\displaystyle 0+a_{22}^{,}x_{2}+\dots +a_{2n}^{,}x_{n}=b_{2}^{,}}$

${\displaystyle \dots }$

${\displaystyle 0+a_{m2}^{,}x_{2}+\dots +a_{mn}^{,}x_{n}=b_{m}^{,}}$

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

${\displaystyle a_{11}^{,,}x_{1}+0+\dots +a_{1n}^{,,}x_{n}=b_{1}^{,,}}$

${\displaystyle 0+a_{22}^{,,}x_{2}+\dots +a_{2n}^{,,}x_{n}=b_{2}^{,,}}$

${\displaystyle \dots }$

${\displaystyle 0+0+\dots +a_{mn}^{,,}x_{n}=b_{m}^{,,}}$

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

${\displaystyle a_{11}^{*}x_{1}+0+\dots +a_{1r+1}^{*}x_{r+1}+\dots +a_{1n}x_{n}=b_{1}^{*}}$

${\displaystyle 0+a_{22}^{*}x_{2}+\dots +a_{2r+1}^{*}x_{r+1}+\dots +a_{2n}^{*}x_{n}=b_{2}^{*}}$

${\displaystyle \dots }$

${\displaystyle 0+0+\dots +a_{rr}^{*}x_{r}+a_{rr+1}^{*}x_{r+1}+\dots +a_{rn}^{*}x_{n}=b_{r}^{*}}$

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

${\displaystyle \dots }$

${\displaystyle 0=b_{m}^{*}}$

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

${\displaystyle {\begin{bmatrix}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}^{*}\\\vdots &&\ddots &&\vdots &&\vdots &\vdots \\0&0&\dots &a_{rr}^{*}&a_{rr+1}^{*}&\dots &a_{rn}^{*}&b_{r}^{*}\\0&\vdots &&&&&0&b_{r+1}^{*}\\\vdots &&&&&&\vdots &\vdots \\0&\dots &&&&&0&b_{n}^{*}\\\end{bmatrix}}}$

Következmények

Ha a ${\displaystyle 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:

${\displaystyle {\begin{pmatrix}a_{11}^{(1)}&a_{12}^{(1)}&\cdots &a_{1n}^{(1)}\\0&a_{22}^{(2)}&\cdots &a_{2n}^{(2)}\\\vdots &\cdots &\vdots \\0&0&\cdots &a_{nn}^{(n)}\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}}={\begin{pmatrix}b_{1}^{(1)}\\b_{2}^{(2)}\\\cdot \\b_{n}^{(n)}\end{pmatrix}}}$

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

for ${\displaystyle k\leftarrow 1}$ to ${\displaystyle n-1}$ do

for ${\displaystyle i\leftarrow k+1}$ to ${\displaystyle n}$ do

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

${\displaystyle b_{i}\leftarrow b_{i}-lb_{k}}$

for ${\displaystyle j\leftarrow k}$ to ${\displaystyle n}$ do

${\displaystyle a_{ij}\leftarrow a_{ij}-la_{kj}}$

end for

end for

end for

return ${\displaystyle (a_{ij}),(b_{i})}$

end function

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

A kiküszöbölés vezető rendben ${\displaystyle 2n^{3}/3}$ műveletet tesz szükségessé, tehát a visszahelyettesítés ${\displaystyle 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:

${\displaystyle {\begin{pmatrix}1&5&-2\\2&3&1\\2&4&-3\end{pmatrix}}}$ ${\displaystyle {\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}}$ = ${\displaystyle {\begin{pmatrix}2\\5\\2\end{pmatrix}}}$ (főelem: 1) →

${\displaystyle {\begin{pmatrix}1&5&-2\\0&-7&5\\0&-6&1\end{pmatrix}}}$ ${\displaystyle {\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}}$ = ${\displaystyle {\begin{pmatrix}2\\1\\-2\end{pmatrix}}}$ (főelem: -7) →

${\displaystyle {\begin{pmatrix}1&5&-2\\0&-7&5\\0&0&{\frac {-23}{7}}\end{pmatrix}}}$ ${\displaystyle {\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}}$ = ${\displaystyle {\begin{pmatrix}2\\1\\{\frac {-20}{7}}\end{pmatrix}}}$

A megoldások: ${\displaystyle 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.^[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

• 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

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