Soustava lineárních rovnic

V matematice se soustavou lineárních rovnic označuje systém jedné nebo více lineárních rovnic se společnými neznámými.

Příkladem soustavy tří lineárních rovnic o třech neznámých je:

Jsou-li neznámým proměnným přiřazeny hodnoty tak, že všechny rovnice soustavy platí zároveň, nazývá se tato volba hodnot řešením soustavy. V naší ukázce je řešením uspořádaná trojice , protože splňuje všechny tři rovnice současně. Slovo „soustava“ naznačuje, že podmínky dané rovnicemi je třeba splnit najednou, nikoli jen některé.

Soustava lineárních rovnic je ústřední pojem lineární algebry, oboru, který je používán ve mnoha oblastech moderní matematiky. Algoritmy pro nalezení řešení jsou důležitou součástí numerické lineární algebry.

Důležitost této oblasti matematiky spočívá v tom, že fyzikální modely bývají metodou konečných prvků nebo metodou konečných diferencí převáděny na úlohy s obrovskými soustavami lineárních rovnic. Proto hrají metody pro práci s těmito rovnicemi a algoritmy pro řešení těchto rovnic významnou roli ve strojírenství, fyzice, chemii, informatice a ekonomii. 

Soustava nelineárních rovnic může být často aproximována lineární soustavou rovnic (viz lineární aproximace), což je užitečná technika při vytváření matematického modelu, počítačové simulace nějakého komplexního systému. 

Řešení soustav lineárních rovnic se uplatňuje ve speciálních optimalizačních úlohách nazývaných lineární programování.

Velmi často jsou koeficienty rovnic i hledaná řešení reálná nebo komplexní čísla, ale celá teorie lineární algebry i její algoritmy platí, i když se namísto čísel vezmou prvky libovolného algebraického tělesa. Pro řešení soustav v jiných algebraických strukturách byly vybudovány jiné postupy a jiné teorie. Například pro okruh celých čísel poskytuje celočíselné lineární programování řadu metod pro nalezení „nejlepšího“ celočíselného řešení. Dalším příkladem je teorie Gröbnerových bází, v níž se pro koeficienty i neznámé používají polynomy. Ještě exotičtějším příkladem je tropická geometrie.

Základní ukázky

Triviální příklad 
Soustava jedné rovnice o jedné reálné neznámé

 

má jednoznačné řešení

 

Nicméně, za soustavu bývá zpravidla považován systém s alespoň dvěma rovnicemi.

Jednoduchý netriviální příklad 
Nejjednodušší netriviální soustavu lineárních rovnic tvoří dvě rovnice o dvou neznámých, například:

 

Tuto soustavu lze vyřešit tak, že se z první rovnice vyjádří  v závislosti na :

 

a tento výraz se dosadí do druhé rovnice:

 

Výsledná rovnice má pouze jednu neznámou  s řešením . Zpětným dosazením do první rovnice lze dopočítat hodnotu neznámé . 

Uvedený postup lze zobecnit pro soustavy s více neznámými (viz odstavec „eliminace neznámých“ níže nebo článek o elementární algebře).

Obecný tvar 
Soustava  lineárních rovnic o  neznámých  bývá obvykle zapsána ve tvaru

kde proměnné , … , jsou neznámé a čísla   jsou koeficienty soustavy. Čísla , kde , jsou absolutní členy soustavy (též tzv. pravá strana soustavy). Koeficienty i absolutní členy mohou být prvky libovolného tělesa, tedy kromě reálných čísel jimi mohou být např. i komplexní čísla.

Soustavu lze popsat i úsporněji, např. ve složkovém zápisu:
 pro .

Maticová rovnice 
Koeficienty soustavy bývají obvykle uspořádány do matice:

Tuto matici nazýváme matice soustavy.

Pro neznámé a pravou stranu soustavy se použijí sloupcové vektory

Celou soustavu rovnic je pak lze zapsat s pomocí maticového součinu jedinou rovnicí
 
neboli

Pro výpočet řešení soustavy lineárních rovnic bývá často využívána tzv. rozšířená matice soustavy

ze které lze zjistit existenci a jednoznačnost řešení, např. Gaussovou eliminační metodou.

