The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b01num [2025/06/07 12:10] – [Aproximace funkcí] mistrjirkastatnice:bakalar:b4b01num [2025/06/07 13:38] (current) – [Numerická integrace] mistrjirka
Line 52: Line 52:
 **Interpolace polynomy, splinová interpolace a metoda nejmenších čtverců. Kritéria pro výběr metody.** **Interpolace polynomy, splinová interpolace a metoda nejmenších čtverců. Kritéria pro výběr metody.**
  
-Metody pro nahrazení složitých funkcí nebo datových množin jednoduššími funkcemi, s důrazem na interpolaci polynomy, spliny a metodu nejmenších čtverců. Volba metody závisí na charakteru dat a požadované přesnosti. 
  
-==== Účel a význam aproximace funkcí ====+**Metody pro nalezení funkce vhodně reprezentující daná data, rozdělené na interpolaci (přesný průchod body) a aproximaci (minimalizace chyby).**
  
-Aproximace funkcí slouží k nahrazení obtížně zpracovatelných funkcí (např. transcendentních) nebo diskrétních dat jednoduššími analytickými modely. Používá se v těchto situacích:\\ +==== Rozlišení interpolace a aproximace ====
-- **Interpolace**: Když požadujeme **přesnou shodu s daty v uzlových bodech** (např. rekonstrukce signálů, finanční modely).\\ +
-- **Aproximace**: Když data obsahují **šum nebo nepřesnosti** a cílem je zachytit trend bez nutnosti průchodu všemi body (např. regresní analýza v experimentálních vědách) .+
  
-==== Metody interpolace ====+  * **Interpolace**: Používáme, když požadujeme **přesnou shodu funkčních hodnot v uzlových bodech**. Vhodná pro: 
 +    * Rekonstrukci křivek z přesných měření (např. fyzikální experimenty)  
 +    * Úlohy vyžadující exaktní průchod daty (např. CAD systémy)  
 +  * **Aproximace**: Používáme, když akceptujeme **malou odchylku v bodech** a minimalizujeme celkovou chybu. Vhodná pro: 
 +    * Zpracování šumivých dat (např. ekonomické prognózy)  
 +    * Kompresi signálů (např. MP3, JPEG) 
  
-  - **Interpolace polynomy** +==== Interpolace polynomy ====
-    * Polynom stupně $n-1$ prochází přesně $n$ bodů.\\+
  
-    * **Výhody**: Snadná derivace/integrace, univerzální použití (Weierstrassova věta) .\\+  * **Definice**: Pro dané body $(x_0,y_0),\dots,(x_{n-1},y_{n-1})$ hledáme polynom $\phi$ stupně $<n$ splňující $\phi(x_i) = y_i$  
 +  * **Matematický popis**: 
 +    * //Lagrangeova forma//:\\ 
 +$\phi(t) = \sum_{j=0}^{n-1} y_j \rho_j(t)$, kde $\rho_j(t) = \prod_{\substack{i=0 \\ i \neq j}}^{n-1} \frac{t - x_i}{x_j - x_i}$  
 +    * //Nevýhody//: Velké oscilace pro $n > 20$, citlivost na lokální změny  
 +  * **Použití**: Ideální pro malý počet bodů ($n < 15$) a hladké funkce 
  
-    * **Nevýhody**: Oscilace pro vysoký počet bodů, nevhodná pro data s nespojitostmi.\\+==== Splinová interpolace ====
  
-    * **Formy**: +  * **Definice**: Po částech polynomiální funkce (obvykle kubické), spojitá v první a druhé derivaci  Pro intervaly $[x_{i-1}, x_i]$: $\phi_i(t) = y_{i-1}\eta_i(t) + y_i\varrho_i(t) + c_{i-1}\sigma_i(t) + c_i\tau_i(t)$,\\ 
-      * //Lagrangeova//: $\phi(t) = \sum_{j} y_j \prod_{i \neq j} \frac{t - x_i}{x_j - x_i}$.\\ +kde $\eta_i, \varrho_i, \sigma_i, \tau_i$ jsou kubické polynomy  
- +  * **Podmínky**: 
-      * //Newtonova//: Používá dělené diference pro postupné přidávání bodů . +    * Spojitost derivací: $\phi_i'(x_i) = \phi_{i+1}'(x_i)$, $\phi_i''(x_i) = \phi_{i+1}''(x_i)$ pro $i=1,\dots,n-2$  
-  - **Splinová interpolace** +  * **Výhody**: Minimalizace oscilací, odolnost vůči lokálním změnám 
-    * **Kubické spliny**: Po částech polynomy 3. stupně spojené v uzlech s podmínkami hladkosti (spojitost 1. a 2. derivace).\\ +
- +
-    * **Výhody**: Eliminuje oscilace, vhodná pro větší počet bodů .\\ +
- +
-    * **Nevýhody**: Vyšší výpočetní náročnost.+
  
 ==== Metoda nejmenších čtverců ==== ==== Metoda nejmenších čtverců ====
  
-  * Minimalizuje součet čtverců odchylek $\sum_i (y_i - \phi(x_i))^2$.\\ +  * **Definice**: Minimalizuje součet čtverců odchylek $\min \sum_{i=0}^{n-1} (\phi(x_i) - y_i)^2$  
- +  * **Matematický popis**:\\ 
-  * **Použití**: Pro data se šumem, kdy stačí přibližný trend (např. kalibrace senzorů) .\\ +Pro bázi $\{\phi_0,\dots,\phi_{k-1}\}$ hledáme koeficienty $c_j$ řešením soustavy:\\ 
- +$\sum_{j=0}^{k-1} c_j \left( \phi_j(\vec{x}) \cdot \phi_m(\vec{x}) \right) = \vec{y} \cdot \phi_m(\vec{x})$, $m=0,\dots,k-1$  
-  * **Implementace**: Řešení soustavy lineárních rovnic pro koeficienty bázových funkcí.+  * **Použití**: 
 +    * Přeurčené soustavy ($n > k$), šumivá data  
 +    * Speciální případ: trigonometrická aproximace pro periodické signály (FFT) 
  
 ==== Kritéria pro výběr metody ==== ==== Kritéria pro výběr metody ====
  
