01NUM1:Kapitola4: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
(upřesnění poznámky k ekvivalentním úpravám.)
(upřesnění ekvivalentních úprav.)
Řádka 29: Řádka 29:
 
\begin{remark}
 
\begin{remark}
 
\label{ElementarniPricitani}
 
\label{ElementarniPricitani}
Přičtení \( \alpha \)-násobku \( k \)-tého řádku matice \( \matice A \) k jejímu \( l \)-tému řádku je ekvivalentní násobení maticí \( \matice M \), kde
+
Přičtení \( \alpha \)-násobku \( k \)-tého řádku matice \( \matice A \) k jejímu \( l \)-tému řádku je ekvivalentní násobení maticí \( \matice M \) zleva, kde
 
\[ \matice M_{ij} =
 
\[ \matice M_{ij} =
 
\begin{cases}
 
\begin{cases}

Verze z 9. 1. 2017, 13:07

PDF [ znovu generovat, výstup z překladu ] Kompletní WikiSkriptum včetně všech podkapitol.
PDF Této kapitoly [ znovu generovat, výstup z překladu ] Přeložení pouze této kaptioly.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01NUM1

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01NUM1Dedicma2 3. 6. 202419:49
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůDedicma2 3. 6. 202419:48
Header editovatHlavičkový souborDedicma2 17. 1. 201616:20 header.tex
Kapitola0 editovatZnačeníDedicma2 23. 5. 201721:32 znaceni.tex
Kapitola2 editovatOpakování a doplnění znalostí z lineární algebryDedicma2 3. 6. 202415:41 prezentace2.tex
Kapitola3 editovatÚvod do numerické matematikyDedicma2 3. 6. 202415:51 prezentace3.tex
Kapitola4 editovatPřímé metody pro lineární soustavyDedicma2 3. 6. 202416:47 prezentace4.tex
Kapitola5 editovatIterativní metodyDedicma2 3. 6. 202416:59 prezentace5.tex
Kapitola6 editovatVlastní čísla a vektory maticDedicma2 3. 6. 202417:07 prezentace6.tex
Kapitola7 editovatNelineární rovniceKubuondr 31. 1. 201714:27 prezentace7.tex
Kapitola8 editovatInterpolaceKubuondr 31. 1. 201715:43 prezentace8.tex
Kapitola9 editovatDerivace a integraceKubuondr 31. 1. 201717:33 prezentace9.tex

Zdrojový kód

%\wikiskriptum{01NUM1}
\section{Přímé metody pro lineární soustavy}
 
\subsection{Pravidla o elementárních úpravách}
 
\begin{define}
\label{ElementarniUpravy}
Elementárními úpravami matice nazveme:
\begin{itemize}
\item Násobení všech prvků jednoho řádku konstantou
\item Přičtení násobku jednoho řádku k jinému
\item Prohození dvou řádků
\end{itemize}
a obdobné úpravy pro sloupce.
\end{define}
 
\begin{remark}
\label{ElementarniNasobeni}
Násobení \( k \)-tého řádku matice \( \matice A \) číslem \( \alpha \) je ekvivalentní násobení maticí \( \matice M \), kde
\[ \matice M_{ij} =
\begin{cases}
\alpha, & i = j = k \\
1, & i = j \neq k \\
0, & i \neq j \\
\end{cases}
\]
\end{remark}
 
\begin{remark}
\label{ElementarniPricitani}
Přičtení \( \alpha \)-násobku \( k \)-tého řádku matice \( \matice A \) k jejímu \( l \)-tému řádku je ekvivalentní násobení maticí \( \matice M \) zleva, kde
\[ \matice M_{ij} =
\begin{cases}
\alpha, & i = l \wedge j = k \\
1, & i = j \\
0, & \text{jinak} \\
\end{cases}
\]
\end{remark}
 
\begin{remark}
\label{ElementarniMatice}
Provedení konečného počtu řádkových, resp. sloupcových elementárních úprav matice je ekvivalentní násobení zleva, resp. zprava takovou maticí, která vznikla z matice \( \matice I \) stejnými elementárními úpravami, provedenými ve stejném pořadí.
\end{remark}
 
\subsection{Gaussova eliminační metoda}
 
Gaussova eliminační metoda (GEM) je přímou metodou řešení soustavy lineárních algebraických rovnic \( \matice A \vec x = \vec b \), kde matice \( \matice A \) je regulární. Skládá se ze dvou fází:
\begin{enumerate}[(1)]
\item \textbf{Přímý chod} - Převádíme pomocí elementárních úprav soustavu \( \matice A \vec x = \vec b \) na soustavu \( \matice U \vec x = \vec d \), kde matice \( \matice U \) je horní trojúhelníková.
\item \textbf{Zpětný chod} - Řešíme soustavu \( \matice U \vec x = \vec d \) pomocí zpětné substituce.
\end{enumerate}
 
\subsection{Gaussova eliminační metoda - přímý chod}
Mějme regulární matici \( \matice A \in \mathbbm C^{n, n} \). Mějme soustavu
\[
\begin{pmatrix}
\matice A_{11} & \matice A_{12} & \cdots & \matice A_{1n} \\
\matice A_{21} & \matice A_{22} & \cdots & \matice A_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
\matice A_{n1} & \matice A_{n2} & \cdots & \matice A_{nn} \\
\end{pmatrix}
\begin{pmatrix}
\vec x_1 \\
\vec x_2 \\
\vdots \\
\vec x_n \\
\end{pmatrix} =
\begin{pmatrix}
\vec b_1 \\
\vec b_2 \\
\vdots \\
\vec b_n \\
\end{pmatrix}
\]
Předpokládáme \( \matice A_{11} \neq 0 \). Nazveme tento prvek pivotem v prvním kroku.
\\ Nyní provedeme následující elemetární úpravy:
\begin{enumerate}[1)]
\item Vydělíme celý první řádek prvkem \( \matice A_{11} \)
\item \( \forall k \in \hat n \setminus \{ 1 \} \) odečteme od \( k \)-tého řádku \( \matice A_{k1} \) násobek prvního řádku.
\end{enumerate}
Dostáváme tedy soustavu
\[
\begin{pmatrix}
1 & \matice U_{12} & \cdots & \matice U_{1n} \\
0 & \matice A_{22}^{( 1 )} & \cdots & \matice A_{2n}^{( 1 )} \\
\vdots & \vdots & \ddots & \vdots \\
0 & \matice A_{n2}^{( 1 )} & \cdots & \matice A_{nn}^{( 1 )} \\
\end{pmatrix}
\begin{pmatrix}
\vec x_1 \\
\vec x_2 \\
\vdots \\
\vec x_n \\
\end{pmatrix} =
\begin{pmatrix}
\vec d_1 \\
\vec b_2^{( 1 )} \\
\vdots \\
\vec b_n^{( 1 )} \\
\end{pmatrix}
\]
při značení
\[ \matice U_{1j} = \frac{\matice A_{1j}}{\matice A_{11}} \]
\[ \vec d_1 = \frac{\vec b_1}{\matice A_{11}} \]
\[ \matice A_{ij}^{( 1 )} = \matice A_{ij} - \matice A_{i1} \matice U_{1j} \]
\[ \vec b_i^{( 1 )} = \vec b_i - \matice A_{i1} \vec d_1 \]
Nyní aplikujeme stejný postup na soustavu bez prvního řádku a sloupce. Obecně tedy počítáme při \( k \)-tém kroku
\[ \matice U_{kj} = \frac{\matice A_{kj}^{( k - 1 )}}{\matice A_{kk}^{( k - 1 )}} \]
\[ \vec d_k = \frac{\vec b_k^{( k - 1 )}}{\matice A_{kk}^{( k - 1 )}} \]
\[ \matice A_{ij}^{( k )} = \matice A_{ij}^{( k - 1 )} - \matice A_{ik}^{( k - 1 )} \matice U_{kj} \]
\[ \vec b_i^{( k )} = \vec b_i^{( k - 1 )} - \matice A_{ik}^{( k - 1 )} \vec d_k \]
 
\subsection{Gaussova eliminační metoda - zpětný chod}
Řešíme soustavu s horní trojúhelníkovou maticí \( \matice U \vec x = \vec d \).
Obecně napočítáváme \( \vec x_k \) od \( n \) dolů jako
\[ \vec x_k = \vec d_k - \sum_{i = k + 1}^{n} \matice U_{ki} \vec x_i \]
 
\subsection{Gaussova eliminační metoda - složitost}
Gaussovu eliminační metodu provádíme v \( n \) krocích. V každém takovémto \( k \)-tém kroku:
\begin{enumerate}[1)]
\item Dělíme řádek pivotem, tj. \( n - k \) operací
\item Odečítáme řádek ode všech ostatních, tj. \( n - k + 1 \) operací na \( n - k + 1 \) řádcích, dohromady \( ( n - k + 1 )^2 \) operací
\end{enumerate}
To je dohromady \( \sum_{k = 1}^n n - k + ( n - k + 1 )^2 \) operací, tedy složitost je
\[ \mathcal O ( n^3 ) \]
což znamená, že Gaussova eliminační metoda je v praxi použitelná pouze pro malé matice.
 
