A Gauss–Jordan-elimináció

1. Mire jó a Gauss–Jordan-elimináció?

Ez az az eljárás, amivel a lineáris algebra első félévének a számolós feladatai megoldhatók. Egyetlen algoritmus, három feladattípusra:

Lineáris egyenletrendszer megoldása, akkor is, ha nincs megoldás, és akkor is, ha végtelen sok van.
Mátrix rangjának meghatározása: a lépcsős alakban a nem csupa nulla sorok száma.
Inverz mátrix kiszámítása: az $[A\,|\,I]$ táblán végigfuttatva.

Az alapgondolat egyszerű: az egyenletrendszert olyan lépésekkel alakítjuk, amelyek nem változtatják meg a megoldáshalmazt, addig, amíg a megoldás egyszerűen le nem olvasható. Mivel az ismeretlenek neve a számolásban nem játszik szerepet, elég az együtthatókat írni, így lesz az egyenletrendszerből bővített mátrix:

\begin{cases} x+2y+z=9 \\ 2x+y-z=0 \\ 3x-y+2z=9 \end{cases} \qquad\longleftrightarrow\qquad \left[\begin{array}{ccc|c} 1 & 2 & 1 & 9 \\ 2 & 1 & -1 & 0 \\ 3 & -1 & 2 & 9 \end{array}\right]

A függőleges vonal csak elválasztás: tőle balra az együtthatók, jobbra a jobb oldalak állnak. Minden sor egy egyenlet, minden oszlop egy ismeretlen.

2. Az elemi sorműveletek

Három művelet megengedett, és mindhárom megfordítható, ezért nem veszíthetünk el és nem is nyerhetünk megoldást általuk:

Művelet	Jelölés	Miért szabad?
Két sor cseréje	$S_i \leftrightarrow S_j$	az egyenletek sorrendje nem befolyásolja a megoldást
Sor szorzása nem nulla számmal	$S_i \to \lambda S_i$	egy egyenlet mindkét oldalának szorzása ekvivalens átalakítás
Sor másik sor számszorosával növelve	$S_i \to S_i + \lambda S_j$	egyenlőhöz egyenlőt adva az egyenlőség megmarad

Sorokkal dolgozunk, nem oszlopokkal

Egyenletrendszernél oszlopműveletet nem szabad végezni: az oszlopok az ismeretleneket jelentik, a keverésük más rendszert adna. A $\lambda=0$ szorzó is tilos: egy sort nullázva egy egyenletet dobnánk el.

3. Lépcsős és redukált lépcsős alak

A cél egy olyan alak, amiből a megoldás leolvasható. Két szintje van, és a kettő különbsége adja a Gauss- és a Gauss–Jordan-módszer közti különbséget.

Lépcsős alak (Gauss). Minden sor első nem nulla eleme, a vezéregyes, az előző sorénál jobbra van, alatta az oszlopban csupa nulla áll, a csupa nulla sorok pedig legalul.

\left[\begin{array}{ccc|c} 1 & 2 & 1 & 9 \\ 0 & 1 & 1 & 6 \\ 0 & 0 & 1 & 4 \end{array}\right]

Innen visszahelyettesítéssel jutunk el a megoldáshoz: az utolsó sorból $z=4$ , ezt a másodikba írva $y=2$ , és így tovább.

Redukált lépcsős alak (Gauss–Jordan). Itt egy lépéssel tovább megyünk: a vezéregyesek fölött is nullát csinálunk.

\left[\begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 4 \end{array}\right]

Ebből már nincs mit számolni: $x=1$ , $y=2$ , $z=4$ . Ez a redukált lépcsős alak, és egy mátrixhoz pontosan egy ilyen tartozik, függetlenül attól, milyen sorrendben végeztük a műveleteket.

4. Az algoritmus lépésről lépésre

Az eljárás oszloponként halad balról jobbra. Egy oszlopban mindig ugyanaz a négy lépés:

Vezérelem választása. Az aktuális oszlopban, az eddig lezárt sorok alatt keress nem nulla elemet. Ha nincs, lépj a következő oszlopra: ez az oszlop szabad ismeretlenhez fog tartozni.
Sorcsere, ha kell. Vidd a választott elem sorát az aktuális sor helyére. Kézi számolásnál érdemes olyat választani, amivel a legkevesebb tört keletkezik: az $1$ vagy $-1$ a legjobb jelölt.
Normálás. Oszd el a sort a vezérelemmel, hogy a helyén $1$ álljon.
Kinullázás. Az oszlop összes többi sorából vond ki a vezérsor megfelelő számszorosát, a Gauss–Jordannál a vezéregyes fölötti sorokból is.

