Soustavy lineárních rovnic

Definice: Vektor $b$ o $m$ složkách je uspořádaná $m$-tice $b\in T^m$

$$\begin{array}{rl}b& =\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right)\end{array}$$

Definice: Matice $A$ typu $m\times n$ je soubor $m\cdot n$ čísel z daného tělesa $T$ uspořádané do tabulky s $m$ řádky a $n$ sloupci. Píšeme $A\in T^{m\times n}$.

$$\begin{array}{rl}A& =\left(\begin{array}{cccc}{a}_{1,1}& a_{1,2}& \dots & a_{1,n}\\ a_{2,1}& a_{2,2}& \dots & a_{2,n}\\ ⋮& ⋮& & ⋮\\ a_{m,1}& a_{m,2}& \dots & a_{m,n}\end{array}\right)\end{array}$$

Na maticích zavádíme operaci transpozice, kde platí $\forall i,j:(A{)}_{i,j}=(A^T{)}_{j,i}.$ Tuto operaci můžeme zavést i na vektorech uvažujeme-li vektor $b\in T^m$ jako matici $B\in T^{m\times 1}$ tímto zavádíme řádkové vektory.

---

Reprezentace soustavy rovnic

Mějme soustavu rovnic nad nějakým tělesem, že $a_{i,j},x_i,b_j\in T$ a mějme soustavu rovnic

$$\begin{array}{rl}{a}_{1,1}{x}_1+a_{1,2}{x}_2+\dots +a_{1,n}{x}_n& =b_1\\ a_{2,1}{x}_1+a_{2,2}{x}_2+\dots +a_{2,n}{x}_n& =b_2\\ ⋮& =⋮\\ a_{m,1}{x}_1+a_{m,2}{x}_2+\dots +a_{m,n}{x}_n& =b_m\end{array}$$

Nechť $A\in T^{m\times n},b\in T^m$ a vektor neznámých $x=(x_1,\dots ,x_n{)}^T$ pak soustava rovnic výše se dá reprezentovat pomocí $Ax=b$, kde

• $A$ je matice soustavy,
• $b$ je vektor pravých stran,
• $(A|b)\in T^{m\times (n+1)}$ je rozšířená matice soustavy. Vektor $x\in T^n$ je řešení soustavy $Ax=b$ pokud splňuje všechny její rovnice. Speciálními tzv. homogenními soustavami jsou takové, kde $Ax=0$ umožňující $x=0$.

---

Elementární řádkové úpravy

Definice: $A\sim A^{\prime }$ píšeme, pokud lze $A^{\prime }$ získat jakoukoliv z následujících elementárních řádkových úprav:

