Gauss-elimináció

A matematikában a Gauss-elimináció (más néven sorredukció) lineáris egyenletrendszerek megoldására használt módszer. Nevét Carl Friedrich Gaussról, egy híres német matematikusról kapta, aki írt erről a módszerről, de nem ő találta fel.

A Gauss-elimináció elvégzéséhez a lineáris egyenletrendszerben szereplő kifejezések együtthatóit egy kiterjesztett mátrixnak nevezett mátrix létrehozására használjuk. Ezután elemi sorműveletekkel egyszerűsítjük a mátrixot. Az alkalmazott háromféle sorművelet a következő:

1. típus: Egy sor cseréje egy másik sorral.

2. típus: Egy sor szorzása nem nulla számmal.

3. típus: Egy sor hozzáadása vagy kivonása egy másik sorból.

A Gauss-elimináció célja az, hogy a mátrixot sor-echelon formában kapjuk meg. Ha egy mátrix sor-echelon formában van, az azt jelenti, hogy balról jobbra haladva minden sor legalább eggyel több nullás taggal kezdődik, mint a fölötte lévő sor. A Gauss-elimináció egyes definíciói szerint a mátrix eredményének redukált sor-echelon formában kell lennie. Ez azt jelenti, hogy a mátrix sor-echelon formában van, és minden sorban az egyetlen nem nulla kifejezés 1. A Gauss-eliminációt, amely redukált sor-echelon mátrixeredményt hoz létre, néha Gauss-Jordan-eliminációnak nevezik.

Példa

Tegyük fel, hogy a cél az, hogy megtaláljuk a válaszokat erre a lineáris egyenletrendszerre.

