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 ${\boldsymbol {A}}$ nedourčené soustavy lineárních rovnic ${\boldsymbol {Ax}}={\boldsymbol {b}}$ má více sloupců než řádků.

Terminologie

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

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:

{\begin{array}{rcrcrcl}x&+&y&+&z&=&1\\x&+&y&+&z&=&3\end{array}}

Na druhou stranu, následující soustava nad reálnými čísly

{\begin{array}{rcrcrcl}x&+&y&+&z&=&1\\x&+&y&+&2z&=&3\end{array}}

je konzistentní a má nekonečně mnoho řešení, mimo jiná $(x,y,z)=(1,-2,2),(2,-3,2)$ nebo $(3,-4,2)$ . 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í $z=2$ . Po substituci $2$ za $z$ do první rovnice je vidět, že $y$ může nabývat jakýchkoli hodnot, a že pro první neznámou pak platí $x=-1-y$ .

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á $k$ volných parametrů, kde $k$ 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 $k$ proměnných, je možné využít např. Gaussovu eliminaci nebo Mooreovu–Penroseovu pseudoinverzní matici ${\boldsymbol {A}}^{+}$ . Přibližné řešení reálných a komplexních nekonzistentních soustav lze získat např. metodou nejmenších čtverců.

Homogenní soustavy

Homogenní soustava lineárních rovnic je ve tvaru ${\boldsymbol {Ax}}={\boldsymbol {0}}$ a tato má vždy triviální řešení ${\boldsymbol {x}}={\boldsymbol {0}}$ . 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

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 $0=1$ lze získat z daných rovnic lineární kombinací s polynomiálními koeficienty. Má-li nedourčená soustava $t$ rovnic v $n$ proměnných ( $t<n$ ) v komplexním oboru alespoň jedno řešení, pak množina všech jejích řešení je algebraická varieta dimenze alespoň $n-t$ . Je-li nedourčená reálná či komplexní soustava vybrána náhodně, má množina řešení skoro jistě dimenzi $n-t$ .

Jiné typy podmínek

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

Reference

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

↑ 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

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

[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]

[1]