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 [szerkesztés]

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.^[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:

$Ax=b\,$

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

$T_1Ax=T_1b\,$

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

$T_2T_1Ax=T_2T_1b\,$

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³-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 [szerkesztés]

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 [szerkesztés]

$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}\neq0$ . (Ez az állapot az egyenletek sorrendjének felcserélésével elérhető.) Ekkor vonjuk ki az i. egyenletből ( ahol $i\geq2$ ) 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 [szerkesztés]

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 [szerkesztés]

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

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

end function

Ebben az algoritmusban feltételeztük, hogy az $a^{(k)}_{kk} \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^{(n)}_{nn} \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 [szerkesztés]

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