Soustavy lineárních rovnic, Frobeniova věta, Gaussova eliminační metoda, Cramerovo pravidlo

Lineární rovnice

• Uvažujme číselné těleso $T$ a prvky $a_1,\dots ,a_n,b\in T$. Úloha určit všechny $n$-tice $\left(x_1,\dots ,x_n\right)\in T^n$, pro něž platí${\sum }_{i=1}^n{a}_i{x}_i=a_1{x}_1+\cdots +a_n{x}_n=b$se nazývá lineární rovnice (LR) o $n$ neznámých nad $T$. Každá $n$-tice, pro kterou tato rovnost nastane, se nazývá řešení této rovnice.

Isibalo - Lineární rovnice

Soustava lineárních rovnic

• Nechť $T$ je číselné těleso a $a_{ij},b_i\in T$ pro každé $i=1,\dots ,m$ a každé $j=1,\dots ,n$. Úloha určit všechny $n$-tice $\left(x_1,\dots ,x_n\right)\in T^n$, pro které současně platí $(S)\{\begin{array}{c}{\sum }_{j=1}^n{a}_{1j}{x}_j=a_{11}{x}_1+\cdots +a_{1n}{x}_n=b_1,(R_1)\\ ⋮\\ {\sum }_{j=1}^n{a}_{mj}{x}_j=a_{m1}{x}_1+\cdots +a_{mn}{x}_n=b_m,(R_m)\end{array}$se nazývá soustava $m$ lineárních rovnic (SLR) o $n$ neznámých nad $T$. Každá $n$-tice splňující $(S)$ se nazývá řešení této soustavy.

---

• Jsou-li $M_1,\dots ,M_m$ množiny řešení rovnic $\left(R_1\right),\dots ,\left(R_m\right)$, pak pro množinu řešení soustavy $(S)$ platí $M=M_1\cap \dots \cap M_m$
• Soustavu $(S)$ můžeme zkráceně zapisovat jako ${\sum }_{j=1}^n{a}_{ij}{x}_j=b_i,i=1,\dots ,m$

Isibalo - Soustava lineárních rovnic

Matice soustavy lineárních rovnic

• Nechť je dána soustava $(S)$ lineárních rovnic. Pak matici

$$A=\left(\begin{array}{ccc}{a}_{11}& \dots & a_{1n}\\ a_{21}& \dots & a_{2n}\\ ⋮& & ⋮\\ a_{m1}& \dots & a_{mn}\end{array}\right),\mathrm{resp}\cdot \left(A\mid {\vec{b}}^T\right)=\left(\begin{array}{cccc}{a}_{11}& \dots & a_{1n}& b_1\\ a_{21}& \dots & a_{2n}& b_2\\ ⋮& & ⋮& ⋮\\ a_{m1}& \dots & a_{mn}& b_m\end{array}\right)$$

nazýváme matice soustavy $(S)$, resp. rozšířená matice soustavy $(S)$.

Řešitelnost SLR

• SLR $A{\vec{x}}^T={\vec{b}}^T$ se nazývá řešitelná, jestliže existuje alespoň jedno její řešení. Dvě soustavy lineárních rovnic $A{\vec{x}}^T={\vec{b}}^T$ a $B{\vec{x}}^T={\vec{c}}^T$ nazveme ekvivalentní, jestliže mají stejné množiny řešení.

---

• SLR $A{\vec{x}}^T={\vec{b}}^T$ je řešitelná právě když je vektor $\vec{b}$ lineární kombinací sloupců matice $A\in {\mathcal{M}}_{m\times n}(T)$

Frobeniova věta

• Nehomogenní soustava lineárních rovnic $A{\vec{x}}^T={\vec{b}}^T$ je řešitelná právě tehdy, jeli $\mathrm{h}(A)=\mathrm{h}\left(A\mid {\vec{b}}^T\right)$.

---

• Je-li v této situaci navíc $\mathrm{h}(A)=n$, pak má tato soustava právě jedno řešení, pokud $\mathrm{h}(A)<n$, pak má nekonečně mnoho řešení (závislých na $n-\mathrm{h}(A)$ parametrech).

Frobeniova věta

Lineární soustava rovnic má řešení, pokud a jen pokud je hodnost matice koeficientů rovna hodnosti rozšířené matice. Rozšířená matice zahrnuje jak matici koeficientů, tak sloupec pravých stran rovnic. To se dá vyjádřit vztahem: $\mathrm{h}(A)=\mathrm{h}\left(A\mid {\vec{b}}^T\right)$

Elementární řádkové transformace - EŘT

• EŘT matice $A\in {\mathcal{M}}_{m\times n}(T)$ nazýváme tyto úpravy:
  1. vzájemnou záměnu dvou řádků v $A$
  2. vynásobení některého řádku nenulovým číslem z $T$
  3. přičtení nenulového násobku některého řádku k jinému řádku v $A$

Definice řádkové ekvivalence

• Nechť $A,B\in {\mathcal{M}}_{m\times n}(T)$. Říkáme, že matice $A$ je řádkově ekvivalentní s maticí $B$, jestliže můžeme matici $B$ získat z $A$ pomocí konečného počtu EŘT. Pak píšeme $A\sim B$.

---

• Věta: Nechť $A,B\in {\mathcal{M}}_{m\times n}(T)$. Jestliže $A\sim B$, pak matice $A$ i $B$ určují stejné řádkové podprostory.

Příklad

Platí $A=\left(\begin{array}{rr}1& 2\\ -1& 0\\ 3& 2\end{array}\right)\sim \left(\begin{array}{rr}-6& -4\\ -1& 0\\ 0& 2\end{array}\right)=B$, protože $B$ můžeme z $A$ získat takto:

1. zaměníme $1.$ a $3.$ řádek
2. $1.$ řádek získané matice vynásobíme $(-2)$
3. ke $3.$ řádku této matice přičteme její $2.$ řádek.

Gaussův tvar

Vedoucí prvek

• Vedoucím prvkem řádku (řádkového vektoru) matice $A\in {\mathcal{M}}_{m\times n}(T)$ rozumíme první nenulový prvek zleva v tomto řádku.

• O matici $A\in {\mathcal{M}}_{m\times n}(T)$ řekneme, že je v Gaussově tvaru (GT), pokud všechny její nulové řádky jsou až za nenulovými a navíc pro každé její dva nenulové řádky $\overrightarrow{a_i},\overrightarrow{a_j}$ musí být splněno, že pokud $i<j$, pak vedoucí prvek $i$-tého řádku leží ve sloupci, jehož index je menší než index sloupce, ve kterém leží vedoucí prvek $j$-tého řádku.

Příklad

$$A=\left(\begin{array}{ccccc}1& 2& -5& 0& 1\\ 0& 0& 2& 0& 5\\ 0& 0& 0& -5& 4\\ 0& 0& 0& 0& 0\end{array}\right)\text{je v GT,}B=\left(\begin{array}{rrrr}0& 2& -5& 0\\ 0& 0& 3& 1\\ 0& 0& -2& 8\\ 0& 0& 0& -8\end{array}\right)\text{nenıˊ v GT.}$$

Tip

• Každá matice $A\in {\mathcal{M}}_{m\times n}(T)$ je řádkově ekvivalentní s některou maticí v Gaussově tvaru.

• Věta: Je-li $A\sim B$ pro některé matice $A,B\in {\mathcal{M}}_{m\times n}(T)$, pak nenulové řádky matice $B$ tvoří bázi řádkového podprostoru matice $A$.

Gaussova eliminační metoda

• Nechť je dána soustava lineárních rovnic $A{\vec{x}}^T={\vec{b}}^T$, kde $A\in {\mathcal{M}}_{m\times n}(T)$.
• Matici $\left(A\mid {\vec{b}}^T\right)$ převedeme pomocí elementárních řádkových transformací na matici $\left(B\mid {\vec{c}}^T\right)$, která je v GT (Gaussově tvaru).
• Pracujeme tedy dál s jinou soustavou, která má ale podle věty stejnou množinu řešení jako daná.

---

• Je-li $\mathrm{h}(A)=\mathrm{h}\left(A\mid {\vec{b}}^T\right)=h<n$, pak

$$\left(B\mid {\vec{c}}^T\right)=\left(\begin{array}{ccccccc}{b}_{11}& b_{12}& \dots & b_{1h}& \dots & b_{1n}& c_1\\ 0& b_{22}& \dots & b_{2h}& \dots & b_{2n}& c_2\\ ⋮& ⋮& \ddots & ⋮& & ⋮& ⋮\\ 0& 0& \dots & b_{hh}& \dots & b_{hn}& c_h\\ 0& & & \dots & & 0& 0\\ ⋮& & & & & ⋮& ⋮\\ 0& & & \dots & & 0& 0\end{array}\right)$$

• Přitom se dá vždy zařídit (prohození sloupců), že $b_{ii}\ne 0$ pro každé $i=$ $1,2,\dots ,h$.

---

• Z rovnice $b_{hh}{x}_h+\dots +b_{hn}{x}_n=c_h$, která odpovídá poslednímu nenulovému řádku matice $\left(B\mid {\vec{c}}^T\right)$ vypočítáme $x_h$ v závislosti na $x_{h+1},\dots ,x_n$.
• Z rovnice, která odpovídá předposlednímu nenulovému řádku vypočítáme v závislosti na $x_{h+1},\dots ,x_n$ neznámou $x_{h-1}$. $⋮$
• Z rovnice odpovídající prvnímu řádku $\left(B\mid {\vec{c}}^T\right)$ dopočítáme $x_1$ v závislosti na $x_{h+1},\dots ,x_n$.

---

• Jestliže $\mathrm{h}(A)=\mathrm{h}\left(A\mid {\vec{b}}^T\right)=n$, pak

$$\left(B\mid {\vec{c}}^T\right)=\left(\begin{array}{ccccc}{b}_{11}& b_{12}& \dots & b_{1n}& c_1\\ 0& b_{22}& \dots & b_{2n}& c_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \dots & b_{nn}& c_n\\ 0& \dots & & 0& 0\\ ⋮& & & ⋮& ⋮\\ 0& \dots & & 0& 0\end{array}\right).$$

---

• Z rovnice $b_{nn}{x}_n=c_n$, která odpovídá $n$-tému řádku matice $\left(B\mid {\vec{c}}^T\right)$ máme

$$x_n=\frac{1}{b_{nn}}\cdot c_n$$

• Z rovnice, která odpovídá předposlednímu nenulovému řádku vypočítáme

$$x_{n-1}=\frac{1}{b_{n-1,n-1}}\cdot \left(c_{n-1}-b_{n-1,n}\cdot x_n\right)$$

$⋮$

• Až konečně z rovnice odpovídající prvnímu řádku $\left(B\mid {\vec{c}}^T\right)$ dopočítáme

$$x_1=\frac{1}{b_{11}}\cdot \left(c_1-b_{1n}\cdot x_n-b_{1,n-1}\cdot x_{n-1}-\cdots -b_{12}\cdot x_2\right)$$

Isibalo - Gaussova eliminační metoda

Gaussova eliminační metoda

Používá se k vyřešení soustav lineárních rovnic.

1. Soustavu rovnic přepíšeme do matice i se sloupcem pravých stran.
2. Při aplikování Gaussové eliminační metody tzn. upravuji matici na “trojúhelníkový” (Gaussův) tvar pomocí EŘT.
3. Po úpravě na Gaussův tvar pomocí zpětné substituce od posledního řádku postupně dosazujeme známé hodnoty do předchozích rovnic a řešíme zbylé neznámé.

Cramerovo pravidlo

• Další možnost jak řešit SLR.
• Nelze použít vždy.
• Pouze když soustava obsahuje tolik rovnic jako neznámých a navíc hodnost její matice je plná.

Věta (Cramerovo pravidlo):

• Je dána soustava $n$ lineárních rovnic $A{\vec{x}}^T={\vec{b}}^T$ o $n$ neznámých nad $T$ taková, že platí $\det (A)\ne 0$. Pak tato soustava má právě jedno řešení $\vec{x}=\left(x_1,\dots ,x_n\right)$, pro něž platí

$$x_j=\frac{\det \left(A_j\right)}{\det (A)}\forall j=1,\dots ,n$$

• Přitom matice $A_j$ je matice, kterou získáme nahrazením $j$-tého sloupcového vektoru matice $A$, tedy ${\overrightarrow{a_j}}^T$, vektorem ${\vec{b}}^T$.

Příklad

• Určete druhou složku vektoru řešení soustavy:

$$\begin{array}{rl}{x}_1+2x_2+5x_3& =-9\\ x_1-x_2+3x_3& =2\\ 3x_1-6x_2-x_3& =25\end{array}$$

• Řešení: Podle Cramerova pravidla je $x_2=\frac{|A_2|}{|A|}$, kde:

$$|A|=\left|\begin{array}{rrr}1& 2& 5\\ 1& -1& 3\\ 3& -6& -1\end{array}\right|=20\text{ a }\left|A_2\right|=\left|\begin{array}{rrr}1& -9& 5\\ 1& 2& 3\\ 3& 25& -1\end{array}\right|=-60$$

tedy $x_2=-3$.

Isibalo - Cramerovo pravidlo

Navigace

Předchozí: Eukleidovské vektorové prostory, ortogonální a ortonormální báze, Schwarzova nerovnost, Schmidtova ortogonalizační metoda Následující: Lineární zobrazení a transformace a jejich matice Celý okruh: 1. Teoretické základy informačních technologií