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)

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.

• 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:
  • 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 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:
  • 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:
  • Používá lineární interpolaci

• 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

• Globální chybová odhada (např. pro metodu bisekce):
  • $|e_k| \leq \frac{b - a}{2^k}$

• Lokální chybová odhada:
  • Pro Newtonovu metodu: $|x_{k+1} - r| \approx C|x_k - r|^2$
  • Pro jednoduchou iteraci: $|e_{k+1}| \leq L|e_k|$

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

V praxi je důležité:

• Ochránit proti odklonu (divergence)
• Využít vhodného zaokrouhlení
• Počítat s numerickou nestabilitou
• Používat adaptivní kroky pro efektivitu

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.

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.