\subsection{Gaussova eliminační metoda - numerická analýza}
 
\begin{define*}
Definujeme rozšířenou matici soustavy jako
\[ \matice P =
\begin{pmatrix}[c|c]
\matice A & \vec b \\
\end{pmatrix}
\]
\end{define*}
 
Využijeme \ref{ElementarniMatice} a \ref{ElementarniNasobeni}, díky kterým je dělení prvního řádku prvkem \( \matice A_{11} \) ekvivalentní násobení zleva maticí
\[ \left ( \matice M_1^{( 1 )} \right)_{ij} =
\begin{cases}
\frac{1}{\matice A_{11}}, & i = j = 1 \\
1, & i = j \neq 1 \\
0, & i \neq j \\
\end{cases}
\]
A díky \ref{ElementarniPricitani} je odečítání \( \matice A_{k1} \) násobku prvního řádku ke \( k \)-tému ekvivalentní násobení zleva maticí
\[ \left ( \matice M_k^{( 1 )} \right)_{ij} =
\begin{cases}
- \matice A_{k1}, & i = k \wedge j = 1 \\
1, & i = j \\
0, & \text{jinak} \\
\end{cases}
\]
Dohromady tedy definujeme matici úprav v prvním kroku jako
\[ \matice M^{( 1 )} = \prod_{k = 0}^{n - 1} \matice M_{n - k}^{( 1 )} =
\begin{pmatrix}
\frac{1}{\matice A_{11}} &&&& \\
- \frac{\matice A_{21}}{\matice A_{11}} & 1 &&& \\
- \frac{\matice A_{31}}{\matice A_{11}} && 1 && \\
\vdots &&& \ddots & \\
- \frac{\matice A_{n1}}{\matice A_{11}} &&&& 1 \\
\end{pmatrix}
\]
 
