Wikipedista:Jirka Fiala/Pískoviště - en

V matematice je soustava rovnic považován za přeurčený, pokud existuje více rovnic než neznámých. Přeurčená soustava je téměř vždy nekonzistentní (nemá žádné řešení), když je konstruován s náhodnými koeficienty. Přeurčená soustava však bude mít v některých případech řešení, například pokud se některá rovnice vyskytuje v soustavě několikrát nebo pokud jsou některé rovnice lineárními kombinacemi ostatních.

Terminologii lze popsat z hlediska konceptu počítání omezení . Na každou neznámou lze pohlížet jako na dostupný stupeň svobody. Na každou rovnici zavedenou do soustavy lze pohlížet jako na omezení, které omezuje jeden stupeň volnosti . Kritický případ tedy nastává, když se počet rovnic a počet volných proměnných rovná. Pro každou proměnnou poskytující stupeň volnosti existuje odpovídající omezení. Přeurčený případ nastává, když je soustava přehnaně omezen — to znamená, když rovnice převyšují počet neznámých. Naproti tomu nedostatečně určený případ nastává, když je soustava omezený – to znamená, když je počet rovnic menší než počet neznámých. Takové soustavy mají obvykle nekonečné množství řešení.

Předurčené lineární soustavy rovnic

Příklad ve dvou rozměrech

#1 soustava tří lineárně nezávislých rovnic, tři řádky, žádná řešení

#2 soustava tří lineárně nezávislých rovnic, tři řádky (dvě rovnoběžné ), žádná řešení

#3 soustava tří lineárně nezávislých rovnic, tři řádky (všechny rovnoběžné), žádná řešení

#4 soustava tří rovnic (jedna rovnice lineárně závislá na ostatních), tři řádky (dvě shodné), jedno řešení

#5 soustava tří rovnic (jedna rovnice lineárně závislá na ostatních), tři řádky, jedno řešení

#6 soustava tří rovnic (dvě rovnice každá lineárně závislá na třetí), tři shodné čáry, nekonečno řešení

Uvažujme soustava 3 rovnic a 2 neznámých ( X a Y ), který je přeurčen, protože 3 > 2, a který odpovídá diagramu #1:

$${\begin{aligned}Y&=-2X-1\\Y&=3X-2\\Y&=X+1\end{aligned}}$$

. Pro každou dvojici lineárních rovnic existuje jedno řešení: pro první a druhou rovnici (0,2, −1,4), pro první a třetí (−2/3, 1/3) a pro druhý a třetí (1,5, 2.5). Neexistuje však řešení, které by uspokojilo všechny tři současně. Diagramy #2 a 3 ukazují další konfigurace, které jsou nekonzistentní, protože žádný bod není na všech úsecích. Soustavy tohoto druhu jsou považovány za nekonzistentní.

Jediné případy, kdy přeurčená soustava má ve skutečnosti řešení, jsou ukázány v diagramech #4, 5 a 6. Tyto výjimky mohou nastat pouze tehdy, když přeurčený soustava obsahuje dostatek lineárně závislých rovnic, aby počet nezávislých rovnic nepřesáhl počet neznámých. Lineární závislost znamená, že některé rovnice lze získat lineárním kombinováním jiných rovnic. Například Y = X + 1 a 2 Y = 2 X + 2 jsou lineárně závislé rovnice, protože druhou lze získat tím, že vezmeme dvojnásobek první.

Maticová forma

Jakýkoli soustava lineárních rovnic lze zapsat jako maticovou rovnici. Předchozí soustava rovnic (v diagramu č. 1) lze zapsat následovně:

$${\begin{bmatrix}2&1\\-3&1\\-1&1\\\end{bmatrix}}{\begin{bmatrix}X\\Y\end{bmatrix}}={\begin{bmatrix}-1\\-2\\1\end{bmatrix}}$$

Všimněte si, že počet řádků matice koeficientů (odpovídajících rovnicím) převyšuje počet sloupců (odpovídajících neznámým), což znamená, že soustava je přeurčená. Hodnost této matice je 2, což odpovídá počtu závislých proměnných v soustavě. Lineární soustava je konzistentní právě tehdy, když matice koeficientů má stejnou úroveň jako její rozšířená matice (matice koeficientů s přidaným sloupcem navíc, přičemž tento sloupec je sloupcovým vektorem konstant). Rozšířená matice má hodnost 3, takže soustava je nekonzistentní. Nulita je 0, což znamená, že nulový prostor obsahuje pouze nulový vektor a nemá tedy žádnou bázi.

V lineární algebře jsou pojmy řádkový prostor, sloupcový prostor a nulový prostor důležité pro určení vlastností matic. Neformální diskuse o omezeních a stupních volnosti výše se přímo vztahuje k těmto formálnějším konceptům.