-  - **Počet a rozložení dat**: +  - **Počet bodů**: 
-    * Malý počet bodů $\rightarrow$ **polynomiální interpolace**.\\ +    * $n \leq 15$: Polynomiální interpolace  
- +    * $n > 15$: Spliny nebo nejmenší čtverce  
-    * Větší počet bodů $\rightarrow$ **spliny** (zamezení oscilacím).\\ +  - **Požadovaná přesnost**: 
- +    * Exaktní shoda: Interpolace  
-  - **Přesnost požadavků**: +    * Tolerovatelná chyba: Nejmenší čtverce 
-    * Přesná shoda v bodech $\rightarrow$ **interpolace**.\\ +
- +
-    * Toleruje odchylky $\rightarrow$ **metoda nejmenších čtverců** .\\ +
   - **Charakter dat**:   - **Charakter dat**:
-    * Hladká data $\rightarrow$ polynomy/spliny.\\ +    * Periodická data: Goniometrický polynom + FFT  
- +    * Nespojitosti/hrany: Spliny 
-    * Šum nebo odlehlé hodnoty $\rightarrow$ metoda nejmenších čtverců.\\ +
   - **Výpočetní náročnost**:   - **Výpočetní náročnost**:
-    * Polynomy: Rychlé pro malé $n$.\\+    * Rychlé vyhodnocení: Lineární/lokální spliny  
 +    * Optimalizace: Ortogonální báze (Čebyševovy polynomy) 
  
-    * Spliny a MNČ: Náročnější, ale stabilnější pro reálná data .+<tikzjax> 
 +\usepackage{amsmath} 
 +\usepackage{pgfplots} 
 +\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} 
 +\begin{document}
  
-==== Příklad rozhodování ====+% Vizualizace metod 
 +\begin{tikzpicture}[scale=0.7] 
 +% Data points 
 +\draw[fill=black] (1,1) circle (2pt) node[below]{$(x_0,y_0)$}; 
 +\draw[fill=black] (3,2) circle (2pt) node[above]{$(x_1,y_1)$}; 
 +\draw[fill=black] (5,0.5) circle (2pt) node[below]{$(x_2,y_2)$}; 
 +\draw[fill=black] (7,3) circle (2pt) node[above]{$(x_3,y_3)$};
  
-  * **Interpolace**: Modelování přesné teplotní křivky z měření v pevných časech .\\ 
  
-  * **Aproximace MNČ**: Předpověď budoucích hodnot akcií z historických dat s chybami . 
  
-==== Lagrangeova interpolace ==== 
-Lagrangeova interpolace vyjadřuje výsledný polynom jako lineární kombinaci bazických polynomů: 
-$$ 
-\phi(x) = \sum_{j=0}^{n-1} y_j \prod_{\substack{0 \le m \le n-1 \\ m\neq j}} \frac{x - x_m}{x_j - x_m}. 
-$$ 
-Každý bazický polynom je stupně **n−1** a zajišťuje, že $\phi(x_j)=y_j$. 
  
-==== Newtonova interpolace ==== +% Spline interpolation (blue) 
-Newtonova interpolace používá tzv. dělené diference k postupné konstrukci polynomu. Výhodou je jednodušší aktualizace při přidání nového bodu.+\draw[blue, thick] (1,1) .. controls (2,1.4) and (2.5,2.2) .. (3,2); 
 +\draw[blue, thick] (3,2) .. controls (4,1.8) and (4.5,0.3) .. (5,0.5); 
 +\draw[blue, thick] (5,0.5) .. controls (6,0.7) and (6.5,2.5) .. (7,3);
  
-==== Dělené diference ==== +% Least squares (green) 
-Dělené diference definujeme rekurzivně: +\draw[green, thick, domain=0.8:7.5] plot (\x, {0.4*\x + 0.2});
-$$ +
-f[x_i] = y_i,\quad +
-f[x_i,x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1}-x_i},\quad +
-f[x_i,x_{i+1},x_{i+2}] = \frac{f[x_{i+1},x_{i+2}] - f[x_i,x_{i+1}]}{x_{i+2}-x_i},\;\dots +
-$$ +
-V tabulce rozdílných diferencí najdeme koeficienty pro konstrukci polynomu.+
  
-==== Newtonova stupňovatá forma ==== +% Legend 
-Polynom se pak zapíše jako: +\node at (4,-1.5) {Legenda:}; 
-$$ +\draw[blue, thick] (3,-2.5) -- (4,-2.5) node[right]{Spline}; 
-\phi(x) = f[x_0] + f[x_0,x_1](x-x_0) +\draw[green, thick] (3,-3) -- (4,-3) node[right]{Nejmenší čtverce};
-* f[x_0,x_1,x_2](x-x_0)(x-x_1) + \dots + f[x_0,\dots,x_{n-1}]\prod_{i=0}^{n-2}(x-x_i). +
-$$ +
-Poslední člen má stupeň **n−1**.+
  