\begin{define*}
Definujeme matici úprav v \( k \)-tém kroku Gaussovy eliminační metody jako jako
\[ \matice M^{( k )} = \prod_{l = 0}^{n - k} \matice M_{n - l}^{( k )} \]
\end{define*}
 
\begin{remark*}
Matice úprav v \( k \)-tém kroku Gaussovy eliminační metody má tvar
\[ \matice M^{( k )} =
\begin{pmatrix}
1 &&&&&& \\
& \ddots &&&&& \\
&& 1 &&&& \\
&&& \frac{1}{\matice A_{kk}^{( k - 1 )}} &&& \\
&&& - \frac{\matice A_{k + 1, k}^{( k - 1 )}}{\matice A_{kk}^{( k - 1 )}} & 1 && \\
&&& \vdots && \ddots & \\
&&& - \frac{\matice A_{nk}^{( k - 1 )}}{\matice A_{kk}^{( k - 1 )}} &&& 1 \\
\end{pmatrix}
\]
kde sloupec s podíly je \( k \)-tý.
\end{remark*}
 
\begin{define*}
Definujeme matici soustavy na konci \( k \)-tého kroku Gaussovy eliminační metody jako
\[ \matice P^{( k )} = \matice M^{( k )} \matice P^{( k - 1 )} \]
kde
\[ \matice P^{( 0 )} = \matice P \]
\end{define*}
 
