Verze z 15. 1. 2016, 00:41

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 \), 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 elementárních úprav matice je ekvivalentní násobení zleva 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 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 \) )] \todo{Důkaz 4.5 - zpětná implikace}
\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á suituace 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 lepší 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_{kk}^{( 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_{lk}^{( k - 1 )}, & i = l \wedge j = k \\
1, & i = j \\
0, & \text{jinak} \\
\end{cases}
\]
\end{remark*}
 
A tedy \todo{A co ty podíly?}
 
\[ \left( \matice M^{( k )} \right)^{-1} =
\begin{pmatrix}
1 &&&&&& \\
& \ddots &&&&& \\
&& 1 &&&& \\
&&& \matice A_{kk}^{( k - 1 )} &&& \\
&&& - \matice A_{k + 1, k}^{( k - 1 )} & 1 && \\
&&& \vdots && \ddots & \\
&&& \matice A_{nk}^{( k - 1 )} &&& 1 \\
\end{pmatrix}
\]
 
\begin{lemma}
\todo{Lemma 4.7}
\end{lemma}
 
Díky předchozího 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.
 
\begin{example}
\todo{Příklad 4.8}
\end{example}
 
\subsection{Kompaktní schéma pro LU faktorizaci}
 
\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ů
\[ \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 < j \]
je vidět, že funkce jsou nejvýše kvadratické, a tedy spojité.
\end{proof}
\end{theorem}
 
\subsection{LU rozklad pro symetrické matice - Choleského dekompozice}
 
\setcounter{define}{10}
\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}