2 x + y - z = 8 ( R 1 ) - 3 x - y + 2 z = - 11 ( R 2 ) - 2 x + y + 2 z = - 3 ( R 3 ) {\displaystyle {\begin{alignedat}{7}2x&&\\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\qquad (R_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (R_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (R_{3})\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\qquad (R_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (R_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (R_{3})\end{alignedat}}$

Először is a rendszert kiterjesztett mátrixszá kell alakítani. Egy kibővített mátrixban minden lineáris egyenlet egy sor lesz. Az augmentált mátrix egyik oldalán a lineáris egyenlet minden egyes tagjának együtthatói a mátrixban számokká válnak. A bővített mátrix másik oldalán az egyes lineáris egyenletek konstans tételei vannak. Erre a rendszerre a kiterjesztett mátrix a következő:

[ 2 1 - 1 8 - 3 - 1 2 - 11 - 2 1 2 - 3 ] {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\\\-3&-1&2&-11\\\-2&1&2&-3\end{array}}}\right]} $\left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$

Ezután a kiterjesztett mátrixon sorműveleteket lehet végezni annak egyszerűsítése érdekében. Az alábbi táblázat az egyenletrendszeren és a kiegészített mátrixon végzett sorcsökkentési folyamatot mutatja be.

Egyenletrendszer	Soros műveletek	Megnövelt mátrix
2 x + y - z = 8 - 3 x - y + 2 z = - 11 - 2 x + y + 2 z = - 3 {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\\-3x&&\;-\;&&y&&\;+\;&&2z&& \;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}$		[ 2 1 - 1 8 - 3 - 1 2 - 11 - 2 1 2 - 3 ] {\displaystyle \left[{\begin{array}{ccc\|c}2&1&-1&8\\\\-3&-1&2&-11\\\-2&1&2&-3\end{array}}}\right]} $\left[{\begin{array}{ccc\|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$
2 x + y - z = 8 1 2 y + 1 2 z = 1 2 y + z = 5 {\displaystyle {\begin{alignedat}{7}2x&&\;+&&&y&&\;-&&&\;z&&\;=\;&&8&\\\\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+&&y&&\;-&&\;z&&\;=\;&&8&\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}$	R 2 + 3 2 R 1 → R 2 {\displaystyle R_{2}+{\frac {3}{2}}R_{1}\rightarrow R_{2}} $R_{2}+{\frac {3}{2}}R_{1}\rightarrow R_{2}$ R 3 + R 1 → R 3 {\displaystyle R_{3}+R_{1}\rightarrow R_{3}} $R_{3}+R_{1}\rightarrow R_{3}$	[ 2 1 - 1 8 0 1 / 2 1 / 2 1 0 2 1 5 ] {\displaystyle \left[{\begin{array}{ccc\|c}2&1&-1&8\\\\0&1/2&1/2&1/2&1\\\0&2&1&5\end{array}}\right]} $\left[{\begin{array}{ccc\|c}2&1&-1&8\\0&1/2&1/2&1\\0&2&1&5\end{array}}\right]$
2 x + y - z = 8 1 2 y + 1 2 z = 1 - z = 1 {\displaystyle {\begin{alignedat}{7}2x&&\;+&&&&y\;&&&-&&&\;z\;&&=\;&&8&\\\\\&&&&{\frac {1}{2}}y\;&&+&&\;{\frac {1}{2}}z\;&&=\;&&1&\\&&&&&&&&\;-z\;& &\;=\;&&1&\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+&&y\;&&-&&\;z\;&&=\;&&8&\\&&&&{\frac {1}{2}}y\;&&+&&\;{\frac {1}{2}}z\;&&=\;&&1&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}$	R 3 + - 4 R 2 → R 3 {\displaystyle R_{3}+-4R_{2}\rightarrow R_{3}} $R_{3}+-4R_{2}\rightarrow R_{3}$	[ 2 1 - 1 8 0 1 / 2 1 / 2 1 0 0 - 1 1 ] {\displaystyle \left[{\begin{array}{ccc\|c}2&1&-1&8\\\\0&1/2&1/2&1/2&1\\0&0&-1&1\end{array}}\right]} $\left[{\begin{array}{ccc\|c}2&1&-1&8\\0&1/2&1/2&1\\0&0&-1&1\end{array}}\right]$

A mátrix most már sor-egész alakban van. Ezt háromszög alaknak is nevezik.

Egyenletrendszer	Soros műveletek	Megnövelt mátrix
2 x + y = 7 1 2 y = 3 / 2 - z = 1 {\displaystyle {\begin{alignedat}{7}2x&&\;+&&&y\;&&&&\;\;\;&&=\;&&7&\\\&&&&&&&&{\frac {1}{2}}y\;&&&&\;\;&&=\;&&3/2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&{\frac {1}{2}}y\;&&&&\;\;&&=\;&&3/2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}$	R 2 + 1 2 R 3 → R 2 {\displaystyle R_{2}+{\frac {1}{2}}R_{3}}\rightarrow R_{2}} $R_{2}+{\frac {1}{2}}R_{3}\rightarrow R_{2}$ R 1 - R 3 → R 1 {\displaystyle R_{1}-R_{3}\rightarrow R_{1}} $R_{1}-R_{3}\rightarrow R_{1}$	[ 2 1 0 7 0 1 / 2 0 3 / 2 0 0 0 - 1 1 ] {\displaystyle \left[{\begin{array}{ccc\|c}2&1&0&7\\\0&1/2&0&3/2\\\0&0&-1&1\end{array}}}\right]} $\left[{\begin{array}{ccc\|c}2&1&0&7\\0&1/2&0&3/2\\0&0&-1&1\end{array}}\right]$
2 x + y = 7 y = 3 z = - 1 {\displaystyle {\begin{alignedat}{7}2x&&\;+&&&y\;&&&&\;\;&&=\;&&7&\\\&&&&&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}$	2 R 2 → R 2 {\displaystyle 2R_{2}\rightarrow R_{2}} $2R_{2}\rightarrow R_{2}$ R 3 → R 3 {\displaystyle -R_{3}\rightarrow R_{3}} $-R_{3}\rightarrow R_{3}$	[ 2 1 0 7 0 0 1 0 3 0 0 0 1 - 1 ] {\displaystyle \left[{\begin{array}{ccc\|c}2&1&0&7\\\0&1&0&3\\0&0&1&-1\end{array}}}\right]} $\left[{\begin{array}{ccc\|c}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]$
x = 2 y = 3 z = - 1 {\displaystyle {\begin{alignedat}{7}x&&\;&&\;&&&&\;\;\;&&=\;&&2&\\\\&&&& y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}} ${\begin{alignedat}{7}x&&\;&&\;&&&&\;\;&&=\;&&2&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}$	R 1 - R 2 → R 1 {\displaystyle R_{1}-R_{2}\rightarrow R_{1}} $R_{1}-R_{2}\rightarrow R_{1}$ 1 2 R 1 → R 1 {\displaystyle {\frac {1}{2}}R_{1}\rightarrow R_{1}} ${\frac {1}{2}}R_{1}\rightarrow R_{1}$	[ 1 0 0 2 0 0 1 0 3 0 0 0 1 - 1 ] {\displaystyle \left[{\begin{array}{ccc\|c}1&0&0&2\\\0&1&0&3\\0&0&1&-1\end{array}}}\right]} $\left[{\begin{array}{ccc\|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

A mátrix most már redukált sor-egész alakban van. A mátrix leolvasása azt mutatja, hogy az egyenletrendszer megoldása akkor következik be, ha x = 2, y = 3 és z = -1.

Kérdések és válaszok

K: Mi az a Gauss-elimináció?

V: A Gauss-elimináció a matematikában lineáris egyenletrendszerek megoldására használt módszer.

K: Kinek a nevét viseli?

V: Carl Friedrich Gaussról, egy híres német matematikusról nevezték el, aki írt erről a módszerről, de nem ő találta fel.

K: Hogyan történik a Gauss-elimináció?

V: A Gauss-elimináció úgy történik, hogy a lineáris egyenletrendszerben szereplő kifejezések együtthatóit felhasználva létrehozunk egy kiegészített mátrixot. Ezután elemi sorműveletekkel egyszerűsítik a mátrixot.

K: Milyen háromféle sorműveletet használnak a Gauss-eliminációban?

V: A Gauss-eliminációban használt háromféle sorművelet a következő: Egy sor felcserélése egy másik sorral, egy sor szorzása egy nem nulla számmal, és egy sor hozzáadása vagy kivonása egy másik sorból.

K: Mi a célja a Gauss-eliminációnak?

V: A Gauss-elimináció célja az, hogy a mátrixot sor-echelon formában kapjuk meg.

K: Mi az a sor-echelon forma?

V: Ha egy mátrix sor-echelon formában van, az azt jelenti, hogy balról jobbra haladva minden sor legalább eggyel több zérus kifejezéssel kezdődik, mint a fölötte lévő sor.

K: Mi a redukált sor-echelon forma?

V: A redukált sor-echelon forma azt jelenti, hogy a mátrix sor-echelon formában van, és minden sorban az egyetlen nem nulla tag 1. A redukált sor-echelon mátrix eredményét létrehozó Gauss-eliminációt néha Gauss-Jordan-eliminációnak is nevezik.