\begin{remark*}
Matice soustavy na konci \( k \)-tého kroku Gaussovy eliminační metody má tvar
\[ \matice P^{( k )} =
\begin{pmatrix}[ccccccc|c]
1 & \matice U_{12} & \cdots & \matice U_{1, k - 1} & \matice U_{1k} & \cdots & \matice U_{1n} & \vec d_1 \\
& 1 & \cdots & \matice U_{2, k - 1} & \matice U_{2k} & \cdots & \matice U_{2n} & \vec d_2 \\
&& \ddots && \vdots & \ddots & \vdots & \vdots \\
&&& 1 & \matice U_{k - 1, k} & \cdots & \matice U_{k - 1, n} & \vec d_{k - 1} \\
&&&& \matice A_{kk}^{( k - 1 )} & \cdots & \matice A_{kn}^{( k - 1 )} & \vec b_k^{( k - 1 )} \\
&&&& \vdots & \ddots & \vdots & \vdots \\
&&&& \matice A_{nk}^{( k - 1 )} & \cdots & \matice A_{nn}^{( k - 1 )} & \vec b_n^{( k - 1 )} \\
\end{pmatrix}
\]
\end{remark*}
 
\begin{define*}
Definujeme matici úprav Gaussovy eliminační metody jako
\[ \matice M = \prod_{k = 0}^{n - 1} \matice M^{( n - k )} \]
\end{define*}
 
Vidíme, že platí
\[
\begin{pmatrix}[c|c]
\matice U & \vec d \\
\end{pmatrix}
= \matice P^{( n )} = \matice{M P}
\]
a tedy také
\[ \matice U = \matice{M A} \]
Na diagonále matice \( \matice M \) jsou převrácené hodnoty pivotů Gaussovy eliminační metody. Definujeme tedy matici
\[ \matice D_{ij} =
\begin{cases}
\matice A_{ii}^{( i - 1 )}, & i = j \\
0, & i \neq j \\
\end{cases}
\]
a pro ní platí
\[ \matice A = \left( \matice M^{-1} \matice D^{-1} \right) \matice D \matice U \]
což je podle \ref{LDR} LDR rozklad.
 
\begin{theorem}
\label{GEMRegularni}
Základní Gaussovu eliminační metodu lze provést právě tehdy, když je matice soustavy silně regulární.
\begin{proof}
\begin{enumerate}
\item[( \( \Rightarrow \) )]Označíme matici \( \matice A \) po \( k \)-té úprávě jako \( \matice A^{( k )} \). Protože lze provést Gaussovu eliminační metodu, má matice \( \matice A \) nenulové pivoty, tj.
\[ \matice A_{ii}^{( i - 1 )} \neq 0, \; \forall i \in \hat n \]
a existuje rozklad \( \matice A = \matice M^{-1} \matice U \). Označíme \( \matice L = \matice M^{-1} \) a víme, že
\[ \matice L_{ii} = \matice A_{ii}^{( i - 1 )}, \; \forall i \in \hat n \]
Dále víme, že na diagonále matice \( \matice U \) jsou jedničky, tedy \( \det \matice U = 1 \). Blokově rozepíšeme (velikosti bloků jsou stejné):
\[ \matice A = \matice{L U} =
\begin{pmatrix}
\matice A_1 & \matice A_2 \\
\matice A_3 & \matice A_4 \\
\end{pmatrix} = 
\begin{pmatrix}
\matice L_1 & \Theta \\
\matice L_2 & \matice L_3 \\
\end{pmatrix}
\begin{pmatrix}
\matice U_1 & \matice U_2 \\
\Theta & \matice U_3 \\
\end{pmatrix}
\]
a tedy 
\[ \det \matice A_1 = \det \matice L_1 \det \matice U_1 = \prod_{i = 1}^n \matice A_{ii}^{( i - 1 )} \neq 0 \]
Protože velikost bloků můžeme volit libovolně, je matice \( \matice A \) silně regulární.
\item[( \( \Leftarrow \) )] (sporem) Nechť je \(i  \) nejnižší index, pro který je jeho pivot roven 0, tj. \[ \matice A_{ii}^{( i - 1 )} = 0. \]
Provedeme \(i-1 \) kroků GEM. Blok \( \matice A_1 \) pro \(i \)-tý krok bude horní trojúhelníková matice s jedničkami na diagonále s výjimkou posledního prvku, který bude nulový.
To implikuje, že \[ \det \matice A_1 = 0 \] a tudíž není matice \( \matice A \) silně regulární.
 
