Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

## Řešení soustavy úpravou matice

Definice (Elementární operace)

Následující tři operace nazýváme elementárními operacemi s maticí A (všechny jsou ekvivalentní vynásobení vhodnou regulární maticí zleva):

1. vynásobení i-tého řádku číslem
   (zapsáno formou maticového násobení )
2. vynásobení i-tého řádku číslem a přičtení k j-tému řádku,
   (maticový zápis )
3. výměna i-tého a j-tého řádku, (je možné složit z předcházejících dvou)
   (maticový zápis )

Věta (O elementárních operacích)

Elementární operace na rozšířené matici soustavy rovnic nemění množinu řešení soustavy.

Důkaz

Důkaz stačí pro operace 1. a 2., protože třetí je jejich kombinací. Pro úpravy:

1. Po úpravě jsou všechny rovnice (řádky matice) až na -tou nezměněné, tedy každé řešení původní soustavy je splňuje. Pro upravený řádek platí

   což je zřejmě také splněno. Podobně se dokáže, že každé řešení upravené matice splňuje i všechny rovnice původní.
2. Všechny řádky až na -tý jsou nezměněné a pro -tý řádek platí:

   a to je také splněno. Opačná implikace se dokáže podobně.

Definice (Odstupňovaný tvar matice)

Řekneme, že matice typu je v (řádkově) odstupňovaném tvaru, jestliže jsou splněny následující podmínky:

1. existuje takové, že řádky jsou nenulové a nulové
2. pro platí

Algoritmus (Řešení soustavy lin. rovnic)

Soustavu lineárních rovnic lze řešit následovně

1. Sestavit rozšířenou matici soustavy
2. Převést pomocí elementárních úprav matici do odstupňovaného tvaru
3. Pomocí zpětné substituce popsat všechna řešení

Algoritmus (Gaussova eliminace)

Gaussova eliminace je algoritmus pro úpravu dané matice na odstupňovaný tvar elementárními řádkovými úpravami. Postup:

1. Utřídíme řádky podle délek úseků počátečních nul vzestupně
2. Najdeme-li dva řádky se stejně dlouhým úsekem poč. nul ( ), potom k -tému řádku přičteme -násobek i-tého řádku
3. Kroky 1. - 2. opakujeme, dokud existují dva řádky se stejně dlouhým úsekem poč. nul.

Je zaručeno, že algoritmus skončí, protože s každým cyklem roste součet délek počátečních úseků nul všech řádků minimálně o 1 a ten je omezený číslem . Složitost algoritmu je .

Algoritmus (Zpětná substituce)

Buď rozšířená matice soustavy v odstupňovaném tvaru (získaná pomocí elementárních úprav). Pokud počáteční úsek nul na nějakém řádku má délku (tedy nenulové číslo je jen ve sloupci pravých stran), soustava nemá řešení. Jinak nazveme bázové proměnné ty, v jejichž sloupci je v nějakém řádku první nenulové číslo ( ), ostatní nazveme volné. Existuje potom jednoznačné přiřazení hodnot bázovým proměnným tak, že dohromady tvoří řešení soustavy. Každé řešení je navíc možné získat touto metodou.

Postup:

Indukcí podle . Nechť je i-tá bázová proměnná a hodnoty proměnných pro jsou dané (buď jsou volné, nebo využívám ind. předpoklad). Potom po dosazení do -té rovnice získám

tedy jednu rovnici o 1 neznámé, která má jednoznačné řešení. Libovolné řešení této soustavy lze získat touto metodou - stačí nastavit volné proměnné podle něj a bázové vyjdou správně, protože jejich hodnota je určena jednoznačně. Navíc které proměnné jsou volné a které jsou bázové je také určeno jednoznačně - jinak vždy najdu různé množiny řešení (což je pro stejnou soustavu rovnic nesmysl).

Algoritmus (Gauss-Jordanova eliminace)

Gauss-Jordanova eliminace je varianta Gaussovy eliminace, která převádí matici na tzv. redukovaný odstupňovaný tvar, to je takový tvar, kde v každém sloupci, příslušejícím nějaké bázové proměnné, je pouze jedno nenulové číslo. Zpětná substituce je pak jednodušší, ale je třeba více aritmetických operací (asymptoticky jsou však algoritmy stejné)

TODO: zkontrolovat & doplnit podrobněji

Poznámka

S řešením soustav rovnic Gaussovou metodou nastává problem při strojových výpočtech - i malá zaokrouhlovací chyba může způsobit velmi radikální změnu množiny řešení (takové matice soustav se nazývají špatně podmíněné).