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 nahrazení složitých funkcí nebo datových množin jednoduššími funkcemi, s důrazem na interpolaci polynomy, spliny a metodu nejmenších čtverců. Volba metody závisí na charakteru dat a požadované přesnosti.

Aproximace funkcí slouží k nahrazení obtížně zpracovatelných funkcí (např. transcendentních) nebo diskrétních dat jednoduššími analytickými modely. Používá se v těchto situacích:
- Interpolace: Když požadujeme přesnou shodu s daty v uzlových bodech (např. rekonstrukce signálů, finanční modely).
- Aproximace: Když data obsahují šum nebo nepřesnosti a cílem je zachytit trend bez nutnosti průchodu všemi body (např. regresní analýza v experimentálních vědách) .

1. Interpolace polynomy
   • Polynom stupně $n-1$ prochází přesně $n$ bodů.
     

• Výhody: Snadná derivace/integrace, univerzální použití (Weierstrassova věta) .
  

• Nevýhody: Oscilace pro vysoký počet bodů, nevhodná pro data s nespojitostmi.
  

• Formy:
  • Lagrangeova: $\phi(t) = \sum_{j} y_j \prod_{i \neq j} \frac{t - x_i}{x_j - x_i}$.
    

• Newtonova: Používá dělené diference pro postupné přidávání bodů .

1. Splinová interpolace

• Kubické spliny: Po částech polynomy 3. stupně spojené v uzlech s podmínkami hladkosti (spojitost 1. a 2. derivace).
  

• Výhody: Eliminuje oscilace, vhodná pro větší počet bodů .
  

• Nevýhody: Vyšší výpočetní náročnost.

• Minimalizuje součet čtverců odchylek $\sum_i (y_i - \phi(x_i))^2$.
  

• Použití: Pro data se šumem, kdy stačí přibližný trend (např. kalibrace senzorů) .
  

• Implementace: Řešení soustavy lineárních rovnic pro koeficienty bázových funkcí.

1. Počet a rozložení dat:
   • Malý počet bodů $\rightarrow$ polynomiální interpolace.
     

• Větší počet bodů $\rightarrow$ spliny (zamezení oscilacím).
  

1. Přesnost požadavků:
   • Přesná shoda v bodech $\rightarrow$ interpolace.
     

• Toleruje odchylky $\rightarrow$ metoda nejmenších čtverců .
  

1. Charakter dat:
   • Hladká data $\rightarrow$ polynomy/spliny.
     

• Šum nebo odlehlé hodnoty $\rightarrow$ metoda nejmenších čtverců.
  

1. Výpočetní náročnost:
   • Polynomy: Rychlé pro malé $n$.
     

• Spliny a MNČ: Náročnější, ale stabilnější pro reálná data .

• Interpolace: Modelování přesné teplotní křivky z měření v pevných časech .
  

• Aproximace MNČ: Předpověď budoucích hodnot akcií z historických dat s chybami .

Lagrangeova interpolace vyjadřuje výsledný polynom jako lineární kombinaci bazických polynomů: $$ \phi(x) = \sum_{j=0}^{n-1} y_j \prod_{\substack{0 \le m \le n-1 \\ m\neq j}} \frac{x - x_m}{x_j - x_m}. $$ Každý bazický polynom je stupně n−1 a zajišťuje, že $\phi(x_j)=y_j$.

Newtonova interpolace používá tzv. dělené diference k postupné konstrukci polynomu. Výhodou je jednodušší aktualizace při přidání nového bodu.

Dělené diference definujeme rekurzivně: $$ f[x_i] = y_i,\quad f[x_i,x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1}-x_i},\quad f[x_i,x_{i+1},x_{i+2}] = \frac{f[x_{i+1},x_{i+2}] - f[x_i,x_{i+1}]}{x_{i+2}-x_i},\;\dots $$ V tabulce rozdílných diferencí najdeme koeficienty pro konstrukci polynomu.

Polynom se pak zapíše jako: $$ \phi(x) = f[x_0] + f[x_0,x_1](x-x_0) * f[x_0,x_1,x_2](x-x_0)(x-x_1) + \dots + f[x_0,\dots,x_{n-1}]\prod_{i=0}^{n-2}(x-x_i). $$ Poslední člen má stupeň n−1.

• Efektivita výpočtu tabulky v $\mathcal O(n^2)$ a vyhodnocení $\phi(x)$ v $\mathcal O(n)$.
• Snadné přidání nového bodu – doplníme jeden sloupec a člen, bez přepočtu celého polynomu.
• Lepší numerická stabilita než přímá Lagrangeova forma při větším $n$.

Spliny jsou lokálně definované polynomy spojité až do druhé derivace. Nejčastěji se používá kubický spline (stupně 3).

Máme n datových bodů, mezi kterými je n−1 sousedních intervalů $[x_i,x_{i+1}]$. Na každém intervalu definujeme polynom stupně 3: $$ s_i(x) = a_i + b_i(x-x_i) + c_i(x-x_i)^2 + d_i(x-x_i)^3,\quad x\in[x_i,x_{i+1}]. $$ Celkem tedy sestavujeme n−1 kubických polynomů. Podmínky:

• $s_i(x_i)=y_i$ a $s_i(x_{i+1})=y_{i+1}$ (interpolace).
• Spojitost první a druhé derivace:
  • $s_i'(x_{i+1})=s_{i+1}'(x_{i+1})$,
  • $s_i''(x_{i+1})=s_{i+1}''(x_{i+1})$.
• Hraniční podmínky (např. „přírodní“ spline: $s_0''(x_0)=0$ a $s_{n-2}''(x_{n-1})=0$).

Kubický spline tak zaručuje hladké proložení bez ostrých zlomenin.

Pro interpolaci teplotních dat je kubický spline ideální, protože:

• zachovává lokální variabilitu,
• zaručuje spojitost až do druhé derivace,
• při přidání bodu se mění pouze koeficienty v sousedních intervalech.

Používá se, když data obsahují šum a hledáme optimální přizpůsobení funkce.

Hledáme aproximaci $$ \phi(x) = \sum_{i=1}^m a_i\varphi_i(x), $$ kde koeficienty $a_i$ minimalizují $$ \sum_{j=1}^N\bigl(f(x_j)-\phi(x_j)\bigr)^2. $$ Řešíme tak soustavu normálních rovnic.

Pro polynomy stupně 3 ($\varphi_i(x)=x^{i-1}$) se řeší 4×4 soustava pro koeficienty $a_1,\dots,a_4$.

Volba závisí na typu dat a požadavcích:

• Interpolace polynomem – pro přesná data a menší počet uzlů.
• Spliny – pro větší sady dat, kde požadujeme hladkost.
• Metoda nejmenších čtverců – pro šumová data a robustní aproximaci.

Aproximace funkcí vyžaduje zvážit počet dat, přesnost a hladkost výsledné funkce. Každá metoda má své výhody a nevýhody podle konkrétní aplikace.

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.