\end{enumerate}
\end{proof}
\end{theorem}
 
\subsection{Modifikovaná Gaussova eliminační metoda}
 
Pokud matice \( \matice A \) není silně regulární, může se stát, že některý z pivotů je nulový. V tom případě využijeme \ref{ElementarniUpravy} a prohozením některých řádků a sloupců najdeme nenulový pivot (Což pro regulární matice vždy půjde).
\\ Může se ale také stát, že námi zvolený pivot kvůli zaokrouhlovacím chybám sice nebude nulový, ale bude velmi malý. V takovémto případě sice může použít základní Gaussovu eliminační metodu, ale výsledek nemůže dávat smysl. Podobná situace může nastat, pokud je \( \matice A \) špatně podmíněná, tedy podle \ref{SingularniVzdalenost} je blízká množině singulárních matic.
 
\begin{example}
\todo{Příklad 4.6}
\end{example}
 
Naopak pokud by některý pivot byl velmi velký, může se stát, že po vydělení tímto pivotem by ostatní řádky už příliš neovlinily následující úpravy matice. To ale tolik nevadí, protože výpočet to moc neovlivní.
\\ Modifikovaná Gaussova eliminační metoda tedy spočívá ve výběru správného pivota v každém kroku. Vybíráme buď největší prvek ze zbývající submatice (\( \mathcal O ( n^2 ) \)), nebo kvůli nižší výpočetní náročnosti pouze z řádku, kde je původní pivot. Těmito úpravami vlastně převádíme matici na silně regulární.
 
\subsection{GEM a více pravých stran}
Pokud chceme vyřešit stejnou soustavu s více pravými stranami, stačí přímý chod provést pouze jednou se všemi pravými stranami najednou. Naopak zpětný chod musíme provádět pro každou pravou stranu zvlášť, avšak složitost zpětného chodu je pouze \( \mathcal O ( n^2) \).
\\ Abychom mohli provést přímý chod pouze jednou, potřebujeme znát všechny pravé strany na počátku výpočtu, což v praxi často není možné. Tento problém řeší tzv. LU rozklad.
 
\subsection{GEM a LU rozklad}
Označíme \( \matice L = \matice M^{-1} \). Poté
\[ \matice A = \matice{L U} \]
Tímto můžeme převést úlohu \( \matice A \vec x = \vec b \) na tři úlohy
\begin{itemize}
\item \( \matice A = \matice{L U} \)
\item \( \matice U \vec x = \vec d \)
\item \( \matice L \vec d = \vec b \)
\end{itemize}
z nichž pouze poslední závisí na pravé straně původní úlohy. Navíc matice \( \matice L \) a \( \matice U \) jsou trojúhelníkové, takže řešení druhé a třetí úlohy má složitost \( \mathcal O ( n^2 ) \).
 
\begin{remark*}
Díky definici matice úprav Gaussovy eliminační metody můžeme určit tvar matice \( \matice L \) pomocí kroků Gaussovy eliminační metody, tedy
\[ \matice L = \left( \prod_{k = 0}^{n - 1} \matice M^{( n -  k )} \right)^{-1} = \prod_{k = 1}^{n} \left( \matice M^{( k )} \right)^{-1} \]
Obdobně díky definici matice úprav v \( k \)-tém kroku Gaussovy eliminační metody můžeme určit
\[ \left( \matice M^{( k )} \right)^{-1} = \left( \prod_{l = 0}^{n - k} \matice M_{n - l}^{( k )} \right)^{-1} = \prod_{l = k}^{n} \left( \matice M_{l}^{( k )} \right)^{-1} \]
kde už triviálně
\[ \left( \matice M_{k}^{( k )} \right)_{ij}^{-1} =
\begin{cases}
\matice A_{k,k}^{( k - 1 )}, & i = j = k \\
1, & i = j \neq k \\
0, & i \neq j \\
\end{cases}
\]
a
\[ \left( \matice M_{l}^{( k )} \right)_{ij}^{-1} =
\begin{cases}
- \matice A_{l,k}^{( k - 1 )}, & i = l \wedge j = k \\
1, & i = j \\
0, & \text{jinak} \\
\end{cases}
\]
\end{remark*}
 
