EZLAMA
LA · Přednáška 2

Gaussova eliminace

Řádkové úpravy, pivot, schodovitý tvar, Gauss–Jordan.

Univerzální početní nástroj celé lineární algebry: převod matice na schodovitý tvar a co z něj vyčteš.

Zdroj: Přednáška 2

3.1Proč Gaussovu metodu potřebuješ

Stejná metoda řeší několik zdánlivě různých úloh: soustavy rovnic, hodnost matic, zjištění lineární nezávislosti, hledání báze, výpočet inverzní matice, jádra lineárního zobrazení a někdy i determinanty.

Princip: postupnými úpravami uděláš z nepřehledné matice jednoduchou, aniž bys změnil řešení odpovídající soustavy nebo hodnost.

3.2Tři povolené řádkové úpravy

  1. Výměna dvou řádků: R1↔R3R_1\leftrightarrow R_3.
  2. Násobení celého řádku nenulovým číslem: R2←12R2R_2\leftarrow\frac12R_2.
  3. Přičtení násobku jiného řádku: R3←R3−2R1R_3\leftarrow R_3-2R_1.

Při sčítání/mínus musíš provést operaci pro všechny sloupce řádku, včetně pravé strany, je-li připojena.

Proč se nesmí řádek násobit nulou: ztratily by se informace a operace by nešla obrátit.

3.3Co je pivot a schodovitý tvar

Pivot je první nenulový prvek zleva v nenulovém řádku. Ve schodovitém tvaru jsou všechny nenulové řádky nahoře, nuly pod pivoty a další pivot v následujícím řádku leží víc vpravo.

Příklad schodovitého tvaru:

(1203004500020000).\begin{pmatrix} 1&2&0&3\\ 0&0&4&5\\ 0&0&0&2\\ 0&0&0&0 \end{pmatrix}.

Pivoty jsou v pozicích (1,1)(1,1), (2,3)(2,3), (3,4)(3,4); nejsou nutně všechny na diagonále.

Redukovaný schodovitý tvar (RREF): pivoty se navíc upraví na 1 a nad i pod každým pivotem jsou nuly. Pro určení řešení je výborný, ale často není nutné jít tak daleko.

3.4Podrobný univerzální algoritmusPostup

  1. Napiš matici (pro soustavu rozšířenou matici [A∣b][A\mid b]).
  2. Ve sloupci, kde chceš pivot, najdi nenulový prvek; pokud první řádek nemá vhodné číslo, řádky prohoď.
  3. Vyber pivot (pro pohodlné počítání třeba 1 nebo -1).
  4. Pomocí přičítání násobků pivotového řádku udělej pod pivotem nuly.
  5. Přesuň se na další řádek a další vhodný sloupec.
  6. Takto pokračuj až do schodovitého tvaru.
  7. Zjisti, zda je řádek [0 ⋯ 0∣c][0\ \cdots\ 0\mid c] s c≠0c\ne0. Pokud ano, soustava nemá řešení.
  8. Jinak zvol volné proměnné (sloupce bez pivotu) jako parametry a pivotové proměnné dopočítej zpětným dosazováním.
  9. Pro kontrolu dosaď řešení do všech původních rovnic.

3.5Ukázka se třemi neznámými

Řeš soustavu

x+y+z=6,2x+y−z=1,x−y+2z=5.\begin{aligned} x+y+z&=6,\\ 2x+y-z&=1,\\ x-y+2z&=5. \end{aligned}

Rozšířená matice:

(111621−111−125).\left(\begin{array}{ccc|c}1&1&1&6\\2&1&-1&1\\1&-1&2&5\end{array}\right).

První krok: první pivot je 1 v levém horním rohu. Odstraň xx z druhého a třetího řádku:

R2←R2−2R1,R3←R3−R1.R_2\leftarrow R_2-2R_1,\qquad R_3\leftarrow R_3-R_1.

∼(11160−1−3−110−21−1).\sim\left(\begin{array}{ccc|c}1&1&1&6\\0&-1&-3&-11\\0&-2&1&-1\end{array}\right).

Druhý krok: odstraň yy z třetího řádku: R3←R3−2R2R_3\leftarrow R_3-2R_2.

∼(11160−1−3−1100721).\sim\left(\begin{array}{ccc|c}1&1&1&6\\0&-1&-3&-11\\0&0&7&21\end{array}\right).

Zpětné dosazení: 7z=21⇒z=37z=21\Rightarrow z=3.

Druhý řádek: −y−3⋅3=−11⇒−y=−2⇒y=2-y-3\cdot3=-11\Rightarrow-y= -2\Rightarrow y=2.

První řádek: x+2+3=6⇒x=1x+2+3=6\Rightarrow x=1.

