statnice:bakalar:b4b01num

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Aproximace funkcí. Chyby numerických algoritmů, řešení rovnic a výpočtu integračních ======
  * Zdroje chyb numerických algoritmů.
  * Aproximace funkcí: interpolace polynomy a spliny, metoda nejmenších čtverců. Volba aproximace metody.
  * Numerické metody řešení (jedné) nelineární rovnice, problematika separace kořenů.
  * Numerické řešení soustav lineárních rovnic, možné problémy, argumenty pro použití finitních nebo iteračních metod.
  * Numerická integrace - princip, možné problémy, volba metody, problematika odhadu chyb.

===== Zdroje chyb =====
**Zdroje chyb numerických algoritmů.**
__POZOR AI generated z pdf zdrojů (dochází čas lol)__
==== Řád chyby ====
Řád chyby je jak rychle chyba v numerické metody klesá se zmenšujícím se krokem -> čím výšší řád chyby tím rychleji se chyba zmenšuje s menším dělením, nebo více samplovacími body.
==== Modelová chyba ====
<markdown>
Vzniká při aproximaci skutečného systému matematickým modelem. Například:
- Při odstranění maličkých efektů v fyzikálních rovnicích
- Při zjednodušení složitých procesů pro jejich řešení
- V ekonomických modelech s předpokladem lineárního chování
- V mechanice se zanedbáním vzdušného odporu
</markdown>

==== Diskretizační chyba ====
<markdown>
Vzniká při přepisu spojité úlohy do diskrétního prostoru:
- Při numerickém integrování (Simpsonovo pravidlo)
- V metodě konečných prvků pro řešení diferenciálních rovnic
- Při aproximaci derivace pomocí diferenčních vzorců
</markdown>

==== Chyba zaokrouhlení ====
<markdown>
Vzniká kvůli omezené přesnosti počítačové aritmetiky (floating point čísla):
- Při sčítání velkých a malých čísel
- V iterativních metodách pro řešení soustav rovnic
- Při výpočtu velkých mocnin nebo exponentiály
</markdown>


==== Kombinace chyb ====
<markdown>
Pro optimální výsledek musí být diskretizační chyba stejně velká nebo větší než chyba zaokrouhlení. Pokud není, nepřinese to zlepšení přesnosti.
</markdown>

==== Klíčové postřehy ====
<markdown>
- **Tichonovova regularizace**: Technika užitá pro řešení nestabilních úloh (např. neúplně určených soustav rovnic). Pomáhá omezit vliv velké chyby na koncový výsledek.
- Iterativní metody mohou amplifikovat chyby ze každého kroku
- Stabilita algoritmu znamená, že limituje chyby zaokrouhlení a jejich akumulaci
</markdown>

===== Aproximace funkcí =====
**Interpolace polynomy, splinová interpolace a metoda nejmenších čtverců. Kritéria pro výběr metody.**


**Metody pro nalezení funkce vhodně reprezentující daná data, rozdělené na interpolaci (přesný průchod body) a aproximaci (minimalizace chyby).**

==== Rozlišení interpolace a aproximace ====

  * **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 ====

  * **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 

==== Splinová interpolace ====

  * **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)$,\\
kde $\eta_i, \varrho_i, \sigma_i, \tau_i$ jsou kubické polynomy 
  * **Podmínky**:
    * 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$ 
  * **Výhody**: Minimalizace oscilací, odolnost vůči lokálním změnám 

==== Metoda nejmenších čtverců ====

  * **Definice**: Minimalizuje součet čtverců odchylek $\min \sum_{i=0}^{n-1} (\phi(x_i) - y_i)^2$ 
  * **Matematický popis**:\\
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$ 
  * **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 ====

  - **Počet bodů**:
    * $n \leq 15$: Polynomiální interpolace 
    * $n > 15$: Spliny nebo nejmenší čtverce 
  - **Požadovaná přesnost**:
    * Exaktní shoda: Interpolace 
    * Tolerovatelná chyba: Nejmenší čtverce 
  - **Charakter dat**:
    * Periodická data: Goniometrický polynom + FFT 
    * Nespojitosti/hrany: Spliny 
  - **Výpočetní náročnost**:
    * Rychlé vyhodnocení: Lineární/lokální spliny 
    * Optimalizace: Ortogonální báze (Čebyševovy polynomy) 

<tikzjax>
\usepackage{amsmath}
\usepackage{pgfplots}
\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta}
\begin{document}

% 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)$};




% Spline interpolation (blue)
\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);

% Least squares (green)
\draw[green, thick, domain=0.8:7.5] plot (\x, {0.4*\x + 0.2});

% Legend
\node at (4,-1.5) {Legenda:};
\draw[blue, thick] (3,-2.5) -- (4,-2.5) node[right]{Spline};
\draw[green, thick] (3,-3) -- (4,-3) node[right]{Nejmenší čtverce};

\end{tikzpicture}

\end{document}
</tikzjax>

===== Numerické metody řešení nelineárních rovnic =====


**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 , 