A tedy 
 
\[ \left( \matice M^{( k )} \right)^{-1} =
\begin{pmatrix}
1 &&&&&& \\
& \ddots &&&&& \\
&& 1 &&&& \\
&&& \matice A_{k,k}^{( k - 1 )} &&& \\
&&& \matice A_{k + 1, k}^{( k - 1 )} & 1 && \\
&&& \vdots && \ddots & \\
&&& \matice A_{n,k}^{( k - 1 )} &&& 1 \\
\end{pmatrix}
\]
 
\begin{lemma}
Pro \(i<j\) platí, že součin matic typu
\[ \left( \matice M^{( i )} \right)^{-1} \left(\matice M^{( j )} \right)^{-1} \]
odpovídá jejich "sjednocení", tj. nahrazení \( i\)-tého sloupce druhé matice \( i\)-tým sloupcem první matice. Vizuálně viz prezentace.
\end{lemma}
\begin{proof}
Zřejmé, je vidět z roznásobení.
\end{proof}
 
\begin{remark*}
Pro platnost lemmatu je zásadní platnost nerovnosti \(i<j\) (zajišťuje jedničku na $i$–tém prvku diagonály druhé matice, a tím pouhé „překopírování“ $i$–tého řádku první matice).
\end{remark*}
 
\begin{remark*}
Toto lemma platí obecně pro matice této struktury, ne jen matice \( \matice M\).
\end{remark*}
 
 
Díky předchozímu lemmatu již vidíme
\[ \matice L =
\begin{pmatrix}
\matice A_{11} &&&& \\
\matice A_{21} & \matice A_{22}^{( 1 )} &&& \\
\matice A_{31} & \matice A_{32}^{( 1 )} & \matice A_{33}^{( 2 )} && \\
\vdots & \vdots & \vdots &\ddots & \\
\matice A_{n1} & \matice A_{n2}^{( 1 )} & \matice A_{n3}^{( 2 )} & \cdots & \matice A_{nn}^{( n - 1 )}
\end{pmatrix}
\]
 
Což jsou přesně prvky, které se nulují pod diagonálou v Gaussově eliminační metodě. Proto v praxi počítáme LU rozklad tak, že upravujeme matici jako v přímém chodu Gaussovy eliminační metody a nenulujeme prvky pod diagonálou. K tomu navíc nepotřebujeme žádnou paměť navíc, všechny úpravy se provádí na jediné matici. (Jedničky na diagonále matice \( \matice U\) nemusíme ukládat.)
 
\begin{example}
\todo{Příklad 4.8}
\end{example}
 
\subsection{Kompaktní schéma pro LU faktorizaci} V praxi se k vypočítání LU rozkladu nepoužívá Gaussova eliminační metoda, ale 2 metody, známé jako Croutova a Doolittlova faktorizace. Croutova faktorizace generuje jedničky na diagonále matice \( \matice U \), kdežto Doolitlova faktorizace generuje jedničky na diagonále matice \( \matice L \). Nejde tedy o stejný rozklad! Ve skutečnosti jsou rozklady vzájemnou transpozicí, tedy
\[ \matice A = \matice L_C \matice U_C = \left( \matice U_D \right)^T \left( \matice L_D \right)^T \]
Provedeme numerickou analýzu Croutovy faktorizace, Doolittlova faktorizace je obdobná. Vyjdeme ze vztahu
\[ \matice A_{ij} = \sum_{k = 1}^{\min \{ i, j \}} \matice L_{ik} \matice U_{kj} \]
Předpokládáme \( \matice U_{ii} = 1 \) a tedy ze vztahu pro prvky \( \matice A_{i1} \) a \( \matice A_{1j} \)
\[ \matice L_{i1} = \matice A_{i1} \]
\[ \matice U_{1j} = \frac{\matice A_{1j}}{\matice L_{11}} \]
Obdobně můžeme upravit vztahy pro prvky \( \matice A_{i2} \) a \( \matice A_{2j} \), tentokrát se ovšem musíme omezit na \( i \geq 2 \) a \( j \geq 2 \):
\[ \matice L_{i2} = \matice A_{i2} - \matice L_{i1} \matice U_{12} \]
\[ \matice U_{2j} = \frac{\matice A_{2j} - \matice L_{21} \matice U_{1j}}{\matice L_{22}} \]
A obecně ze vztahu pro \( \matice A_{ij} \) dostaneme
\[ \matice L_{ij} = \matice A_{ij} -\sum_{k = 1}^{j - 1} \matice L_{ik} \matice U_{kj}, \; \forall j \leq i \]
\[ \matice U_{ij} = \frac{\matice A_{ij} -\sum_{k = 1}^{i - 1} \matice L_{ik} \matice U_{kj}}{\matice L_{ii}}, \; \forall i \leq j \]
Je ovšem vidět, že tento algoritmus lze provést pouze, pokud nejsou žádné diagonální prvky matice \( \matice L \) nulové. Na diagonále matice \( \matice L \) jsou ale pivoty základní Gaussovy eliminační metody a proto platí následující věta.
 