Ha az utolsó oszlop is sorra került, a bal oldalon redukált lépcsős alak áll. Ez legfeljebb annyi vezéregyest tartalmaz, ahány sor van; a vezéregyesek száma pedig épp a mátrix rangja.

Kézi számolásnál a törtek kerülhetők

A normálást nem kötelező azonnal elvégezni: előbb sorcserével és egész számszorosokkal is el lehet jutni oda, hogy a vezérelem 1 legyen. Ez nem gyorsítja az algoritmust, de dolgozatban jelentősen csökkenti a hibázás esélyét.

5. Kidolgozott példa: egyenletrendszer megoldása

Három egyenlet, három ismeretlen

Oldjuk meg a következő egyenletrendszert:

\begin{cases} x+2y+z=9 \\ 2x+y-z=0 \\ 3x-y+2z=9 \end{cases}

Felírjuk a bővített mátrixot:
$\left[\begin{array}{ccc|c} 1 & 2 & 1 & 9 \\ 2 & 1 & -1 & 0 \\ 3 & -1 & 2 & 9 \end{array}\right]$
Az első oszlop vezérelem már 1, tehát csak nullázunk: $S_2 \to S_2-2S_1$ és $S_3 \to S_3-3S_1$ .
$\left[\begin{array}{ccc|c} 1 & 2 & 1 & 9 \\ 0 & -3 & -3 & -18 \\ 0 & -7 & -1 & -18 \end{array}\right]$
A második sort elosztjuk $-3$ -mal, hogy a második oszlopban vezéregyes álljon: $S_2 \to -\tfrac{1}{3}S_2$ .
$\left[\begin{array}{ccc|c} 1 & 2 & 1 & 9 \\ 0 & 1 & 1 & 6 \\ 0 & -7 & -1 & -18 \end{array}\right]$
Nullázzuk a második oszlopot fölötte és alatta: $S_1 \to S_1-2S_2$ és $S_3 \to S_3+7S_2$ .
$\left[\begin{array}{ccc|c} 1 & 0 & -1 & -3 \\ 0 & 1 & 1 & 6 \\ 0 & 0 & 6 & 24 \end{array}\right]$
A harmadik sort elosztjuk 6-tal: $S_3 \to \tfrac{1}{6}S_3$ .
$\left[\begin{array}{ccc|c} 1 & 0 & -1 & -3 \\ 0 & 1 & 1 & 6 \\ 0 & 0 & 1 & 4 \end{array}\right]$
Végül a harmadik oszlopot is kinullázzuk: $S_1 \to S_1+S_3$ és $S_2 \to S_2-S_3$ .
$\left[\begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 4 \end{array}\right]$
A megoldás leolvasható: $x=1$ , $y=2$ , $z=4$ . Ellenőrzésként érdemes visszahelyettesíteni mindhárom eredeti egyenletbe: egy perc, és kizárja a számolási hibát.

6. A megoldhatóság leolvasása

Nem minden rendszernek van pontosan egy megoldása, és a redukált alak ezt is megmutatja. A kulcs a rangok összehasonlítása: legyen $r=\operatorname{rang}(A)$ az együtthatómátrix rangja, $r'=\operatorname{rang}([A|b])$ a bővítetté, és $n$ az ismeretlenek száma.

Amit a végén látsz	Amit jelent
$r \neq r'$	nincs megoldás: a táblában egy $[\,0\;0\;0\,\|\,c\,]$ alakú sor jelenik meg nem nulla $c$ -vel, ami a $0=c$ ellentmondás
$r=r'=n$	pontosan egy megoldás: minden ismeretlenhez tartozik vezéregyes
$r=r'<n$	végtelen sok megoldás, $n-r$ szabad paraméterrel

Végtelen sok megoldás felírása

Tegyük fel, hogy a redukált alak a következő lett:

\left[\begin{array}{ccc|c} 1 & 0 & -2 & 3 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{array}\right]

Vezéregyes az első és a második oszlopban van, tehát $r=r'=2$ , miközben $n=3$ . Egy szabad paraméter lesz.
A harmadik oszlopban nincs vezéregyes, tehát $z$ a szabad ismeretlen. Legyen $z=t$ , ahol $t$ tetszőleges valós szám.
A két sorból kifejezve a többit: $x=3+2t$ és $y=1-t$ .
A megoldáshalmaz tehát:
$\begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 3 \\ 1 \\ 0 \end{pmatrix} + t\begin{pmatrix} 2 \\ -1 \\ 1 \end{pmatrix}, \qquad t\in\mathbb{R}$