==== Přehled 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                                   |




==== 1. Metoda půlení intervalu (Bisekce) ====

**Matematický princip**:\\
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>
\usepackage{amsmath}
\usepackage{pgfplots}
\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta}
\begin{document}
\begin{tikzpicture}[thick,xscale=1,yscale=1]
  % Axes
  \draw[->] (0,0) -- (5,0) node[right] {$x$};
  \draw[->] (0,-1) -- (0,4) node[above] {$f(x)$};

  % Function (example cubic)
  \draw[domain=0.5:4.5,smooth,variable=\x,blue]
    plot ({\x},{0.1*(\x-3)^3 + 0.5});

  % Endpoints a=1, b=4
  \foreach \X/\lbl in {1/a,4/b}{
    \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);
  }

  % Midpoint c = (a+b)/2 = 2.5
  \coordinate (C) at (2.5,{0.1*(2.5-3)^3+0.5});
  \draw[dashed] (2.5,0) node[below] {$c$} -- (C);
  \fill (C) circle (1.5pt);
\end{tikzpicture}

\end{document}
</tikzjax>



==== 2. Newtonova metoda ====

**Matematický princip**:\\
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**:

{{:statnice:bakalar:pasted:20250607-125539.png?490}}



==== 3. Metoda sečen ====

**Matematický princip**:\\
Aproximace derivace:\\
$$
x_{i+1} = x_i - f(x_i) \cdot \frac{x_i - x_{i-1}}{f(x_i) - f(x_{i-1})}
$$\\
**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**:

{{:statnice:bakalar:pasted:20250607-125807.png?400}}




==== 4. Regula falsi ====

**Matematický princip**:\\
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**:

<tikzjax>
\usepackage{amsmath}
\usepackage{pgfplots}
\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta}
\begin{document}

\begin{tikzpicture}[thick, xscale=1, yscale=1]
  % Axes
  \draw[->] (0,0) -- (5,0) node[right]{$x$};
  \draw[->] (0,-1) -- (0,4) node[above]{$f(x)$};

  % Plot f
  \draw[name path=function,blue,smooth,domain=1:4]
    plot (\x,{0.1*(\x-3)^3+0.5});

  % Points A and B
  \coordinate (A) at (1,{0.1*(1-3)^3+0.5});
  \coordinate (B) at (4,{0.1*(4-3)^3+0.5});
  \fill (A) circle (1.5pt) (B) circle (1.5pt);

  % Secant AB
  \draw[name path=secant,red] (A) -- (B);

  % Intersection C = false-position
  \draw[name intersections={of=secant and function, by=C}];
  \draw[dashed] (C) -- (C|-0,0) node[below]{$c$};
  \fill (C) circle (1.5pt);
\end{tikzpicture}

\end{document}
</tikzjax>



==== 5. Metoda prosté iterace ====

**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):

<tikzjax>
\usepackage{amsmath}
\usepackage{pgfplots}
\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta}
\begin{document}
\begin{tikzpicture}[thick,xscale=1,yscale=1]
  % Axes
  \draw[->] (0,0) -- (4,0) node[right]{$x$};
  \draw[->] (0,0) -- (0,4) node[above]{$y$};

  % y = g(x) and y = x
  \draw[blue,smooth,domain=0:4]
    plot (\x,{1+0.5*(\x-1)}) node[above]{$y=g(x)$};
  \draw[black,domain=0:4] plot (\x,\x) node[right]{$y=x$};

  % One cobweb iteration from x0=1
  \coordinate (P0) at (1,0);
  \coordinate (P1) at (1,{1+0.5*(1-1)});
  \coordinate (P2) at ({1+0.5*(1-1)},{1+0.5*(1-1)});
  \draw[dashed] (P0) -- (P1) -- (P2);
  \fill (P1) circle (1.5pt) (P2) circle (1.5pt);
\end{tikzpicture}

\end{document}
</tikzjax>



==== Problematika separace kořenů ====

  - **Analýza funkce**:
    * Tabulace hodnot, hledání intervalů se znaménkovou změnou\\

    * Studium derivací pro monotonii ($f'(x) > 0$ → rostoucí)\\

  - **Problémy**:
    * Násobné kořeny (např. $f(x) = (x-2)^2$): $f(a) \cdot f(b) < 0$ neplatí\\

    * Řešení: Transformace $h(x) = \frac{f(x)}{f'(x)}$ redukuje násobnost \\

  - **Kritické případy**:
    * Nespojitosti, periodické funkce – vyžadují speciální algoritmy (např. kombinace s derivacemi) 

===== 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.**



===== Numerická integrace =====

**Numerická integrace - princip, možné problémy, volba metody, problematika odhadu chyb.**

==== Princip numerické integrace ====

Numerická integrace je postup přibližného výpočtu **definitního integrálu**\\
$$
\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 ====

=== 1. Obdélníková metoda (Rectangle Rule) ===

  * **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ě).\\

  * **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)$)

  * **Výhody**: Jednoduchost, malá početní náročnost.\\

  * **Nevýhody**: Malá přesnost, nevhodné pro funkcí s rychlým zrychlením.

