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.

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

1. Rozklad $A = D + L + U$ ($D$ diagonální, $L$ ostře dolní, $U$ ostře horní trojúhelníková).
2. Iterační vzorec: $\vec{x}^{(k+1)} = D^{-1} \left( \vec{b} - (L + U) \vec{x}^{(k)} \right)$
3. Jednoduchá implementace, paralelizovatelná, ale pomalá konvergence

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

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

1. Metoda levých obdélníků

• Myšlenka: Funkce se aproximuje hodnotou v levém konci každého podintervalu.
• Matematicky: Pro interval $[a, b]$ rozdělený na $n$ podintervalů o šířce $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: 1 (přesná pro polynomy stupně 0, např. konstantní funkce).

2. Metoda středních obdélníků

• Myšlenka: Funkce se aproximuje hodnotou ve středu každého podintervalu.
• Matematicky:

$$ I_S = h \sum_{i=0}^{n-1} f\left(x_i + \frac{h}{2}\right). $$

• Řád metody: 2 (přesná pro lineární polynomy, např. $x^1$).

3. Lichoběžníková metoda (Trapezoid)

• Myšlenka: Funkce se aproximuje lineárně mezi konci podintervalu (plocha lichoběžníku).
• Matematicky:

$$ I_T = \frac{h}{2} \left[ f(a) + 2 \sum_{i=1}^{n-1} f(x_i) + f(b) \right]. $$

• Řád metody: 2 (přesná pro lineární polynomy).

4. Simpsonova metoda

• Myšlenka: Funkce se aproximuje kvadratickou parabolou přes dvojice podintervalů.
• Matematicky (pro sudé $n$):

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

• Řád metody: 4 (přesná pro kubické polynomy, např. $x^3$).

5. 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]$.
• 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.

• Řád metody: $2n-1$ (pro $n$ bodů přesná pro polynomy stupně $\leq 2n-1$).

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: Numerické chyby (zaokrouhlovací, metody), singularity, oscilace funkce.
  

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

$$ E_{1/2} \approx \frac{I_{h/2} - I_h}{2^p - 1}. $$

• Vylepšení integrálu:
  

$$ I_{\text{vylepšené}} = I_{h/2} + E_{1/2}. $$

• 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

• 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žší).
  

• Chyba metody: Pro krok $h$ a řád $p$ je globální chyba $O(h^p)$.

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

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).
2. Interval délky: Pro velké intervaly nebo singulární body použít adaptivní metody nebo substituci.
3. 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.