Přeskočit na obsah

Nedourčená soustava rovnic

Z Wikipedie, otevřené encyklopedie

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]
Podrobnější informace naleznete v článku Soustava lineárních rovnic.

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]

V tomto článku byl použit překlad textu z článku Underdetermined system na anglické Wikipedii.

  1. Hrbáček, R.; Rajmic, P.; Veselý, V. & Špiřík, J. Řídké reprezentace signálů: úvod do problematiky. Elektrorevue – Internetový časopis, 2011, 1-10 [1]

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. 

Související články

[editovat | editovat zdroj]