01NUM1:Kapitola4: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
(Choleského dekopmozice.) |
(Oprava kompilace, drobné změny textace) |
||
(Není zobrazeno 5 mezilehlých verzí od jednoho dalšího uživatele.) | |||
Řádka 1: | Řádka 1: | ||
%\wikiskriptum{01NUM1} | %\wikiskriptum{01NUM1} | ||
\section{Přímé metody pro lineární soustavy} | \section{Přímé metody pro lineární soustavy} | ||
− | + | ||
\subsection{Pravidla o elementárních úpravách} | \subsection{Pravidla o elementárních úpravách} | ||
− | + | ||
\begin{define} | \begin{define} | ||
\label{ElementarniUpravy} | \label{ElementarniUpravy} | ||
Řádka 14: | Řádka 14: | ||
a obdobné úpravy pro sloupce. | a obdobné úpravy pro sloupce. | ||
\end{define} | \end{define} | ||
− | + | ||
\begin{remark} | \begin{remark} | ||
\label{ElementarniNasobeni} | \label{ElementarniNasobeni} | ||
− | Násobení \( k \)-tého řádku matice \( \matice A \) číslem \( \alpha \) je ekvivalentní násobení maticí \( \matice M \), kde | + | Násobení \( k \)-tého řádku matice \( \matice A \) číslem \( \alpha \) je ekvivalentní násobení maticí \( \matice M \) zleva, kde |
\[ \matice M_{ij} = | \[ \matice M_{ij} = | ||
\begin{cases} | \begin{cases} | ||
Řádka 26: | Řádka 26: | ||
\] | \] | ||
\end{remark} | \end{remark} | ||
− | + | ||
\begin{remark} | \begin{remark} | ||
\label{ElementarniPricitani} | \label{ElementarniPricitani} | ||
Řádka 38: | Řádka 38: | ||
\] | \] | ||
\end{remark} | \end{remark} | ||
− | + | ||
\begin{remark} | \begin{remark} | ||
\label{ElementarniMatice} | \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í. | 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} | \end{remark} | ||
− | + | ||
\subsection{Gaussova eliminační metoda} | \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í: | 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)] | \begin{enumerate}[(1)] | ||
Řádka 51: | Řádka 51: | ||
\item \textbf{Zpětný chod} - Řešíme soustavu \( \matice U \vec x = \vec d \) pomocí zpětné substituce. | \item \textbf{Zpětný chod} - Řešíme soustavu \( \matice U \vec x = \vec d \) pomocí zpětné substituce. | ||
\end{enumerate} | \end{enumerate} | ||
− | + | ||
\subsection{Gaussova eliminační metoda - přímý chod} | \subsection{Gaussova eliminační metoda - přímý chod} | ||
Mějme regulární matici \( \matice A \in \mathbbm C^{n, n} \). Mějme soustavu | Mějme regulární matici \( \matice A \in \mathbbm C^{n, n} \). Mějme soustavu | ||
Řádka 111: | Řádka 111: | ||
\[ \matice A_{ij}^{( k )} = \matice A_{ij}^{( k - 1 )} - \matice A_{ik}^{( k - 1 )} \matice U_{kj} \] | \[ \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 \] | \[ \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} | \subsection{Gaussova eliminační metoda - zpětný chod} | ||
Řešíme soustavu s horní trojúhelníkovou maticí \( \matice U \vec x = \vec d \). | Ř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 | 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 \] | \[ \vec x_k = \vec d_k - \sum_{i = k + 1}^{n} \matice U_{ki} \vec x_i \] | ||
− | + | ||
\subsection{Gaussova eliminační metoda - složitost} | \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: | Gaussovu eliminační metodu provádíme v \( n \) krocích. V každém takovémto \( k \)-tém kroku: | ||
Řádka 126: | Řádka 126: | ||
\[ \mathcal O ( n^3 ) \] | \[ \mathcal O ( n^3 ) \] | ||
což znamená, že Gaussova eliminační metoda je v praxi použitelná pouze pro malé matice. | což znamená, že Gaussova eliminační metoda je v praxi použitelná pouze pro malé matice. | ||
− | + | ||
\subsection{Gaussova eliminační metoda - numerická analýza} | \subsection{Gaussova eliminační metoda - numerická analýza} | ||
− | + | ||
\begin{define*} | \begin{define*} | ||
Definujeme rozšířenou matici soustavy jako | Definujeme rozšířenou matici soustavy jako | ||
Řádka 137: | Řádka 137: | ||
\] | \] | ||
\end{define*} | \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í | 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} = | \[ \left ( \matice M_1^{( 1 )} \right)_{ij} = | ||
Řádka 164: | Řádka 164: | ||
\end{pmatrix} | \end{pmatrix} | ||
\] | \] | ||
− | + | ||
\begin{define*} | \begin{define*} | ||
− | Definujeme matici úprav v \( k \)-tém kroku Gaussovy eliminační metody | + | Definujeme matici úprav v \( k \)-tém kroku Gaussovy eliminační metody jako |
\[ \matice M^{( k )} = \prod_{l = 0}^{n - k} \matice M_{n - l}^{( k )} \] | \[ \matice M^{( k )} = \prod_{l = 0}^{n - k} \matice M_{n - l}^{( k )} \] | ||
\end{define*} | \end{define*} | ||
− | + | ||
\begin{remark*} | \begin{remark*} | ||
Matice úprav v \( k \)-tém kroku Gaussovy eliminační metody má tvar | Matice úprav v \( k \)-tém kroku Gaussovy eliminační metody má tvar | ||
Řádka 185: | Řádka 185: | ||
kde sloupec s podíly je \( k \)-tý. | kde sloupec s podíly je \( k \)-tý. | ||
\end{remark*} | \end{remark*} | ||
− | + | ||
\begin{define*} | \begin{define*} | ||
Definujeme matici soustavy na konci \( k \)-tého kroku Gaussovy eliminační metody jako | Definujeme matici soustavy na konci \( k \)-tého kroku Gaussovy eliminační metody jako | ||
Řádka 192: | Řádka 192: | ||
\[ \matice P^{( 0 )} = \matice P \] | \[ \matice P^{( 0 )} = \matice P \] | ||
\end{define*} | \end{define*} | ||
− | + | ||
\begin{remark*} | \begin{remark*} | ||
Matice soustavy na konci \( k \)-tého kroku Gaussovy eliminační metody má tvar | Matice soustavy na konci \( k \)-tého kroku Gaussovy eliminační metody má tvar | ||
Řádka 207: | Řádka 207: | ||
\] | \] | ||
\end{remark*} | \end{remark*} | ||
− | + | ||
\begin{define*} | \begin{define*} | ||
Definujeme matici úprav Gaussovy eliminační metody jako | Definujeme matici úprav Gaussovy eliminační metody jako | ||
\[ \matice M = \prod_{k = 0}^{n - 1} \matice M^{( n - k )} \] | \[ \matice M = \prod_{k = 0}^{n - 1} \matice M^{( n - k )} \] | ||
\end{define*} | \end{define*} | ||
− | + | ||
Vidíme, že platí | Vidíme, že platí | ||
\[ | \[ | ||
Řádka 232: | Řádka 232: | ||
\[ \matice A = \left( \matice M^{-1} \matice D^{-1} \right) \matice D \matice U \] | \[ \matice A = \left( \matice M^{-1} \matice D^{-1} \right) \matice D \matice U \] | ||
což je podle \ref{LDR} LDR rozklad. | což je podle \ref{LDR} LDR rozklad. | ||
− | + | ||
\begin{theorem} | \begin{theorem} | ||
\label{GEMRegularni} | \label{GEMRegularni} | ||
Řádka 258: | Řádka 258: | ||
\] | \] | ||
a tedy | a tedy | ||
− | \[ \det \matice A_1 = \det \matice L_1 \det \matice U_1 = \prod_{i = 1}^ | + | \[ \det \matice A_1 = \det \matice L_1 \det \matice U_1 = \prod_{i = 1}^k \matice A_{ii}^{( i - 1 )} \neq 0 \] |
− | Protože velikost bloků můžeme volit libovolně, je matice \( \matice A \) silně regulární. | + | Protože velikost bloků můžeme volit libovolně, tj. \(k \in \hat n\), 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. \] | \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ý. | 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í. | To implikuje, že \[ \det \matice A_1 = 0 \] a tudíž není matice \( \matice A \) silně regulární. | ||
− | + | ||
\end{enumerate} | \end{enumerate} | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\subsection{Modifikovaná Gaussova eliminační metoda} | \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). | 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. | \\ 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} | \begin{example} | ||
\todo{Příklad 4.6} | \todo{Příklad 4.6} | ||
\end{example} | \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í. | 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í. | \\ 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} | \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) \). | 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. | \\ 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} | \subsection{GEM a LU rozklad} | ||
Označíme \( \matice L = \matice M^{-1} \). Poté | Označíme \( \matice L = \matice M^{-1} \). Poté | ||
Řádka 294: | Řádka 294: | ||
\end{itemize} | \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 ) \). | 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*} | \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 | 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}.\] | \[ \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 | 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},\] | \[ \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},\] | ||
Řádka 318: | Řádka 317: | ||
\] | \] | ||
\end{remark*} | \end{remark*} | ||
− | + | ||
A tedy | A tedy | ||
− | + | ||
\[ \left( \matice M^{( k )} \right)^{-1} = | \[ \left( \matice M^{( k )} \right)^{-1} = | ||
\begin{pmatrix} | \begin{pmatrix} | ||
Řádka 332: | Řádka 331: | ||
\end{pmatrix} | \end{pmatrix} | ||
\] | \] | ||
− | + | ||
\begin{lemma} | \begin{lemma} | ||
Pro \(i<j\) platí, že součin matic typu | Pro \(i<j\) platí, že součin matic typu | ||
Řádka 341: | Řádka 340: | ||
Zřejmé, je vidět z roznásobení. | Zřejmé, je vidět z roznásobení. | ||
\end{proof} | \end{proof} | ||
− | + | ||
\begin{remark*} | \begin{remark*} | ||
Pro platnost lemmatu je zásadní platnost nerovnosti \(i<j\), tj. pořadí násobení! (Nerovnosti 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.) | Pro platnost lemmatu je zásadní platnost nerovnosti \(i<j\), tj. pořadí násobení! (Nerovnosti 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*} | \end{remark*} | ||
− | + | ||
\begin{remark*} | \begin{remark*} | ||
Toto lemma platí obecně pro matice této struktury, ne jen matice \( \matice M\). | Toto lemma platí obecně pro matice této struktury, ne jen matice \( \matice M\). | ||
\end{remark*} | \end{remark*} | ||
− | + | ||
− | + | ||
Díky předchozímu lemmatu již vidíme | Díky předchozímu lemmatu již vidíme | ||
\[ \matice L = | \[ \matice L = | ||
Řádka 361: | Řádka 360: | ||
\end{pmatrix} | \end{pmatrix} | ||
\] | \] | ||
− | + | ||
Což jsou přesně prvky, které se nulují pod diagonálou v Gaussově eliminační metodě. Proto lze LU rozklad počítat 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 a matici postupně přepisujeme, protože každý její prvek potřebujeme právě jednou.) | Což jsou přesně prvky, které se nulují pod diagonálou v Gaussově eliminační metodě. Proto lze LU rozklad počítat 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 a matici postupně přepisujeme, protože každý její prvek potřebujeme právě jednou.) | ||
\begin{example} | \begin{example} | ||
\todo{Příklad 4.8} | \todo{Příklad 4.8} | ||
\end{example} | \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 | \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 \] | \[ \matice A = \matice L_C \matice U_C = \left( \matice U_D \right)^T \left( \matice L_D \right)^T \] | ||
Řádka 381: | Řádka 380: | ||
a následně pro pevné \(i\) iterací přes \(j>i\) | a následně pro pevné \(i\) iterací přes \(j>i\) | ||
\[ \matice U_{ij} = \frac{\matice A_{ij} -\sum_{k = 1}^{i - 1} \matice L_{ik} \matice U_{kj}}{\matice L_{ii}}. \] | \[ \matice U_{ij} = \frac{\matice A_{ij} -\sum_{k = 1}^{i - 1} \matice L_{ik} \matice U_{kj}}{\matice L_{ii}}. \] | ||
− | + | ||
− | + | ||
\begin{theorem*} | \begin{theorem*} | ||
Croutovu a Doolittlovu faktorizaci lze provést právě tehdy, když je matice \( \matice A \) silně regulární. | Croutovu a Doolittlovu faktorizaci lze provést právě tehdy, když je matice \( \matice A \) silně regulární. | ||
+ | \begin{proof} | ||
+ | Algoritmy lze provést právě tehdy, když nejsou žádné diagonální prvky matice \( \matice L \) nulové. Na diagonále matice \( \matice L \) jsou ale pivoty základní Gaussovy eliminační metody (plyne z jednoznačnosti LU rozkladu). Z \ref{GEMRegularni} plyne tvrzení věty. | ||
+ | \end{proof} | ||
\end{theorem*} | \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ěť. | 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} | \begin{theorem} | ||
\label{LUSpojity} | \label{LUSpojity} | ||
Řádka 396: | Řádka 397: | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} | ||
− | + | ||
\begin{remark*} | \begin{remark*} | ||
Z důkazu \ref{LUSpojity} výše je zřejmé, že i tato metoda bude mít problémy s malými pivoty, tj. bude méně stabilní pro špatně podmíněné matice. | Z důkazu \ref{LUSpojity} výše je zřejmé, že i tato metoda bude mít problémy s malými pivoty, tj. bude méně stabilní pro špatně podmíněné matice. | ||
\end{remark*} | \end{remark*} | ||
− | + | ||
\begin{example} | \begin{example} | ||
\todo{Příklad 4.10} | \todo{Příklad 4.10} | ||
\end{example} | \end{example} | ||
− | + | ||
\subsection{LU rozklad pro symetrické matice - Choleského dekompozice} | \subsection{LU rozklad pro symetrické matice - Choleského dekompozice} | ||
− | + | ||
\begin{theorem}[Choleského rozklad] | \begin{theorem}[Choleského rozklad] | ||
\label{CholeskehoRozklad} | \label{CholeskehoRozklad} | ||
Řádka 417: | Řádka 418: | ||
\end{proof} | \end{proof} | ||
\end{theorem} | \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 | 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} \overline{\matice S}_{ki} \] | + | \[ \matice S_{ii} = \sqrt{\matice A_{ii} -\sum_{k = 1}^{i - 1} \matice S_{ki} \overline{\matice S}_{ki}} \] |
− | \[ \matice S_{ij} = \frac{\matice A_{ij} -\sum_{k = 1}^{i - 1} \overline{\matice S}_{ki} \matice S_{kj}}{\overline{\matice S}_{ii} \] | + | \[ \matice S_{ij} = \frac{\matice A_{ij} -\sum_{k = 1}^{i - 1} \overline{\matice S}_{ki} \matice S_{kj}}{\overline{\matice S}_{ii}} \] |
\todo{Zkontrolovat. Mělo by to být takto, ale nejsem si jistý} | \todo{Zkontrolovat. Mělo by to být takto, ale nejsem si jistý} | ||
\begin{example} | \begin{example} | ||
\todo{Příklad 4.12} | \todo{Příklad 4.12} | ||
\end{example} | \end{example} | ||
− | + | ||
\subsection{Thomasův algoritmus} | \subsection{Thomasův algoritmus} | ||
\todo{Thomasův algoritmus} | \todo{Thomasův algoritmus} | ||
− | + | ||
\subsection{Schurův doplněk} | \subsection{Schurův doplněk} | ||
\todo{Schurův doplněk} | \todo{Schurův doplněk} |
Aktuální verze z 3. 6. 2024, 16:47
[ 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. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01NUM1
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu 01NUM1 | Dedicma2 | 3. 6. 2024 | 19:49 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Dedicma2 | 3. 6. 2024 | 19:48 | ||
Header | editovat | Hlavičkový soubor | Dedicma2 | 17. 1. 2016 | 16:20 | header.tex | |
Kapitola0 | editovat | Značení | Dedicma2 | 23. 5. 2017 | 21:32 | znaceni.tex | |
Kapitola2 | editovat | Opakování a doplnění znalostí z lineární algebry | Dedicma2 | 3. 6. 2024 | 15:41 | prezentace2.tex | |
Kapitola3 | editovat | Úvod do numerické matematiky | Dedicma2 | 3. 6. 2024 | 15:51 | prezentace3.tex | |
Kapitola4 | editovat | Přímé metody pro lineární soustavy | Dedicma2 | 3. 6. 2024 | 16:47 | prezentace4.tex | |
Kapitola5 | editovat | Iterativní metody | Dedicma2 | 3. 6. 2024 | 16:59 | prezentace5.tex | |
Kapitola6 | editovat | Vlastní čísla a vektory matic | Dedicma2 | 3. 6. 2024 | 17:07 | prezentace6.tex | |
Kapitola7 | editovat | Nelineární rovnice | Kubuondr | 31. 1. 2017 | 14:27 | prezentace7.tex | |
Kapitola8 | editovat | Interpolace | Kubuondr | 31. 1. 2017 | 15:43 | prezentace8.tex | |
Kapitola9 | editovat | Derivace a integrace | Kubuondr | 31. 1. 2017 | 17: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 \) zleva, 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 \[ \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}^k \matice A_{ii}^{( i - 1 )} \neq 0 \] Protože velikost bloků můžeme volit libovolně, tj. \(k \in \hat n\), 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\), tj. pořadí násobení! (Nerovnosti 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 lze LU rozklad počítat 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 a matici postupně přepisujeme, protože každý její prvek potřebujeme právě jednou.) \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}} , \forall j>1\] 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}}, \forall j>2\] A obecně ze vztahu pro \( \matice A_{ij} \) dostaneme pro \(j\) pevné iterací přes \(i\geq j\) \[ \matice L_{ij} = \matice A_{ij} -\sum_{k = 1}^{j - 1} \matice L_{ik} \matice U_{kj}\] a následně pro pevné \(i\) iterací přes \(j>i\) \[ \matice U_{ij} = \frac{\matice A_{ij} -\sum_{k = 1}^{i - 1} \matice L_{ik} \matice U_{kj}}{\matice L_{ii}}. \] \begin{theorem*} Croutovu a Doolittlovu faktorizaci lze provést právě tehdy, když je matice \( \matice A \) silně regulární. \begin{proof} Algoritmy lze provést právě tehdy, když nejsou žádné diagonální prvky matice \( \matice L \) nulové. Na diagonále matice \( \matice L \) jsou ale pivoty základní Gaussovy eliminační metody (plyne z jednoznačnosti LU rozkladu). Z \ref{GEMRegularni} plyne tvrzení věty. \end{proof} \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 racionální funkce, a tedy spojité za předpokladu nenulovosti \(\matice L_{ii}\). \end{proof} \end{theorem} \begin{remark*} Z důkazu \ref{LUSpojity} výše je zřejmé, že i tato metoda bude mít problémy s malými pivoty, tj. bude méně stabilní pro špatně podmíněné matice. \end{remark*} \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} \overline{\matice S}_{ki}} \] \[ \matice S_{ij} = \frac{\matice A_{ij} -\sum_{k = 1}^{i - 1} \overline{\matice S}_{ki} \matice S_{kj}}{\overline{\matice S}_{ii}} \] \todo{Zkontrolovat. Mělo by to být takto, ale nejsem si jistý} \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}