Homogenní případ

Homogenní případ (ve kterém jsou všechny konstantní členy nulové) je vždy konzistentní (protože existuje triviální řešení s úplnou nulou). Existují dva případy v závislosti na počtu lineárně závislých rovnic: buď existuje pouze triviální řešení, nebo existuje triviální řešení plus nekonečná množina dalších řešení.

Uvažujme soustavu lineárních rovnic: L _i = 0 pro 1 ≤ i ≤ M, a proměnné X ₁, X ₂, ... , X _N, kde _každé Li je vážený součet X _i s. Pak X ₁ = X ₂ = ⋯ = X _N = 0 je vždy řešení. Když M < N je soustava podurčený a vždy existuje nekonečno dalších řešení. Ve skutečnosti je rozměr prostoru řešení vždy alespoň N − M .

Pro M ≥ N nemusí existovat jiné řešení, než že všechny hodnoty jsou 0. Nekonečno dalších řešení bude pouze tehdy, když soustava rovnic bude mít dostatek závislostí (lineárně závislých rovnic), aby počet nezávislých rovnic byl nejvýše N − 1. Ale s M ≥ N by počet nezávislých rovnic mohl být až N, v takovém případě je triviální řešení jediné.

Nehomogenní případ

V soustavách lineárních rovnic platí L _i = c _i pro 1 ≤ i ≤ M, v proměnných X ₁, X ₂, ... , X _N rovnice jsou někdy lineárně závislé; ve skutečnosti počet lineárně nezávislých rovnic nemůže překročit N +1. Máme následující možné případy pro přeurčená soustava s N neznámými a M rovnicemi ( M > N ).

• M = N +1 a všechny M rovnice jsou lineárně nezávislé . Tento případ nepřináší žádné řešení. Příklad: x = 1, x = 2.
• M > N, ale pouze K rovnic ( K < M a K ≤ N +1) je lineárně nezávislých. Existují tři možné dílčí případy:
  • K = N +1. Tento případ nepřináší žádné řešení. Příklad: 2 x = 2, x = 1, x = 2.
  • K = N. Tento případ vede buď k jedinému řešení, nebo k žádnému řešení, přičemž druhé nastane, když vektor koeficientů jedné rovnice lze replikovat váženým součtem vektorů koeficientů jiných rovnic, ale vážený součet aplikovaný na konstantní členy ostatních rovnic ano. nereplikuje konstantní člen jedné rovnice. Příklad s jedním řešením: 2 x = 2, x = 1. Příklad bez řešení: 2 x + 2 y = 2, x + y = 1, x + y = 3.
  • K < N . Tento případ poskytuje buď nekonečně mnoho řešení, nebo žádné řešení, přičemž druhé nastává jako v předchozím dílčím případu. Příklad s nekonečně mnoha řešeními: 3 x + 3 y = 3, 2 x + 2 y = 2, x + y = 1. Příklad bez řešení: 3 x + 3 y + 3 z = 3, 2 x + 2 y + 2 z = 2, x + y + z = 1, x + y + z = 4.

Tyto výsledky mohou být snáze srozumitelné, když rozšířenou matici koeficientů soustavy vložíte do řádkové řady pomocí Gaussovy eliminace . Tato řádková forma je rozšířená matice soustavy rovnic, která je ekvivalentní dané soustavě (má přesně stejná řešení). Počet nezávislých rovnic v původním soustavě je počet nenulových řádků v odstupňovaném tvaru. Soustava je nekonzistentní (žádné řešení) tehdy a jen tehdy, když poslední nenulový řádek ve tvaru řady má pouze jeden nenulový záznam, který je v posledním sloupci (dává rovnici 0 = c, kde c je nenulová konstanta) . Jinak existuje právě jedno řešení, kdy je počet nenulových řádků v odstupňovaném tvaru roven počtu neznámých, a existuje nekonečně mnoho řešení, kdy je počet nenulových řádků nižší než počet proměnných.

Řečeno jinak, podle Frobeniovy věty je jakákoli soustava rovnic (přeurčený nebo jinak) nekonzistentní, pokud je hodnost rozšířené matice větší než hodnost matice koeficientů . Pokud jsou naopak pořadí těchto dvou matic stejné, soustava musí mít alespoň jedno řešení. Řešení je jedinečné právě tehdy, když se hodnost rovná počtu proměnných. Jinak má obecné řešení k volných parametrů, kde k je rozdíl mezi počtem proměnných a hodností; proto v takovém případě existuje nekonečno řešení.

Přesná řešení