Vektorová rovnice 
Na řešení soustavy lineárních rovnic lze pohlížet i tak, že neznámé jsou koeficienty lineární kombinace, v níž je vektor pravých stran zapsán pomocí sloupcových vektorů koeficientů:

 

Tento pohled umožňuje uplatnit veškeré nástroje z teorie vektorových prostorů (obecněji modulů). Například množina všech možných lineárních kombinací vektorů na levé straně se nazývá lineární obal a uvedená rovnice má řešení, právě když se vektor pravých stran patří do tohoto obalu.

Homogenní soustava lineárních rovnic 
Jsou-li všechny absolutní členy soustavy rovny nule, nazývá se soustava homogenní. Homogenní soustavy mají zápis ve tvaru
,
což v rozvinutém tvaru znamená

neboli
 pro ,
Pokud je alespoň jeden z absolutních členů  nenulový, jde o nehomogenní soustavu lineárních rovnic.

Každá homogenní soustava má alespoň jedno řešení, označované jako nulové (neboli triviální) řešení, ve kterém je každé neznámé přiřazeno číslo 0. Pokud je matice soustavy regulární, jde o jediné řešení. Je-li naopak singulární, je řešení více. 

Množina řešení homogenní soustavy lineárních rovnic  má následující vlastnosti:

 Jsou-li  a  jsou dvě řešení, pak jejich vektorový součet  je také řešením.
 Je-li  řešení soustavy a  je libovolný skalár, pak  je také řešením.

Jinými slovy, množina řešení tvoří vektorový prostor nazývaný jádro matice . Jádro se značí  (z anglického kernel = jádro). Někdy se též nazývá nulový prostor matice .

Množina řešení 

Při řešení nehomogenní soustavy nad nekonečným tělesem, což jsou například reálná či komplexní čísla, mohou nastat následující případy:
 soustava nemá řešení
 soustava má jedno řešení
 soustava má nekonečně mnoho řešení

Nad konečnými tělesy soustava nemá žádné řešení nebo jich může mít jen konečně mnoho (jedno nebo více).

Homogenní soustava lineárních algebraických rovnic má vždy triviální řešení, tzn.  pro všechna .

Geometrická interpretace 

Množiny řešení soustav o dvou reálných neznámých lze znázornit v euklidovské rovině v níž osy odpovídají neznámým  a .  Lineární rovnice odpovídají přímkám (s výjimkou triviálních rovnic se všemi koeficienty nulovými). Protože řešení soustavy musí splňovat všechny rovnice, tvoří množina řešení průnik těchto přímek. Průnikem pak může být buď jediný bod, prázdná množina nebo i přímka - to v případě, že přímky odpovídající rovnicím splývají.

Lineární rovnice o třech reálných neznámých určuje zpravidla rovinu v trojrozměrném euklidovském prostoru. Množina řešení je pak průsečíkem těchto rovin a může to být buď rovina, přímka, jeden bod nebo prázdná množina. Například rovnoběžné roviny v prostoru se neprotínají vůbec. 

Je-li neznámých , pak netriviální lineární rovnice určují nadroviny v -rozměrném prostoru. Množina řešení je průnikem těchto nadrovin a má dimenzi nejvýše  (vyjma triviálního případu, kdy matice soustavy je nulová).

Případy v obecné poloze 
Podle počtu rovnic a neznámých se rozlišují následující případy:
 Má-li soustava stejný počet rovnic jako neznámých, bývá její řešení často jednoznačné.
 Má-li soustava více rovnic než neznámých, nazývá se přeurčená. U soustav s daty z praxe zpravidla nemívá řešení.
 Má-li soustava méně rovnic než neznámých, nazývá se nedourčená. Řešení je zpravidla více. Soustava nemusí mít řešení, ale řešení nikdy není jednoznačné.

Následující obrázky ilustrují tuto trichotomii v případě dvou neznámých:

{| border=0 cellpadding=5
|-
| width="150" align="center" | 
| width="150" align="center" | 
| width="150" align="center" | 
|-
|align="center"| Jedna rovnice
|align="center"| Dvě rovnice
|align="center"| Tři rovnice
|}