=== 2. Lichoběžníková metoda (Trapezoidal Rule) ===

  * **Princip**: Interval rozdělí na $n$ podintervalů, které aproximuje **lichoběžníky** (lineární interpolace).\\

  * **Formule**:\\
$$
\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}
$$\\

  * **Řád metody**: 2 (chyba $O(h^2)$).\\

  * **Výhody**: Lépe přesná než obdélníková, stabilní pro hladké funkce.\\

  * **Nevýhody**: Chyba se zvětšuje pro funkce s velkými druhými derivacemi.

=== 3. Simpsonova metoda (Simpson’s Rule) ===

  * **Princip**: Užívá **parabolické interpolace** (kvadratické polynomy) na párových podintervalech.\\

  * **Formule**:\\
$$
\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]
$$\\
(vyžaduje sudé $n$).\\

  * **Řád metody**: 4 (chyba $O(h^4)$).\\

  * **Výhody**: Vysoká přesnost pro hladké funkce.\\

  * **Nevýhody**: Závislost na počtu podintervalů, složitější výpočet -> velmi pomalé.

=== 4. Newton-Cotesovy vzorce ===

Soubor metod, které zobecňují trapezoidální a Simpsonovu metodu.\\
- **Vzorce**:\\
$$
  \int_{a}^{b} f(x) \, dx \approx \sum_{i=0}^{n} w_i f(x_i)
  $$\\
kde $w_i$ jsou váhy závislé na počtu uzlů $n+1$.\\
- **Problém**: Pro $\ge 8$ uzlů nastává **Rungeova fenoména** (oscilace interpolujících polynomů).

==== Problémy a optimalizace ====

=== 1. Odhad chyby a kompozitní metody ===

  * **Kompozice**: Rozdělení $[a, b]$ na $n$ podintervalů a aplikace metody na každý.\\

  * **Chyba trapezoidální metody**:\\
$$
E \approx -\frac{(b - a)^3}{12n^2} f''(\xi), \quad \xi \in [a,b]
$$\\

  * **Chyba Simpsonovy metody**:\\
$$
E \approx -\frac{(b - a)^5}{180n^4} f^{(4)}(\xi)
$$

=== 2. Richardsonova extrapolace ===

Sloučení dvou odhadů s různými kroky $h$ a $h/2$ pro odstranění vedení v chybě.\\
- **Příklad**: U trapezoidální metody:\\
$$
  I(h/2) = I(h) + \frac{E(h)}{4} \Rightarrow \text{vyšší řád} O(h^4)
  $$

=== 3. 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).

==== Integrace v nekonečném intervalu ====

=== 1. Substituce změny proměnné ===

  * **Příklad 1**: Pro $\int_{a}^{\infty} f(x) \, dx$:\\
$$
x = \frac{a}{1 - t}, \quad t \in [0,1] \Rightarrow dx = \frac{a}{(1 - t)^2} dt
$$\\

  * **Příklad 2**: Pro $\int_{-\infty}^{\infty} f(x) \, dx$:\\
$$
x = \tan(t), \quad t \in (-\pi/2, \pi/2) \Rightarrow dx = \sec^2(t) dt
$$

=== 2. Speciální kvadratury ===

  * **Gauss-Laguerre**: Pro $\int_{0}^{\infty} e^{-x} f(x) \, dx$.\\

  * **Gauss-Hermite**: Pro $\int_{-\infty}^{\infty} e^{-x^2} f(x) \, dx$.

==== Kritéria volby metody ====

  - **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.\\

  - **Výpočetní náročnost**: Obdélníková je nejrychlejší, ale malá přesnost.

==== Příklad aplikace ====

**Vypočtěte** $\int_{0}^{1} e^{-x^2} dx$ s přesností $10^{-4}$ pomocí trapezoidální metody:\\
1. Odhad chyby:\\
$$
   \left| E \right| \leq \frac{(1-0)^3}{12n^2} \max |f''(x)| \Rightarrow \max |f''(x)| = \max |4x^2 - 2| e^{-x^2} \approx 2 \text{ na } [0,1]
   $$\\
2. Vyžaduje $n \approx \sqrt{2/(12 \cdot 10^{-4})} \approx 37$.

==== Souhrn ====

  * **Vysoký řád** (Simpson) vs. **efektivita** (adaptivní metody).\\

  * Pro **nekonečné intervaly** používejte substituce nebo specializované kvadratury.\\

  * **Chyba** je klíčová pro optimalizaci výpočtu.

**Poznámka**: Pro reálné problémy doporučuje se použít numerické knihovny (např. ''%%scipy.quad%%''), které kombinují různé metody a optimalizují chybu automaticky.
Trace: • b0b35apo • b4b01num • b4b36pdv • b0b36pjv • b4b35osy • b0b33opt • b4b39iur • b4b01dma • b4b36fup • b0b01lgr
Search

Navigation

Print/export

Tools

QR Code
