Definice: Vektor o složkách je uspořádaná -tice
Definice: Matice typu je soubor čísel z daného tělesa uspořádané do tabulky s řádky a sloupci. Píšeme .
Na maticích zavádíme operaci transpozice, kde platí Tuto operaci můžeme zavést i na vektorech uvažujeme-li vektor jako matici tímto zavádíme řádkové vektory.
Reprezentace soustavy rovnic
Mějme soustavu rovnic nad nějakým tělesem, že a mějme soustavu rovnic
Nechť a vektor neznámých pak soustava rovnic výše se dá reprezentovat pomocí , kde
- je matice soustavy,
- je vektor pravých stran,
- je rozšířená matice soustavy. Vektor je řešení soustavy pokud splňuje všechny její rovnice. Speciálními tzv. homogenními soustavami jsou takové, kde umožňující .
Elementární řádkové úpravy
Definice: píšeme, pokud lze získat jakoukoliv z následujících elementárních řádkových úprav:
- Vynásobení - tého řádku nenulovou konstantou , tedy formálně
- Přičtení - tého řádku k -tému, formálně Z těchto úprav snadno odvodíme další dvě a to
- Přičtení -tého řádku vynásobeného k -tému řádku.
- Záměna dvou řádků. Posloupnost takových elementárních úprav značíme .
Věta: Nechť a jsou dvě soustavy rovnic splňující , pak obě soustavy mají stejné množiny řešení. Důkaz: Bereme v potaz vždy jen dotknutý -tý řádek, protože ostatní jsou nezměněny:
- pro násobení
- pro násobení
- pro součet řádků
- pro součet řádků
Gaussova eliminace
Definice: Matice je řádkově odstupňovaném tvaru , pokud jsou nenulové řádky seřazeny podle počtu počátečních nul a nulové řádky jsou pod nenulovými. Značíme . 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 v , jsou bázické odpovídají-li sloupcům nějakého pivotu, ostatní jsou volné.
Definice: Hodnost matice je rovna počtu pivotů v libovolné v tvaru.
Gaussova-Jordanova eliminace
Definice: Redukovaný odstupňovaný tvar matice je , kde každý pivot má hodnotu a všechny ostatní prvky ve sloupcích s pivoty jsou 0.
Můžeme rozšířit Gaussovu eliminaci na Gauss-Jordanovu eliminaci následovně
- najdeme pomocí algoritmu tvar,
- každý řádek vydělíme , tedy příslušným pivotem,
- , eliminujeme každé s přičtením -násobku -tého řádku k -tému čímž nad dostaneme .
Množiny řešení
Homogenní soustava .
Její množina řešení je nulový prostor (jádrо matice):
Nechť . Pak
- dimenze prostoru je .
- Existuje báze taková, že
- Soustava má pouze triviální řešení právě když .
Nehomogenní soustava
Řešení existuje právě tehdy, když leží v obrazu matice . Množina řešení je označována
Vztah mezi homogenní a nehomogenní množinou řešení
- Pokud řeší a řeší , pak řeší .
- Pokud řeší , pak řeší .
Tedy množina řešení nehomogenní soustavy je afinní posunutí jádra matice:
Pokud existuje nějaké konkrétní řešení (tzv. partikulární řešení), pak
- Postup řešení (Gaussova eliminace)
- Sestrojme rozšířenou matici .
- Převeďme ji do stupňovitého (resp. redukovaného) tvaru .
- Zkontrolujme kompatibilitu: pokud v posledním sloupci vznikne pivot, soustava nemá řešení.
- Řešme homogenní část : vybereme volných proměnných jako parametry a vyjádříme zbývající proměnné lineárně v jejich závislosti.
- Najděme partikulární řešení řešící (např. nastavením všech parametrů na nulu a vyřešením zbývajících rovnic).
- Celková množina řešení je
- Ověření úplnosti množiny řešení
Dosazení obecného řešení zpět do původní soustavy ověří jak správnost partikulárního řešení , tak úplnost generované afinní množiny.