Pomocí maticové algebry lze získat všechna přesná řešení, nebo lze ukázat, že žádné neexistuje. Viz soustava lineárních rovnic#Řešení matice .

Přibližná řešení

Metoda obyčejných nejmenších čtverců může být použita k nalezení přibližného řešení přeurčené soustavy. Pro soustava $A\mathbf {x} =\mathbf {b} ,$ z úlohy se získá vzorec nejmenších čtverců

$$\min _{\mathbf {x} }\lVert A\mathbf {x} -\mathbf {b} \rVert ,$$

jehož řešení lze zapsat normálními rovnicemi

$$\mathbf {x} =\left(A^{\mathsf {T}}A\right)^{-1}A^{\mathsf {T}}\mathbf {b} ,$$

kde ${\mathsf {T}}$ označuje maticovou transpozici za předpokladu $\left(A^{\mathsf {T}}A\right)^{-1}$ existuje (tj. za předpokladu, že A má úplné pořadí sloupce ). S tímto vzorcem se najde přibližné řešení, když žádné přesné řešení neexistuje, a poskytuje přesné řešení, když nějaké existuje. Pro dosažení dobré numerické přesnosti je však preferováno použití QR faktorizace A k vyřešení problému nejmenších čtverců.

Použití QR faktorizace

QR rozklad (vysoké) matice $A$ je reprezentace matice ve formě produktu,

$A=QR,$

kde $Q$ je (vysoká) semiortonormální matice, která pokrývá rozsah matice $A$, a kde $R$ je (malá) čtvercová pravoúhelníková matice.

Řešení problému minimalizace normy $\|Ax-b\|^{2}$ se pak uvádí jako

$x=R^{-1}Q^{T}b,$

kde v praxi místo počítání $R^{-1}$ jeden by měl provést běh zpětné substituce na pravoúhlém soustavau

$Rx=Q^{T}b.$

Použití dekompozice singulární hodnoty

Dekompozice singulární hodnoty (SVD) (vysoké) matice $A$ je reprezentace matice ve formě produktu,

$A=USV^{T},$

kde $U$ je (vysoká) semiortonormální matice, která pokrývá rozsah matice $A$, $S$ je (malá) čtvercová diagonální matice s nezápornými singulárními hodnotami podél úhlopříčky a kde $V$ je (malá) čtvercová ortonormální matice.

Řešení problému minimalizace normy $\|Ax-b\|^{2}$ se pak uvádí jako

$x=VS^{-1}U^{T}b.$

Předurčené nelineární soustavy rovnic

V konečných rozměrných prostorech může být soustava rovnic zapsán nebo reprezentován ve formě

$\left\{{\begin{array}{ccc}f_{1}(x_{1},\ldots ,x_{n})&=&0\\\vdots &\vdots &\vdots \\f_{m}(x_{1},\ldots ,x_{n})&=&0\end{array}}\right.$

nebo ve formě $\mathbf {f} (\mathbf {x} )=\mathbf {0}$ s

$\mathbf {f} (\mathbf {x} )=\left[{\begin{array}{c}f_{1}(x_{1},\ldots ,x_{n})\\\vdots \\f_{m}(x_{1},\ldots ,x_{n})\end{array}}\right]\;\;\;{\mbox{and}}\;\;\;\mathbf {0} =\left[{\begin{array}{c}0\\\vdots \\0\end{array}}\right]$

kde $\mathbf {x} =(x_{1},\ldots ,x_{n})$ je bodem v $\mathbb {R} ^{n}$ nebo $C^{n}$ a $f_{1},\ldots ,f_{m}$ jsou reálné nebo komplexní funkce. Soustava je přeurčená, pokud $m>n$. Naproti tomu soustava je nedourčená soustava pokud $m<n$ .

Jako efektivní metoda pro řešení přeurčených soustav Gauss-Newtonova iterace lokálně kvadraticky konverguje k řešením, ve kterých jsou jakobijské matice $\mathbf {f} (\mathbf {x} )$ jsou injektivní.

V obecném použití

Tento koncept lze také aplikovat na obecnější soustavy rovnic, jako jsou soustavy polynomických rovnic nebo parciální diferenciální rovnice . V případě soustav polynomických rovnic se může stát, že předurčená soustava má řešení, ale že žádná rovnice není důsledkem ostatních a že při odstranění jakékoli rovnice má nová soustava řešení více. Například, $(x-1)(x-2)=0,(x-1)(x-3)=0$ má jediné řešení $x=1,$ ale každá rovnice má sama o sobě dvě řešení.

Viz také

• Nedourčená soustava rovnic
• Frobeniova věta
• Metoda nejmenších čtverců
• Komprimované snímání
• Pseudoinverze matice

[[Kategorie:Lineární algebra]]