Zdrojový kód
%\wikiskriptum{01NM}
\section{Finitní metody}
\subsection{Přehled potřebných pojmů a vět}
\begin{define}
\begin{enumerate}
\item Vektorem rozumíme prvek prostoru $\mathbbm C^{n,1}$.
\newline Značení složek: $x_i^{(k)}$ je $i$-tá složka vektoru $\vk x$.
\item Maticí typu $(m\, n)$ rozumíme prvek prostoru $\mathbbm C^{m,n}$.
\newline Značení prvků: $[A]_{ij}$ je prvek v $i$-tém řádku a $j$-tém sloupci matice $A$.
\end{enumerate}
\end{define}
\begin{define}
Buď $A\in\mathbbm C^{m, n}$. Potom matici $A^H=\bar A^T$ nazveme maticí hermitovsky sdruženou k matici A.
\end{define}
\begin{define}
Buď $A\in\mathbbm C^{n, n}$.
\begin{enumerate}
\item Matice $A$ se nazývá normální, je-li $A^HA=AA^H$.
\item Matice $A$ se nazývá hermitovská, je-li $A^H=A$.
\item Matice $A$ se nazývá unitární, je-li $A^HA=I$.
\end{enumerate}
\end{define}
\begin{define}
\begin{enumerate}
\item Hermitovská matice se nazývá symetrická, jsou-li všechny její prvky reálné.
\item Unitární matice se nazývá ortogonální, jsou-li všechny její prvky reálné.
\end{enumerate}
\end{define}
\begin{remark}
\begin{enumerate}
\item Čtvercová matice $A$, která má všechny prvky reálné, je symetrická, právě když $A^T=A$.
\item Čtvercová matice $A$, která má všechny prvky reálné, je ortogonální, právě když $A^TA=I$.
\item Pojmy symetrické a ortogonální matice mají nepatrně jiný význam než loni: Tehdy byly tyto pojmy zavedeny pouze pro matice nad $\mathbbm R$, nyní se však pohybujeme nad $\mathbbm C$.
\end{enumerate}
\end{remark}
\begin{define}
Buď $L=(l_{ij})$ čtvercová matice. Řekneme, že je dolní (levá) trojúhelníková, platí-li $l_{ij}=0$ pro $j>i$.
Buď $R=(r_{ij})$ čtvercová matice. Řekneme, že je horní (pravá) trojúhelníková, platí-li $r_{ij}=0$ pro $i>j$.
\end{define}
\begin{theorem}
\label{maticetrojsouc}
Součin dolních (horních) trojúhelníkových matic je opět dolní (horní) trojúhelníková matice a diagonálními prvky tohoto součinu jsou součiny odpovídajících diagonálních prvků faktorů.
\begin{proof}
Důkaz provedeme pro případ dolních trojúhelníkových matic. Buďte $A=(a_{ij})\, B=(b_{ij})$ dolní trojúhelníkové matice. Označme $C=(c_{ij})=AB$. Potom platí
\begin{equation}
\label{cviceni11}
c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\hdots+a_{in}b_{nj}.
\end{equation}
Protože $a_{ii+1}=a_{ii+2}=\hdots=a_{in}=0$ a $b_{1j}=b_{2j}=\hdots=b_{j-1j}=0$, jsou v (\ref{cviceni11}) nenulové nejvýše sčítance $j$-tý, $(j+1)$-ní, $\hdots$, $i$-tý. Pro $j>i$ je tedy $c_{ij}=0$ a matice $C$ je dolní trojúhelníková.
Druhá část tvrzení: Položíme-li v (\ref{cviceni11}) $j=i$, dostaneme $c_{ii}=a_{ii}b_{ii}$.
\end{proof}
\end{theorem}
\begin{theorem}
\label{maticetrojinv}
Inverzní matice k regulární dolní (horní) trojúhelníkové matici je opět dolní (horní) trojúhelníková matice a jejími diagonálními prvky jsou převrácené hodnoty původních diagonálních prvků.
\begin{proof}
Důkaz opět provedeme pouze pro případ dolní trojúhelníkové matice. Buď $A=(a_{ij})$ regulární dolní trojúhelníková matice. Označme $B=(b_{ij})=A^{-1}$. Vyjděme ze vztahu $AB=I$. Zvolme si $j$-tý sloupec matice $B$ a rozepišme tento vztah po řádcích. Pro první řádek dostaneme $a_{11}b_{1j}=0$. Protože regulární trojúhelníková matice musí mít všechny diagonální prvky nenulové, vyplývá odtud $b_{1j}=0$. Další řádek:
\[
a_{21}\underbrace{b_{1j}}_{=0}+\underbrace{a_{22}}_{\ne 0}b_{2j}=0\Rightarrow b_{2j}=0
\]
a tak to jde až do $(j-1)$-ního řádku. Pro $j$-tý řádek dostaneme
\[
\underbrace{{a_{j1}b_{1j}}+a_{j2}b_{2j}+\hdots+a_{jj-1}b_{j-1j}}_{=0}+a_{jj}b_{jj}=1\Rightarrow b_{jj}=\frac{1}{a_{jj}}.
\]
\end{proof}
\end{theorem}
\begin{define}
Buď $A=(a_{ij})$ čtvercová matice. Řekneme, že je silně regulární, jsou-li všechny její vedoucí hlavní minory nenulové, tj. platí-li
\[
a_{11}\ne 0\,
\left |
\begin{matrix}
a_{11} & a_{12}\\
a_{21} & a_{22}
\end{matrix}
\right |
\ne 0\, \hdots\, \det A\ne 0.
\]
\end{define}
\begin{theorem}[trojúhelníkový rozklad]
\label{ALDR}
Každou silně regulární matici $A$ lze jediným způsobem vyjádřit ve tvaru $A=LDR$, kde $L$ je dolní trojúhelníková matice s jedničkami na diagonále, $D$ diagonální matice a $R$ horní trojúhelníková matice s jedničkami na diagonále.
\begin{proof}
Jednoznačnost: Nechť má silně regulární matice $A$ dva různé trojúhelníkové rozklady $A=LDR=L'D'R'$. Z poslední rovnosti plyne $LD=L'D'R'R^{-1}$ a dále ${L'}^{-1}LD=D'R'R^{-1}$. Na levé straně této rovnice je podle vět \ref{maticetrojsouc} a \ref{maticetrojinv} dolní a na pravé straně horní trojúhelníková matice, musí se tedy jednat o diagonální matici. Podle předpokladu mají matice ${L'}^{-1}L$ a $R'R^{-1}$ jedničky na diagonále, takže matice ${L'}^{-1}LD$ musí mít podle věty \ref{maticetrojsouc} tytéž diagonální prvky jako matice $D$. Je tedy ${L'}^{-1}LD=D$, to ale znamená, že ${L'}^{-1}L=I\Rightarrow L=L'$. Podobně zjistíme, že $R=R'$ a odtud ihned plyne i $D=D'$.
Existence: Matematickou indukcí podle řádu $n$ matice $A$. Pro $n=1$ je rozklad triviální: $A=(a_{11})=(1)(a_{11})(1)$. Nechť tvrzení platí pro matici typu $(n-1\, n-1)$. Dokážeme, že platí i pro matici typu $(n\, n)$. Buď
\begin{equation}
\label{cviceni12}
A=\left(
\begin{matrix}
\hat A & \vec v\\
\vec u^T & \alpha
\end{matrix}
\right)
\end{equation}
silně regulární matice. Podle definice musí být i matice $\hat A$ silně regulární, a tak podle indukčního předpokladu existuje pro ni rozklad $\hat A=\hat L\hat D\hat R$. Hledejme rozklad matice $A$ ve tvaru
\[
A=\left(
\begin{matrix}
\hat L & \vec o\\
\vec l^T & 1
\end{matrix}
\right)\left(
\begin{matrix}
\hat D & \vec o\\
\vec o^T & \delta
\end{matrix}
\right)\left(
\begin{matrix}
\hat R & \vec r\\
\vec o^T & 1
\end{matrix}
\right)=\left(
\begin{matrix}
\hat L & \vec o\\
\vec l^T & 1
\end{matrix}
\right)\left(
\begin{matrix}
\hat D\hat R & \hat D\vec r\\
\vec o^T & \delta
\end{matrix}
\right)=\left(
\begin{matrix}
\hat L\hat D\hat R & \hat L\hat D\vec r\\
\vec l^T\hat D\hat R & \vec l^T\hat D\vec r+\delta
\end{matrix}
\right).
\]
Poslední matici porovnáme s maticí na pravé straně (\ref{cviceni12}) a dostaneme $\vec r=\hat D^{-1}\hat L^{-1}\vec v$, $\vec l^T=\vec u^T\hat R^{-1}\hat D^{-1}\, \delta=\alpha-\vec l^T\hat D\vec r$. Našli jsme tedy požadovaný rozklad matice $A$.
\end{proof}
\end{theorem}
\begin{theorem}[počítání s blokovými maticemi]
Operace s blokovými maticemi lze provádět stejně jako s prvkovými maticemi, je-li rozdělení na bloky provedeno tak, aby dílčí operace měly smysl.
Speciálně, při násobení blokových matic $A\, B$ musí být v $i$-tém blokovém řádku matice $B$ tolik prvkových řádků, kolik je prvkových sloupců v $i$-tém blokovém sloupci matice $A$.
\end{theorem}
\begin{define}
\label{podobnost}
Čtvercové matice $A\, B$ nazýváme podobné, jestliže existuje regulární matice $T$ taková, že platí $A=T^{-1}BT$.
\end{define}
\begin{remark}
Význam předchozí definice je následující:
Buďte $\mathcal X$ báze lineárního prostoru $P$, $L$ lineární operátor na $P$ a označme $B$ $=$ $^{\mathcal X}L$ matici operátoru $L$ v bázi $\mathcal X$. Potom matice $A$ je podobná matici $B$, jestliže existuje taková báze $\mathcal Y$ prostoru $P$, že $A$ $=$ $^{\mathcal Y}L$.
Matice $T$ z předchozí definice je tedy maticí přechodu \linebreak[4]$T$ $=$ $_{\mathcal X}\text{\bf P}_{\mathcal Y}$.
\end{remark}
\begin{tvrz}
Podobné matice mají stejné charakteristické polynomy, a tudíž i stejná vlastní čísla, a k pevně zvolenému vlastnímu číslu $\lambda$ přísluší stejný počet lineárně nezávislých vlastních vektorů u obou matic.
\begin{proof}
První část tvrzení: Buďte $A\, B$ dvě podobné matice, tj. nechť existuje taková regulární matice $T$, že $A=T^{-1}BT$. Potom
\[
\abs{A-\lambda I}=\abs{T^{-1}BT-\lambda T^{-1}T}=\abs{T^{-1}(B-\lambda I)T}=\abs{T}^{-1}\abs{B-\lambda I}\abs{T}=\abs{B-\lambda I}.
\]
Druhá část tvrzení: Buďte $\lambda$ vlastní číslo matice $A$, $\vec x$ k němu příslušející vlastní vektor. Potom platí $A\vec x=\lambda\vec x\Leftrightarrow T^{-1}BT\vec x=\lambda\vec x\Leftrightarrow BT\vec x=\lambda T\vec x$. Druhá část tvrzení nyní vyplývá z toho, že je-li $T$ regulární matice, potom je soubor vektorů $\vec x^{(1)}\, \hdots\, \vec x^{(n)}$ lineárně nezávislý právě tehdy, je-li lineárně nezávislý soubor $T\vec x^{(1)}\, \hdots\, T\vec x^{(n)}$.
\end{proof}
\end{tvrz}
\begin{remark}
\begin{enumerate}
\item Předchozí tvrzení neznamená nic jiného, než že vlastní čísla lineárního operátoru jsou dána jednoznačně, a to i co do násobností. Připomeňme, že násobnost vlastního čísla $\lambda$ jakožto kořene charakteristického polynomu se nazývá algebraická násobnost a počet lineárně nezávislých vlastních vektorů příslušejících k vlastnímu číslu $\lambda$ se nazývá geometrická násobnost.
\item Připomeňme si větu 92 z lineární algebry: Lineární operátor na prostoru konečné dimenze nad tělesem $T$ je diagonalizovatelný právě tehdy, jsou-li všechny kořeny charakteristického polynomu prvky tělesa $T$ a je-li geometrická násobnost každého vlastního čísla tohoto operátoru rovna jeho algebraické násobnosti. Protože se pohybujeme nad tělesem $\mathbbm C$, je první podmínka automaticky splněna.\footnote{Zároveň to ovšem znamená, že matice, která má všechny prvky reálné, může mít imaginární vlastní čísla.} V duchu definice \ref{podobnost} můžeme tedy větu přeformulovat takto: Matice je podobná nějaké diagonální matici, právě když jsou si algebraická a geometrická násobnost každého jejího vlastního čísla rovny. Zobecněním tohoto tvrzení je následující věta:
\end{enumerate}
\end{remark}
\begin{theorem}[Jordan]
Buďte $\lambda_1\, \hdots\, \lambda_p$ všechna navzájem různá vlastní čísla matice $A\in T^{n, n}$. Potom je matice $A$ podobná blokově diagonální matici
\[
\left (
\begin{matrix}
J_1^{(1)}\\
& \ddots\\
& & J_{s_1}^{(1)}\\
& & & \ddots\\
& & & & J_1^{(p)}\\
& & & & & \ddots\\
& & & & & & J_{s_p}^{(p)}
\end{matrix}
\right )
\]
typu $(n\, n)$, kde diagonální bloky $J_i^{(k)}\, k\in\hat p\, i\in\widehat{s_k}$ jsou tvaru
\[
J_i^{(k)}=
\left (
\begin{matrix}
\lambda_k\\
1 & \ddots\\
& \ddots & \ddots\\
& & 1 & \lambda_k
\end{matrix}
\right )
\]
nebo speciálně $J_i^{(k)}=(\lambda_k)$.
Přitom až na pořadí diagonálních bloků je tato matice dána jednoznačně.
\end{theorem}
\begin{remark}
Číslo $s_k$ v předchozí větě je geometrickou násobností vlastního čísla $\lambda_k$, zatímco součet počtu řádků, resp. sloupců všech bloků $J_i^{(k)}\, i\in\widehat{s_k}$ je jeho násobností algebraickou. Zároveň samozřejmě platí $\sum_{k=1}^p s_k=n$.
\end{remark}
\begin{define}
Elementární úpravou provedenou v dané matici nazveme
\begin{itemize}
\item vynásobení všech prvků zvoleného řádku, resp. sloupce matice číslem $\alpha$,
\item připočtení $\alpha$-násobků prvků zvoleného $j$-tého řádku, resp. sloupce k prvkům zvoleného $i$-tého řádku, resp. sloupce.
\end{itemize}
\end{define}
\begin{theorem}[pravidlo o elementárních úpravách]
Provedeme-li na řádky, resp. sloupce matice $A$ konečnou posloupnost elementárních úprav, je výsledek ekvivalentní násobení matice $A$ zleva, resp. zprava maticí, která vznikne z jednotkové matice $I$ odpovídajícího rozměru stejnou posloupností elementárních úprav.
\end{theorem}
\subsection{Gaussova eliminační metoda}
Gaussova eliminační metoda je principiálně nejjednodušší a také nejpoužívanější metodou pro řešení soustav lineárních algebraických rovnic. Vyskytuje se celá řada modifikací této metody. Společným základním principem všech je převedení problému na řešení soustavy s trojúhelníkovou maticí.
\subsubsection{Schéma jediného dělení}
Řešme soustavu
\begin{equation}
\label{soustava}
\begin{array}{c}
a_{11}x_1+a_{12}x_2+\hdots+a_{1n}x_n = g_1\\
a_{21}x_1+a_{22}x_2+\hdots+a_{2n}x_n = g_2\\
\hdots\\
a_{n1}x_1+a_{n2}x_2+\hdots+a_{nn}x_n = g_n\\
\end{array}
\end{equation}
s regulární maticí $A=(a_{ij})$. Převedení na soustavu s trojúhelníkovou maticí se provádí v $n$ krocích. V prvním kroku nejdříve vydělíme první rovnici prvkem $a_{11}$ (předpokládáme proto $a_{11}\ne 0$). Získáme rovnici tvaru
\begin{equation}
\label{Gauss}
x_1+b_{12}x_2+\hdots+b_{1n}x_n = c_1,
\end{equation}
kde $b_{1j}=\frac{a_{1j}}{a_{11}}$ pro $j=2\, \hdots\, n$ a $c_1=\frac{g_1}{a_{11}}$. Dále od $i$-té rovnice ($i=2\, \hdots\, n$) odečteme $a_{i1}$-násobek rovnice (\ref{Gauss}), takže získáme soustavu $n-1$ rovnic o $n-1$ neznámých
\[
\begin{array}{c}
a_{22}^{(1)}x_2+\hdots+a_{2n}^{(1)}x_n = g_2^{(1)}\\
\hdots\\
a_{n2}^{(1)}x_2+\hdots+a_{nn}^{(1)}x_n = g_n^{(1)},\\
\end{array}
\]
kde $a_{ij}^{(1)}=a_{ij}-a_{i1}b_{1j}$ a $g_i^{(1)}=g_i-a_{i1}c_1$ pro $i\, j=2\, \hdots\, n$. Na tuto soustavu použijeme stejný postup ve druhém kroku (předpokládáme tedy $a_{22}^{(1)}\ne 0$). Analogicky postupujeme dále. Po $n$ krocích dojdeme k soustavě tvaru
\begin{equation}
\label{trojG}
\begin{array}{rcl}
x_1+b_{12} x_2+\hdots+b_{1n} x_n &= &c_1\\
x_2+\hdots+b_{2n} x_n &= &c_2\\
\hdots\\
x_n &= &c_n.
\end{array}
\end{equation}
V $k$-tém kroku se pro $i\, j=k+1\, \hdots\, n$; $k=2\, \hdots\, n$ počítá
\[
b_{kj}=\frac{a_{kj}^{(k-1)}}{a_{kk}^{(k-1)}}\, c_k=\frac{g_k^{(k-1)}}{a_{kk}^{(k-1)}}\, a_{ij}^{(k)}=a_{ij}^{(k-1)}-a_{ik}^{(k-1)} b_{kj}\, g_i^{(k)}=g_i^{(k-1)}-a_{ik}^{(k-1)} c_k.
\]
Podmínkou proveditelnosti tohoto procesu --- nazýváme ho přímý chod --- je, aby $\forall k\in\hat n$ platilo $a_{kk}^{(k-1)}\ne 0$. Řešení soustavy je snadné:
\[
x_n=c_n\, x_k=c_k-(b_{kk+1} x_{k+1}+\hdots +b_{kn} x_n),
\]
kde $k=n-1\, n-2\, \hdots\, 1$. Výpočet řešení podle těchto vzorců se nazývá zpětný chod.
\begin{sloz}
Přímý chod: v každém kroku se provádí $n^2$ operací, neboť se zpracovává matice typu $(n, n)$. Složitost je tedy $O(n^3)$.
Zpětný chod: v každém kroku se provádí ,,skalárních součin", tj. $n$ násobení a sčítání. Složitost je tedy $O(n^2)$.
\end{sloz}
\begin{tvrz}
\label{resitelnostG}
Přímý chod Gaussovy eliminační metody je proveditelný (tj. \linebreak[4]$a_{kk}^{(k-1)}\ne 0$ pro všechna $k\in\hat n$) jen tehdy, je-li matice soustavy (\ref{soustava}) silně regulární.
\begin{proof}
Označme $P=(A\, G)$ rozšířenou matici soustavy (\ref{soustava}). V prvním kroku přímého chodu se tato matice převede do tvaru
\[
P^{(1)}=\left(
\begin{matrix}
1 & b_{12} & \hdots & b_{1n} & c_1\\
0 & a_{22}^{(1)} & \hdots & a_{2n}^{(1)} & g_2^{(1)}\\
\vdots & \vdots & & \vdots & \vdots\\
0 & a_{n2}^{(1)} & \hdots & a_{nn}^{(1)} & g_n^{(1)}\\
\end{matrix}
\right).
\]
Podle pravidla o elementárních úpravách tedy platí $P^{(1)}=L^{(1)}P$, kde
\[
L^{(1)}=\left(
\begin{matrix}
\frac{1}{a_{11}}\\
-\frac{a_{21}}{a_{11}} & 1\\
\vdots & & \ddots\\
-\frac{a_{n1}}{a_{11}} & \hdots & \hdots & 1\\
\end{matrix}
\right).
\]
Obecně v $k$-tém kroku matici
\[
P^{(k-1)}=\left(
\begin{matrix}
1 & b_{12} & \hdots & \hdots & b_{1k} & \hdots & b_{1n} & c_1\\
& 1 & \hdots & \hdots & b_{2k} & \hdots & b_{2n} & c_2\\
& & \ddots & & \vdots & & \vdots & \vdots\\
& & & 1 & b_{k-1k} & \hdots & b_{k-1n} & c_{k-1}\\
& & & & a_{kk}^{(k-1)} & \hdots & a_{kn}^{(k-1)} & g_k^{(k-1)}\\
& & & & \vdots & & \vdots & \vdots\\
& & & & a_{nk}^{(k-1)} & \hdots & a_{nn}^{(k-1)} & g_n^{(k-1)}\\
\end{matrix}
\right)
\]
převádíme do tvaru
\[
P^{(k)}=\left(
\begin{matrix}
1 & b_{12} & \hdots & b_{1k} & b_{1k+1} & \hdots & b_{1n} & c_1\\
& 1 & \hdots & b_{2k} & b_{2k+1}& \hdots & b_{2n} & c_2\\
& & \ddots & & \vdots & & \vdots & \vdots\\
& & & 1 & b_{kk+1} & \hdots & b_{kn} & c_k\\
& & & & a_{k+1k+1}^{(k)} & \hdots & a_{k+1n}^{(k)} & g_{k+1}^{(k)}\\
& & & & \vdots & & \vdots & \vdots\\
& & & & a_{nk+1}^{(k)} & \hdots & a_{nn}^{(k)} & g_n^{(k)}\\
\end{matrix}
\right)
\]
a tato úprava je ekvivalentní vynásobení matice $P^{(k-1)}$ zleva maticí
\[
L^{(k)}=\left(
\begin{matrix}
1\\
& \ddots\\
& & 1\\
& & & \frac{1}{a_{kk}^{(k-1)}}\\
& & & -\frac{a_{k+1k}^{(k-1)}}{a_{kk}^{(k-1)}} & 1\\
& & & \vdots & & \ddots\\
& & & -\frac{a_{nk}^{(k-1)}}{a_{kk}^{(k-1)}} & & & 1\\
\end{matrix}
\right).
\]
Nakonec takto získáme rozšířenou matici $P^{(n)}=(B\, C)$ soustavy (\ref{trojG}). Přitom zřejmě platí
\[
P^{(n)}=\underbrace{L^{(n)}\hdots L^{(1)}}_{\text{ozn. }L}P,
\]
tj. $(B\, C)=L(A\, G)=(LA\, LG)$. Odtud $B=LA$ neboli
\[
\left(
\begin{matrix}
1 & b_{12} & \hdots & b_{1k}\\
& 1 & \hdots & b_{2k}\\
& & \ddots & \vdots\\
& & & 1
\end{matrix}
\right)=\left(
\begin{matrix}
\frac{1}{a_{11}}\\
l_{21} & \frac{1}{a_{22}^{(1)}}\\
\vdots & \vdots & \ddots\\
l_{k1} & l_{k2} & \hdots & \frac{1}{a_{kk}^{(k-1)}}
\end{matrix}
\right)\left(
\begin{matrix}
a_{11} & a_{12} & \hdots & a_{1k}\\
a_{21} & a_{22} & \hdots & a_{2k}\\
\vdots & \vdots & & \vdots\\
a_{k1} & a_{k2} & \hdots & a_{kk}\\
\end{matrix}
\right).
\]
Přejdeme-li v této rovnici k determinantům, dostaneme
\[
1=\frac{1}{a_{11}a_{22}^{(1)}\hdots a_{kk}^{(k-1)}}\left|
\begin{matrix}
a_{11} & \hdots & a_{1k}\\
\vdots & & \vdots\\
a_{k1} & \hdots & a_{kk}
\end{matrix}
\right|,
\]
tj.
\[
\left|
\begin{matrix}
a_{11} & \hdots & a_{1k}\\
\vdots & & \vdots\\
a_{k1} & \hdots & a_{kk}
\end{matrix}
\right|=a_{11}a_{22}^{(1)}\hdots a_{kk}^{(k-1)}.
\]
Matice soustavy tedy musí být silně regulární.
\end{proof}
\end{tvrz}
\subsubsection{Schéma jediného dělení s hlavními prvky}
Podmínkou řešitelnosti soustavy (\ref{soustava}) je $(\forall k\in\hat n)(a_{kk}^{(k-1)}\ne 0)$. Případ, že některý z těchto prvků je přesně roven nule, je spíše výjimečný a není pro programátora nebezpečný, protože se projeví přetečením a výpočet se zastaví. Mnohem zákeřnější je případ, kdy někter\' y z těchto prvků je v absolutní hodnotě malý vzhledem k ostatním koeficientům, s nimiž se v příslušné fázi výpočtu pracuje. V tomto případě se totiž koeficienty soustavy pro další krok získávají odečítáním velkých čísel, jejichž první cifry se shodují. Protože počítač počítá jen na pevný počet cifer, znamená to, že výsledek odečítání má menší počet platných cifer. Následující příklad ukazuje, jak může odečtením dvou velkých čísel s osmi platnými číslicemi vzniknout číslo s pěti platnými číslicemi:
\[
\begin{array}{r@{.}l}
XXXXX&XXX\\
-XXXXX&XXX\\
\hline
XX&XXXXXX
\end{array}
\]
Pokud je mezi prvky $a_{kk}^{(k-1)}$ malých prvků více, mohlo by se dokonce stát, že výsledek výpočtu nemá s řešením soustavy nic společného. Tento nedostatek odstraňuje schéma jediného dělení s hlavními prvky. Spočívá v tom, že se před zahájením prvního kroku celá matice soustavy prohledá a najde se její v absolutní hodnotě největší prvek $a_{ij}$. Ten se prohlásí za hlavní prvek v prvním kroku, tj. $i$-tá rovnice se jím vydělí a od zbývajících rovnic se odečte takový násobek vzniklé rovnice, aby koeficienty u $j$-té neznámé byly nulové. V dalším kroku se postupuje stejně pro soustavu zmenšenou o $i$-tou rovnici.
Algoritmus vyžaduje, aby v počítači byly vyhrazeny dva organizační celočíselné vektory o $n$ složkách, do nichž se zaznamenává, v jakém pořadí byly hlavní prvky vybírány. Zpětný chod se pak provádí v inverzním pořadí.
\begin{sloz}
Prohledáváme $n$-krát matici typu $(n, n)$ $\Rightarrow$ $O(n^3)$.
\end{sloz}
Daleko rychlejší --- a praxe ukazuje, že téměř stejně účinné --- je schéma jediného dělení s hlavními prvky v řádku/sloupci, kdy napřed najdeme v absolutní hodnotě největší prvek v 1. řádku (sloupci), prohlásíme ho za hlavní v 1. kroku atd. Místo dvou organizačních vektorů zřejmě postačí jeden.
\begin{sloz}
Prohledáváme $n$-krát pole o $n$ prvcích $\Rightarrow$ $O(n^2)$.
\end{sloz}
\subsubsection{Kompaktní schéma}
Schéma jediného dělení a jeho modifikace umožňují řešit soustavu s více pravými stranami jen tehdy, jsou-li všechny pravé strany známy již v okamžiku, kdy se provádí přímý chod. To ale není vždy možné, např. proto, že další pravá strana závisí na řešení soustavy s předchozí pravou stranou.
Označme $P=(A, G)$ rozšířenou matici soustavy (\ref{soustava}).
Z důkazu tvrzení \ref{resitelnostG} je zřejmé, že řešit soustavu Gaussovou eliminační metodou znamená v podstatě pouze nalézt takovou dolní trojúhelníkovou matici $L$, aby platilo
\begin{equation}
\label{Grozklad}
LP=P^{(n)},
\end{equation}
kde $P^{(n)}=(B, C)$ je rozšířená matice soustavy (\ref{trojG}). Rovnici (\ref{Grozklad}) můžeme rozepsat:
\begin{equation}
\label{LAB}
LA=B\, LG=C.
\end{equation}
Z první rovnosti vyplývá $A=L^{-1}B$, kde $L$ (a proto i $L^{-1}$) je dolní trojúhelníková matice a $B$ horní trojúhelníková matice s jedničkami na diagonále. Je-li matice $A$ soustavy silně regulární, potom je podle věty \ref{ALDR} matice $L$ dána jednoznačně, a tak vzhledem k (\ref{Grozklad}) je i matice $P^{(n)}$ dána jednoznačně.
Pokusme se tedy nalézt přímo prvky matic $L^{-1}$ a $P^{(n)}$ na základě podmínky
\begin{equation}
\label{PLP}
P=L^{-1} P^{(n)}.
\end{equation}
Pro jednoduchost zápisu označme
\[
P=
\left(
\begin{matrix}
a_{11} & \hdots & a_{1n} & a_{1n+1}\\
\vdots & & \vdots & \vdots\\
a_{n1} & \hdots & a_{nn} & a_{nn+1}\\
\end{matrix}
\right)
\,
\]
\[
L^{-1}=
\left(
\begin{matrix}
l_{11}\\
l_{21} & l_{22}\\
\vdots & \vdots & \ddots\\
l_{n1} & l_{n2} & \hdots & l_{nn}\\
\end{matrix}
\right)
\, P^{(n)}=
\left(
\begin{matrix}
1 & r_{12} & \hdots & r_{1n} & r_{1n+1}\\
& 1 & \hdots & r_{2n} & r_{2n+1}\\
& & \ddots & \vdots & \vdots\\
& & & 1 & r_{nn+1}\\
\end{matrix}
\right) .
\]
Ze vztahu (\ref{PLP}) dostaneme
\[
\begin{array}{ll}
a_{ij}=l_{i1} r_{1j}+l_{i2} r_{2j}+\hdots+l_{ij-1} r_{j-1j}+l_{ij} & \text{pro }i\ge j\, i\in\hat n,\\
a_{ij}=l_{i1} r_{1j}+l_{i2} r_{2j}+\hdots+l_{ii-1} r_{i-1j}+l_{ii} r_{ij} & \text{pro }i<j\, j\in\widehat{n+1}
\end{array}
\]
a odtud plyne
\[
\begin{array}{rll}
l_{ij}= & a_{ij}-(l_{i1} r_{1j}+l_{i2} r_{2j}+\hdots+l_{ij-1} r_{j-1j}) & \text{pro }i\ge j\, i\in\hat n,\\
r_{ij}= & \frac{1}{l_{ii}} [a_{ij}-(l_{i1} r_{1j}+l_{i2} r_{2j}+\hdots+l_{ii-1} r_{i-1j})] & \text{pro }i<j\, j\in\widehat{n+1}.
\end{array}
\]
Při výpočtu prvků $l_{ij}\, r_{ij}$ se doporučuje následující postup: Prvky se ukládají do jedné matice o $n$ řádcích a $n+1$ sloupcích, přičemž pod a na diagonálu rovnáme prvky matice $L^{-1}$ a nad diagonálu prvky matice $P^{(n)}$ (diagonální jedničky je totiž zbytečné zaznamenávat). Nejprve se vypočte první sloupec matice $L^{-1}$. Je zřejmé, že jeho prvky se získají pouhým opsáním prvního sloupce matice $P$. Pak se počítá první řádek matice $P^{(n)}$ tak, že se odpovídající prvky matice $P$ dělí hodnotou $l_{11}$ (ta je v tomto okamžiku již známa). Další postup znázorňuje schéma:
\[
\begin{matrix}
l_{11} & r_{12} & r_{13} & \hdots & r_{1n} & r_{1n+1} & \leftarrow & \text{2. krok}\\
%\cline{2-6}\\
l_{21} & l_{22} & r_{23} & \hdots & r_{2n} & r_{2n+1} & \leftarrow & \text{4. krok}\\
%\cline{3-6}\\
l_{31} & l_{32} & l_{33}\\
\vdots & \vdots & \vdots\\
l_{n1} & l_{n2} & l_{n3}\\
\uparrow & \uparrow & \uparrow\\
\text{1. krok} & \text{3. krok} & \text{5. krok}
\end{matrix}
\]
Obecný prvek $l_{ij}$ se tedy počítá tak, že se od prvku, který leží na stejném místě v matici $P$, odečte ,,skalární součin" doposud napočtených prvků v témže řádku a sloupci.
Podobně prvek $r_{ij}$ se získá odečtením ,,skalárního součinu" doposud napočtených prvků v témže řádku a sloupci (kromě prvku $l_{ii}$) od prvku $a_{ij}$, ovšem rozdíl je třeba dělit $l_{ii}$.
Při výpočtu na počítači je vhodné prvky $l_{ij}$ a $r_{ij}$ rovnat přímo na místa, kde byly odpovídající prvky $a_{ij}$, neboť ty už dále nebudou potřeba.
Po skončení výpočtu matic $L^{-1}$ a $P^{(n)}$ stačí jen vyřešit soustavu s rozšířenou maticí $P^{(n)}$, tj. provést zpětný chod, a soustava (\ref{soustava}) je vyřešena.
Chceme-li nyní řešit soustavu s novou pravou stranou $A\vec x=\vec f$, postupujeme takto: Podle (\ref{LAB}) platí $A=L^{-1} B$. Máme tedy řešit soustavu $L^{-1}B\vec x=\vec f$, tj.
\[
L^{-1}\vec y=\vec f\, \vec y=B\vec x.
\]
To jsou dvě soustavy s trojúhelníkovými maticemi a ty lze řešit velmi rychle:
\begin{sloz}
$O(n^2)$.
\end{sloz}
\subsection{Modifikace Gaussovy eliminační metody pro soustavy se speciálními vlastnostmi}
\subsubsection{Metoda faktorizace}
Řešme soustavu
\begin{equation}
\label{tridig}
\begin{array}{ccccccccccc}
a_1 x_1 &+& b_1 x_2 & & & & & & &=& f_1\\
c_2 x_1 &+& a_2 x_2 &+& b_2 x_3 & & & & &=& f_2\\
& & c_3 x_2 &+& a_3 x_3 &+& b_3 x_4 & & &=& f_3\\
& & & \ddots & & \ddots & & \ddots & & & \vdots\\
& & & & c_{n-1} x_{n-2} &+& a_{n-1} x_{n-1} &+& b_{n-1} x_n &=& f_{n-1}\\
& & & & & & c_n x_{n-1} &+& a_n x_n &=& f_n
\end{array}
\end{equation}
tak, že se pokusíme rovnou nalézt vzorce pro zpětný chod ve tvaru
\begin{equation}
\label{zchf}
x_k=\mu_k x_{k+1} + \rho_k
\end{equation}
pro $k=n-1\, n-2\, \hdots\, 1$.
Dosadíme-li do $i$-té rovnice soustavy (\ref{tridig}), kde $i=2\, \hdots\, n-1$, (tj. do ,,vnitřní" rovnice) za $x_{i-1}$ ze vztahu (\ref{zchf}), dostaneme
\[
c_i(\mu_{i-1} x_i + \rho_{i-1}) + a_i x_i + b_i x_{i+1}=f_i
\]
a odtud
\[
x_i=\frac{-b_i}{c_i \mu_{i-1} + a_i} x_{i+1} + \frac{f_i-c_i \rho_{i-1}}{c_i \mu_{i-1} + a_i}.
\]
Porovnáním s (\ref{zchf}) získáme
\begin{equation}
\label{miro}
\mu_i=\frac{-b_i}{c_i \mu_{i-1} + a_i}\, \rho_i=\frac{f_i - c_i \rho_{i-1}}{c_i \mu_{i-1} + a_i},
\end{equation}
kde $i=2\, \hdots\, n-1$. První rovnici soustavy (\ref{tridig}) přepíšeme do tvaru
\[
x_1=-\frac{b_1}{a_1} x_2 + \frac{f_1}{a_1}.
\]
Tento vztah opět porovnáme s (\ref{zchf}) a dostaneme
\[
\mu_1=-\frac{b_1}{a_1}\, \rho_1=\frac{f_1}{a_1}.
\]
Poslední rovnice soustavy (\ref{tridig}) tvoří společně s rovnicí $x_{n-1}=\mu_{n-1} x_n + \rho_{n-1}$ systém dvou rovnic o dvou neznámých $x_{n-1}\, x_n$ a z něj vypočteme
\[
x_n=\frac{f_n-c_n \rho_{n-1}}{c_n \mu_{n-1} + a_n}.
\]
Algoritmus lze ještě vylepšit: Položíme-li
\begin{equation}
\label{vyleps}
c_1=0\, b_n=0,
\end{equation}
potom (\ref{zchf}) i (\ref{miro}) platí $\forall k\in\hat n$. Postup řešení soustavy (\ref{tridig}) je tedy následující:
\begin{itemize}
\item inicializace (\ref{vyleps}),
\item výpočet $\mu_i\, \rho_i$ pro $i=1\, \hdots\, n$ podle (\ref{miro}),
\item výpočet $x_i$ pro $i=n\, n-1\, \hdots\, 1$ podle (\ref{zchf}).
\end{itemize}
\begin{sloz}
Výborná: $O(n)$.
\end{sloz}
\begin{tvrz}
Matice soustavy musí být silně reguární. Přitom platí
\[
\det A_{kk}=\prod_{i=1}^k (c_i \mu_{i-1} + a_i),
\]
kde klademe $c_1=0$.
\begin{proof}
Indukcí podle $k$: Pro $k=1$ tvrzení zřejmě platí. Pro $k=2$ je
\[
\prod_{i=1}^2 (c_i \mu_{i-1} + a_i)=a_1 (-c_2\frac{b_1}{a_1} + a_2)=a_1 a_2-b_1 c_2=\det A_{22}.
\]
Nechť tvrzení platí pro $k-1$. Dokážeme, že platí pro $k$:
\newline
Determinant matice $A_{kk}$ rozvineme podle posledního řádku/sloupce a máme
\begin{equation}
\label{dukfak}
\det A_{kk}=a_k \det A_{k-1k-1}-c_k b_{k-1} \det A_{k-2k-2}.
\end{equation}
Podle indukčního předpokladu je $\det A_{k-1k-1}=\det A_{k-2k-2} (c_{k-1} \mu_{k-2} + a_{k-1})$. Podle (\ref{miro}) je $b_{k-1}=-\mu_{k-1} (c_{k-1} \mu_{k-2} + a_{k-1})$. Oba tyto vztahy dosadíme do (\ref{dukfak}) a dostaneme
\[
\det A_{kk}=\det A_{k-2k-2} [a_k (c_{k-1} \mu_{k-2} + a_{k-1}) + c_k \mu_{k-1} (c_{k-1} \mu_{k-2} + a_{k-1})]=
\]
\[
=\prod_{i=1}^{k-2} (c_i \mu_{i-1} + a_i) (c_{k-1} \mu_{k-2} + a_{k-1}) (c_k \mu_{k-1} + a_k)=\prod_{i=1}^k (c_i \mu_{i-1} + a_i).
\]
Je zřejmé, že kdyby matice soustavy nebyla silně regulární, dělili bychom v (\ref{miro}) nulou.
\end{proof}
\end{tvrz}
\subsubsection{Choleskiho metoda (druhých odmocnin)}
Řešme soustavu
\begin{equation}
\label{Chsoust}
A\vec x=\vec f,
\end{equation}
kde matice $A$ je symetrická a silně regulární. Potom podle věty \ref{ALDR} lze matici rozložit ve tvaru $A=LDR$, odkud $A^T=R^TD^TL^T$. Ze symetrie matice $A$ a z jednoznačnosti rozkladu vyplývá, že $L=R^T$, tj. $A=R^TDR$.
Zřejmě existuje diagonální matice $D_1$ taková, že $D=D_1^2$, přičemž každý prvek matice $D_1$ je buď reálný, nebo ryze imaginární. Proto platí
\begin{equation}
\label{Choles}
A=R^TD_1D_1R=S^TS,
\end{equation}
kde $S=D_1R$. Matice $S$ sice není dána jednoznačně, ale víme o ní tolik, že je horní trojúhelníková a že v každém jejím řádku jsou všechny prvky buď reálné, nebo ryze imaginární. Proto ji můžeme v počítači zobrazit jako reálné pole plus jeden logický vektor o $n$ složkách, kam si zaznamenáváme, které řádky jsou reálné a které ryze imaginární.
Dále budeme postupovat stejně jako u kompaktního schématu. Buďte $A=(a_{ij})$,
\[
S=
\left (
\begin{matrix}
s_{11} & s_{12} & \hdots & s_{1n}\\
& s_{22} & \hdots & s_{2n}\\
& & \ddots & \vdots\\
& & & s_{nn}\\
\end{matrix}
\right ) .
\]
Podle (\ref{Choles}) platí
\[
\begin{array}{ll}
a_{ii}=s_{1i}^2 + s_{2i}^2 + \hdots+ s_{ii}^2 & \text{pro }i\in\hat n,\\
a_{ij}=s_{1i} s_{1j}+s_{2i} s_{2j}+\hdots+s_{ii} s_{ij} & \text{pro }i\in\hat n\, j=i+1\, \hdots\, n
\end{array}
\]
a odtud plyne
\begin{equation}
\label{vzCh}
\begin{array}{rll}
s_{ii}= & \sqrt{a_{ii}-(s_{1i}^2 + s_{2i}^2 + \hdots + s_{i-1i}^2)} & \text{pro }i\in\hat n,\\
s_{ij}= & \frac{1}{s_{ii}} [a_{ij}-(s_{1i} s_{1j}+s_{2i} s_{2j}+\hdots+s_{i-1i} s_{i-1j})] & \text{pro }i\in\hat n\, j=i+1\, \hdots\, n.
\end{array}
\end{equation}
Výpočet prvků $s_{ij}$ se provádí po řádcích. Je snadné si rozmyslet, že výrazy v kulatých závorkách ve vzorcích (\ref{vzCh}) jsou vždy reálné a že při výpočtu $s_{ii}$ je lhostejné, kterou odmocninu použijeme.
Rovněž je zřejmé, že prvek $s_{ij}$ můžeme ihned po jeho vypočtení zapsat na místo, kde byl původně uložen prvek $a_{ij}$.
Vlastní řešení se provádí ve třech krocích:
\begin{enumerate}
\item Najdeme rozklad (\ref{Choles}) matice $A$ podle (\ref{vzCh}). Tím přejde soustava (\ref{Chsoust}) ve tvar $S^TS\vec x=\vec b$, tj.
\item $S^T\vec y=\vec f$ (soustava s dolní trojúhelníkovou maticí),
\item $S\vec x=\vec y$ (soustava s horní trojúhelníkovou maticí).
\end{enumerate}
\subsection{Inverze matice}
Ukážeme na příbuznost mezi úlohou řešit soustavu lineárních algebraických rovnic a úlohou nalézt inverzní matici. Buď $A$ regulární matice.
\begin{enumerate}
\item Rovnici $A\vec x=\vec b$ vynásobíme zleva maticí $A^{-1}$ a tím získáme její řešení ve tvaru $\vec x=A^{-1} \vec b$.
\item Označme $\vec x^{(1)}\, \hdots\, \vec x^{(n)}$ sloupce matice $A^{-1}$. Protože platí $AA^{-1}=I$, musí platit $A(\vec x^{(1)}\, \hdots\, \vec x^{(n)})=(\vec e^{(1)}\, \hdots\, \vec e^{(n)})$, tj. musí být splněno $n$ soustav lineárních algebraických rovnic $A\vec x^{(i)}=\vec e^{(i)}\, i\in\hat n$, které se liší pouze pravou stranou.\footnote{To je Gaussova metoda k nalezení inverzní matice popsaná v lineární algebře (věta 67).}
\end{enumerate}
\subsubsection{Obecné eliminační schéma}
Buď $A$ regulární matice. Sestavme blokovou matici
\begin{equation}
\label{obelsch}
\left (
\begin{matrix}
A & B\\
C & D
\end{matrix}
\right ).
\end{equation}
Tuto matici chceme převést na blokovou matici tvaru
\begin{equation}
\label{tvaroes}
\left (
\begin{matrix}
I & ?\\
O & ?
\end{matrix}
\right )
\end{equation}
těmito úpravami:
\begin{itemize}
\item Řádky z horní poloviny (tj. řádky tvořené prvky matic $A\, B$) se smějí násobit nenulovým číslem.
\item Ke všem řádkům se smějí přičítat násobky řádků opět z horní poloviny.
\end{itemize}
Tyto úpravy mají týž výsledek jako vynásebení matice (\ref{obelsch}) zleva maticí, která z jednotkové matice odpovídajícího rozměru vznikne stejnými úpravami. Vzhledem k našim omezením musí mít tato matice blokový tvar
\[
\left (
\begin{matrix}
X & O\\
Y & I
\end{matrix}
\right ),
\]
kde blok $X$ má rozměr matice $A$ a blok $Y$ rozměr matice $C$. Má-li mít součin
\[
\left (
\begin{matrix}
X & O\\
Y & I
\end{matrix}
\right )
\left (
\begin{matrix}
A & B\\
C & D
\end{matrix}
\right )=
\left (
\begin{matrix}
XA & XB\\
YA + C & YB + D
\end{matrix}
\right )
\]
tvar (\ref{tvaroes}), musí platit
\[
XA=I \Leftrightarrow X=A^{-1}\, YA + C=O \Leftrightarrow Y=-CA^{-1},
\]
takže
\begin{equation}
\label{typoes}
XB=A^{-1}B\, YB+D=D-CA^{-1}B.
\end{equation}
Obecné eliminační schéma tedy slouží k výpočtu výrazů typu (\ref{typoes}).
\begin{enumerate}
\item Chceme-li počítat pouze $A^{-1}$, volíme $B=I\, C=O\, D=O$.
\item Zvolíme-li $B=\vec b$, řeší schéma soustavu $A\vec x=\vec b$.
\item Zvolíme-li $B=(I\, \vec b)$, řeší se obě úlohy najednou.
\item Zvolíme-li $B=\vec b\, C=-\vec c^T\, D=d$, počítá se funkční hodnota lineární funkce (přesněji afinního zobrazení, resp. funkcionálu)
\[
f(x_1\, \hdots\, x_n)=c_1 x_1 + \hdots + c_n x_n + d
\]
v bodě $\vec x=(x_1\, \hdots\, x_n)^T$, který je řešením soustavy $A\vec x=\vec b$:
\[
\left (
\begin{matrix}
A &
\begin{matrix}
b_1\\
\vdots\\
b_n
\end{matrix}\\
\begin{matrix}
-c_1 & \hdots & -c_n
\end{matrix}
& d
\end{matrix}
\right )\sim
\left (
\begin{matrix}
I & A^{-1}
\left (
\begin{matrix}
b_1\\
\vdots\\
b_n
\end{matrix}
\right )\\
\vec o^T & d+\sum_{i=1}^n c_i x_i
\end{matrix}
\right ).
\]
\end{enumerate}
\subsubsection{Metoda ovroubení}
Má se ovroubit ubrus, aby se netřepil.
\begin{define}
Řekneme, že matice $A_n=(a_{ij})$ vznikla z matice $A_{n-1}$ ovroubením, je-li
\begin{equation}
\label{ovroube}
A_{n}=
\left (
\begin{matrix}
A_{n-1} & \vec u_n\\
\vec v_n^T & a_{nn}
\end{matrix}
\right ).
\end{equation}
\end{define}
Buď matice $A=(a_{ij})$ silně regulární. Výpočet $A^{-1}$ se při metodě ovroubení provádí v $n$ krocích. V $k$-tém kroku se předpokládá, že známe $A_{k-1}^{-1}$ a pomocí efektivních vzorců se počítá $A_k^{-1}$.
Hledejme
\[
A_n^{-1}=
\left (
\begin{matrix}
P_{n-1} & \vec r_n\\
\vec q_n^T & 1/\beta
\end{matrix}
\right ).
\]
Prvek v pravém dolním rohu je zřejmě nenulový, protože $A_{nn}^{-1}=\frac{1}{\det A} A_{nn}^{adj.}$, tj. je to nenulový násobek algebraického doplňku prvku $a_{nn}$ v (\ref{ovroube}). Platí
\[
I=A_n A_n^{-1}=
\left (
\begin{matrix}
A_{n-1} P_{n-1} + \vec u_n \vec q_n^T & A_{n-1} \vec r_n + \frac{1}{\beta} \vec u_n\\
\vec v_n^T P_{n-1} + a_{nn} \vec q_n^T & \vec v_n^T \vec r_n + \frac{a_{nn}}{\beta}
\end{matrix}
\right ),
\]
a proto dostáváme
\[
A_{n-1} P_{n-1} + \vec u_n \vec q_n^T = I\,
A_{n-1} \vec r_n + \frac{1}{\beta} \vec u_n = \vec o,
\]
\[
\vec v_n^T P_{n-1} + a_{nn} \vec q_n^T = \vec o^T\,
\vec v_n^T \vec r_n + \frac{a_{nn}}{\beta} = 1.
\]
Z druhé rovnice vyjádříme
\begin{equation}
\label{ovrn}
\vec r_n=-\frac{1}{\beta} A_{n-1}^{-1} \vec u_n
\end{equation}
a tento vztah dosadíme do poslední rovnice:
\begin{equation}
\label{ovbeta}
\beta=a_{nn}-\vec v_n^T A_{n-1}^{-1} \vec u_n.
\end{equation}
První rovnici vynásobíme zleva maticí $A_{n-1}^{-1}$:
\[
P_{n-1}=A_{n-1}^{-1} - A_{n-1}^{-1} \vec u_n \vec q_n^T
\]
a dosadíme do třetí rovnice:
\[
\vec o=\vec v_n^T A_{n-1}^{-1} - \vec v_n^T A_{n-1}^{-1} \vec u_n \vec q_n^T + a_{nn} \vec q_n^T =\vec v_n^T A_{n-1}^{-1} + \underbrace{(a_{nn}-\vec v_n^T A_{n-1}^{-1} \vec u_n)}_{\beta}\vec q_n^T.
\]
Odtud
\begin{equation}
\label{ovqn}
\vec q_n^T=-\frac{1}{\beta} \vec v_n^T A_{n-1}^{-1},
\end{equation}
\begin{equation}
\label{ovpn}
P_{n-1}=A_{n-1}^{-1} + \frac{1}{\beta} A_{n-1}^{-1} \vec u_n \vec v_n^T A_{n-1}^{-1}.
\end{equation}
Hledané vzorce jsou (\ref{ovbeta}), (\ref{ovrn}), (\ref{ovqn}) a (\ref{ovpn}).
Při výpočtu na počítači se nejprve spočítá $A_1^{-1}=(\frac{1}{a_{11}})$ a pak se postupně vypočítává $A_2^{-1}\, \hdots\, A_n^{-1}$.
Máme pracovní pole
\[
\begin{tabular}{|c|c|}
\hline
& $a_{1n}$\\
$A_{n-1}^{-1}$ & \vdots\\
& $a_{1n-1}$\\
\hline
$a_{n1} \hdots a_{nn-1}$ & $a_{nn}$\\
\hline
\end{tabular}
\]
a navíc potřebujeme dva ($n-1$)-složkové vektory $\beta$ a $\gamma$. Výpočet matice $A_n^{-1}$ sestává ze tří kroků:
\begin{itemize}
\item Spočtou se pomocné hodnoty
\[
\left (
\begin{matrix}
\beta_1\\
\vdots\\
\beta_{n-1}
\end{matrix}
\right ) =-A_{n-1}^{-1} \vec u_n=-A_{n-1}^{-1}
\left (
\begin{matrix}
a_{1n}\\
\vdots\\
a_{n-1n}
\end{matrix}
\right ) ,
\]
\[
(\gamma_1\, \hdots\, \gamma_{n-1})=-\vec v_n^T A_{n-1}^{-1}=-(a_{n1}\hdots a_{nn-1}) A_{n-1}^{-1}.
\]
\item Spočte se číslo $\beta$ podle jednoho ze vztahů
\[
\beta=a_{nn}+a_{n1}\beta_1+\hdots+a_{nn-1}\beta_{n-1},
\]
\[
\beta=a_{nn}+\gamma_1 a_{1n}+\hdots+\gamma_{n-1} a_{n-1n}.
\]
Měli bychom provést oba výpočty, abychom ověřili chyby vzniklé zaokrouhlováním.
\item Dosavadní hodnoty na místech o indexech $(i\, j)$, kde $i\, j\in\widehat{n-1}$, se opraví o $\frac{\beta_i \gamma_j}{\beta}$, neboť v souladu s (\ref{ovpn}) platí
\[
P_{n-1}=A_{n-1}^{-1} + \frac{1}{\beta}
\left (
\begin{matrix}
\beta_1\\
\vdots\\
\beta_{n-1}
\end{matrix}
\right )
(\gamma_1\hdots\gamma_{n-1}).
\]
Na místo s indexem $(n\, n)$ se dosadí $\frac{1}{\beta}$. Na místa o indexech $(i\, k)$, kde $i\in\widehat{n-1}$ se dosadí $\frac{\beta_i}{\beta}$. Na místa o indexech $(k\, j)$, kde $j\in\widehat{n-1}$ se dosadí $\frac{\gamma_j}{\beta}$.
\end{itemize}
