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)

Numerické řešení soustav lineárních rovnic, možné problémy, argumenty pro použití finitních nebo iteračních metod.

• Příklady: Gaussova eliminační metoda, LU dekompozice, QR rozklad.
  

• Výhody:
  • Pro malé a střední matice (např. $n < 1000$) jsou efektivní.
    

• Přesné řešení (do chyby zaokrouhlení) v konečném počtu kroků.
  

• Problémy:
  • 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í.
  

• Paměťové nároky: Ukládání celé matice (i pro řídké matice).
  

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

• Příklady: Jacobiho metoda, Gaussova-Seidelova metoda, metoda konjugovaných gradientů (pro symetrické pozitivně definitní matice).
  

• Výhody:
  • Efektivní pro velké řídké matice (např. $n > 10^4$), protože využívají jen operace s nenulovými prvky.
    

• Nižší paměťové nároky (neukládá se celá matice, jen její struktura).
  

• Problémy:
  • Konvergence není zaručena: Závisí na vlastnostech matice (např. diagonální dominance, pozitivní definitnost).
    

• Pomalá konvergence bez předpodmínky (preconditioner).
  

• Citlivost na volbu počátečního odhadu.
• 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).

• Špatně podmíněné matice: Malá nebo nulová determinant, velké chyby v řešení.
  

• Numerická nestabilita: Např. v Gaussově eliminaci bez pivotace.
  

• Chyby zaokrouhlení: Akumulace v přímých metodách pro velké $n$.
  

• Řídké matice: Iterační metody výrazně převyšují přímé metody.

• Přeurčená soustava $Ax = b$: Řešeno metodou nejmenších čtverců pomocí normálních rovnic nebo QR.
  

• Příklad řídké matice: Iterační metoda (např. CG) pro řešení $Ax = b$, kde $A$ má jen $O(n)$ nenulových prvků.

• Finitní metody jsou vhodné pro malé matice a přesné řešení.
  

• Iterační metody dominují u velkých řídkých matic a při náročnosti na paměť.
  

• Výběr závisí na rozměru matice, její struktuře a požadované přesnosti.

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.