Gauss-elimináció

A Gauss-elimináció egy eljárás, amivel megtalálhatjuk egy lineáris egyenletrendszer megoldásait, meghatározhatjuk egy mátrix rangját.

Az eljárás során először a kibővített együtthatómátrixot elemi sorekvivalens átalakítások felhasználásával lépcsős alakúra hozzuk, majd a második lépésben redukált lépcsős alakra redukáljuk.

Az eljárás leírása

A lineáris egyenletrendszereket rendezhetjük úgy, hogy az egyenlőség jobb oldalára írjuk a konstansokat, a bal oldalára pedig rögzített sorrendben az ismeretleneket és az együtthatókat. Ha ezeket az együtthatókat és konstansokat táblázatba rendezzük, akkor kapjuk a kibővített együtthatómátrixot. A kibővített együtthatómátrix akkor lépcsős alakú, ha minden sor az első nemnulla eleme 1 (vezéregyes), valamint bármely vezéregyes alatt csak tőle jobbra lévő oszlopban vannak vezéregyesek. A redukált lépcsős alak az olyan lépcsős alak amiben minden vezéregyes az egyetlen nemnulla elem az oszlopában.

A lineáris egyenletrendszer megoldásait nem változtatják meg az elemi sorekvivalens átalakítások:

• Sorok felcserélése
• Egy sor elemeinek nullától különböző számmal történő végigszorzása
• Egy sor konstansszorosának másikhoz való elemenkénti hozzáadása

Példák

1.

Lineáris egyenletrendszer	Kibővített együtthatómátrix
$\begin{matrix}2x+y-z&=&8 \\ -3x-y+2z&=&-11 \\ -2x+y+2z&=&-3 \end{matrix}$	$\begin{bmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3\end{bmatrix}$
Adjuk hozzá a második sorhoz az első sor 3/2-szeresét, ekkor kiesik az x
$\begin{matrix}2x+y-z&=&8 \\ \frac{1}{2}y+\frac{1}{2}z&=&1 \\ -2x+y+2z&=&-3 \end{matrix}$	$\begin{bmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ -2 & 1 & 2 & -3\end{bmatrix}$
Adjuk hozzá a harmadik sorhoz az elsőt, hogy ott se legyen x
$\begin{matrix}2x+y-z&=&8 \\ \frac{1}{2}y+\frac{1}{2}z&=&1 \\ 2y+z&=&5 \end{matrix}$	$\begin{bmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 2 & 1 & 5\end{bmatrix}$
Most vonjuk ki a harmadik sorból a második sor 4-szeresét
$\begin{matrix}2x+y-z&=&8 \\ \frac{1}{2}y+\frac{1}{2}z&=&1 \\ -z&=&1 \end{matrix}$	$\begin{bmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 0 & -1 & 1\end{bmatrix}$
Meg is vagyunk az eljárás első felével, vagyis az együtthatómátrix lépcsős alakú, szorozzuk be a 3. sort -1-el, ezzel fejezzük ki z-t
$\begin{matrix}2x+y-z&=&8 \\ \frac{1}{2}y+\frac{1}{2}z&=&1 \\ z&=&-1 \end{matrix}$	$\begin{bmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 0 & 1 & -1\end{bmatrix}$
Most a második egyenletbe z-t behelyettesítve fejezzük ki y-t (a második sort szorozzuk be kettővel és vonjuk ki belőle a harmadik sort)
$\begin{matrix}2x+y-z&=&8 \\ y&=&3 \\ z&=&-1 \end{matrix}$	$\begin{bmatrix} 2 & 1 & -1 & 8 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1\end{bmatrix}$
Végül az első egyenletbe y-t és z-t behelyettesítve fejezzük ki x-et (Vonjuk ki belőle a második sort, adjuk hozzá a harmadikat és osszuk el kettővel)
$\begin{matrix}x&=&2 \\ y&=&3 \\ z&=&-1 \end{matrix}$	$\begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1\end{bmatrix}$
És ezzel meg is volnánk a kibővített együtthatómátrix redukált lépcsős alakú, minden ismeretlen ki van fejezve.

2.

$\begin{matrix} x_1 + 2x_2 + 3x_3 & = & 2 \\ x_1 + x_2 + x_3 & = & 2 \\ 3x_1 + 3x_2 + x_3 & = & 0 \end{matrix}$

$\begin{bmatrix} 1 & 2 & 3 & 2 \\ 1 & 1 & 1 & 2 \\ 3 & 3 & 1 & 0 \end{bmatrix}$

$\begin{bmatrix} 1 & 2 & 3 & 2 \\ 0 & -1 & -2 & 0 \\ 0 & -3 & -8 & -6 \end{bmatrix}$

$\begin{bmatrix} 1 & 2 & 3 & 2 \\ 0 & -1 & -2 & 0 \\ 0 & 0 & -2 & -6 \end{bmatrix}$

$\begin{bmatrix} 1 & 2 & 3 & 2 \\ 0 & -1 & -2 & 0\\ 0 & 0 & 1 & 3 \end{bmatrix}$

$\begin{bmatrix} 1 & 2 & 3 & 2 \\ 0 & 1 & 0 & -6\\ 0 & 0 & 1 & 3 \end{bmatrix}$

$\begin{bmatrix} 1 & 0 & 0 & 5 \\ 0 & 1 & 0 & -6\\ 0 & 0 & 1 & 3 \end{bmatrix}$

---

1. x₁ + 2x₂ + 3x₃ = 2
2. x₁ + x₂ + x₃ = 2
3. 3x₁ + 3x₂ + x₃ = 0

Az együtthatómátrix:

[1]

Az eljárás:

[2]

Linkek

• Gaussian elimination szócikk az angol wikipediáról
• Lineáris egyenletrendszerek Fleiner Tamás bsz1 jegyzete