Zobrazení zdroje stránky Soustava lineárních rovnic

V [[matematika|matematice]] se '''soustavou lineárních rovnic''' označuje systém jedné nebo více [[lineární rovnice|lineárních rovnic]] se společnými [[Neznámá|neznámými]].

Příkladem soustavy tří lineárních rovnic o třech neznámých je:
[[Soubor:Secretsharing 3-point.svg|náhled|vpravo|V soustavě lineárních rovnic o třech neznámých určují rovnice polohu [[rovina|rovin]]. Souřadnice [[průsečík]]u jsou řešením soustavy.]]

<math>\begin{array}{rcrcrcr}
3x&+&2y&-&z&=&1\\
2x&-&2y&+&4z&=&-2\\
-x&+&\frac{1}{2}y&-&z&=&0
\end{array}
</math>

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í rovnice|řešením soustavy]]'''. V naší ukázce je řešením uspořádaná trojice <math>(x,y,z)=(1,-2,-2)</math>, 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í algebra|lineární algebry]], oboru, který je používán ve mnoha oblastech moderní matematiky. [[Algoritmus|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í [[metoda konečných prvků|metodou konečných prvků]] nebo [[metoda konečných diferencí|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 [[Inženýrství|strojírenství]], [[Fyzika|fyzice]], [[Chemie|chemii]], [[Matematická informatika|informatice]] a [[Ekonomie|ekonomii]]. 

Soustava nelineárních rovnic může být často [[Aproximace|aproximována]] lineární soustavou rovnic (viz [[lineární aproximace]]), což je užitečná technika při vytváření [[Matematický model|matematického modelu]], [[Počítačová simulace|počítačové simulace]] nějakého [[Komplexní systém|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 [[Koeficient|koeficienty]] rovnic i hledaná řešení [[Reálné číslo|reálná]] nebo [[Komplexní číslo|komplexní čísla]], ale celá teorie lineární algebry i její algoritmy platí, i když se namísto čísel vezmou prvky libovolného [[Komutativní těleso|algebraického tělesa]]. Pro řešení soustav v jiných [[Algebraická struktura|algebraických strukturách]] byly vybudovány jiné postupy a jiné teorie. Například pro [[Okruh (algebra)|okruh]] celých [[Celé číslo|čísel]] poskytuje [[Celočíselné programování|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í [[Polynom|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é

: <math>2x = 4</math>

má jednoznačné řešení

: <math>x = 2.</math>

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:

: <math>\begin{array}{rcrcr}
2x & + & 3y & = & 6 \\
4x & + & 9y & = & 15
\end{array}</math>

Tuto soustavu lze vyřešit tak, že se z první rovnice vyjádří <math>x</math> v závislosti na <math>y</math>:

: <math>x = 3 - \frac{3}{2}y</math>

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

: <math>4\left( 3 - \frac{3}{2}y \right) + 9y = 15.</math>

Výsledná rovnice má pouze jednu neznámou <math>y</math> s řešením <math>y = 1</math>. Zpětným dosazením do první rovnice lze dopočítat hodnotu neznámé <math>x = \frac{3}{2}</math>. 

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í algebra|elementární algebře]]).

== Obecný tvar ==
Soustava <math>m</math> lineárních rovnic o <math>n</math> [[Neznámá|neznámých]] <ref>{{Citace monografie
 | titul = Slovník školské matematiky
 | vydavatel = SPN
 | místo = Praha
 | rok = 1981
 | počet_stran = 240
}}</ref> bývá obvykle zapsána ve tvaru

<math>
\begin{array}{rcr}
a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &=& b_1 \\
a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n &=& b_2 \\
&\vdots& \\
a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &=& b_m \\
\end{array}
</math>

kde proměnné <math>x_1</math>, … ,<math>x_n</math> jsou [[neznámá|neznámé]] a čísla  <math>a_{ij}</math> jsou ''koeficienty soustavy''. [[číslo|Čísla]] <math>b_i</math>, kde <math>i = 1, 2, ...,m</math>, jsou ''absolutní členy soustavy'' (též tzv. ''pravá strana soustavy''). Koeficienty i absolutní členy mohou být prvky libovolného [[Těleso (algebra)|tělesa]], tedy kromě reálných čísel jimi mohou být např. i [[komplexní číslo|komplexní čísla]].

Soustavu lze popsat i úsporněji, např. ve složkovém zápisu:
:<math>\sum_{j=1}^n a_{ij} x_j = b_i</math> pro <math>i = 1,2, ..., m</math>.

=== Maticová rovnice ===
Koeficienty soustavy bývají obvykle uspořádány do [[matice]]:
:<math>\boldsymbol{A} = 
\begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix} 
</math>
Tuto matici nazýváme ''matice soustavy''.

Pro neznámé a pravou stranu soustavy se použijí sloupcové [[vektor]]y
:<math>\boldsymbol{x} = \begin{pmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n
\end{pmatrix} </math>
:<math>\boldsymbol{b} = \begin{pmatrix}
b_1 \\
b_2 \\
\vdots \\
b_m
\end{pmatrix} </math>

Celou soustavu rovnic je pak lze zapsat s pomocí [[součin matic|maticového součinu]] jedinou rovnicí
: <math>
\begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix} 

\begin{pmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n
\end{pmatrix} 
=
\begin{pmatrix}
b_1 \\
b_2 \\
\vdots \\
b_m
\end{pmatrix} 

</math>
neboli
:<math>\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}</math>
Pro výpočet řešení soustavy lineárních rovnic bývá často využívána tzv. [[rozšířená matice soustavy]]
:<math>(\boldsymbol{A}|\boldsymbol{b}) = 
\left(\begin{array}{cccc|c}
a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\
a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn} & b_m 
\end{array}\right)
</math>

ze které lze zjistit existenci a jednoznačnost řešení, např. [[Gaussova eliminační metoda|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ů:

: <math>
x_1\begin{pmatrix}a_{11}\\a_{21}\\ \vdots \\a_{m1}\end{pmatrix} +
x_2\begin{pmatrix}a_{12}\\a_{22}\\ \vdots \\a_{m2}\end{pmatrix} +
\dots +
x_n\begin{pmatrix}a_{1n}\\a_{2n}\\ \vdots \\a_{mn}\end{pmatrix}
=\begin{pmatrix}b_1\\b_2\\ \vdots \\b_m\end{pmatrix}
</math>

Tento pohled umožňuje uplatnit veškeré nástroje z teorie ''[[Vektorový prostor|vektorových prostorů]]'' (obecněji ''[[Modul (matematika)|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
:<math>\boldsymbol{A}\boldsymbol{x} = \boldsymbol{0}</math>,
což v rozvinutém tvaru znamená

:<math>\begin{array}{rcrcrcr}
a_{11} x_1 & + & a_{12} x_2 & + \cdots + & a_{1n} x_n & = & 0 \\
a_{21} x_1 & + & a_{22} x_2 & + \cdots + & a_{2n} x_n & = & 0 \\
      &    &      &       & &  \vdots\;\ && \\
a_{m1} x_1 & + & a_{m2} x_2 & + \cdots + & a_{mn} x_n & = & 0 \\
\end{array}</math>

neboli
:<math>\sum_{j=1}^n a_{ij} x_j = 0</math> pro <math>i = 1, 2 ,...,m</math>,
Pokud je alespoň jeden z absolutních členů <math>b_i</math> 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í matice|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 <math>\boldsymbol{A}\boldsymbol{x} = \boldsymbol{0} </math> má následující vlastnosti:

* Jsou-li <math>\boldsymbol u</math> a <math>\boldsymbol v</math> jsou dvě řešení, pak jejich vektorový součet <math>\boldsymbol u+\boldsymbol v</math> je také řešením.
* Je-li <math>\boldsymbol u</math> řešení soustavy a <math>r</math> je libovolný [[skalár]], pak <math>r\boldsymbol u</math> je také řešením.

Jinými slovy, množina řešení tvoří [[Vektorový podprostor|vektorový prostor]] nazývaný '''[[jádro matice]]''' <math>\boldsymbol{A}</math>. Jádro se značí <math>\ker\boldsymbol{A}</math> (z anglického ''kernel'' = jádro). Někdy se též nazývá '''[[nulový prostor]] matice''' <math>\boldsymbol{A}</math>.

== Množina řešení ==
[[Soubor:Eq R Z5.svg|náhled|Množina řešení reálné rovnice <math>x_1 + 2x_2 = 2</math> tvoří přímku s nekonečně mnoha body, zatímco rovnice se stejnými koeficienty nad tělesem <math>\mathbb Z_5</math> má jen pět řešení.]]
Při řešení nehomogenní soustavy nad nekonečným [[Těleso (algebra)|tělesem]], což jsou například [[reálné číslo|reálná]] či [[komplexní číslo|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é těleso|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. <math>x_i = 0</math> pro všechna <math>i</math>.

=== Geometrická interpretace ===
[[Soubor:Intersecting_Lines.svg|vpravo|náhled| Množinou řešení soustavy reálných rovnic <math>x-y=-1</math>  a <math>
3x+y=9
</math> je jediný bod <math>(2,3)</math>.]][[Soubor:Intersecting_Planes_2.svg|vpravo|náhled| Množina řešení soustavy dvou rovnic o třech reálných neznámých tvoří zpravidla přímku.]]
Množiny řešení soustav o dvou reálných neznámých lze znázornit v [[Kartézská soustava souřadnic|euklidovské rovině]] v níž osy odpovídají neznámým <math>x</math> a <math>y</math>.  Lineární rovnice odpovídají [[Přímka|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 [[3D|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 <math>n</math>, pak netriviální lineární rovnice určují [[Nadrovina|nadroviny]] v [[Dimenze|<math>n</math>-rozměrném prostoru]]. Množina řešení je průnikem těchto nadrovin a má dimenzi nejvýše <math>n-1</math> (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á soustava rovnic|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á soustava rovnic|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" | [[Image:One Line.svg|120px]]
| width="150" align="center" | [[Image:Two Lines.svg|120px]]
| width="150" align="center" | [[Image:Three Lines.svg|120px]]
|-
|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í nezávislost|lineárně závislé]]'', nebo pokud je soustava ''[[Soustava lineárních rovnic|nekonzistentní]]'' a nemá více rovnic než neznámých.

== Vlastnosti ==

=== Nezávislost ===
Stane-li se, že některá rovnice soustavy je [[lineární kombinace|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í závislost|lineárně nezávislé]] rovnice.

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

[[Soubor:Three_Intersecting_Lines.svg|vpravo|náhled| Rovnice <math>x-2y=-1</math>, <math>
3x+5y=8
</math> a <math>4x+3y=7</math> jsou lineárně závislé.]]
Například rovnice

: <math>3x+2y=6</math> a <math>6x+4y=12</math>

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

: <math>\begin{array}{rcrcr}
 x & - & 2y & = & -1  \\
 3x & + & 5y & = & 8  \\
 4x & + & 3y & = & 7 
\end{array}</math>

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 ===
[[Soubor:Parallel_Lines.svg|vpravo|náhled| Rovnice <math>3x+2y=6</math> a <math>3x+2y=12</math> jsou nekonzistentní.]]
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 [[Kontradikce|spor]], třeba jako výrok <math>0=1</math>.

Například rovnice

: <math>3x+2y=6</math> a <math>3x+2y=12</math>

jsou nekonzistentní.  Spor <math>0 = 1</math> lze získat vydělením jejich rozdílu šesti. Odpovídající přímky jsou [[Rovnoběžnost|rovnoběžné]].

Soustava

: <math>\begin{array}{rcrcr}
 x & + & y & = & 1 \\
2x & + & y & = & 1 \\
3x & + & 2y & = & 3 
\end{array}</math>

je nekonzistentní, protože součet prvních dvou je <math>3x + 2y = 2</math>, a následné odečtení třetí dá <math>0 = 1</math>. 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 ====
{{hlavní|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|rozšířené matice soustavy]]: <math>\operatorname{rank}(\boldsymbol{A}|\boldsymbol{b})=\operatorname{rank}\boldsymbol{A}</math>. V tomto případě je soustava konzistentní. Pokud je hodnost matice <math>\boldsymbol{A}</math> rovna počtu neznámých, má soustava jedno řešení; pokud je <math>\operatorname{rank}\boldsymbol{A}</math> menší než počet neznámých, je řešení více. 

Hodnost matice <math>\boldsymbol{A}</math> nemůže být z definice větší než počet neznámých, ale je-li hodnost rozšířené matice  soustavy <math>(\boldsymbol{A}|\boldsymbol{b})</math> 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 <math>\boldsymbol{p}</math> nějaké konkrétní řešení soustavy <math>\boldsymbol {Ax}=\boldsymbol b</math>, pak lze celou množinu řešení této soustavy popsat výrazem <math>\{ \boldsymbol{p}+\boldsymbol{v} \colon  \boldsymbol{v}\in \ker \boldsymbol A\}</math>. Zde <math>\ker \boldsymbol A</math> značí [[jádro matice]] a tvoří ho všechna řešení soustavy <math>\boldsymbol {Ax}=\boldsymbol 0</math>.

Jinými slovy, množinu řešení soustavy <math>\boldsymbol{Ax}=\boldsymbol b</math> lze získat [[Posunutí (geometrie)|posunem]] jádra matice <math>\boldsymbol A</math> o vektor <math>\boldsymbol{p}</math>.

== 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ř. <math>x=3</math>, <math>y=-2</math> a <math>z=6</math>. Je-li dáno nějaké pořadí neznámých, například [[Abecední řazení|abecední]], může být řešení popsáno [[Vektorový prostor|vektorem]] hodnot, jako je <math>(3, -2, 6)^\mathsf T</math> v uvedeném příkladě.

Aby bylo možné popsat i [[Nekonečná množina|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

: <math>\begin{array}{rcrcr}
 x & + & 3y & - & 2z & = & 5 \\
3x & + & 5y & + & 6z & = & 7 
\end{array}</math>

lze popsat rovnicemi:

: <math>x=-7z-1</math> a <math>y=3z+2\text{.}</math>

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

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 <math>z</math>. 

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

: <math>y=-\frac{3}{7}x + \frac{11}{7}</math> a <math>z=-\frac{1}{7}x-\frac{1}{7}</math>.

je alternativním popisem téže množiny řešení, jen <math>x</math> je zde volná proměnná a <math>y</math> a <math>z</math> 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ě:

:<math>\begin{array}{rcrcrcr}
x&+&3y&-&2z&=&5\\
3x&+&5y&+&6z&=&7\\
2x&+&4y&+&3z&=&8
\end{array}</math>
lze z první rovnice vyjádřit <math>x = 5 + 2z - 3y</math>. Jeho dosazením do druhé a třetí rovnice 
:<math>\begin{array}{rcrcrcr}
3(5 + 2z - 3y)&+&5y&+&6z&=&7\\
2(5 + 2z - 3y)&+&4y&+&3z&=&8
\end{array}</math>
se soustava zredukuje na
:<math>\begin{array}{rcrcr}
-y&+&3z&=&-2\\
-2y&+&7z&=&-2
\end{array}</math>
Z první rovnice lze vyjádřit <math>y=3z+2</math> a jeho dosazením do druhé získat 
:<math>\begin{array}{rcl}
-2(3z+2)+7z&=&-2 \\
\Rightarrow z&=&2
\end{array}</math>

Dosazení <math>z= 2</math>  do vyjádření pro <math>y
 </math> dává <math>y= 8</math>. Z hodnot <math>y</math> a <math>z</math> se pak dopočítá <math>x=-15</math>. Řešením soustavy je uspořádaná trojice <math>(x,y,z)=(-15,8,2)</math>.

=== Gaussova eliminace ===
Gaussova eliminace vychází z poznatku, že [[rozšířená matice|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í matice|elementární ekvivalentní řádkové úpravy]]:

: '''Typ 1''' : změna pořadí řádků
: '''Typ 2''' : vynásobení řádku nenulovým [[Skalár|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 eliminační metoda|Gaussova eliminace]] a [[Gaussova–Jordanova eliminace]]. Gaussova–Jordanova eliminace matice soustavy z předchozího příkladu odpovídá následujícímu výpočtu:

: <math>\begin{align}\left(\begin{array}{rrr|r}
1 & 3 & -2 & 5 \\
3 & 5 & 6 & 7 \\
2 & 4 & 3 & 8
\end{array}\right)&\sim
\left(\begin{array}{rrr|r}
1 & 3 & -2 & 5 \\
0 & -4 & 12 & -8 \\
2 & 4 & 3 & 8
\end{array}\right)\sim
\left(\begin{array}{rrr|r}
1 & 3 & -2 & 5 \\
0 & -4 & 12 & -8 \\
0 & -2 & 7 & -2
\end{array}\right)\sim
\left(\begin{array}{rrr|r}
1 & 3 & -2 & 5 \\
0 & 1 & -3 & 2 \\
0 & -2 & 7 & -2
\end{array}\right)
\\
&\sim
\left(\begin{array}{rrr|r}
1 & 3 & -2 & 5 \\
0 & 1 & -3 & 2 \\
0 & 0 & 1 & 2
\end{array}\right)\sim
\left(\begin{array}{rrr|r}
1 & 3 & -2 & 5 \\
0 & 1 & 0 & 8 \\
0 & 0 & 1 & 2
\end{array}\right)\sim
\left(\begin{array}{rrr|r}
1 & 3 & 0 & 9 \\
0 & 1 & 0 & 8 \\
0 & 0 & 1 & 2
\end{array}\right)\sim
\left(\begin{array}{rrr|r}
1 & 0 & 0 & -15 \\
0 & 1 & 0 & 8 \\
0 & 0 & 1 & 2
\end{array}\right).\end{align}</math>

Z poslední matice lze snadno odvodit řešení <math>x=-15</math>, <math>y=8</math> a <math>z=2</math>. 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|determinantů]]. Například řešení soustavy

: <math>\begin{array}{rcrcr}
 x & + & 3y & - & 2z & = & 5 \\
3x & + & 5y & + & 6z & = & 7 \\
2x & + & 4y & + & 3z & = & 8 
\end{array}</math>

je dáno podíly

: <math>
x=\frac
{\, \begin{vmatrix}5&3&-2\\7&5&6\\8&4&3\end{vmatrix} \,}
{\, \begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix} \,}
,\;\;\;\;
y=\frac
{\, \begin{vmatrix}1&5&-2\\3&7&6\\2&8&3\end{vmatrix} \,}
{\, \begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix} \,}
,\;\;\;\;
z=\frac
{\, \begin{vmatrix}1&3&5\\3&5&7\\2&4&8\end{vmatrix} \,}
{\, \begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix} \,}.
</math>

Pro každou proměnnou je ve jmenovateli determinant [[matice koeficientů|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 <math>\boldsymbol A\boldsymbol{x}=\boldsymbol{b}</math> lze popsat i maticovým výrazem. U soustav s regulární maticí <math>\boldsymbol A</math> je jednoznačné řešení dané vztahem

: <math>\boldsymbol{x}=\boldsymbol A^{-1}\boldsymbol{b}</math>

kde <math>\boldsymbol A^{-1}</math> je [[Regulární matice|inverzní]] matice k matici <math>\boldsymbol A</math>. 

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í [[Pseudoinverze matice|Mooreovy–Penroseovy inverze]] k <math>\boldsymbol A</math>, označované <math>\boldsymbol A^+</math> následovně:

: <math>\boldsymbol{x}=\boldsymbol A^+ \boldsymbol{b} + \left(\mathbf I - \boldsymbol A^+ \boldsymbol A\right)\boldsymbol{w}</math>

kde <math>\boldsymbol{w}</math> 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 <math>\boldsymbol{w}=\boldsymbol{0}</math> splňuje <math>\boldsymbol A\boldsymbol{x}=\boldsymbol{b}</math>, neboli <math>\boldsymbol A\boldsymbol A^+ \boldsymbol{b}=\boldsymbol{b}.</math> 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 <math>\boldsymbol A</math> je čtvercová a má plnou hodnost, se <math>\boldsymbol A^+</math> shoduje s <math>\boldsymbol A^{-1}</math> a obecná rovnice řešení se zjednoduší na již známý vztah

: <math>\boldsymbol{x}=\boldsymbol A^{-1}\boldsymbol{b} + \left(\mathbf I - \boldsymbol A^{-1}\boldsymbol A\right)\boldsymbol{w} = \boldsymbol A^{-1}\boldsymbol{b} + \left(\mathbf I-\mathbf I\right)\boldsymbol{w} = \boldsymbol A^{-1}\boldsymbol{b}</math>

Během algebraických úprav byl vektor <math>\boldsymbol{w}</math> zcela eliminován a řešení je jednoznačné. V ostatních případech však <math>\boldsymbol{w}</math> zůstane, přičemž volby vektoru <math>\boldsymbol{w}</math> 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 <math>\boldsymbol A</math>. Ten bývá výhodný, zejména je-li třeba vyřešit několik soustav se shodnou maticí <math>\boldsymbol A</math>, ale různými vektory <math>\boldsymbol b</math>.

Rychlejší anebo přesnější algoritmy byly navrženy pro matice <math>\boldsymbol A</math> s nějakou speciální strukturou. Například [[Choleského dekompozice|Choleského rozklad]] bývá rychlejší pro soustavy s [[Pozitivně definitní matice|pozitivně definitní maticí]]. Levinsonova [[rekurze]] je rychlá metoda pro [[Toeplitzova matice|Toeplitzovy matice]]. Dalším příkladem matic, pro něž jsou známy speciální metody jsou [[Řídká matice|ří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í rozklad|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í metoda|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. <ref>{{cite news |last1=Hartnett |first1=Kevin |title=New Algorithm Breaks Speed Limit for Solving Linear Equations |url=https://www.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/ |access-date=9. března 2021 |work=Quanta Magazine |date=8 března 2021}}</ref>

Pro soustavy lineárních rovnic byl navržen i kvantový algoritmus. <ref>{{Citace arXiv|jméno=Aram W.|příjmení=Harrow|id=0811.3171}} </ref>

== Odkazy ==
=== Reference ===
{{Překlad|en|System of linear equations|1136505701}}
<references/>

=== Literatura ===
* {{Citace monografie
| příjmení = Bečvář
| jméno = Jindřich
| titul = Lineární algebra
| vydání = 1.
| vydavatel = Matfyzpress
| místo = Praha
| rok vydání = 2019
| počet_stran = 436
| isbn = 978-80-7378-392-1
}}
* {{Citace monografie
| příjmení = Hladík
| jméno = Milan
| titul = Lineární algebra (nejen) pro informatiky
| vydání = 1.
| vydavatel = Matfyzpress
| místo = Praha
| rok vydání = 2019
| počet_stran = 328
| isbn = 978-80-7378-378-5
}}
* {{Citace elektronické monografie
 | příjmení = Olšák
 | jméno = Petr
 | titul = Lineární algebra
 | url = http://petr.olsak.net/ftp/olsak/linal/linal.pdf
 | místo = Praha
 | datum vydání = 2007
 | datum přístupu = 2023-02-20
 }}
* {{Citace elektronické monografie
 | příjmení1 = Motl
 | jméno1 = Luboš
 | příjmení2 = Zahradník
 | jméno2 = Miloš
 | titul = Pěstujeme lineární algebru
 | url = https://matematika.cuni.cz/zahradnik-pla.html
 | datum přístupu = 2023-02-20
 }}

=== 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 ===
* {{Commonscat}}
* [http://www.hackmath.net/cz/kalkulacka/reseni-soustavy-linearnich-rovnic Online výpočet soustav lineárních rovnic]

{{Autoritní data}}
{{Portály|Matematika}}

[[Kategorie:Lineární algebra]]
[[Kategorie:Rovnice]]