NME01:Kapitola4
Z WikiSkripta FJFI ČVUT v Praze
Verze z 5. 6. 2021, 16:56, kterou vytvořil Kunzmart (diskuse | příspěvky) (Založena nová stránka s textem „% \wikiskriptum{NME01} \subsection{Řešení soustav \texorpdfstring{\(\mathbb{A}\vec{x}=\vec{b}\)}{Ax = b}} \begin{itemize} \item \underline{metody:} p…“)
[ 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 NME01
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu NME01 | Kunzmart | 5. 6. 2021 | 17:33 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Kunzmart | 5. 6. 2021 | 17:59 | ||
Header | editovat | Hlavičkový soubor | Kunzmart | 5. 6. 2021 | 16:54 | header.tex | |
Kapitola1 | editovat | Reprezentace čísel v počítači | Kunzmart | 5. 6. 2021 | 16:55 | 01_reprezentace_cisel_v_pocitaci.tex | |
Kapitola2 | editovat | Chyby | Kunzmart | 5. 6. 2021 | 16:55 | 02_chyby.tex | |
Kapitola3 | editovat | Úlohy lineární algebry | Kunzmart | 5. 6. 2021 | 17:30 | 03_ulohy_lin_alg.tex | |
Kapitola4 | editovat | Řešení soustav Ax - b | Kunzmart | 5. 6. 2021 | 16:56 | 03a_reseni_soustav_Ax-b.tex | |
Kapitola5 | editovat | Vlastní čísla | Kunzmart | 5. 6. 2021 | 16:56 | 03b_vlastni_cisla.tex | |
Kapitola6 | editovat | Determinant | Kunzmart | 5. 6. 2021 | 16:57 | 03c_determinant.tex | |
Kapitola7 | editovat | Aproximace funkcí | Kunzmart | 5. 6. 2021 | 17:31 | 04_aproximace_funkci.tex | |
Kapitola8 | editovat | Interpolace | Kunzmart | 5. 6. 2021 | 16:57 | 04a_interpolace.tex | |
Kapitola9 | editovat | Čebyševova aproximace | Kunzmart | 5. 6. 2021 | 16:58 | 04b_cebysevovy_aproximace.tex | |
Kapitola10 | editovat | Metoda nejmenších čtverců | Kunzmart | 5. 6. 2021 | 16:58 | 04c_metoda_nejmensich_ctvercu.tex | |
Kapitola11 | editovat | Řešení nelineárních rovnic | Kunzmart | 5. 6. 2021 | 17:32 | 05_reseni_nelinearnich_rovnic.tex | |
Kapitola12 | editovat | Bisekce | Kunzmart | 5. 6. 2021 | 16:59 | 05a_bisekce.tex | |
Kapitola13 | editovat | Metoda sečen | Kunzmart | 5. 6. 2021 | 16:59 | 05b_metoda_secen.tex | |
Kapitola14 | editovat | Regula falsi | Kunzmart | 5. 6. 2021 | 17:00 | 05c_regula_falsi.tex | |
Kapitola15 | editovat | Metoda Newton-Raphsonova | Kunzmart | 5. 6. 2021 | 17:00 | 05d_newton_raphsonova_metoda.tex | |
Kapitola16 | editovat | Hledání kořenu polynomu | Kunzmart | 5. 6. 2021 | 17:00 | 05e_hledani_korenu_polynomu.tex | |
Kapitola17 | editovat | Mullerova metoda | Kunzmart | 5. 6. 2021 | 17:01 | 05f_mullerova_metoda.tex | |
Kapitola18 | editovat | Prostá iterace | Kunzmart | 5. 6. 2021 | 17:01 | 05g_prosta_iterace.tex | |
Kapitola19 | editovat | Metoda Newton-Raphson pro systémy rovnic | Kunzmart | 5. 6. 2021 | 17:01 | 05h_newton_raphsonova_metoda_pro_systemy_rovnic.tex | |
Kapitola20 | editovat | Hledání extrémů funkcí | Kunzmart | 5. 6. 2021 | 17:32 | 06_hledani_extremu_funkci.tex | |
Kapitola21 | editovat | Metoda zlatého řezu | Kunzmart | 5. 6. 2021 | 17:03 | 06a_metoda_zlateho_rezu.tex | |
Kapitola22 | editovat | Parabolická iterpolace | Kunzmart | 5. 6. 2021 | 17:04 | 06b_parabolicka_iterpolace.tex | |
Kapitola23 | editovat | Nelder Meadova metoda | Kunzmart | 5. 6. 2021 | 17:09 | 06c_nelder_meadova_metoda.tex | |
Kapitola24 | editovat | Gradientní metody | Kunzmart | 5. 6. 2021 | 17:09 | 06d_gradientni_metody.tex | |
Kapitola25 | editovat | Numerická integrace | Kunzmart | 5. 6. 2021 | 17:32 | 07_numericka_integrace.tex | |
Kapitola26 | editovat | Kvadraturní vzorce | Kunzmart | 5. 6. 2021 | 17:09 | 07a_kvadraturni_vzorce.tex | |
Kapitola27 | editovat | Integrály se singularitami | Kunzmart | 5. 6. 2021 | 17:10 | 07b_integraly_se_singularitami.tex | |
Kapitola28 | editovat | Gaussovy kvadratury | Kunzmart | 5. 6. 2021 | 17:20 | 07c_gaussovy_kvadratury.tex | |
Kapitola29 | editovat | Integrace Monte Carlo | Kunzmart | 5. 6. 2021 | 17:20 | 07d_integrace_monte_carlo.tex | |
Kapitola30 | editovat | Obyčejné diferenciální rovnice | Kunzmart | 5. 6. 2021 | 17:33 | 08_obycejne_diferencialni_rce.tex | |
Kapitola31 | editovat | Eulerova metoda | Kunzmart | 5. 6. 2021 | 17:21 | 08a_eulerova_metoda.tex | |
Kapitola32 | editovat | Metoda středního bodu | Kunzmart | 5. 6. 2021 | 17:21 | 08b_metoda_stredniho_bodu.tex | |
Kapitola33 | editovat | Heunova metoda | Kunzmart | 5. 6. 2021 | 17:22 | 08c_heunova_metoda.tex | |
Kapitola34 | editovat | Runge Kuttovy metody | Kunzmart | 5. 6. 2021 | 17:22 | 08d_runge_kuttovy_metody.tex | |
Kapitola35 | editovat | Metoda leap frog | Kunzmart | 5. 6. 2021 | 17:22 | 08e_metoda_leap_frog.tex | |
Kapitola36 | editovat | Metoda prediktor korektor | Kunzmart | 5. 6. 2021 | 17:22 | 08f_metoda_prediktor_korektor.tex | |
Kapitola37 | editovat | Metoda střelby | Kunzmart | 5. 6. 2021 | 17:23 | 08g_metoda_strelby.tex | |
Kapitola38 | editovat | Metoda konečných diferencí | Kunzmart | 5. 6. 2021 | 17:23 | 08h_metoda_konecnych_diferenci.tex | |
Kapitola39 | editovat | Variační metody | Kunzmart | 5. 6. 2021 | 17:23 | 08i_variacni_metody.tex |
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}