Zdrojový kód
% \wikiskriptum{NME01}
\subsection{Řešení soustav \texorpdfstring{\(\mathbb{A}\vec{x}=\vec{b}\)}{Ax = b}}
\begin{itemize}
\item \underline{metody:} přímé, iterační, gradientní
\end{itemize}
\subsubsection{Přímé metody}
\begin{itemize}
\item = spočívají v příslušné úpravě matice na \( \triangle \) tvar (diagonální), tj. \underline{přímý běh},
potom řešení soustavy s horní \( \triangle \) maticí \( \mathbb{U} \) nebo dolní \( \triangle \) \( \mathbb{L} \), tj. \underline{zpětný běh}
\item \underline{řešení soustav s \( \mathbb{U} \) resp. \( \mathbb{L} \):} (zpětný běh)
\[
\begin{aligned}\mathbb{U} = \begin{pmatrix} u_{11} & u_{12} & \ldots & u_{1n} \\ 0 & u_{22} & \ldots & u_{2n}\\ \vdots & \vdots &\ddots & \vdots \\ 0 & 0 & \ldots & u_{nn}\end{pmatrix}, \mathbb{U}\vec{x} = \vec{b} \implies & x_{n} = \frac{b_n}{u_{nn}} \land u_{n-1}\text{\stackunder{\( x_{n-1} + u_{nn} x_{n} = b_{n-1} \)}{\( \hookrightarrow x_{n-1} = \frac{b_{n-1}}{u_{n-1}}- \frac{1}{u_{n-1}}x_{n}u_{nn} \)}} \\\\
& \qquad\implies
\text{\stackengine{\stackgap}{\( \boxed{x_k = \frac{1}{u_{kk}}\left(b_k-\sum_{j = k+1}^{n} u_{kj}x_j\right)} \)}
{\scriptsize\( \hookrightarrow \) \underline{zpětný běh} - postupujeme ve směru \underline{klesání \( k \)}}{U}{l}{F}{T}{S}}
\end{aligned}
\]
\vspace{-7em}
\begin{itemize}
\item \underline{složitost} \( \sim n^2 \) (\( n \) násobení a \( n \) sčítání)
\end{itemize}
\vspace{1em}
\item \underline{Gaussova a Gauss-Jordanova eliminace:}
\begin{itemize}
\item převod soustavy \( \mathbb{A}\vec{x}=\vec{b} \) na soustavu s \( \mathbb{U} \) nebo \( \mathbb{D} \)
\item základem je tzv. \underline{pivoting} \( \rightarrow \) \underline{pivot}, hlavní prvek, volíme tak, aby byl v dané iteraci na prvním místě \( \impliedby \) nechceme kvůli chybám při odečtení dostat špatné výsledky
\[
\begin{aligned} & \mathbb{A} = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} \rightarrow
\text{\stackengine{\stackgap}{upravíme přenásobením 1. řádku \( a_{i1} \) a násobením \( \frac{-1}{a_{11}} \)}
{\( \implies \) sečteme řádky a provedeme úpravu na jenotkové matici \( \implies \) získáme \( \mathbb{D}_1 \)}{U}{l}{F}{T}{\stacktype}} \\&
\text{tj. } \mathbb{D}_1 \mathbb{A}\vec{x} = \mathbb{D}_1\vec{b}\text{, kde }\mathbb{D}_1 =
\begin{pmatrix}
\phantom{-}1 & 0 & 0 \\
-\frac{a_{21}}{a_{11}} & 1 & 0 \\
-\frac{a_{21}}{a_{11}} & 0 & 1
\end{pmatrix}
\text{ a ozn. \stackengine{\stackgap}{\underline{\( \mathbb{A}^{(1)} \coloneqq\mathbb{D}_1\mathbb{A}\) }, \( \underline{\vec{b}^{(1)}\coloneqq\mathbb{D}_1\vec{b}} \)}
{\( \implies \) pokračujeme dále v iteracích}{U}{l}{F}{T}{\stacktype}}\end{aligned}\]
\vspace{-1em}
\item \underline{složitost} \( \sim n^3 \)
\item při Gauss-Jordanově eliminaci upravujeme \( \forall \) prvky mimo diagonálu \( \implies \) převedeme \( \mathbb{A} \) na \( \mathbb{I} \) a\\ \( \mathbb{D} = \mathbb{A}^{-1} = \mathbb{D}_n\cdot\ldots\cdot\mathbb{D}_2\cdot\mathbb{D}_1\cdot\mathbb{I} \)
\item \underline{problémy metody:} postupná ztráta přesnosti vlivem zaokrouhlování, mohou vznikat singulární matice, což vede na špatně podmíněnou úlohu\ldots
\end{itemize}
\pagebreak
\item \underline{L-U dekompozice:}
\begin{itemize}
\item využívá faktu, že každou regulární matici lze rozložit na součin \( \mathbb{A} = \mathbb{L}\cdot\mathbb{U} \)
\item \underline{výhody:} lze si \underline{\( \mathbb{L} \) a \( \mathbb{U} \) předpočítat}, pokud nám chodí \underline{nová data} (vektor \( \vec{b} \)), obě matice lze kompaktně zapsat do jedné, lze iterativně zpřesnit výsledek
\item \underline{řešení:} \( \mathbb{A}\vec{x} = \vec{b} \Leftrightarrow (\mathbb{L}\cdot\mathbb{U}) \vec{x} = \vec{b} \Leftrightarrow \text{\stackengine{\stackgap - 1em}{\( \underbrace{\mathbb{L}\cdot(\mathbb{U}\vec{x}) = \vec{b}} \)}{2 soustavy s \( \triangle \) maticí:
\stackengine{\stackgap}{\( \left.\begin{aligned}&\mathbb{L}\vec{y}=\vec{b}\\&\mathbb{U}\text{\underline{{\( \vec{x} \)}}} = \vec{y}\end{aligned}\right\} \) 2 \( \times \) zpětný běh}
{\hspace{1em}\( \hookrightarrow \) \underline{\scriptsize hledáme}}{U}{l}{F}{T}{\stacktype}}{U}{l}{F}{T}{\stacktype}} \)
\vspace{-1em}
\item hledání matic \( \mathbb{L} \) a \( \mathbb{U} \) :
\begin{itemize}
\item \underline{Croutův algoritmus} - z definice násobení matic:
\item [\underline{př.:}] \( \mathbb{A} = \begin{pmatrix} 1 & 2 & 4 \\ 3 & 8 & 14 \\ 2 & 6 & 13 \end{pmatrix} = \underbrace{\begin{pmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & 1 & 1 \end{pmatrix}}_{\mathbb{L}}\cdot \underbrace{\begin{pmatrix} 1 & 2 & 4 \\ 0 & 2 & 2 \\ 0 & 0 & 3 \end{pmatrix}}_{\mathbb{U}} \rightarrow \begin{pmatrix} 1 & 2 & 4 \\ 3 & 2 & 2 \\ 2 & 1 & 3 \end{pmatrix} = (\mathbb{L}\backslash \mathbb{U}) \)
\end{itemize}
\item \underline{složitost} \( \sim n^3 \) (2 zpětné chody)
\end{itemize}
\end{itemize}
\subsubsection{Iterační metody}
\begin{itemize}
\item \underline{postup}
\begin{enumerate}
\item odhadneme řešení soustavy \( \mathbb{A}\vec{x} = \vec{b} \rightarrow \) \underline{odhad} \( \vec{x}^{(0)} \), \( \vec{c}_0 = \vec{b} \)
\item přiblížení k přesnému řešení získáme vztahem \( \boxed{\vec{x}^{(k+1)} = \mathbb{B}_k \cdot\vec{x}^{(k)} + \vec{c}_k} \)
\end{enumerate}
\item \( \begin{aligned} & \text{\( \mathbb{B}_{k} = \mathbb{B} \) (konstantní) \( \implies\) \underline{stacionární metody}} \\
& \text{\( \mathbb{B}_k \) v každém kroku jiná \( \implies \) \underline{nestacionární metody}}\end{aligned} \)
\item konvergence nestacionárních metod:
\begin{itemize}
\item pro \( \forall \) vl. čísla \( \mathbb{B} \) musí platit \underline{\( |\lambda|\stackon{<}{!}1 \)} \( \Leftrightarrow \) \underline{spektrální poloměr:} \( \boxed{\rho(\mathbb{B}) = \max_{i \in \hat{n}} |\lambda_i| < 1} \) \( \leftarrow \) nutná a posatčující podmínka
\item nebo poukud v některé normě platí \( \|\mathbb{B}\| < 1 \) \( \implies \) konverguje
\end{itemize}
\item \underline{chyba:} iterujeme, dokud \( \|\vec{x}^{(n)} - \vec{x}\| \le \varepsilon \Leftrightarrow \|\vec{x}^{(k)} - \vec{x}\| = \|\vec{x}^{(k)}-\mathbb{A}^{-1}\vec{b}\| = \|\mathbb{A}^{-1}(\mathbb{A}\vec{x}^{(k)} - \vec{b})\| \le \|\mathbb{A}^{-1}\|\cdot\|\mathbb{A}\vec{x}^{(k)}-\vec{b}\| \le \varepsilon \)
\item\underline{prostá iterace:}
\begin{itemize}
\item rovnici \( \mathbb{A}\vec{x}=\vec{b} \) upravíme: \( \mathbb{I}\vec{x} + \mathbb{A}\vec{x} = \mathbb{I}\vec{x} + \vec{b} \Leftrightarrow \vec{x} = \underbrace{(\mathbb{I}-\mathbb{A})}_{\text{\reflectbox{\( \coloneqq \)}}\mathbb{B}}\vec{x} + \vec{b} \)
\vspace{-1.5em}
\item \underline{iterujeme} \( \boxed{\vec{x}^{(k+1)} = \mathbb{B}\vec{x}^{(k)} + \vec{b}} \), \( \vec{x}^{(0)} \) \ldots první odhad
\item \underline{v praxi nepoužívaná} - nepřesná a často diverguje
\end{itemize}
\item \underline{Jakobiho a Gauss-Sidelova metoda:}
\begin{itemize}
\item odvození:
\begin{enumerate}[label=\roman*)]
\item přepíšeme soustavu rovnic \( \mathbb{A}\vec{x} = \vec{b}:\begin{aligned} & a_{11}x_1 + a_{12}x_2 + a_{13}x_3 = b_1 \\
& a_{21}x_1 + a_{22}x_2 + a_{23}x_3 = b_2 \\
& a_{31}x_1 + a_{32}x_2 + a_{33}x_3 = b_3\end{aligned} \)
\item v každém řádku vyjádříme 1 neznámou:
\[
\begin{aligned}
& x_1 = \frac{1}{a_{11}}(b_1-a_{12}x_2-a_{13}x_3) \\
& x_2 = \frac{1}{a_{22}}(b_2-a_{21}x_1-a_{23}x_3) \\
& x_3 = \frac{1}{a_{33}}(b_3-a_{31}x_1-a_{32}x_2)
\end{aligned}
\text{\stackengine{\stackgap}{\( \longrightarrow \)}
{\hspace{1em}\scriptsize\underline{iterujeme}\hspace{1em}}{O}{c}{F}{F}{\stacktype}}
\begin{aligned}
& x_1^{(k+1)} = \frac{1}{a_{11}}(b_1-a_{12}x_2^{(k)}-a_{13}x_3^{(k)}) \\
& x_2^{(k+1)} = \frac{1}{a_{22}}(b_2-a_{21}x_1^{(k)}-a_{23}x_3^{(k)}) \\
& x_3^{(k+1)} = \frac{1}{a_{33}}(b_3-a_{31}x_1^{(k)}-a_{32}x_2^{(k)})
\end{aligned}
\]
\item \(\underbrace{\begin{pmatrix}
a_{11} & a_{12} & a_{13} \\
a_{21} & a_{22} & a_{23} \\
a_{31} & a_{32} & a_{33}
\end{pmatrix} }_{=\mathbb{A}} =
\underbrace{\begin{pmatrix}
0 & 0 & 0 \\
a_{21} & 0 & 0 \\
a_{31} & a_{32} & 0
\end{pmatrix} }_{\mathbb{L}} +
\underbrace{\begin{pmatrix}
a_{11} & 0 & 0 \\
0 & a_{22} & 0 \\
0 & 0 & a_{33}
\end{pmatrix} }_{\mathbb{D}} +
\underbrace{\begin{pmatrix}
0 & a_{12} & a_{13} \\
0 & 0 & a_{23} \\
0 & 0 & 0
\end{pmatrix} }_{\mathbb{U}}
\)
\item celkem: \(\boxed{\vec{x}^{(k+1)}=\mathbb{D}^{-1}(\vec{b}-(\mathbb{L}+\mathbb{U})\vec{x}^{(k)})}\) \ldots\underline{Jakobiho metoda}
\item jelikož už ale složky \(\vec{x}^{(k+1)}\) známe z předchozích iterací, můžeme je využít k dašímu zpřesnění\\ \(\implies\) \underline{Gauss-Sidelova metoda}
\[
\text{maticově } \implies
\text{\stackengine{\stackgap }{\( \mathbb{D}\cdot\vec{x}^{(k+1)}+\mathbb{L}\cdot\vec{x}^{(k+1)} = \vec{b} - \mathbb{U}\cdot\vec{x}^{(k)} \)}
{\( \Leftrightarrow\boxed{\vec{x}^{(k+1)}=(\mathbb{D}+\mathbb{L})^{-1}\cdot(\vec{b}-\mathbb{U}\cdot\vec{x}^{(k)})} \)}{U}{l}{F}{T}{\stacktype}
}
\]
\end{enumerate}
\item \underline{konvergence Jacobiho metody:} \(\mathbb{A}\) je \underline{diagonálně dominantní}
\item \underline{konvergence Gauss-Sidelovy metody:} \(\mathbb{A}\) je \underline{diagonálně dominantní} \(\lor\) \(\mathbb{A}\) je \underline{pozitivně definitní}
\item \underline{problém Gauss-Sidelovy metody:}
\begin{itemize}
\item konverguje sice pro hodně matic, ale \underline{pomalu konverguje}
\item[\(\implies\)] metoda \underline{superrelaxace:}
\begin{itemize}
\item slouží k urychlení konvergence G.-S. metody
\item dána vztahem \(\boxed{x_{i}^{(k+1)}=x_{i}^{(k)}+\omega\Delta x_{i}^{(k)}}\), kde \(\Delta x_{i}^{(k)}=x_{i}^{(k+1)}-x_{i}^{(k)}\), \( \omega\)\ldots \underline{relaxační faktor}, \(\omega \in (0,2)\), \(\boxed{\omega_{\text{opt}} = \frac{2}{1+\sqrt{1-\rho^2(\mathbb{B})} }}\), \underline{\(\omega_{\text{opt}}\)\ldots optimální \(\omega\)}, \(\mathbb{B}\) je iterační matice G.-S. tj. \underline{\(\mathbb{B}=-(\mathbb{D}+\mathbb{L})^{-1}\cdot\mathbb{U}\)}
\end{itemize}
\end{itemize}
\end{itemize}
\item \uwave{další:}
\begin{itemize}
\item \underline{soustava s tridiagonální maticí:} \[\mathbb{A}\vec{x}=\vec{f}\implies
\begin{pmatrix}
a_1 & b_1 & \phantom{\vdots} & & \ldots & 0 \\
c_2 & a_1 & b_2 & & & \vdots \\
& c_3 & a_3 & b_3 & \phantom{\vdots} & \\
& \phantom{\vdots} & \ddots & \ddots & \ddots & \\
\vdots & & & c_{n-1} & a_{n-1} & b_{n-1} \\
0 & \ldots & \phantom{\vdots} & & a_n & b_n
\end{pmatrix}\cdot
\begin{pmatrix}
x_1\phantom{\vdots} \\
x_2\phantom{\vdots} \\
x_3\phantom{\vdots} \\
\vdots \\
x_{n-1}\phantom{\vdots} \\
x_{n}\phantom{\vdots}
\end{pmatrix} =
\begin{pmatrix}
f_1\phantom{\vdots} \\
f_2\phantom{\vdots} \\
f_3\phantom{\vdots} \\
\vdots \\
f_{n-1}\phantom{\vdots} \\
f_n\phantom{\vdots}
\end{pmatrix}
\]
\vspace{-1em}
\begin{itemize}
\item předpokládáme zpětný běh:
\begin{enumerate}[label=\roman*)]
\item \( x_{i} = \mu_i x_{i+1} + \rho_i \rightarrow\) dosadíme do \(j\)-tého řádku \( c_jx_{j-1} + a_j x_j + b_j x_{j+1} = f_j\)
\item po dosazení dostaneme: \(c_j (\mu_{j-1} x_j + \rho_{j-1}) + a_j x_j + b_j \hookannotateunder{x_{j+1}}{známe z předchozí iterace} = f_j \implies\) získáme \underline{koeficienty \(\mu_j\) a \(\rho_j\)}\\ \(\implies\) \underline{dostaneme \(x_j\)}
\end{enumerate}
\end{itemize}
\end{itemize}
\item pro řídké matice používáme \underline{gradientní metody}
\end{itemize}
\subsubsection{Podmíněnost řešení \texorpdfstring{\( \mathbb{A}\vec{x} = \vec{b} \)}{Ax = b} }
\begin{itemize}
\item nechť \(\Delta\mathbb{A}, \Delta\vec{b}\) jsou změny dat. Zajímá nás změna řešení \(\frac{\|\Delta\vec{x}\|}{\|\vec{x}\|}\)
\begin{itemize}
\item[\( \hookrightarrow \)] řešíme problém: \((\mathbb{A} + \Delta\mathbb{A})(\vec{x}+\Delta\vec{x}) = \vec{b} + \Delta\vec{b}\)
\item [\(\implies\)] 2 případy:
\begin{enumerate}
\item \uwave{\(\Delta\mathbb{A} = \mathbb{O}\)}
\begin{enumerate}[label= \roman*)]
\item \(\implies \mathbb{A}\cdot\vec{x} + \mathbb{A}\cdot\Delta\vec{x} = \vec{b} + \Delta\vec{b} \Leftrightarrow \Delta\vec{x} = \mathbb{A}^{-1} \cdot \Delta \vec{b}\)
\item platí \(\|\Delta\vec{x}\| \le \|\mathbb{A}^{-1}\| \cdot \left\|\Delta\vec{b}\right\| \land \|\vec{x}\|\le\|\mathbb{A}^{-1}\| \cdot \left\|\vec{b}\right\|\)\\
\(\implies\) relativní změna \(\frac{\|\Delta\vec{x}\|}{\vec{x}}\le\text{\stackengine{\stackgap}{\(\underbrace{\|\mathbb{A}\| \cdot \|\mathbb{A}^{-1}\|} \cdot \frac{\left\|\Delta\vec{b}\right\|}{\left\|\vec{b}\right\|}\)}{\scriptsize\underline{\(C_{p}\)}\ldots \underline{podmíněnost matice}}{U}{l}{F}{T}{\stacktype}}\)
\end{enumerate}
\item \uwave{\(\Delta\mathbb{A} \neq \mathbb{O}\)}
\begin{itemize}
\item[\(\implies\)] \(\frac{\|\Delta\vec{x}\|}{\|\vec{x}\|} \le C_{p} \frac{\frac{\|\Delta\mathbb{A}\|}{\|\mathbb{A}\|}+\frac{\|\Delta\vec{b}\|}{\|\vec{b}\|}}{1-C_{p}\frac{\|\Delta\mathbb{A}\|}{\|\mathbb{A}\|}}\)
\end{itemize}
\end{enumerate}
\item[\(\implies\)] podmíněnost úlohy záleží pouze na \underline{matici \(\mathbb{A}\), nikoliv na \(\vec{b}\)}
\end{itemize}
\end{itemize}