-==== Výhody ==== +\end{tikzpicture}
-  * **Efektivita** výpočtu tabulky v $\mathcal O(n^2)$ a vyhodnocení $\phi(x)$ v $\mathcal O(n)$.   +
-  * **Snadné přidání** nového bodu – doplníme jeden sloupec a člen, bez přepočtu celého polynomu.   +
-  * **Lepší numerická stabilita** než přímá Lagrangeova forma při větším $n$. +
- +
-=== Splinová interpolace === +
-Spliny jsou lokálně definované polynomy spojité až do druhé derivace. Nejčastěji se používá **kubický spline** (stupně 3). +
- +
-==== Princip splinů ==== +
-Máme **n** datových bodů, mezi kterými je **n−1** sousedních intervalů $[x_i,x_{i+1}]$. Na každém intervalu definujeme polynom stupně 3: +
-$$ +
-s_i(x) = a_i + b_i(x-x_i) + c_i(x-x_i)^2 + d_i(x-x_i)^3,\quad x\in[x_i,x_{i+1}]. +
-$$ +
-Celkem tedy sestavujeme **n−1** kubických polynomů. Podmínky: +
-  * $s_i(x_i)=y_i$ a $s_i(x_{i+1})=y_{i+1}$ (interpolace).   +
-  * Spojitost první a druhé derivace:   +
-    * $s_i'(x_{i+1})=s_{i+1}'(x_{i+1})$,   +
-    * $s_i''(x_{i+1})=s_{i+1}''(x_{i+1})$.   +
-  * Hraniční podmínky (např. „přírodní“ spline: $s_0''(x_0)=0$ a $s_{n-2}''(x_{n-1})=0$). +
- +
-Kubický spline tak zaručuje hladké proložení bez ostrých zlomenin. +
- +
-==== Příklad použití ==== +
-Pro interpolaci teplotních dat je kubický spline ideální, protože: +
-  * zachovává lokální variabilitu,   +
-  * zaručuje spojitost až do druhé derivace,   +
-  * při přidání bodu se mění pouze koeficienty v sousedních intervalech. +
- +
-=== Metoda nejmenších čtverců === +
-Používá se, když data obsahují šum a hledáme optimální přizpůsobení funkce. +
- +
-==== Základní formulace ==== +
-Hledáme aproximaci +
-$$ +
-\phi(x) = \sum_{i=1}^m a_i\varphi_i(x), +
-$$ +
-kde koeficienty $a_i$ minimalizují +
-$$ +
-\sum_{j=1}^N\bigl(f(x_j)-\phi(x_j)\bigr)^2. +
-$$ +
-Řešíme tak soustavu normálních rovnic. +
- +
-==== Příklad ==== +
-Pro polynomy stupně 3 ($\varphi_i(x)=x^{i-1}$) se řeší 4×4 soustava pro koeficienty $a_1,\dots,a_4$. +
- +
-=== Výběr metody aproximace === +
-Volba závisí na typu dat a požadavcích: +
-  * **Interpolace polynomem** – pro **přesná data** a menší počet uzlů.   +
-  * **Spliny** – pro **větší sady dat**, kde požadujeme hladkost.   +
-  * **Metoda nejmenších čtverců** – pro **šumová data** a robustní aproximaci. +
- +
-=== Závěr === +
-Aproximace funkcí vyžaduje zvážit počet dat, přesnost a hladkost výsledné funkce. Každá metoda má své výhody a nevýhody podle konkrétní aplikace.+
  
 +\end{document}
 +</tikzjax>
  
 ===== Numerické metody řešení nelineárních rovnic ===== ===== Numerické metody řešení nelineárních rovnic =====
  
-Nelineární rovnice obecně může být zapsána jako **$f(x) = 0$**, kde $f$ je reálná funkce. Jejich řešení se liší od lineárních rovnic tím, že obvykle nelze najít všechna řešení analyticky a musíme použít numerické metody. 
  
-==== Problémata separace kořenů ====+**Numerické metody řešení rovnice $f(x) = 0$** slouží k nalezení kořenů, kdy analytické řešení není možné. Předpokladem je separace kořenů – nalezení intervalu $\langle a, b \rangle$ s $f(a) \cdot f(b) < 0$ a jediným kořenem. Metody se liší rychlostí konvergence, požadavky na derivace a garancemi konvergence , 
  
-  * **Význam separativity**: Separace kořenů znamená identifikaci úsečky, která obsahuje právě jeden kořen rovnice $f(x) = 0$. Je tedy požadováno: +==== Přehled metod ====
-    * Existuje alespoň jeden kořen v této úsečce +
-    * V této úsečce není žádný další kořen+
  
-  * **Věta o střední hodnotě (IVS)**: Pokud je funkce $f$ spojitá na $[a,b]$ a $f(a) \cdot f(b) < 0$, pak rovnice $f(x) = 0$ má alespoň jeden kořen v intervalu $(a,b)$. Tato podmínka poslouží jako základ pro mnoho metod.+^Metoda            ^Vstup   ^Derivace^Konvergence         ^Řád konvergence                     ^ 
 +|**Bisekce**       |Interval|Ne      |Vždy                |1                                   | 
 +|**Regula falsi**  |Interval|Ne      |Vždy                |1                                   | 
 +|**Metoda sečen**  |2 body  |Ne      |Lokální             |$\frac{1+\sqrt{5}}{2} \approx 1.618$| 
 +|**Newtonova**     |1 bod   |1.      |Lokální             |2                                   | 
 +|**Prostá iterace**|1 bod   |Ne      |Kontraktivita $\phi$|1                                   |
  
-==== Základní numerické metody ==== 
  
-  * **Metoda bisekce**: 
-    * Prostá a spolehlivá metoda 
-    * Vyžaduje interval $[a,b]$, kde $f(a) \cdot f(b) < 0$ 
-    * Půlí interval, dokud nejsou kořeny odděleny dostatečně blízko 
  
-  * **Metoda jednoduché iterace**: 
-    * Výraz $f(x) = 0$ převedeme na tvar $x = \varphi(x)$ 
-    * Opakovaně vypočítáváme: $x_{k+1} = \varphi(x_k)$ 
-    * Konverguje, pokud $|\varphi'(x)| < 1$ ve směru konvergence 
  