A csupa nulla sor nem hiba

A $[\,0\;0\;0\,|\,0\,]$ sor azt jelenti, hogy az egyik egyenlet a többi következménye volt, nem hordozott új információt. Ez teljesen szabályos, és épp ez vezet a végtelen sok megoldáshoz. Ellentmondás csak akkor van, ha a vonaltól jobbra nem nulla áll.

7. Inverz mátrix számítása Gauss–Jordannal

Ugyanez az algoritmus adja az inverz mátrixot is. Írjuk a mátrix mellé az egységmátrixot, és elimináljunk addig, amíg a bal oldalon egységmátrix nem áll:

Az inverz megkeresése

\big[\,A \;|\; I\,\big] \;\longrightarrow\; \big[\,I \;|\; A^{-1}\,\big]

Ha közben a bal oldalon csupa nulla sor keletkezik, akkor $\det A = 0$ , a mátrixnak nincs inverze, és ez az eljárás magától kiderül, nem kell előre determinánst számolni.

Egy 3×3 mátrix inverze

Legyen

A=\begin{pmatrix} 1 & 2 & 3 \\ 0 & 1 & 4 \\ 5 & 6 & 0 \end{pmatrix}

Felírjuk az $[A\,|\,I]$ táblát:
$\left[\begin{array}{ccc|ccc} 1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 4 & 0 & 1 & 0 \\ 5 & 6 & 0 & 0 & 0 & 1 \end{array}\right]$
Az első oszlop alatt nullázunk: $S_3 \to S_3-5S_1$ .
$\left[\begin{array}{ccc|ccc} 1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 4 & 0 & 1 & 0 \\ 0 & -4 & -15 & -5 & 0 & 1 \end{array}\right]$
A második oszlopban a vezérelem már 1, így csak nullázunk fölötte és alatta: $S_1 \to S_1-2S_2$ és $S_3 \to S_3+4S_2$ .
$\left[\begin{array}{ccc|ccc} 1 & 0 & -5 & 1 & -2 & 0 \\ 0 & 1 & 4 & 0 & 1 & 0 \\ 0 & 0 & 1 & -5 & 4 & 1 \end{array}\right]$
A harmadik oszlop vezéreleme is 1, tehát jöhet az utolsó nullázás: $S_1 \to S_1+5S_3$ és $S_2 \to S_2-4S_3$ .
$\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & -24 & 18 & 5 \\ 0 & 1 & 0 & 20 & -15 & -4 \\ 0 & 0 & 1 & -5 & 4 & 1 \end{array}\right]$
A bal oldalon egységmátrix áll, tehát a jobb oldal az inverz:
$A^{-1}=\begin{pmatrix} -24 & 18 & 5 \\ 20 & -15 & -4 \\ -5 & 4 & 1 \end{pmatrix}$
Ellenőrzés: $AA^{-1}=I$ , érdemes legalább egy sort végigszorozni.

8. Tipikus hibák

A jobb oldal kimarad a műveletből. A sorművelet a teljes sorra vonatkozik, a függőleges vonaltól jobbra álló elemekre is. Ez a leggyakoribb hiba az egész témakörben.
Két sor egyszerre módosítva. Egy lépésben egy sor változik, és a vezérsor közben érintetlen marad. Ha a vezérsort is átírod ugyanabban a lépésben, a következő kivonás már rossz számokkal dolgozik.
Oszlopművelet. Egyenletrendszernél tilos: az oszlopok az ismeretleneket jelentik. Csak sorokkal dolgozunk.
Nullával való szorzás vagy osztás. A sor $\lambda$ -szorosára változtatása csak $\lambda\neq 0$ esetén megengedett, és vezérelemnek sem választható nulla.
Az ellentmondó sor félreolvasása. A $[\,0\;0\;0\,|\,0\,]$ sor rendben van, a $[\,0\;0\;0\,|\,5\,]$ viszont azt jelenti, hogy a rendszernek nincs megoldása. A különbség a vonal jobb oldalán van.
A szabad paraméter elhagyása. Ha kevesebb a vezéregyes, mint az ismeretlen, a válasz nem egyetlen számhármas, hanem egy paraméteres megoldáshalmaz. Egyetlen konkrét megoldás megadása itt hiányos válasz.
Elmaradó ellenőrzés. A visszahelyettesítés, illetve inverznél az $AA^{-1}=I$ szorzás percek alatt kizárja a számolási hibát: egy hosszú eliminációnál ez mindig megéri.