Nedourčená soustava rovnic
Soustava lineárních rovnic, která obsahuje více neznámých než rovnic, se v lineární algebře nazývá nedourčená. (Na rozdíl od přeurčené soustavy, která má více rovnic než neznámých.)
Matice nedourčené soustavy lineárních rovnic má více sloupců než řádků.
Terminologie
[editovat | editovat zdroj]Terminologii lze vysvětlit pomocí počítání omezujících podmínek. Každou neznámou lze považovat za stupeň volnosti. Každou rovnici soustavy lze považovat za omezení, které omezuje jeden stupeň volnosti. Hraniční případ mezi přeurčenou a nedourčenou soustavou nastává, když se počet rovnic shoduje s počtem neznámých. Pro každou neznámou, která dává stupeň volnosti, existuje odpovídající omezení, které jeden stupeň volnosti odstraňuje. Nedourčený případ naopak nastává, je-li soustava nedostatečně omezená, čili když počet neznámých převyšuje počet rovnic.
Řešení nedourčených soustav
[editovat | editovat zdroj]Nedourčená soustava mívá často více řešení (v reálném a komplexním případě nekonečně mnoho), ale nemusí mít žádné řešení a nikdy nemá jednoznačné řešení.
Příkladem nedourčené soustavy nemající žádné řešení (neboli nekonzistentní soustavy) je:
Na druhou stranu, následující soustava nad reálnými čísly
je konzistentní a má nekonečně mnoho řešení, mimo jiná nebo . Všechna tato řešení lze získat z rozdílu obou rovnic, z nějž vyplývá, že všechna řešení splňují . Po substituci za do první rovnice je vidět, že může nabývat jakýchkoli hodnot, a že pro první neznámou pak platí .
Přesněji řečeno, podle Frobeniovy věty je každá soustava lineárních rovnic (nedourčená i jiná) nekonzistentní, právě když je hodnost rozšířené matice soustavy větší než hodnost matice soustavy. Pokud se naopak hodnosti těchto dvou matic shodují, má soustava alespoň jedno řešení. V nedourčené soustavě je tato hodnost nutně menší než počet neznámých, a tak v reálném či komplexním případě má soustava nutně nekonečně mnoho řešení. Obecné řešení má volných parametrů, kde je rozdíl mezi počtem proměnných a hodností.
Pro rozhodnutí, zda má nedourčená soustava řešení, a pokud nějaká má, vyjádřit všechna řešení jako lineární funkce proměnných, je možné využít např. Gaussovu eliminaci nebo Mooreovu–Penroseovu pseudoinverzní matici . Přibližné řešení reálných a komplexních nekonzistentních soustav lze získat např. metodou nejmenších čtverců.
Homogenní soustavy
[editovat | editovat zdroj]Homogenní soustava lineárních rovnic je ve tvaru a tato má vždy triviální řešení . Nedourčená homogenní soustava lineárních rovnic má vždy alespoň jedno netriviální řešení a tato řešení tvoří vektorový prostor, jehož dimenze je rovna rozdílu počtu neznámých a hodnosti matice soustavy.
Nedourčené polynomiální soustavy
[editovat | editovat zdroj]Hlavní vlastnost lineárních nedourčených soustav, že buď nemají žádné řešení nebo jich mají nekonečně mnoho, lze zobecnit soustavy polynomiálních rovnic následujícím způsobem.
O soustavě polynomiálních rovnic, která má méně rovnic než neznámých, se říká, že je nedourčená. Buď má nekonečně mnoho komplexních řešení (nebo obecněji řešení v algebraicky uzavřeném tělese), nebo je nekonzistentní. Podle Hilbertovy věty o nulách je soustava nekonzistentní, právě když rovnici lze získat z daných rovnic lineární kombinací s polynomiálními koeficienty. Má-li nedourčená soustava rovnic v proměnných () v komplexním oboru alespoň jedno řešení, pak množina všech jejích řešení je algebraická varieta dimenze alespoň . Je-li nedourčená reálná či komplexní soustava vybrána náhodně, má množina řešení skoro jistě dimenzi .
Jiné typy podmínek
[editovat | editovat zdroj]Obecně platí, že nedourčená soustava reálných lineárních rovnic má nekonečný počet řešení, pokud vůbec nějaké existuje. V optimalizačních problémech s lineárními podmínkami, jsou však relevantní pouze řešení, která dávají optimální (dle zadání problému buď nejvyšší nebo nejnižší) hodnotu účelové funkce.
V některých problémech je stanoveno, že jedna nebo více neznámých musí nabývat celočíselných hodnot. Celočíselné omezení vede k celočíselnému programování a problémům s diofantickými rovnicemi, které mohou mít pouze konečný počet řešení.
Jiný druh omezení, který se objevuje v teorii kódování, zejména v samoopravných kódech a v kódech pro zpracování signálů (například pro komprimované snímání), spočívá ve stanovení horní meze na počet nenulových složek řešení. U samoopravných kódů toto omezení odpovídá maximálnímu počtu chyb, které lze opravit najednou. Také je možné hledat tzv. řídké řešení s co nejmenším počtem nenulových složek. [1]
Odkazy
[editovat | editovat zdroj]Reference
[editovat | editovat zdroj]V tomto článku byl použit překlad textu z článku Underdetermined system na anglické Wikipedii.
Literatura
[editovat | editovat zdroj]- HLADÍK, Milan. Lineární algebra (nejen) pro informatiky. 1. vyd. Praha: Matfyzpress, 2019. 328 s. ISBN 978-80-7378-378-5. S. 39.
- OLŠÁK, Petr. Lineární algebra [online]. Praha: 2007 [cit. 2023-02-20]. Dostupné online.