\begin{theorem*}
Croutovu a Doolittlovu faktorizaci lze provést právě tehdy, když je matice \( \matice A \) silně regulární.
\end{theorem*}
 
Croutova a Doolittlova faktorizace neumožňují volbu pivotů tak, jako modifikovaná Gaussova eliminační metoda. To ale tolik nevadí, protože prvky matic \( \matice L \) a \( \matice U \) napočítáváme pouze jednou a nepřepisujeme je, čímž se minimalizují chyby výpočtu. Navíc pokud známe \( \matice L_{ij} \) a \( \matice U_{ij} \), nepotřebujeme už dále znát \( \matice A_{ij} \), tedy stejně jako u výpočtu LU rozkladu pomocí Gaussovy eliminační metody můžeme přepisovat prvky matice \( \matice A \) a tím ušetřit paměť. 
 
\begin{theorem}
\label{LUSpojity}
Nechť \( \matice A \in \mathbbm C^{n, n} \) a její LU rozklad \( \matice A = \matice{L U} \). Potom funkce \( \matice L_{ij} ( \matice A_{kl} ) \) a \( \matice U_{ij} ( \matice A_{kl} ) \) jsou spojité.
\begin{proof}
Ze vztahů pro Croutovu faktorizaci je vidět, že jsou to polynomy, a tedy spojité.
\end{proof}
\end{theorem}
 
\begin{example}
\todo{Příklad 4.10}
\end{example}
 
\subsection{LU rozklad pro symetrické matice - Choleského dekompozice}
 
\begin{theorem}[Choleského rozklad]
\label{CholeskehoRozklad}
Nechť je matice \( \matice A \) hermitovská a regulární. Pak existuje horní trojúhelníková matice \( \matice S \) taková, že platí
\[ \matice A = \matice S^* \matice S \]
Tomuto rozkladu se říká Choleského rozklad (dekompozice).
\begin{proof}
Díky \ref{LDR} platí \( \matice A = \matice{L D R} \) a \( \matice A^* = \matice R^* \matice D^* \matice L^* \). Protože je matice \( \matice A \) hermitovská, platí díky jednoznačnosti rozkladu \ref{LDR} \( \matice L = \matice R^* \) a \( \matice D = \matice D^* \). Označíme \( \matice S = \matice D^{\frac{1}{2}} \matice R \) a pak platí
\[ \matice S^* \matice S = \matice R^* \left( \matice D^* \right)^{\frac{1}{2}} \matice D^{\frac{1}{2}} \matice R = \matice{L D R} = \matice A \]
\end{proof}
\end{theorem}
 
Choleského rozklad je pouze speciálním případem LU rozkladu kde \( \matice S = \matice U = \matice L^* \) a tedy můžeme upravit vztahy pro Croutovu faktorizaci do tvaru
\[ \matice S_{ii} = \sqrt{\matice A_{ii} -\sum_{k = 1}^{i - 1} \matice S_{ki}^2} \]
\[ \matice S_{ij} = \frac{\matice A_{ij} -\sum_{k = 1}^{i - 1} \overline{\matice S}_{ki} \matice S_{kj}}{\overline{\matice S}_{ii}} \]
 
\begin{example}
\todo{Příklad 4.12}
\end{example}
 
\subsection{Thomasův algoritmus}
\todo{Thomasův algoritmus}
 
\subsection{Schurův doplněk}
\todo{Schurův doplněk}