Gauss-elimináció

Az eljárás célja és előnyei

Az eljárás során lineáris egyenletrendszerek megoldásait keressük. Az eljárással meghatározható mátrixok rangja és determinánsa is.
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-dik lépés után az egyenletünk:

$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:

$(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 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 n³-el 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-el arányos művelettel.

Megengedett módszerek

A Gauss-elimináció szerint az egyenletrendszereket csak a következő megengedett lépésekkel szabad megoldani, ezek: 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}\neq 0$ . (Ez az állapot az egyenletek sorrendjének felcserélésével elérhető.) Ekkor vonjuk ki az i. egyenletből ( ahol $i\geq 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!=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:

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

${\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 $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}-lb_{k}$

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

$a_{ij}\leftarrow a_{ij}-la_{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)}\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 $a_{nn}^{(n)}\neq 0$ feltétel, akkor a rendszert egyszerűen megoldhatjuk.

A kiküszöbölés vezető rendben $n^{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:

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

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

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

A megoldások: $x_{1}={\frac {31}{23}},x_{2}={\frac {11}{23}},x_{3}={\frac {20}{23}}$

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