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 numerických algoritmů. POZOR AI generated z pdf zdrojů (dochází čas lol)

Řá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.

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

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ů

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

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.

• 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

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

• 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)

• 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

• 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

• 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)

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

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 ,

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:

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:

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:

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:

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

1. Analýza funkce:
   • Tabulace hodnot, hledání intervalů se znaménkovou změnou
     

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

1. 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
  

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

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.

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.

1. LU rozklad:
   • Rozklad $A = LU$ na dolní ($L$) a horní ($U$) trojúhelníkovou matici.
     

• Řeší se dvě soustavy:
  • $L\vec{y} = \vec{b}$ (dopředná substituce),
    

• $U\vec{x} = \vec{y}$ (zpětná substituce).
  

• Efektivní pro opakované výpočty s různými $\vec{b}$

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

1. 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)$

• Rychlejší konvergence než JIM, ale sekvenční výpočet

1. 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}$

• Pro $\omega = 1$ přechází na GSM. Optimální $\omega$ zrychluje konvergenci, ale špatná volba způsobí divergenci

• 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}\|$)
    

• Zaokrouhlovací chyby: Akumulují se v přímých metodách, zejména bez výběru hlavního prvku
  

• Konvergence iterací: Zajištěna pouze pokud $\rho(B) < 1$ (spektrální poloměr iterační matice)
  

• Řídké matice: Přímé metody ztrácejí na efektivitě kvůli “zaplnění” (fill-in), iterační metody ji zachovávají
• Volba metody:

• Reziduální odhad: $\vec{r} = \vec{b} - A\vec{x}_c$ umožňuje zpřesnění řešení
  

• Složitost:
  • Přímé metody: $O(n^3)$ pro GEM, $O(n^2)$ pro zpětný chod.
    

• Iterační metody: $O(n^2)$ na iteraci (pro husté matice), $O(n)$ pro řídké

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

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ů.

• 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.

• 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.

• 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é.

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ů).

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

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

Metody jako Gauss-Kronrod automaticky rozdělují intervaly podle lokálního chybového odhadu (lepší efektivita pro funkcí s různými charakteristikami).

• 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 $$

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

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

1. Hladkost funkce: Pro funkce s velkými derivacemi preferovat metody s vysokým řádem (např. Simpsonova).
   

1. Interval délky: Pro velké intervaly nebo singulární body použít adaptivní metody nebo substituci.
   

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

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$.

• 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.