Gaussova a Gauss-Jordanova eliminace

Řeším soustavu rovnic ${\bf A} \vec{x} = \vec{b}$. V prvním kroku nechť prvek $a_{11} \ne 0$ (lze vždy dosáhnout přehozením rovnic). Prvek $a_{11}$, použitý k úpravě rovnic 2, ..., n nazveme hlavním prvkem (pivot).

Od i-té rovnice odečteme 1.rovnici násobenou multiplikátorem $m_i^{(1)} = - a_{i1}/a_{11}$. Modifikovaná soustava bude mít v 1.sloupci pod diagonálou samé 0. Úprava prováděná současně s pravou stranou odpovídá násobení rovnice maticí

$${\bf D_1} = \left( \begin{array}{ccccc} 1 & 0 & 0 & \ldots &... ...s \\ -a_{n1}/a_{11} & 0 & 0 & \ldots & 1 \end{array} \right)$$

Rovnice po první úpravě má tvar ${\bf D_1 A} \vec{x} = {\bf D_1} \vec{b}$, označíme ${\bf D_1 A} \equiv {\bf A}^{(1)}$ a ${\bf D_1} \vec{b} \equiv \vec{b}^{(1)}$.

Po $k-1$ úpravách má matice ${\bf A}^{(k-1)}$ tvar

$${\bf A}^{(k-1)} = \left( \begin{array}{ccccccc} a_{11} & a_{... ... a_{nk}^{(k-1)} & \ldots & a_{n,n}^{(k-1)} \end{array} \right)$$

Zde horní index značí počet úprav daného prvku.

Pokud $a_{kk}^{(k-1)} \ne 0$, lze ho zvolit za hlavní prvek, spočítat multiplikátory $m_i^{(k)} = - a_{ik}^{(k-1)}/a_{kk}^{(k-1)}$ pro $i = k+1, \ldots,\ n$ a upravit příslušné rovnice.

V $k$-tém kroku úpravy používám jako hlavní prvek prvek $k-1$-krát upravený (odečítání!) hlavní prvek $\rightarrow$ ztráta přesnosti $\Rightarrow$ výběr hlavního prvku.

Bez výběru hlavního prvku - přímé metody nepoužitelné pro obecné matice!!

Počet operací

Na každou 0 $\rightarrow \le n$ vnitřních cyklů, potřebuji $n(n-1)$ prvků $\rightarrow$ 0. Celkový počet vnitřních cyklů $\sim n^3$ (přesněji $\simeq 1/3\ n^3$), složitost algoritmu je řádu $n^3$.

Gauss-Jordanova eliminace

Upravují se všechny prvky mimo diagonálu. Matice se převede na jednotkovou ${\bf I}$. Přímo spočtu inverzní matici ${\bf A}^{-1}$. Vyšší počet operací $\simeq n^3$ vnitřních cyklů.