1. Vynásobení $i$- tého řádku nenulovou konstantou $t\in T\setminus \{0\}$, tedy formálně $a_{k,j}^{\prime }=\{\begin{array}{rcl}{a}_{k,j}& \text{pro}& k\ne i\\ t{a}_{k,j}& \text{pro}& k=i\end{array}$
2. Přičtení $i$- tého řádku k $j$-tému, formálně $a_{k,l}^{\prime }=\{\begin{array}{rcl}{a}_{k,l}& \text{pro}& k\ne i\\ a_{i,l}+a_{j,l}& \text{pro}& k=i\end{array}$ Z těchto úprav snadno odvodíme další dvě a to
3. Přičtení $j$-tého řádku vynásobeného $t\in T$ k $i$-tému řádku.
4. Záměna dvou řádků. Posloupnost takových elementárních úprav značíme $A\sim \sim A^{\prime }$.

Věta: Nechť $Ax=b$ a $A^{\prime }x=b^{\prime }$ jsou dvě soustavy rovnic splňující $(A|b)\sim \sim (A^{\prime }|b^{\prime })$, pak obě soustavy mají stejné množiny řešení. Důkaz: Bereme v potaz vždy jen dotknutý $i$-tý řádek, protože ostatní jsou nezměněny:

1. $Ax=b⟹A^{\prime }x=b^{\prime }$ pro násobení

$$\begin{array}{r}{a}_{i,1}^{\prime }{x}_1+\cdots +a_{i,n}^{\prime }{x}_n=t{a}_{i,1}{x}_1+\cdots +t{a}_{i,n}{x}_n\stackrel{p\check{r}edpoklad}{=}t{b}_i=b_i^{\prime }\end{array}$$

2. $A^{\prime }x=b^{\prime }⟹Ax=b$ pro násobení

$$\begin{array}{r}{a}_{i,1}{x}_1+\cdots +a_{i,n}{x}_n=\frac{1}{t}{a}_{i,1}^{\prime }{x}_1+\cdots +\frac{1}{t}{a}_{i,n}^{\prime }{x}_n\stackrel{p\check{r}edpoklad}{=}\frac{1}{t}{b}_i^{\prime }=b_i\end{array}$$

3. $Ax=b⟹A^{\prime }x=b^{\prime }$ pro součet řádků

$$\begin{array}{r}{a}_{i,1}^{\prime }{x}_1+\cdots +a_{i,n}^{\prime }{x}_n=(a_{i,1}+a_{j,1})x_1+\cdots +(a_{i,n}+a_{j,n})x_n=\\ =(a_{i,1}{x}_1+\cdots +a_{i,n}{x}_n)+(a_{j,1}{x}_1+\cdots +a_{j,n}{x}_n)=b_i+b_j=b_i^{\prime }\end{array}$$

4. $A^{\prime }x=b^{\prime }⟹Ax=b$ pro součet řádků

$$\begin{array}{rl}{a}_{i,1}{x}_1+\cdots +a_{i,n}{x}_n=a_{i,1}{x}_1+\cdots +a_{i,n}{x}_n+b_j-b_j\stackrel{p\check{r}edpoklad}{=}& \\ =(a_{i,1}{x}_1+\cdots +a_{i,n}{x}_n)+(a_{j,1}{x}_1+\cdots +a_{j,n}{x}_n)-b_j\stackrel{p\check{r}eh\acute{a}zen\acute{ı}}{=}& \\ =(a_{i,1}+a_{j,1})x_1+\cdots +(a_{i,n}+a_{j,n})x_n-b_j=a_{i,1}^{\prime }{x}_1+\cdots +a_{i,n}^{\prime }{x}_n& =\\ =b_i^{\prime }-b_j=b_i+b_j-b_j=b_i& \end{array}$$

---

Gaussova eliminace

Definice: Matice $A$ je řádkově odstupňovaném tvaru $(REF)$, pokud jsou nenulové řádky seřazeny podle počtu počátečních nul a nulové řádky jsou pod nenulovými. Značíme $j(i)=\min \{j:a_{i,j}\ne 0\}$. První nenulový prvek v každém řádku je pivot.

	\begin{algorithm}
	\caption{Gaussova eliminace}
	\begin{algorithmic}
	\Input{Matice $A$}
	\Output{Matice $A$ v $REF$ tvaru}
	\For{řádku $i$}\State{určeme $j(i)$, kde pro prázdný řádek $j(i) = \infty$}
	\State{seřaďme řádky $A$ podle $j(i)$}
    \EndFor
    \While{True}
		\If{$\exists i: j(i) = j(i+1) < \infty$}
			\State{přičtěme $- \frac{a_{i+1,j(i+1)}}{a_{i,j(i)}}$ násobek $i$-tého řádku k $(i+1)$-mu řádku}
        \Else
	        \Return{A}
        \EndIf
    \EndWhile
	\end{algorithmic}
	\end{algorithm}

Definice: Proměnné v $A^{\prime }x=b^{\prime }$ v $REF$, jsou bázické odpovídají-li sloupcům nějakého pivotu, ostatní jsou volné.

Definice: Hodnost matice $A$ je $rank(A)$ rovna počtu pivotů v libovolné $A^{\prime }$ v $REF$ tvaru.

---

Gaussova-Jordanova eliminace

Definice: Redukovaný odstupňovaný tvar matice $A$ je $REF$, kde každý pivot má hodnotu $1$ a všechny ostatní prvky ve sloupcích s pivoty jsou 0.

Můžeme rozšířit Gaussovu eliminaci na Gauss-Jordanovu eliminaci následovně

1. najdeme pomocí algoritmu $REF$ tvar,
2. každý řádek vydělíme $a_{i,j(i)}$, tedy příslušným pivotem,
3. $\forall i=\mathbf{r},\dots ,1$, eliminujeme každé $a_{i^{\prime },j(i)}$ s $i^{\prime }<i$ přičtením $-a_{i^{\prime },j(i)}$-násobku $i$-tého řádku k $i^{\prime }$-tému čímž nad $a_{i,j(i)}$ dostaneme $0$.

---

Množiny řešení

Homogenní soustava $Ax=0$.

Její množina řešení je nulový prostor (jádrо matice):

$$\mathrm{Ker}(A)=\{x\in {\mathbb{R}}^n\mid Ax=0\}.$$

Nechť $\mathrm{rank}(A)=r$. Pak

• dimenze prostoru je $n-r$.
• Existuje báze $v_1,\dots ,v_{n-r}\in {\mathbb{R}}^n$ taková, že

$$\mathrm{Ker}(A)=\{p_1{v}_1+\cdots +p_{n-r}{v}_{n-r}\mid p_i\in \mathbb{R}\}.$$

• Soustava má pouze triviální řešení $x=0$ právě když $r=n$.

Nehomogenní soustava $Ax=b.$

Řešení existuje právě tehdy, když $b$ leží v obrazu matice $A$. Množina řešení je označována

$$\{x\in {\mathbb{R}}^n\mid Ax=b\}.$$

Vztah mezi homogenní a nehomogenní množinou řešení

1. Pokud $y$ řeší $Ay=b$ a $x$ řeší $Ax=0$, pak $x+y$ řeší $A(x+y)=b$.
2. Pokud $x_1,x_2$ řeší $Ax=b$, pak $x_1-x_2$ řeší $A(x_1-x_2)=0$.
   Tedy množina řešení nehomogenní soustavy je afinní posunutí jádra matice:

$$\{y+x\mid x\in \mathrm{Ker}(A)\}.$$

Pokud existuje nějaké konkrétní řešení $y$ (tzv. partikulární řešení), pak

$$\{x\mid Ax=b\}=y+\mathrm{Ker}(A)=\{y+p_1{v}_1+\cdots +p_{n-r}{v}_{n-r}\mid p_i\in \mathbb{R}\}.$$

• Postup řešení (Gaussova eliminace)
  1. Sestrojme rozšířenou matici $(A\mid b)$.
  2. Převeďme ji do stupňovitého (resp. redukovaného) tvaru $(A^{\prime }\mid b^{\prime })$.
  3. Zkontrolujme kompatibilitu: pokud v posledním sloupci $b^{\prime }$ vznikne pivot, soustava nemá řešení.
  4. Řešme homogenní část $A^{\prime }x=0$: vybereme $n-r$ volných proměnných jako parametry $p_i$ a vyjádříme zbývající proměnné lineárně v jejich závislosti.
  5. Najděme partikulární řešení $y$ řešící $A^{\prime }x=b^{\prime }$ (např. nastavením všech parametrů na nulu a vyřešením zbývajících rovnic).
  6. Celková množina řešení je

$$y+\mathrm{span}\{v_1,\dots ,v_{n-r}\}.$$

• Ověření úplnosti množiny řešení
  Dosazení obecného řešení $x=y+\sum p_i{v}_i$ zpět do původní soustavy ověří jak správnost partikulárního řešení $y$, tak úplnost generované afinní množiny.