Gauss-elimináció

A Wikipédiából, a szabad enciklopédiából

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 | forrásszöveg szerkesztése]

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 T1 mátrixszal szorozzuk mindkét oldalt:

T_1Ax=T_1b\,

Majd T2 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 = Q1 · Q2 · ... Qm · x' vektorra akarjuk meghatározni. A gyakorlatban a Ti és Qi 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 n3-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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkeszté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}\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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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^{(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 | forrásszöveg szerkesztése]

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}

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

  1. Az eljárással meghatározható mátrixok rangja és determinánsa is.