V pátek 26. dubna 2024 úderem 22 hodiny začíná naše nová
a opravdu velká série soutěží o nejlepší webovou stránku !!
Proto neváhejte a začněte hned zítra soutěžit o lákavé ceny !!

Gaussova eliminační metoda

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)
(+ Masivní vylepšení)
m (→Výpočet inverzní matice: ++)
 
(Nejsou zobrazeny 2 mezilehlé verze.)
Řádka 5: Řádka 5:
== Řešení soustavy lineárních rovnic ==
== Řešení soustavy lineárních rovnic ==
Obecné zadání problému je následující:
Obecné zadání problému je následující:
-
:<math>\sum_{j=1}^n a_{i,j}x_{j} = b, \mbox{ pro } i = 1, 2, \ldots{}, n</math>
+
:<big>\(\sum_{j=1}^n a_{i,j}x_{j} = b, \mbox{ pro } i = 1, 2, \ldots{}, n\)</big>
maticově
maticově
-
:<math>Ax=b, \quad A\in\mathbb{R}^{n\times n}, \; b,x\in\mathbb{R}^n</math>
+
:<big>\(Ax=b, \quad A\in\mathbb{R}^{n\times n}, \; b,x\in\mathbb{R}^n\)</big>
-
kde <math>A</math> je matice soustavy, <math>b</math> pravá strana.
+
kde <big>\(A\)</big> je matice soustavy, <big>\(b\)</big> pravá strana.
[[Soustava lineárních rovnic|Soustavu lineárních algebraických rovnic]] lze vyjádřit ''[[Soustava lineárních rovnic#Z.C3.A1pis|rozšířenou maticí soustavy]]''. Řádkovými (nikoliv sloupcovými) úpravami převádíme tuto matici do tvaru, kdy se pod [[hlavní diagonála|hlavní diagonálou]] nachází pouze [[nula|nuly]]. Upravená matice pak odpovídá soustavě rovnic, která je [[Soustava rovnic|ekvivalentní]] s původní soustavou.
[[Soustava lineárních rovnic|Soustavu lineárních algebraických rovnic]] lze vyjádřit ''[[Soustava lineárních rovnic#Z.C3.A1pis|rozšířenou maticí soustavy]]''. Řádkovými (nikoliv sloupcovými) úpravami převádíme tuto matici do tvaru, kdy se pod [[hlavní diagonála|hlavní diagonálou]] nachází pouze [[nula|nuly]]. Upravená matice pak odpovídá soustavě rovnic, která je [[Soustava rovnic|ekvivalentní]] s původní soustavou.
-
Po těchto úpravách lze obvykle ihned zjistit, zda existují nějaká [[řešení soustavy rovnic|řešení soustavy]]. Pokud je [[hodnost matice|hodnost]] upravené matice (tzn. bez pravé strany) různá od hodnosti upravené rozšířené matice, potom podle [[Frobeniova věta|Frobeniovy věty]] soustava nemá žádné řešení. Je-li hodnost upravené matice stejná jako hodnost upravené rozšířené matice, a současně je tato hodnost rovna počtu neznámých soustavy, pak má soustava právě jedno řešení. Pokud je hodnost upravené matice stejná jako hodnost upravené rozšířené matice, avšak menší než počet neznámých soustavy, má soustava nekonečně mnoho řešení, přičemž <math>n - h</math> [[neznámá|neznámých]], kde <math>n</math> je počet neznámých a <math>h</math> je hodnost upravené matice, zvolíme libovolně a ostatní jsou touto volbou jednoznačně určeny.
+
Po těchto úpravách lze obvykle ihned zjistit, zda existují nějaká [[řešení soustavy rovnic|řešení soustavy]]. Pokud je [[hodnost matice|hodnost]] upravené matice (tzn. bez pravé strany) různá od hodnosti upravené rozšířené matice, potom podle [[Frobeniova věta|Frobeniovy věty]] soustava nemá žádné řešení. Je-li hodnost upravené matice stejná jako hodnost upravené rozšířené matice, a současně je tato hodnost rovna počtu neznámých soustavy, pak má soustava právě jedno řešení. Pokud je hodnost upravené matice stejná jako hodnost upravené rozšířené matice, avšak menší než počet neznámých soustavy, má soustava nekonečně mnoho řešení, přičemž <big>\(n - h\)</big> [[neznámá|neznámých]], kde <big>\(n\)</big> je počet neznámých a <big>\(h\)</big> je hodnost upravené matice, zvolíme libovolně a ostatní jsou touto volbou jednoznačně určeny.
=== Příklad ===
=== Příklad ===
Máme soustavu rovnic:
Máme soustavu rovnic:
<center>
<center>
-
<math>\begin{matrix}8x &-  y &- 2z & = & 0\\ - x &+ 7y &-  z &= &10\\ -2x &-  y &+ 9z &= &23\end{matrix}</math>
+
<big>\(\begin{matrix}8x &-  y &- 2z & = & 0\\ - x &+ 7y &-  z &= &10\\ -2x &-  y &+ 9z &= &23\end{matrix}\)</big>
</center>
</center>
a hledáme čísla ''x'', ''y'', ''z'', která jsou řešením dané soustavy.
a hledáme čísla ''x'', ''y'', ''z'', která jsou řešením dané soustavy.
Řádka 34: Řádka 34:
# třetí řádek násobíme 4 a přičteme první řádek
# třetí řádek násobíme 4 a přičteme první řádek
<center>
<center>
-
<math>\begin{matrix} 8x &- y &-  2z& = & 0\\ &55y &- 10z &= &80\\ &-5y &+ 34z &= &92\end{matrix}</math></center>
+
<big>\(\begin{matrix} 8x &- y &-  2z& = & 0\\ &55y &- 10z &= &80\\ &-5y &+ 34z &= &92\end{matrix}\)</big></center>
''Druhý krok'' – eliminace ''y'' ze třetího řádku
''Druhý krok'' – eliminace ''y'' ze třetího řádku
# první řádek neupravujeme
# první řádek neupravujeme
Řádka 42: Řádka 42:
<center>
<center>
-
<math>\begin{matrix} 8x & - y &  -  2z & = &  0\\ &55y &- 10z &= &80\\ & & z &=  &3 \end{matrix}</math></center>
+
<big>\(\begin{matrix} 8x & - y &  -  2z & = &  0\\ &55y &- 10z &= &80\\ & & z &=  &3 \end{matrix}\)</big></center>
''Třetí krok'' – zpětné dosazení
''Třetí krok'' – zpětné dosazení
# v druhém řádku dosadíme za ''z'' a vyřešíme ''y''
# v druhém řádku dosadíme za ''z'' a vyřešíme ''y''
# v prvním řádku dosadíme za ''z'' a ''y'' a dořešíme ''x''
# v prvním řádku dosadíme za ''z'' a ''y'' a dořešíme ''x''
-
<center><math>x = 1, \  y = 2,\  z = 3 </math></center>
+
<center><big>\(x = 1, \  y = 2,\  z = 3 \)</big></center>
=== Maticový tvar ===
=== Maticový tvar ===
Maticové řešení je často přehlednější a tento tvar je též vhodný k [[algoritmus|algoritmizaci]].
Maticové řešení je často přehlednější a tento tvar je též vhodný k [[algoritmus|algoritmizaci]].
-
Do matice zapisujeme koeficienty následujícím způsobem - levá strana (matice <math>n \times n</math>) koeficienty od neznámých, pravý sloupec obsahuje [[vektor]] pravých stran - výsledná matice <math>(n+1) \times n</math> se nazývá ''[[rozšířená matice soustavy|rozšířená matice]] [[Soustava lineárních rovnic|soustavy lineárních rovnic]]''.
+
Do matice zapisujeme koeficienty následujícím způsobem - levá strana (matice <big>\(n \times n\)</big>) koeficienty od neznámých, pravý sloupec obsahuje [[vektor]] pravých stran - výsledná matice <big>\((n+1) \times n\)</big> se nazývá ''[[rozšířená matice soustavy|rozšířená matice]] [[Soustava lineárních rovnic|soustavy lineárních rovnic]]''.
''Zadání:''
''Zadání:''
-
<math>\begin{pmatrix}8 & -1 & -2 & 0 \\ -1 & 7 & -1 & 10 \\ -2 & -1 & 9 & 23 \end{pmatrix}</math>
+
<big>\(\begin{pmatrix}8 & -1 & -2 & 0 \\ -1 & 7 & -1 & 10 \\ -2 & -1 & 9 & 23 \end{pmatrix}\)</big>
''Po prvním kroku:'' <br />
''Po prvním kroku:'' <br />
-
<math>\begin{pmatrix} 8 & -1 & -2 & 0 \\ 0 & 55 & -10 & 80 \\ 0 & -5 & 34 & 92\end{pmatrix}</math>
+
<big>\(\begin{pmatrix} 8 & -1 & -2 & 0 \\ 0 & 55 & -10 & 80 \\ 0 & -5 & 34 & 92\end{pmatrix}\)</big>
''Po druhém kroku:'' <br />
''Po druhém kroku:'' <br />
-
<math>\begin{pmatrix} 8 & -1 & -2 & 0 \\ 0 & 55 & -10 & 80 \\ 0 & 0 & 1 & 3\end{pmatrix}</math>
+
<big>\(\begin{pmatrix} 8 & -1 & -2 & 0 \\ 0 & 55 & -10 & 80 \\ 0 & 0 & 1 & 3\end{pmatrix}\)</big>
''Po třetím kroku:'' <br />
''Po třetím kroku:'' <br />
Získáváme [[Čtvercová matice#Diagonální matice|diagonální matici]] pro koeficienty s hodnotami pro neznámé v posledním sloupci:
Získáváme [[Čtvercová matice#Diagonální matice|diagonální matici]] pro koeficienty s hodnotami pro neznámé v posledním sloupci:
-
<math>
+
<big>\(
\begin{pmatrix}
\begin{pmatrix}
1 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 \\
Řádka 75: Řádka 75:
0 & 0 & 1 & 3
0 & 0 & 1 & 3
\end{pmatrix}
\end{pmatrix}
-
</math>
+
\)</big>
== Výpočet inverzní matice ==
== Výpočet inverzní matice ==
Řádka 85: Řádka 85:
Sestavíme matici '''B''' o rozměru (''n'' × 2''n'') složenou z původní matice '''A''' a [[jednotková matice|jednotkové matice]] '''I'''<sub>n</sub>. (Odborně řečeno, řešíme současně ''n'' pravých stran tvořených [[Báze (algebra)|bázovými]] vektory.)
Sestavíme matici '''B''' o rozměru (''n'' × 2''n'') složenou z původní matice '''A''' a [[jednotková matice|jednotkové matice]] '''I'''<sub>n</sub>. (Odborně řečeno, řešíme současně ''n'' pravých stran tvořených [[Báze (algebra)|bázovými]] vektory.)
-
:<math>\bold B = \left(\mathbf{A} \mid \mathbf{I}_n\right) = \left(\begin{array}{cccc|cccc} a_{11} & a_{12} & \cdots & a_{1n} & 1 & 0 & \cdots & 0 \\ a_{21} & a_{22} & \cdots & a_{2n} & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} & 0 & 0 & \cdots & 1 \end{array}\right)</math>
+
:<big>\(\boldsymbol{B} = \left(\mathbf{A} \mid \mathbf{I}_n\right) = \left(\begin{array}{cccc|cccc} a_{11} & a_{12} & \cdots & a_{1n} & 1 & 0 & \cdots & 0 \\ a_{21} & a_{22} & \cdots & a_{2n} & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} & 0 & 0 & \cdots & 1 \end{array}\right)\)</big>
Povolenými řádkovými úpravami (záměna řádků, vynasobení řádku skalárem, přičtení jednoho řádku k jinému) převedeme matici '''B''' do tvaru, kdy jednotková matice '''I'''<sub>n</sub> bude vlevo. V takovém případě bude inverzní matice '''A'''<sup>-1</sup> v pravé polovině upravené matice.
Povolenými řádkovými úpravami (záměna řádků, vynasobení řádku skalárem, přičtení jednoho řádku k jinému) převedeme matici '''B''' do tvaru, kdy jednotková matice '''I'''<sub>n</sub> bude vlevo. V takovém případě bude inverzní matice '''A'''<sup>-1</sup> v pravé polovině upravené matice.
-
:<math>\left(\mathbf{I}_n \mid \mathbf{A}^{-1}\right)</math>
+
:<big>\(\left(\mathbf{I}_n \mid \mathbf{A}^{-1}\right)\)</big>
== Související články ==
== Související články ==

Aktuální verze z 2. 6. 2023, 16:43

Gaussova eliminační metoda (Gaussova eliminace) je metodou řešení soustavy lineárních algebraických rovnic. Jedná se o metodu konečnou, tj. metodu vedoucí k (alespoň teoreticky) přesnému řešení v konečně mnoha krocích, postavenou na tzv. LU rozkladu matice soustavy.

Gaussovu eliminaci lze také použít pro výpočet inverzní matice nebo pro výpočet determinantu matice (viz Gaussova eliminace v článku Determinant).

Obsah

Řešení soustavy lineárních rovnic

Obecné zadání problému je následující:

\(\sum_{j=1}^n a_{i,j}x_{j} = b, \mbox{ pro } i = 1, 2, \ldots{}, n\)

maticově

\(Ax=b, \quad A\in\mathbb{R}^{n\times n}, \; b,x\in\mathbb{R}^n\)

kde \(A\) je matice soustavy, \(b\) pravá strana.

Soustavu lineárních algebraických rovnic lze vyjádřit rozšířenou maticí soustavy. Řádkovými (nikoliv sloupcovými) úpravami převádíme tuto matici do tvaru, kdy se pod hlavní diagonálou nachází pouze nuly. Upravená matice pak odpovídá soustavě rovnic, která je ekvivalentní s původní soustavou.

Po těchto úpravách lze obvykle ihned zjistit, zda existují nějaká řešení soustavy. Pokud je hodnost upravené matice (tzn. bez pravé strany) různá od hodnosti upravené rozšířené matice, potom podle Frobeniovy věty soustava nemá žádné řešení. Je-li hodnost upravené matice stejná jako hodnost upravené rozšířené matice, a současně je tato hodnost rovna počtu neznámých soustavy, pak má soustava právě jedno řešení. Pokud je hodnost upravené matice stejná jako hodnost upravené rozšířené matice, avšak menší než počet neznámých soustavy, má soustava nekonečně mnoho řešení, přičemž \(n - h\) neznámých, kde \(n\) je počet neznámých a \(h\) je hodnost upravené matice, zvolíme libovolně a ostatní jsou touto volbou jednoznačně určeny.

Příklad

Máme soustavu rovnic:

\(\begin{matrix}8x &- y &- 2z & = & 0\\ - x &+ 7y &- z &= &10\\ -2x &- y &+ 9z &= &23\end{matrix}\)

a hledáme čísla x, y, z, která jsou řešením dané soustavy.

Cílem je eliminovat jednotlivé neznámé z jednotlivých rovnic soustavy: z první rovnice eliminujeme x (pomocí úprav druhé a třetí rovnice), z druhé y, z třetí z.

Jsou povoleny následující operace, které nezmění hodnost soustavy:

  • násobení či dělení jednotlivých řádků nenulovým číslem
  • prohazování libovolných řádků soustavy
  • přičítání násobků jednotlivých řádků k jinému řádku

Postup pro výše uvedený příklad: První krok – eliminace x z druhého a třetího řádku.

  1. první řádek neupravujeme
  2. druhý řádek násobíme 8 a přičteme první řádek
  3. třetí řádek násobíme 4 a přičteme první řádek
\(\begin{matrix} 8x &- y &- 2z& = & 0\\ &55y &- 10z &= &80\\ &-5y &+ 34z &= &92\end{matrix}\)

Druhý krok – eliminace y ze třetího řádku

  1. první řádek neupravujeme
  2. druhý řádek neupravujeme
  3. třetí řádek násobíme 11 a přičteme druhý řádek
  4. vydělíme třetí řádek 364 a získáme řešení z = 3
\(\begin{matrix} 8x & - y & - 2z & = & 0\\ &55y &- 10z &= &80\\ & & z &= &3 \end{matrix}\)

Třetí krok – zpětné dosazení

  1. v druhém řádku dosadíme za z a vyřešíme y
  2. v prvním řádku dosadíme za z a y a dořešíme x
\(x = 1, \ y = 2,\ z = 3 \)

Maticový tvar

Maticové řešení je často přehlednější a tento tvar je též vhodný k algoritmizaci.

Do matice zapisujeme koeficienty následujícím způsobem - levá strana (matice \(n \times n\)) koeficienty od neznámých, pravý sloupec obsahuje vektor pravých stran - výsledná matice \((n+1) \times n\) se nazývá rozšířená matice soustavy lineárních rovnic.

Zadání:

\(\begin{pmatrix}8 & -1 & -2 & 0 \\ -1 & 7 & -1 & 10 \\ -2 & -1 & 9 & 23 \end{pmatrix}\)

Po prvním kroku:

\(\begin{pmatrix} 8 & -1 & -2 & 0 \\ 0 & 55 & -10 & 80 \\ 0 & -5 & 34 & 92\end{pmatrix}\)

Po druhém kroku:

\(\begin{pmatrix} 8 & -1 & -2 & 0 \\ 0 & 55 & -10 & 80 \\ 0 & 0 & 1 & 3\end{pmatrix}\)

Po třetím kroku:
Získáváme diagonální matici pro koeficienty s hodnotami pro neznámé v posledním sloupci:

\( \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 \end{pmatrix} \)

Výpočet inverzní matice

Viz také Výpočet inverzní matice a příklad v článku Inverzní matice.

Gaussovou eliminací lze také použít pro výpočet inverzní matice A-1 k dané čtvercové matici A o velikosti (n × n) podle následujícího postupu.

Sestavíme matici B o rozměru (n × 2n) složenou z původní matice A a jednotkové matice In. (Odborně řečeno, řešíme současně n pravých stran tvořených bázovými vektory.)

\(\boldsymbol{B} = \left(\mathbf{A} \mid \mathbf{I}_n\right) = \left(\begin{array}{cccc|cccc} a_{11} & a_{12} & \cdots & a_{1n} & 1 & 0 & \cdots & 0 \\ a_{21} & a_{22} & \cdots & a_{2n} & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} & 0 & 0 & \cdots & 1 \end{array}\right)\)

Povolenými řádkovými úpravami (záměna řádků, vynasobení řádku skalárem, přičtení jednoho řádku k jinému) převedeme matici B do tvaru, kdy jednotková matice In bude vlevo. V takovém případě bude inverzní matice A-1 v pravé polovině upravené matice.

\(\left(\mathbf{I}_n \mid \mathbf{A}^{-1}\right)\)

Související články

Externí odkazy

Reference

  • Přehled užité matematiky, Karel Rektorys a spolupracovníci


Citováno z „http://www.multimediaexpo.cz/mmecz/index.php/Gaussova_elimina%C4%8Dn%C3%AD_metoda“