První soustava má nekonečně mnoho řešení, jmenovitě všechny body na modré přímce. Druhá soustava má jediné řešení, a to průnik dvou přímek. Ve třetím případě soustava nemá žádné řešení, protože tři zakreslené přímky nemají společný průnik.

Je třeba mít na paměti, že obrázky výše ukazují pouze obvyklý případ, kdy jsou přímky v tzv. obecné poloze. Může se stát, že soustava dvou rovnic o dvou neznámých nemá řešení a to tehdy, jsou-li přímky rovnoběžné. Podobně se u soustavy tří rovnic mohou odpovídající tři přímky protnout ve společném bodě anebo mohou některé přímky splynout.

Formálně řečeno, soustava lineárních rovnic se chová odlišně od uvedených případů v obecné poloze, pokud jsou rovnice lineárně závislé, nebo pokud je soustava nekonzistentní a nemá více rovnic než neznámých.

Vlastnosti

Nezávislost 
Stane-li se, že některá rovnice soustavy je lineární kombinací ostatních rovnic, pak tato rovnice neklade na řešení soustavy žádné další podmínky, je nadbytečná (nadpočetná), a lze ji ze soustavy rovnic vyloučit aniž by se změnila množina řešení. Tento postup lze opakovat, dokud výsledná soustava rovnic neobsahuje jen lineárně nezávislé rovnice.

Rovnice lineární soustavy jsou nezávislé, pokud žádnou z nich nelze algebraicky odvodit z ostatních. 

Například rovnice

  a 

jsou závislé — jde o stejné rovnice, jen ve druhé jsou všechny koeficienty dvojnásobné. Obě odpovídají téže přímce. 

Rovnice soustavy

 

jsou také závislé, protože třetí rovnice je součtem předchozích dvou. Ve skutečnosti lze kteroukoli z těchto rovnic odvodit z ostatních dvou a kteroukoli z rovnic lze odstranit, aniž by se změnila množina řešení. Odpovídající tři přímky se protínají v jednom bodě.

Konzistence 

Lineárně nezávislé rovnice mohou být vzájemně rozporné, tzn. levou stranu některé z rovnic lze vyjádřit jako lineární kombinaci levých stran ostatních, avšak pravá strana této rovnice není stejnou lineární kombinací pravých stran. Soustavu pak lze upravit ekvivalentními úpravami tak, že bude obsahovat dvě rovnice, jejichž levé strany jsou shodné, avšak pravé strany budou rozdílné. Výsledná soustava je vnitřně rozporná, neboli nekonzistentní a nemá žádné řešení. 

V ostatních případech je soustava konzistentní, což platí speciálně pro soustavy, jejichž levé strany jsou lineárně nezávislé.

U nekonzistentních soustav je možné z rovnic odvodit spor, třeba jako výrok .

Například rovnice

  a 

jsou nekonzistentní.  Spor  lze získat vydělením jejich rozdílu šesti. Odpovídající přímky jsou rovnoběžné.

Soustava

 

je nekonzistentní, protože součet prvních dvou je , a následné odečtení třetí dá . Na druhou stranu, jakákoli dvojice z těchto tří rovnic tvoří konzistentní soustavu, čili má řešení. Stejná situace může nastat pro více rovnic a proměnných.

Frobeniova věta 

Nehomogenní soustava lineárních algebraických rovnic má řešení, právě když hodnost matice soustavy je rovna hodnosti rozšířené matice soustavy: . V tomto případě je soustava konzistentní. Pokud je hodnost matice  rovna počtu neznámých, má soustava jedno řešení; pokud je  menší než počet neznámých, je řešení více. 

Hodnost matice  nemůže být z definice větší než počet neznámých, ale je-li hodnost rozšířené matice  soustavy  větší než počet neznámých, nemůže být splněna podmínka Frobeniovy věty, soustava je tudíž nekonzistentní a nemá žádné řešení.

Ekvivalence soustav 
Pokud dvě soustavy lineárních rovnic používají stejnou množinu neznámých a přitom lze každou z rovnic druhé soustavy odvodit algebraicky z rovnic v první i naopak, říká se o soustavách, že jsou si navzájem ekvivalentní. Nekonzistentní páry soustav jsou si vždy ekvivalentní. U konzistentních ekvivalentních soustav platí, že každá rovnice jedné z nich je lineární kombinací rovnic druhé. Dvě soustavy jsou si tudíž ekvivalentní, právě když mají stejnou množinu řešení.