(x,y,z)=(1,2,3).\boxed{(x,y,z)=(1,2,3).}

Kontrola ve druhé původní rovnici: 2⋅1+2−3=12\cdot1+2-3=1. Souhlasí.

3.6Když vyjde nekonečně mnoho řešení

x+2y+z=3,2x+4y+2z=6.\begin{aligned}x+2y+z&=3,\\2x+4y+2z&=6.\end{aligned}

Druhý řádek je dvojnásobek prvního. Gauss dá

(12130000).\left(\begin{array}{ccc|c}1&2&1&3\\0&0&0&0\end{array}\right).

Máme tři proměnné, ale jen jeden pivot. Zvolíme y=s,z=ty=s,z=t. Potom

x=3−2s−t.x=3-2s-t.

Kompletní řešení, ne pouze jedno:

(x,y,z)=(3,0,0)+s(−2,1,0)+t(−1,0,1),s,t∈R.\boxed{(x,y,z)=(3,0,0)+s(-2,1,0)+t(-1,0,1),\quad s,t\in\mathbb R.}

Důležitá myšlenka: volná proměnná nezmizela; je to parametr, který si smíš zvolit libovolně. Proto jsou nekonečně mnohá řešení.

3.7Když řešení neexistuje

x+y=3,2x+2y=5.\begin{aligned}x+y&=3,\\2x+2y&=5.\end{aligned}

Po odečtení dvojnásobku prvního řádku od druhého:

(11300−1).\left(\begin{array}{cc|c}1&1&3\\0&0&-1\end{array}\right).

Druhý řádek znamená 0=−10=-1, což je spor. Žádné řešení neexistuje. Nezáleží na tom, jaké zvolíš x,yx,y.

3.8Gauss–Jordanova metoda

Gauss odstraňuje prvky pod pivoty. Gauss–Jordan pokračuje i nad nimi a pivoty převádí na 1. Z předchozí matice může vzniknout:

(100101020013).\left(\begin{array}{ccc|c}1&0&0&1\\0&1&0&2\\0&0&1&3\end{array}\right).

Výhoda: výsledek čteš rovnou, bez zpětného dosazování. Nevýhoda: obvykle více početních operací.

3.9Jak poznáš hodnost ze schodovitého tvaru

Hodnost je počet nenulových řádků v libovolném schodovitém tvaru, tedy počet pivotů. Příklad:

(123405010000)\begin{pmatrix}1&2&3&4\\0&5&0&1\\0&0&0&0\end{pmatrix}

má hodnost 2, protože má dvě nenulové řádky a dva pivoty.

3.10Jak řešit zadání s parametrem aa

Na začátku si poznamenáš: nesmím dělit výrazem a−2a-2 bez rozlišení, zda a=2a=2.

Příklad:

x+y=1,x+ay=2.\begin{aligned}x+y&=1,\\x+ay&=2.\end{aligned}

Po R2←R2−R1R_2\leftarrow R_2-R_1 dostaneš (a−1)y=1(a-1)y=1.

  • Pro a≠1a\ne1: y=1/(a−1)y=1/(a-1) a x=1−1/(a−1)=(a−2)/(a−1)x=1-1/(a-1)=(a-2)/(a-1).
  • Pro a=1a=1: rovnice se změní na 0=10=1, takže soustava nemá řešení.

Univerzální pravidlo: výrazy, podle nichž bys dělil, jsou kandidáti na kritické hodnoty parametru. Pro každou kritickou hodnotu se vrať do matice před dělením a samostatně dopočítej hodnosti.

3.11Nejčastější chyby

  1. Přepíšeš špatně znaménko v jednom řádku. Piš explicitně R3←R3−2R1R_3\leftarrow R_3-2R_1.
  2. Zapomeneš provést operaci i na pravé straně rozšířené matice.
  3. Považuješ nulový řádek za „bez řešení“. Nulový řádek znamená redundantní rovnici; spor je až [0⋯0∣c≠0][0\cdots0\mid c\ne0].
  4. Zapomeneš přidat parametry za volné proměnné.
  5. Zaměníš počet řádků a počet pivotů.
  6. Vydělíš parametrickým výrazem, který může být nulový.

3.12Dvě kontrolní úlohy

  • {x+2y=53x+6y=15\begin{cases}x+2y=5\\3x+6y=15\end{cases} → nekonečně mnoho řešení, (x,y)=(5−2t,t)(x,y)=(5-2t,t).
  • {x+2y=53x+6y=14\begin{cases}x+2y=5\\3x+6y=14\end{cases} → žádné řešení.

Přenos do dalších kapitol: stejná eliminace tě bude provázet při počítání hodnosti, inverzní matice, báze, vlastních vektorů i ortogonálních projekcí.