-  * **Newtonova metoda**: +==== 1. Metoda půlení intervalu (Bisekce) ====
-    * Využívá lokální lineární aproximaci funkce +
-    * $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$ +
-    * Konverguje kvadraticky, pokud je výchozí bod dostatečně blízko kořenu+
  
-  * **Metoda Regula falsi**: +**Matematický princip**:\\ 
-    * Používá lineární interpolaci+Interval $\langle a_i, b_i \rangle$ se rekurzivně půlí:\\ 
 +$$ 
 +x_i = \frac{a_i + b_i}{2} 
 +$$\\ 
 +Nový interval:\\ 
 +$$ 
 +\langle a_{i+1}, b_{i+1} \rangle =  
 +\begin{cases}  
 +\langle a_i, x_i \rangle & \text{pokud } f(a_i) \cdot f(x_i) < 0 \\ 
 +\langle x_i, b_i \rangle & \text{jinak} 
 +\end{cases} 
 +$$\\ 
 +**Konvergence**: Lineární ($\varepsilon_i = \frac{b_0 - a_0}{2^i}$), garantovaná pro spojité funkce \\ 
 +**Visualizace**:
  
 <tikzjax> <tikzjax>
-\usetikzlibrary{calc,intersections,arrows.meta} +\usepackage{amsmath} 
 +\usepackage{pgfplots} 
 +\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta}
 \begin{document} \begin{document}
-\begin{tikzpicture}[scale=1.0] +\begin{tikzpicture}[thick,xscale=1,yscale=1] 
-  % Osy +  % Axes 
-  \draw[->] (-0.5,0) -- (3.5,0) node[right] {$x$}; +  \draw[->] (0,0) -- (5,0) node[right] {$x$}; 
-  \draw[->] (0,-1.5) -- (0,2.5) node[above] {$f(x)$}; +  \draw[->] (0,-1) -- (0,4) node[above] {$f(x)$};
- +
-  % Graf funkce f(x) +
-  \draw[domain=0.5:3.3,smooth,variable=\x] +
-    plot ({\x},{0.5*(\x-1.5)^2-0.5}) node[right] {$f(x)$}; +
- +
-  % Body x_{k-1} a x_k (zvolil jsem s nerovnými y, aby secanta nešla rovnoběžně s osou) +
-  \coordinate (A) at (1,{0.5*(1-1.5)^2-0.5}); % (1,-0.375) +
-  \coordinate (B) at (3,{0.5*(3-1.5)^2-0.5}); % (3,0.625) +
-  \fill (A) circle (2pt) node[below left] {$x_{k-1}$}; +
-  \fill (B) circle (2pt) node[below right] {$x_k$}; +
- +
-  % Sekanta +
-  \draw[name path=secant] (A) -- (B) node[midway, above] {sekanta};+
  
-  % Osa x jako cesta pro intersections +  % Function (example cubic) 
-  \draw[name path=axis] (-0.5,0) -- (3.5,0);+  \draw[domain=0.5:4.5,smooth,variable=\x,blue] 
 +    plot ({\x},{0.1*(\x-3)^3 + 0.5});
  
-  % Průsečík secanty s osou x +  % Endpoints a=1, b=4 
-  \path [name intersections={of=secant and axis, by=C}]; +  \foreach \X/\lbl in {1/a,4/b}{ 
-  \fill (C) circle (2pt) node[below] {$x_{k+1}$};+    \draw[dashed] (\X,0) node[below] {$\lbl$} 
 +      -- (\X,{0.1*(\X-3)^3+0.5}); 
 +    \fill (\X,{0.1*(\X-3)^3+0.5}) circle (1.5pt); 
 +  }
  
-  % Pomocné čárkované přímky +  % Midpoint c = (a+b)/2 = 2.5 
-  \draw[dashed] (A) -- (A |- 0,0); +  \coordinate (C) at (2.5,{0.1*(2.5-3)^3+0.5}); 
-  \draw[dashed] (B) -- (B |- 0,0);+  \draw[dashed] (2.5,0) node[below] {$c$} -- (C); 
 +  \fill (C) circle (1.5pt);
 \end{tikzpicture} \end{tikzpicture}
  
 \end{document} \end{document}
 </tikzjax> </tikzjax>
-==== Kritéria konvergence ==== 
  
-  * Pro metodu jednoduché iterace: 
-    * $|\varphi'(x)| < 1$ v okolí řešení (dostačující podmínka) 
-    * Existuje $L < 1$ takový, že $|\varphi(x) - \varphi(y)| \leq L|x - y|$ pro $x, y$ v intervalu 
  
-  * Pro Newtonovu metodu: 
-    * Požadované derivace musí existovat a být spojité 
-    * $f'(x) \neq 0$ ve směru konvergence 
  
-==== Chybové odhady ====+==== 2. Newtonova metoda ====
  