Množiny řešení homogenních a nehomogenních soustav 
Je-li  nějaké konkrétní řešení soustavy , pak lze celou množinu řešení této soustavy popsat výrazem . Zde  značí jádro matice a tvoří ho všechna řešení soustavy .

Jinými slovy, množinu řešení soustavy  lze získat posunem jádra matice  o vektor .

Metody řešení

Popis řešení 
Má-li soustava jednoznačné řešení, lze ji přepsat na systém rovnic, v nichž na levé straně je vždy jen jedna neznámá a na pravé straně její hodnota, např. ,  a . Je-li dáno nějaké pořadí neznámých, například abecední, může být řešení popsáno vektorem hodnot, jako je  v uvedeném příkladě.

Aby bylo možné popsat i nekonečné množiny řešení, jsou některé neznámé označeny jako volné proměnné (nebo nezávislé nebo jako parametry), což znamená, že mohou nabývat libovolných hodnot. Zbývající proměnné jsou pak závislé na hodnotách volných proměnných. Někdy se nazývají bázické proměnné.

Řešení reálné soustavy

 

lze popsat rovnicemi:

  a 

Zde  je volná proměnná, zatímco  a  závisí na . Jakékoli řešení lze získat tak, že se nejprve zvolí hodnota  a z ní se spočítají odpovídající hodnoty pro  a .

Každá volná proměnná dává prostoru řešení jeden stupeň volnosti. Počet volných proměnných je dimenze množiny řešení. Například řešení výše uvedené soustavy tvoří jednodimenzionální prostor - přímku, protože každé řešení lze získat volbou hodnoty jednoho parametru . 

Různé volby volné proměnné poskytují různé popisy stejné množiny řešení. Například 

  a .

je alternativním popisem téže množiny řešení, jen  je zde volná proměnná a  a  jsou závislé.

Eliminace proměnných 
Nejjednodušší metodou řešení soustav lineárních rovnic je eliminace proměnných. Tuto metodu lze popsat následovně:

 Z první rovnice se vyjádří jedna z neznámých pomocí ostatních.
 Tento výraz se dosadí do zbývajících rovnic, čím se získá soustava rovnic, která má o jednu rovnici a o jednu neznámou méně.
 Kroky 1 a 2 se opakují tak dlouho, dokud se soustava nezredukuje na jedinou lineární rovnici.
 Výsledná rovnice se vyřeší a pak zpětným dosazením se určí celé řešení.
 
Například v následující soustavě:

lze z první rovnice vyjádřit . Jeho dosazením do druhé a třetí rovnice 

se soustava zredukuje na

Z první rovnice lze vyjádřit  a jeho dosazením do druhé získat 

Dosazení   do vyjádření pro  dává . Z hodnot  a  se pak dopočítá . Řešením soustavy je uspořádaná trojice .

Gaussova eliminace 
Gaussova eliminace vychází z poznatku, že rozšířenou matici soustavy lze měnit vhodným způsobem tak, aniž by se změnila množina řešení soustavy. Pro tento účel se používají následující elementární ekvivalentní řádkové úpravy:

 Typ 1 : změna pořadí řádků
 Typ 2 : vynásobení řádku nenulovým skalárem
 Typ 3 : přičtení jednoho řádku (nebo jeho skalárního násobku) k jinému

Uvedené operace jsou vratné, a proto získaná rozšířená matice odpovídá soustavě, která je ekvivalentní původní.

Redukci lze provádět různými způsoby. Mezi jednoduché patří Gaussova eliminace a Gauss-Jordanova eliminace. Gauss-Jordanova eliminace matice soustavy z předchozího příkladu odpovídá následujícímu výpočtu:

 

Z poslední matice lze snadno odvodit řešení ,  a . Srovnání s výpočtem v předchozím odstavci o eliminaci proměnných naznačuje, že obě metody jsou ve skutečnosti stejné; rozdíl je jen v zápisu výpočtu.

