Gauss elimináció

Pont 3.2 Gauss elimináció

Bemutatunk egy algoritmust, amelyet általában Gauss eliminációnak nevezünk, amely lehetővé teszi egy lineáris egyenletrendszer megoldó terének leírását. Ez az algoritmus központi szerepet játszik a későbbiek nagy részében.

Projekt 3.2.1.

Megvizsgálunk néhány egyszerű példát, amelyek útmutatást adnak egy általánosabb megközelítés megértéséhez.

Adjunk leírást a megoldó térről a lineáris rendszerhez:

\begin{equation*} \begin{alignedat}{3} x \amp = \amp 2 \\ y \amp = \amp -1. \\ \end{alignedat} \end{equation*}
Adjunk leírást a megoldó térről a lineáris rendszerhez:

\begin{equation*} \begin{alignedat}{4} -x \amp {} + {} \amp 2y \amp {}-{} \amp z \amp {}={} \amp -3 \\ \amp \amp 3y \amp {}+{} \amp z \amp {}={} \amp -1 \\ \amp \amp \amp \amp 2z \amp {}={} \amp 4. \\ \end{alignedat} \end{equation*}
Adjunk leírást a megoldó térről a lineáris rendszerhez:

\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 3y \amp {}={} \amp -1 \\ 2x\amp {}+{} \amp y \amp {}={} \amp 3. \\ \end{alignedat} \end{equation*}
Adjuk meg a következő, egyszerű rendszer megoldó terét: \(0x = 0\text{.}\)
Adjuk meg a következő, egyszerű rendszer megoldó terét: \(0x = 5\text{.}\)

Ezek a példák néhány ötletet adnak, amelyek motiválják egy általános megközelítést a lineáris rendszerek megoldásainak meghatározására.

Megfigyelés 3.2.1.

Először is, egyes rendszerek megoldási terének megtalálása egyszerű. Például, mivel a következő rendszer minden egyenlete egyváltozós:

\begin{equation*} \begin{alignedat}{3} x \amp {}={} \amp -4 \\ y \amp {}={} \amp 2. \\ \end{alignedat} \end{equation*}

így adott változó értéke egyszerűen adódik. Itt tehát pontosan egy megoldás létezik: \((x,y) = (-4,2)\text{.}\) Az ilyen rendszereket szétválaszthatónak nevezzük.

Megfigyelés 3.2.2.

Másodszor, van egy módszer, amelynek segítségével megtalálhatjuk bizonyos típusú lineáris rendszerek megoldásait. Vegyük például a következő rendszert:

\begin{equation*} \begin{alignedat}{4} x \amp {} + {} \amp 2y \amp {}-{} \amp 2z \amp {}={} \amp -4 \\ \amp \amp -y \amp {}+{} \amp z \amp {}={} \amp 3 \\ \amp \amp \amp \amp 3z \amp {}={} \amp 3. \\ \end{alignedat} \end{equation*}

Az utolsó egyenletet megszorozzuk \(1/3\) értékkel, így adódik, hogy

\begin{equation*} \begin{alignedat}{4} x \amp {} + {} \amp 2y \amp {}-{} \amp 2z \amp {}={} \amp -4 \\ \amp \amp -y \amp {}+{} \amp z \amp {}={} \amp 3 \\ \amp \amp \amp \amp z \amp {}={} \amp 1. \\ \end{alignedat} \end{equation*}

Bármely megoldás esetén teljesül, hogy \(z=1\text{.}\)

Miután ezt tudjuk, helyettesíthetjük \(z=1\)-et az első és második egyenletbe, és egyszerűsíthetjük, hogy egy új egyenletrendszert kapjunk, amelynek ugyanazok a megoldásai:

\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 2y {}={} \amp\amp -2 \\ \amp \amp -y {}={} \amp\amp 2. \\ \end{alignedat} \end{equation*}

A második egyenlet, miután mindkét oldalt \(-1\)-gyel megszoroztuk, azt mutatja, hogy \(y=-2\text{.}\) Ezt az értéket ezután behelyettesíthetjük az első egyenletbe, hogy meghatározzuk, hogy \(x=2\text{.}\)

Ezen a módon megkaptuk, hogy csak egy megoldás létezik: \((x,y,z)=(2,-2,1)\text{.}\)

Az eredeti egyenletrendszerünk:

ezt háromszög alaknak nevezzük a képletek által kialakított forma miatt. Ahogy ez a példa is mutatja, a háromszög alakra hozott rendszerek könnyen megoldhatók a bemutatott módszerrel, amelyet visszahelyettesítésnek nevezünk.

Megfigyelés 3.2.3.