-  * **Globální chybová odhada** (např. pro metodu bisekce): +**Matematický princip**:\\ 
-    * $|e_k| \leq \frac{b - a}{2^k}$+Tečna v $x_i$:\\ 
 +$$ 
 +x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)} 
 +$$\\ 
 +**Konvergence**: Kvadratická ($\lim_{i \to \infty} \frac{|x - x_i|}{|x - x_{i-1}|^2} = \left| \frac{f''(x)}{2f'(x)} \right|$) při $f'(x) \neq 0$ \\ 
 +**Visualizace**:
  
-  * **Lokální chybová odhada**: +{{:statnice:bakalar:pasted:20250607-125539.png?490}}
-    * Pro Newtonovu metodu: $|x_{k+1} - r| \approx C|x_k - r|^2$ +
-    * Pro jednoduchou iteraci: $|e_{k+1}| \leq L|e_k|$+
  
-==== Použití a výběr metody ==== 
  
-  * Bisekce je nejistější, ale nejvíc spolehlivá 
-  * Newtonova metoda konverguje rychleji, ale vyžaduje počet derivací 
-  * Metoda sečen je kompromis mezi těmito dvěma metodami 
-  * Pro praktické řešení často kombinujeme více metod (např. bisekci pro oddělení kořene a Newtonovu metodu pro konvergenci) 
  
-==== Užití ve výpočtech ====+==== 3. Metoda sečen ====
  
-V praxi je důležité: +**Matematický princip**:\\ 
-  * Ochránit proti odklonu (divergence) +Aproximace derivace:\\ 
-  * Využít vhodného zaokrouhlení +$$ 
-  * Počítat s numerickou nestabilitou +x_{i+1} = x_i - f(x_i) \cdot \frac{x_i - x_{i-1}}{f(x_i) - f(x_{i-1})} 
-  * Používat adaptivní kroky pro efektivitu+$$\\ 
 +**Konvergence**: Superlineární ($\lim_{i \to \infty} \frac{\ln |x_{i+1} - x_i|}{\ln |x_i - x_{i-1}|} = \frac{1+\sqrt{5}}{2}$) \\ 
 +**Visualizace**:
  
-Metody řešení nelineárních rovnic jsou základně v numerické matematice a mnoho aplikací je tímto problémem ohraničeno. Efektivní a stabilní implementace těchto metod je důležitá pro rychlé a přesné řešení v praxi.+{{:statnice:bakalar:pasted:20250607-125807.png?450}}
  
-===== Numerické řešení soustav lineárních rovnic ===== 
  
-**Numerické řešení soustav lineárních rovnic, možné problémy, argumenty pro použití finitních nebo iteračních metod.** 
  
-==== 1. Finitní (přímé) metody ==== 
  
-  * **Příklady**: Gaussova eliminační metoda, LU dekompozice, QR rozklad.\\+==== 4. Regula falsi ====
  
-  * **Výhody**: +**Matematický princip**:\\ 
-    * Pro malé a střední matice (např. $n < 1000$) jsou efektivní.\\+Kombinace bisekce a sečen. Průsečík sečny s osou $x$:\\ 
 +$$ 
 +x_i = \frac{a_i f(b_i) - b_i f(a_i)}{f(b_i) - f(a_i)} 
 +$$\\ 
 +**Konvergence**: Lineární při zachování intervalu s kořenem \\ 
 +**Visualizace**:
  
-    * Přesné řešení (do chyby zaokrouhlení) v konečném počtu kroků.\\ 
  
-  * **Problémy**: +{{:statnice:bakalar:pasted:20250607-130029.png?450}}
-    * **Výpočetní náročnost**: Složitost $O(n^3)$ pro metody jako LU dekompozice.\\+
  
-    * **Numerická nestabilita**: Pro nevhodné matice (např. špatně podmíněné) mohou vzniknout velké chyby zaokrouhlení.\\+==== 5. Metoda prosté iterace ====
  
-    * **Paměťové nároky**: Ukládání celé matice (i pro řídké matice).\\+**Matematický princip**:\\ 
 +Transformace na $x = \phi(x)$, iterace:\\ 
 +$$ 
 +x_{i+1} = \phi(x_i) 
 +$$\\ 
 +**Konvergence**: Lineární při $|\phi'(x)| < 1$ v okolí kořene. Řád $p$ pro $\phi^{(k)}(x) \neq 0$ ($k = 1, \dots, p-1$) a $\phi^{(p)}(x) \neq 0$ \\ 
 +**Visualizace** (Cobweb diagram):
  
-    * **Pivotace**: Někdy nutná pro stabilitu (např. při eliminaci bez pivotace mohou nastat dělení nulou). 
-  * **Příklady z materiálů**: 
-    * **Normální rovnice** pro řešení přeurčených soustav (např. nejmenší čtverce): $A^T A x = A^T b$.\\ 
  
-    * **QR rozklad** pro řešení soustav s LN sloupci: $Ax = b \Rightarrow Q R x = b \Rightarrow x = R^{-1} Q^T b$.+{{:statnice:bakalar:pasted:20250607-130215.png?450}} 
 +==== Problematika separace kořenů ====
  
-==== 2. Iterační metody ====+  - **Analýza funkce**: 
 +    * Tabulace hodnot, hledání intervalů se znaménkovou změnou\\
  
-  * **Příklady**: Jacobiho metoda, Gaussova-Seidelova metoda, metoda konjugovaných gradientů (pro symetrické pozitivně definitní matice).\\+    * Studium derivací pro monotonii ($f'(x) > 0$ → rostoucí)\\
  
-  * **Výhody**: +  - **Problémy**: 
-    * Efektivní pro **velké řídké matice** (např. $n > 10^4$), protože využívají jen operace s nenulovými prvky.\\+    * Násobné kořeny (např. $f(x) = (x-2)^2$): $f(a) \cdot f(b) < 0$ neplatí\\
  
-    * Nižší paměťové nároky (neukládá se celá matice, jen její struktura).\\+    * Řešení: Transformace $h(x) = \frac{f(x)}{f'(x)}$ redukuje násobnost \\
  
-  * **Problémy**: +  - **Kritické případy**: 
-    * **Konvergence** není zaručena: Závisí na vlastnostech matice (např. diagonální dominance, pozitivní definitnost).\\+    * Nespojitosti, periodické funkce – vyžadují speciální algoritmy (např. kombinace s derivacemi) 
  
-    * **Pomalá konvergence** bez předpodmínky (preconditioner).\\+==== Numerické řešení soustav lineárních rovnic ====
  
-    * **Citlivost na volbu počátečního odhadu**. +**Metody pro řešení soustav lineárních rovnic $A\vec{x} = \vec{b}$, jejich matematické formulace, problémy a kritéria volby mezi přímými a iteračními postupy.**
-  * **Příklady z materiálů**: +
-    * **Nejmenší čtverce** pro přeurčené soustavy: Minimalizace $||Ax - b||_2$ pomocí QR nebo SVD.\\+
  
-    * **Pseudoinverze** pro matice bez plné hodnosti (např. SVD rozklad).+=== Přímé (finitní) metody ===
  
-==== 3. Porovnání a výběr metody ====+Poskytují teoreticky přesné řešení v konečném počtu kroků: 1. **Gaussova eliminace**:\\ 
 +- Převádí matici $A$ na **horní trojúhelníkový tvar** pomocí ekvivalentních úprav.\\ 
 +- **Algoritmus**:\\ 
 +- Pro $k = 1$ až $n-1$:\\ 
 +$a^{(k)}_{i,j} = a^{(k-1)}_{i,j} - \frac{a^{(k-1)}_{i,k}}{a^{(k-1)}_{k,k}} \cdot a^{(k-1)}_{k,j}$\\ 
 +- **Zpětná substituce**:\\ 
 +$x_i = \frac{1}{a^{(i-1)}_{i,i}} \left( a^{(i-1)}_{i,n+1} - \sum_{j=i+1}^n a^{(i-1)}_{i,j}x_j \right)$ \\ 
 +- Výběr hlavního prvku redukuje zaokrouhlovací chyby.
  
-^**Kritérium**        ^**Finitní metody**                       ^**Iterační metody**                    ^ +  - **LU rozklad**: 
-|**Rozměr matice**    |Malé a střední ($n < 1000$)              |Velké ($n > 10^4$)                     | +    * Rozklad $A = LU$ na **dolní ($L$)** a **horní ($U$) trojúhelníkovou matici**.\\
-|**Dostupnost paměti**|Vyžadují větší paměť                     |Efektivní pro řídké matice             | +
-|**Přesnost**         |Vysoká (do chyby zaokrouhlení)           |Závislá na konvergenci a iteracích     | +
-|**Použití**          |Řešení přesných soustav, nejmenší čtverce|Řídké matice, paralelizovatelné systémy|+
  
-==== 4. Typické problémy v numerice ====+    * Řeší se dvě soustavy: 
 +      * $L\vec{y} = \vec{b}$ (dopředná substituce),\\
  
-  * **Špatně podmíněné matice**: Malá nebo nulová determinant, velké chyby v řešení.\\+      * $U\vec{x} = \vec{y}$ (zpětná substituce).\\
  
-  * **Numerická nestabilita**: Např. v Gaussově eliminaci bez pivotace.\\+    * Efektivní pro opakované výpočty s různými $\vec{b}$ 
  
-  * **Chyby zaokrouhlení**: Akumulace v přímých metodách pro velké $n$.\\+=== Iterační metody ===
  
-  * **Řídké matice**: Iterační metody výrazně převyšují přímé metody.+Generují posloupnost aproximací $\vec{x}^{(k)} \to \vec{x}$: 1. **Jacobiho metoda (JIM)**:\\ 
 +- Rozklad $A = D + L + U$ ($D$ diagonální, $L$ ostře dolní, $U$ ostře horní trojúhelníková).\\ 
 +- **Iterační vzorec**:\\ 
 +$\vec{x}^{(k+1)} = D^{-1} \left( \vec{b} - (L + U) \vec{x}^{(k)} \right)$ \\ 
 +- Jednoduchá implementace, paralelizovatelná, ale pomalá konvergence 
  
-==== 5. Ukázkové příklady z materiálů ====+  - **Gaussova-Seidelova metoda (GSM)**: 
 +    * Využívá již aktualizované hodnoty v aktuální iteraci:\\ 
 +$\vec{x}^{(k+1)} = (D + L)^{-1} \left( \vec{b} - U \vec{x}^{(k)} \right)$ \\
  
-  * **Přeurčená soustava** $Ax = b$: Řešeno metodou nejmenších čtverců pomocí normálních rovnic nebo QR.\\+    * Rychlejší konvergence než JIM, ale sekvenční výpočet  
 +  - **Superrelaxační metoda (SOR)**: 
 +    * Zavádí relaxační parametr $\omega$ pro urychlení konvergence:\\ 
 +$\vec{x}^{(k+1)} = (D + \omega L)^{-1} \left[ (1-\omega)D \vec{x}^{(k)} - \omega U \vec{x}^{(k)} \right] + \omega (D + \omega L)^{-1} \vec{b}$ \\
  
-  * **Příklad řídké matice**: Iterační metoda (např. CG) pro řešení $Ax = b$, kde $A$ má jen $O(n)$ nenulových prvků.+    * Pro $\omega = 1$ přechází na GSM. Optimální $\omega$ zrychluje konvergenci, ale špatná volba způsobí divergenci 
  
-==== 6. Závěr ====+=== Problémy a kritéria volby metod ===
  
-  * **Finitní metody** jsou vhodné pro malé matice a přesné řešení.\\+  * **Problémy**: 
 +    * **Špatná podmíněnost**: Malé změny v $A$ nebo $\vec{b}$ vedou k velkým změnám řešení (kritérium: velké $\|A^{-1}\|$) \\
  
-  * **Iterační metody** dominují u velkých řídkých matic a při náročnosti na paměť.\\+    * **Zaokrouhlovací chyby**: Akumulují se v přímých metodách, zejména bez výběru hlavního prvku \\
  
-  * Výběr závisí na rozměru matice, její struktuře a požadované přesnosti. +    * **Konvergence iterací**: Zajištěna pouze pokud $\rho(B) < 1$ (spektrální poloměr iterační matice) \\
-===== Numerická integrace =====+
  
-**Numerická integrace - princip, možné problémy, volba metody, problematika odhadu chyb.**+    * **Řídké matice**: Přímé metody ztrácejí na efektivitě kvůli “zaplnění” (fill-in), iterační metody ji zachovávají  
 +  * **Volba metody**:
  
-==== Princip numerické integrace ====+^**Parametr**             ^**Přímé metody**               ^**Iterační metody**                       ^ 
 +|**Velikost matice**      |Malé až střední systémy        |Velké systémy ($n > 10^3$)                | 
 +|**Struktura matice**     |Plné nebo řídké                |Řídké (např. diskretizace PDE)            | 
 +|**Přesnost**             |Vysoká (teoreticky přesné)     |Přibližná (kontrola rezidua $\|\vec{r}\|$)| 
 +|**Vícenásobná $\vec{b}$**|Efektivní (jednorázový rozklad)|Výhodné s dobrým počátečním odhadem       | 
 +|**Paměťová náročnost**   |Vyšší (např. LU: $O(n^2)$)     |Nižší (např. JIM: $O(n)$)                 |
  
-Numerická integrace je postup přibližného výpočtu **definitního integrálu**\\ +=== Odhady chyb a optimalizace ===
-$$ +
-\int_{a}^{b} f(x) \, dx +
-$$\\ +
-pro případy, kdy analytická řešení (primitivní funkce) nelze získat nebo je výpočet složitý. Základní přístup spočívá v **discretizaci** intervalu $[a, b]$ a aproximaci integrálu pomocí **polynomů**, **geometrických útvarů** nebo **kvadraturních vzorců**.+
  
-==== Hlavní metody numerické integrace ====+  * **Reziduální odhad**: $\vec{r} = \vec{b} - A\vec{x}_c$ umožňuje zpřesnění řešení \\
  
-=== 1. Obdélníková metoda (Rectangle Rule) ===+  * **Složitost**: 
 +    * Přímé metody: $O(n^3)$ pro GEM, $O(n^2)$ pro zpětný chod.\\
  
-  * **Princip**: Rozdělí interval $[a, b]$ na $n$ podintervalů, v každém z nich integrand nahradí **konstantou** (hodnotou v levém, pravém nebo středním bodě).\\+    * Iterační metody: $O(n^2)$ na iteraci (pro husté matice), $O(n)$ pro řídké 
  
-  * **Formule**:\\ 
-$$ 
-\int_{a}^{b} f(x) \, dx \approx \frac{b - a}{n} \sum_{i=1}^{n} f(x_i) 
-$$\\ 
-kde $x_i$ je bod v $i$-tém podintervalu (např. střed = **střední metoda**).\\ 
  
-  * **Řád metody**: pro levé a pravé obdelníky: 1 (chyba je $O(h)$, kde $h = \frac{b-a}{n}$)., pro střední je řád 2 (chyba je $O(h^2)$) +===== Numerická integrace =====
- +
-  * **Výhody**: Jednoduchost, malá početní náročnost.\\+
  
-  * **Nevýhody**: Malá přesnost, nevhodné pro funkcí s rychlým zrychlením.+**Numerická integrace slouží k přibližnému výpočtu určitého integrálu, když analytické řešení není možné. Zahrnuje diskretizaci intervalu, výpočet ploch pod křivkou pomocí jednoduchých geometrických tvarů a řízení chyb.**
  
-=== 2. Lichoběžníková metoda (Trapezoidal Rule) ===+==== Metody numerické integrace ====
  
-  * **Princip**: Interval rozdělí na $n$ podintervalů, které aproximuje **lichoběžníky** (lineární interpolace).\\+  - **Metoda levých obdélníků** 
 +    * **Myšlenka:** Funkce se aproximuje hodnotou v **levém konci** každého podintervalu.\\
  
-  * **Formule**:\\+    * **Matematicky:** Pro interval $[a, b]$ rozdělený na $n$ podintervalů o šířce $h = \frac{b-a}{n}$:\\
 $$ $$
-\int_{a}^{b} f(x) \, dx \approx \frac{h}{2} \left[ f(a) + 2\sum_{i=1}^{n-1} f(x_i) + f(b) \right], \quad h = \frac{b - a}{n}+I_L = h \sum_{i=0}^{n-1} f(x_i), \quad x_i = a + i \cdot h.
 $$\\ $$\\
  
-  * **Řád metody**: 2 (chyba $O(h^2)$).\\+    * **Řád metody:** 1 (přesná pro polynomy stupně 0, např. konstantní funkce). 
 +  - **Metoda středních obdélníků** 
 +    * **Myšlenka:** Funkce se aproximuje hodnotou ve **středu** každého podintervalu.\\
  
-  * **Výhody**: Lépe přesná než obdélníková, stabilní pro hladké funkce.\\+    * **Matematicky:**\\ 
 +$$ 
 +I_S = h \sum_{i=0}^{n-1} f\left(x_i + \frac{h}{2}\right). 
 +$$\\
  
-  * **Nevýhody**: Chyba se zvětšuje pro funkce s velkými druhými derivacemi.+    * **Řád metody:** 2 (přesná pro lineární polynomy, např. $x^1$). 
 +  - **Lichoběžníková metoda (Trapezoid)** 
 +    * **Myšlenka:** Funkce se aproximuje **lineárně** mezi konci podintervalu (plocha lichoběžníku).\\
  
-=== 3. Simpsonova metoda (Simpson’s Rule) ===+    * **Matematicky:**\\ 
 +$$ 
 +I_T = \frac{h}{2} \left[ f(a) + 2 \sum_{i=1}^{n-1} f(x_i) + f(b) \right]. 
 +$$\\
  
-  * **Princip**: Užívá **parabolické interpolace** (kvadratické polynomy) na párových podintervalech.\\+    * **Řád metody:** 2 (přesná pro lineární polynomy). 
 +  - **Simpsonova metoda** 
 +    * **Myšlenka:** Funkce se aproximuje **kvadratickou** parabolou přes dvojice podintervalů.\\
  
-  * **Formule**:\\+    * **Matematicky (pro sudé $n$):**\\
 $$ $$
-\int_{a}^{b} f(x) \, dx \approx \frac{h}{3} \left[ f(a) + 4\sum_{i=1}^{n/2} f(x_{2i-1}) + 2\sum_{i=1}^{(n/2)-1} f(x_{2i}) + f(b) \right]+I_S = \frac{h}{3} \left[ f(a) + 4 \sum_{i=1,3,\dots}^{n-1} f(x_i) + 2 \sum_{i=2,4,\dots}^{n-2} f(x_i) + f(b) \right].
 $$\\ $$\\
-(vyžaduje sudé $n$).\\ 
  
-  * **Řád metody**: 4 (chyba $O(h^4)$).\\+    * **Řád metody:** 4 (přesná pro kubické polynomy, např. $x^3$). 
 +  - **Gaussova kvadratura** 
 +    * **Myšlenka:** Volí **optimální body a váhy** v intervalu $[-1, 1]$ pro maximální přesnost. Transformuje se na $[a, b]$.\\
  
-  * **Výhody**: Vysoká přesnost pro hladké funkce.\\+    * **Matematicky:** Pro $n$ bodů:\\ 
 +$$ 
 +I_G = \frac{b-a}{2} \sum_{i=1}^n w_i f\left( \frac{b-a}{2} t_i + \frac{a+b}{2} \right), 
 +$$\\ 
 +kde $t_i$ jsou kořeny Legendreových polynomů, $w_i$ odpovídající váhy.\\
  
-  * **Nevýhody**: Závislost na počtu podintervalů, složitější výpočet -> velmi pomalé.+    * **Řád metody:** $2n-1$ (pro $n$ bodů přesná pro polynomy stupně $\leq 2n-1$).
  
 === 4. Newton-Cotesovy vzorce === === 4. Newton-Cotesovy vzorce ===
Line 451: Line 414:
  
 ==== Problémy a optimalizace ==== ==== Problémy a optimalizace ====
 +  * **Problémy:** Numerické chyby (zaokrouhlovací, metody), singularity, oscilace funkce.\\
  
-=== 1. Odhad chyby a kompozitní metody ===+=== Metoda polovičního kroku a odhad chyby ===
  
-  * **Kompozice**: Rozdělení $[a, b]$ na $n$ podintervalů a aplikace metody na každý.\\ +  * **Princip:** Integrál $I_h$ se spočte s krokem $h$, pak s $h/2$ pro jemnější dělení. Chyba pro metodu řádu $p$ je:\\
- +
-  * **Chyba trapezoidální metody**:\\+
 $$ $$
-E \approx -\frac{(b - a)^3}{12n^2} f''(\xi), \quad \xi \in [a,b]+E_h \approx \frac{I_h - I_{h/2}}{2^p - 1}.
 $$\\ $$\\
  
-  * **Chyba Simpsonovy metody**:\\ +  * **Vylepšení integrálu:**\\
-$$ +
-E \approx -\frac{(b - a)^5}{180n^4} f^{(4)}(\xi)+
 $$ $$
 +I_{\text{lepšené}} = I_{h/2} + \frac{I_{h/2} - I_h}{2^p - 1}.
 +$$\\
  
-=== 2. Richardsonova extrapolace ===+  * **Souvislost s Richardsonovou extrapolací:** Tento postup je jejím speciálním případem. Kombinací výsledků pro různé $h$ eliminuje vedoucí člen chyby 
  
-Sloučení dvou odhadů s různými kroky $h$ a $h/2$ pro odstranění vedení v chybě.\\ +=== Řád metody === 
-- **Příklad**: U trapezoidální metody:\\ + 
-$$ +  * **Význam:** Udává, do jakého stupně polynomu metoda počítá integrál přesně. Např. metoda řádu 2 přesně integruje polynomy stupně $\leq 1$ (tj. $x^{1}$ a nižší).\\ 
-  I(h/2) = I(h) + \frac{E(h)}{4} \Rightarrow \text{vyšší řád} O(h^4) + 
-  $$+  * **Chyba metody:** Pro krok $h$ a řád $p$ je globální chyba $O(h^p)$. 
 + 
 + 
 +==== Řád chyby ==== 
 + 
 +  * **Definice:** Řád chyby $p$ znamená, že chyba metody klesá jako $h^p$ při zmenšování kroku $h$. 
 +  * **Příklad:** Pro metodu s řádem 2, zmenšení kroku $h$ na polovinu sníží chybu 4krát, protože $E \propto h^2$.
  
-=== 3. Adaptivní kvadratura ===+=== Adaptivní kvadratura ===
  
 Metody jako **Gauss-Kronrod** automaticky rozdělují intervaly podle lokálního chybového odhadu (lepší efektivita pro funkcí s různými charakteristikami). Metody jako **Gauss-Kronrod** automaticky rozdělují intervaly podle lokálního chybového odhadu (lepší efektivita pro funkcí s různými charakteristikami).
Line 500: Line 468:
 ==== Kritéria volby metody ==== ==== Kritéria volby metody ====
  
-  - **Hladkost funkce**: Pro funkce s velkými derivacemi preferovat metody s vysokým řádem (např. Simpsonova).\\ +  - **Hladkost funkce**: Pro funkce s velkými derivacemi preferovat metody s vysokým řádem (např. Simpsonova). 
- +  - **Interval délky**: Pro velké intervaly nebo singulární body použít adaptivní metody nebo substituci.
-  - **Interval délky**: Pro velké intervaly nebo singulární body použít adaptivní metody nebo substituci.\\ +
   - **Výpočetní náročnost**: Obdélníková je nejrychlejší, ale malá přesnost.   - **Výpočetní náročnost**: Obdélníková je nejrychlejší, ale malá přesnost.
  

Trace: • b0b36dbs

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b01num (generated for current page)