Cramerovo pravidlo 
Cramerovo pravidlo poskytuje vzorec pro řešení soustav lineárních rovnic s regulární maticí. Hodnoty neznámých jsou dány podílem dvou determinantů. Například řešení soustavy

 

je dáno podíly

 

Pro každou proměnnou je ve jmenovateli determinant matice koeficientů soustavy, zatímco v čitateli je determinant obdobné matice, jen sloupec odpovídající neznámé byl nahrazen vektorem pravých stran.

Cramerovo pravidlo je důležité spíše z teoretického hlediska, protože výpočet mnoha velkých determinantů je poněkud těžkopádný. (Velké determinanty se skutečně nejsnáze vypočítají pomocí redukce řádků.) Navíc je Cramerovo pravidlo numericky nestabilní, takže není vhodné ani pro přesné řešení malých soustav, ledaže by aritmetické operace byly prováděny v racionální aritmetice s neomezenou přesností.

Maticové řešení 
Množinu řešení soustav  lze popsat i maticovým výrazem. U soustav s regulární maticí  je jednoznačné řešení dané vztahem

 

kde  je inverzní matice k matici . 

V obecném případě, tedy bez ohledu na to, zda je matice soustavy regulární ba dokonce čtvercová, lze všechna řešení (pokud nějaká existují) popsat pomocí Mooreovy–Penroseovy inverze k , označované  následovně:

 

kde  je vektor volných parametrů. Nezbytnou a postačující podmínkou pro existenci řešení je, že potenciální řešení získané dosazením  splňuje , neboli  Pokud tato podmínka neplatí, soustava rovnic je nekonzistentní a nemá žádné řešení. Pokud podmínka platí, soustava je konzistentní a má alespoň jedno řešení. Například ve výše uvedeném případě, kdy  je čtvercová a má plnou hodnost, se  shoduje s  a obecná rovnice řešení se zjednoduší na již známý vztah

 

Během algebraických úprav byl vektor  zcela eliminován a řešení je jednoznačné. V ostatních případech však  zůstane, přičemž volby vektoru  určují množinu řešení rovnice.

Jiné metody 
Zatímco soustavy tří nebo čtyř rovnic lze snadno vyřešit ručně, pro větší soustavy se často používají počítače. Standardní algoritmus pro řešení soustav lineárních rovnic bývá založen na Gaussově eliminaci. Pro numerickou stabilitu je vhodné se vyvarovat dělení malými čísly, například volbou pořadí rovnic. Tento proces se nazývá pivotování. Namísto Gaussovy eliminace, se spíše počítá související LU rozklad matice . Ten bývá výhodný, zejména je-li třeba vyřešit několik soustav se shodnou maticí , ale různými vektory .

Rychlejší anebo přesnější algoritmy byly navrženy pro matice  s nějakou speciální strukturou. Například Choleského rozklad bývá rychlejší pro soustavy s pozitivně definitní maticí. Levinsonova rekurze je rychlá metoda pro Toeplitzovy matice. Dalším příkladem matic, pro něž jsou známy speciální metody jsou řídké matice, což jsou matice s mnoha nulovými prvky. Tyto matice se hojně objevují v praktických aplikacích.

Numerická řešení homogenní soustavy lze nalézt pomocí singulárního rozkladu matice.

Zcela jiný přístup bývá třeba u velmi velkých soustav, jejichž přesné řešení by si vyžádalo příliš mnoho času nebo paměti. Pro ně se používají přibližné iterační metody. Po nalezení počáteční aproximace řešení (která nemusí být vůbec přesná) je přibližné řešení postupně zpřesňováno, dokud se dostatečně nepřiblíží ke skutečnému řešení. Efektivitu iteračních metod může být u některých řídkých matic zvýšena pomocí náhodnosti. 

Pro soustavy lineárních rovnic byl navržen i kvantový algoritmus.

Odkazy

Reference

Literatura

Související články 
 Hodnost matice
 Inverzní matice
 Gaussova eliminační metoda
 Cramerovo pravidlo
 LU rozklad
 Choleského rozklad
 Jacobiho metoda
 Metoda nejmenších čtverců
 Soustava rovnic
 Rovnice

Externí odkazy 
 
 Online výpočet soustav lineárních rovnic

Lineární algebra
Rovnice