Gauss-elimináció

A MathWikiből
(Változatok közti eltérés)
(+kat)
 
(2 szerkesztő 11 közbeeső változata nincs mutatva)
1. sor: 1. sor:
A '''Gauss-elimináció''' egy eljárás, amivel megtalálhatjuk egy lineáris egyenletrendszer megoldásait, meghatározhatjuk egy mátrix rangját.
+
A '''Gauss-elimináció''' egy eljárás, amivel megtalálhatjuk egy lineáris egyenletrendszer megoldásait, meghatározhatjuk egy [[Mátrix rangja|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 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.
5. sor: 5. sor:
 
==Az eljárás leírása==
 
==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 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 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 aminél 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'':
 
A lineáris egyenletrendszer megoldásait nem változtatják meg az ''elemi sorekvivalens átalakítások'':
12. sor: 11. sor:
 
* Egy sor elemeinek nullától különböző számmal történő végigszorzása
 
* 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
 
* Egy sor konstansszorosának másikhoz való elemenkénti hozzáadása
==Példa==
+
==Példák==
Oldjuk meg az alábbi lineáris egyenletrendszert:
+
===1.===
:<math>2x+y-z=8 \ </math>
+
 
:<math>-3x-y+2z=-11 \ </math>
+
{|style="width:80%;text-align:center"
:<math>-2x+y+2z=-3 \ </math>
+
!width="50%"|Lineáris egyenletrendszer
A kibővített együtthatómátrix így néz ki:
+
!width="50%"|Kibővített együtthatómátrix
:<math> \begin{bmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3\end{bmatrix}</math>
+
|-
 +
|<math>\begin{matrix}2x+y-z&=&8 \\ -3x-y+2z&=&-11 \\ -2x+y+2z&=&-3 \end{matrix} </math>
 +
|<math> \begin{bmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3\end{bmatrix}</math>
 +
|-
 +
|colspan="2" style="text-align:left"|Adjuk hozzá a második sorhoz az első sor 3/2-szeresét, ekkor kiesik az x
 +
|-
 +
|<math>\begin{matrix}2x+y-z&=&8 \\ \frac{1}{2}y+\frac{1}{2}z&=&1 \\ -2x+y+2z&=&-3 \end{matrix} </math>
 +
|<math> \begin{bmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ -2 & 1 & 2 & -3\end{bmatrix}</math>
 +
|-
 +
|colspan="2" style="text-align:left"|Adjuk hozzá a harmadik sorhoz az elsőt, hogy ott se legyen x
 +
|-
 +
|<math>\begin{matrix}2x+y-z&=&8 \\ \frac{1}{2}y+\frac{1}{2}z&=&1 \\ 2y+z&=&5 \end{matrix} </math>
 +
|<math> \begin{bmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 2 & 1 & 5\end{bmatrix}</math>
 +
|-
 +
|colspan="2" style="text-align:left"|Most vonjuk ki a harmadik sorból a második sor 4-szeresét
 +
|-
 +
|<math>\begin{matrix}2x+y-z&=&8 \\ \frac{1}{2}y+\frac{1}{2}z&=&1 \\ -z&=&1 \end{matrix} </math>
 +
|<math> \begin{bmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 0 & -1 & 1\end{bmatrix}</math>
 +
|-
 +
|colspan="2" style="text-align:left"|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
 +
|-
 +
|<math>\begin{matrix}2x+y-z&=&8 \\ \frac{1}{2}y+\frac{1}{2}z&=&1 \\ z&=&-1 \end{matrix} </math>
 +
|<math> \begin{bmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 0 & 1 & -1\end{bmatrix}</math>
 +
|-
 +
|colspan="2" style="text-align:left"|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)
 +
|-
 +
|<math>\begin{matrix}2x+y-z&=&8 \\ y&=&3 \\ z&=&-1 \end{matrix} </math>
 +
|<math> \begin{bmatrix} 2 & 1 & -1 & 8 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1\end{bmatrix}</math>
 +
|-
 +
|colspan="2" style="text-align:left"|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)
 +
|-
 +
|<math>\begin{matrix}x&=&2 \\ y&=&3 \\ z&=&-1 \end{matrix} </math>
 +
|<math> \begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1\end{bmatrix}</math>
 +
|-
 +
|colspan="2" style="text-align:left"|É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.===
 +
 
 +
:<math>\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}</math>
 +
:<math>\begin{bmatrix}
 +
  1 & 2 & 3 & 2 \\
 +
  1 & 1 & 1 & 2 \\
 +
  3 & 3 & 1 & 0
 +
\end{bmatrix}</math>
 +
:<math>\begin{bmatrix}
 +
  1 & 2 & 3 & 2 \\
 +
  0 & -1 & -2 & 0 \\
 +
  0 & -3 & -8 & -6
 +
\end{bmatrix}</math>
 +
:<math>\begin{bmatrix}
 +
  1 & 2 & 3 & 2 \\
 +
  0 & -1 & -2 & 0 \\
 +
  0 & 0 & -2 & -6
 +
\end{bmatrix}</math>
 +
:<math>\begin{bmatrix}
 +
  1 & 2 & 3 & 2 \\
 +
  0 & -1 & -2 & 0\\
 +
  0 & 0 & 1 & 3
 +
\end{bmatrix}</math>
 +
:<math>\begin{bmatrix}
 +
  1 & 2 & 3 & 2 \\
 +
  0 & 1 & 0 & -6\\
 +
  0 & 0 & 1 & 3
 +
\end{bmatrix}</math>
 +
:<math>\begin{bmatrix}
 +
  1 & 0 & 0 & 5 \\
 +
  0 & 1 & 0 & -6\\
 +
  0 & 0 & 1 & 3
 +
\end{bmatrix}</math>
 +
--------
 +
# <math>x_1 + 2x_2 + 3x_3 = 2</math>
 +
# <math>x_1 + x_2 + x_3 = 2</math>
 +
# <math>3x_1 + 3x_2 + x_3 = 0</math>
 +
Az együtthatómátrix:
 +
:[http://upload.wikimedia.org/wikipedia/de/0/0e/Gausselimlgs.PNG]
 +
Az eljárás:
 +
:[http://upload.wikimedia.org/wikipedia/de/3/3e/Gausseliminierung.PNG]
 +
==Linkek==
 +
* [http://en.wikipedia.org/wiki/Gauss_elimination Gaussian elimination] szócikk az angol wikipediáról
 +
* [http://www.cs.bme.hu/%7Efleiner/bszjegyzet/bsz1jegyzet.pdf#nameddest=section.2.3 Lineáris egyenletrendszerek] Fleiner Tamás bsz1 jegyzete
 +
 
 +
[[Kategória: Lineáris algebra]]

A lap jelenlegi, 2008. május 20., 12:38-kori változata

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.

Tartalomjegyzék

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. x1 + 2x2 + 3x3 = 2
  2. x1 + x2 + x3 = 2
  3. 3x1 + 3x2 + x3 = 0

Az együtthatómátrix:

[1]

Az eljárás:

[2]

Linkek

Személyes eszközök