Helyettesítést használhatunk még általánosabban is. Tekintsük a következő rendszert:

\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 2y \amp {}={} \amp 1 \\ 2x\amp {}+{} \amp 3y \amp {}={} \amp 3. \\ \end{alignedat} \end{equation*}

az első egyenletből kifejezzük \(x\)-et \(y\) segítségével:

\begin{equation*} x = 1-2y \end{equation*}

ezt behelyettesítjük a második egyenletbe és egyszerűsítünk:

\begin{equation*} \begin{alignedat}{2} 2x + 3y \amp {}= \amp 3 \\ 2(1-2y) + 3y \amp {}={} \amp 3 \\ 2-4y + 3y \amp {}={} \amp 3 \\ -y \amp {}={} \amp 1 \\ y \amp {}={} \amp -1 \\ \end{alignedat} \end{equation*}

Máris kapjuk az \(y=-1\) megoldást, amiből adódik, hogy \((x,y)=(3,-1)\text{.}\)

A fenti lépések hatékonyabban végezhető el, ha az első egyenlet többszörösét adjuk hozzá a másodikhoz. Ebben az esetben az első egyenletet -2-vel megszorozzuk, és hozzáadjuk a második egyenlethez.

\begin{equation*} \begin{array}{cr} \amp -2(\text{első egyenlet}) \\ + \amp \text{második egyenlet} \\ \hline \end{array} \end{equation*}

és kapjuk, hogy

\begin{equation*} \begin{array}{cr} \amp -2(x+2y=1) \\ + \amp 2x+3y = 3 \\ \hline \\ \end{array} \end{equation*}

amiből adódik:

\begin{equation*} \begin{array}{crcr} \amp -2x-4y \amp = \amp -2 \\ + \amp 2x+3y \amp = \amp 3 \\ \hline \amp -y \amp = \amp 1. \\ \end{array} \end{equation*}

Az eredeti rendszert

\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 2y \amp {}={} \amp 1 \\ 2x\amp {}+{} \amp 3y \amp {}={} \amp 3 \\ \end{alignedat} \end{equation*}

ilyen módon háromszög alakra lehet hozni

\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 2y \amp {}={} \amp 1 \\ \amp \amp -y \amp {}={} \amp 1. \\ \end{alignedat} \end{equation*}

Vegyük észre, hogy ez a folyamat megfordítható. A háromszög rendszerből kiindulva visszanyerhetjük az eredeti rendszert az első egyenlet 2-vel való megszorozásával és a másodikhoz való hozzáadásával. Ennek következtében a két rendszer ugyanazzal a megoldástérrel rendelkezik. Ezt a pontot később újra megvizsgáljuk, és adunk egy talán meggyőzőbb magyarázatot.

Természetesen a döntés, hogy az első egyenletet -2-vel szorozzuk meg, azért született, hogy a két egyenletben szereplő \(x\) eliminálva legyen, ami egy olyan háromszög alakú rendszert eredményez, amelyet visszahelyettesítéssel könnyebben meg lehet megoldani.

E megfigyelések alapján három műveletet vezetünk be, amelyek egy lineáris egyenletrendszert egy új egyenletrendszerré alakítanak, amelynek ugyanaz a megoldó tere. Célunk egy új rendszer létrehozása, amelynek megoldó tere megegyezik az eredeti rendszerével és könnyebben kezelhető.

Felszorzás: Egy egyenletet megszorozhatunk egy nem 0 számmal:

\begin{equation*} 2x -4y = 6 \end{equation*}

megoldásai megegyeznek a következővel:

\begin{equation*} \frac12(2x-4y=6) \end{equation*}

vagy

\begin{equation*} x-2y=3\text{.} \end{equation*}
Felcserélés: Egyenletek cseréje természetesen nem változtatja meg a megoldások halmazát:

\begin{equation*} \begin{alignedat}{3} 2x \amp {}+{} \amp 4y \amp {}={} \amp 1 \\ x \amp {}-{} \amp 3y \amp {}={} \amp 0 \\ \end{alignedat} \end{equation*}

megoldásai megegyeznek az alábbi rendszerével:

\begin{equation*} \begin{alignedat}{3} x \amp {}-{} \amp 3y \amp {}={} \amp 0 \\ 2x \amp {}+{} \amp 4y \amp {}={} \amp 1. \\ \end{alignedat} \end{equation*}
Helyettesítés: Ahogyan láttuk egy adott egyenletet nem 0 számmal szorozhatunk, ezt hozzáadhatjuk másik egyenlethez. Ezt a lépést helyettesítésnek nevezzük.

El.Top Köv.