The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b01num [2025/06/07 12:54] – mistrjirkastatnice:bakalar:b4b01num [2025/06/07 13:38] (current) – [Numerická integrace] mistrjirka
Line 218: Line 218:
 **Visualizace**: **Visualizace**:
  
-<tikzjax> +{{:statnice:bakalar:pasted:20250607-125539.png?490}}
-\usepackage{amsmath} +
-\usepackage{pgfplots} +
-\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} +
-\begin{document} +
- +
-\begin{tikzpicture}[thick,yscale=0.8] +
-% Axes +
-  \draw[-latex,name path=xaxis] (-1,0) -- (12,0) node[above]{\large $x$}; +
-  \draw[-latex] (0,-2) -- (0,8) node[right]{\large $y$}; +
- +
-  % Function plot +
-  \draw[ultra thick, orange,name path=function] +
-    plot[smooth,domain=1:9.5] +
-      (\x, {0.1*\x^2 - 1.5}) node[left]{$F(x)$}; +
- +
-  % Tangent at x^(k)=8 +
-  \node[violet,right=0.2cm] at (8,4.9) {\large tangent}; +
-  \draw[gray,thin,dotted] (8,0) -- (8,4.9) +
-    node[circle,fill,inner sep=2pt]{}; +
-  \draw[dashed, violet,name path=Tfunction] +
-    plot[smooth,domain=4.25:9.5] +
-      (\x, {1.6*\x - 7.9}); +
- +
-  % Labels for x^(k) and x^(k+1) +
-  \draw (8,0.1) -- (8,-0.1) node[below] {$x^{(k)}$}; +
-  \draw [name intersections={of=Tfunction and xaxis}] +
-    ($(intersection-1)+(0,0.1)$) -- ++(0,-0.2) +
-    node[below,fill=white] {$x^{(k+1)}$}; +
-\end{tikzpicture} +
- +
-\end{document} +
-</tikzjax>+
  
  
Line 264: Line 232:
 **Visualizace**: **Visualizace**:
  
-<tikzjax> +{{:statnice:bakalar:pasted:20250607-125807.png?450}}
-\usepackage{amsmath} +
-\usepackage{pgfplots} +
-\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} +
-\begin{document} +
- +
-\begin{tikzpicture}[thick, xscale=1, yscale=1] +
-  % Axes +
-  \draw[->] (0,0) -- (5,0) node[right]{$x$}; +
-  \draw[->] (0,-1) -- (0,4) node[above]{$f(x)$}; +
- +
-  % Function +
-  \draw[blue,smooth,domain=0.5:4.5] plot (\x,{0.1*(\x-3)^3+0.5}); +
- +
-  % Initial guesses x0=0.5, x1=1.5 +
-  \coordinate (X0) at (0.5,{0.1*(0.5-3)^3+0.5}); +
-  \coordinate (X1) at (1.5,{0.1*(1.5-3)^3+0.5}); +
-  \fill (X0) circle (1.5pt) (X1) circle (1.5pt); +
- +
-  % Secant line +
-  \draw[red,name path=sec] (X0) -- (X1); +
- +
-  % Intersection X2 with f +
-  \draw[name path=fun2] plot [smooth,domain=0.5:4.5] +
-    (\x,{0.1*(\x-3)^3+0.5}); +
-  \draw[name intersections={of=sec and fun2,by=X2}]; +
-  \draw[dashed] (X2) -- (X2|-0,0) node[below]{$x_2$}; +
-  \fill (X2) circle (1.5pt); +
-\end{tikzpicture}+
  
-\end{document} 
-</tikzjax> 
  
  
Line 308: Line 246:
 **Konvergence**: Lineární při zachování intervalu s kořenem \\ **Konvergence**: Lineární při zachování intervalu s kořenem \\
 **Visualizace**: **Visualizace**:
- 
-<tikzjax> 
-\usepackage{amsmath} 
-\usepackage{pgfplots} 
-\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} 
-\begin{document} 
- 
-\begin{tikzpicture}[thick, xscale=1, yscale=1] 
-  % Axes 
-  \draw[->] (0,0) -- (5,0) node[right]{$x$}; 
-  \draw[->] (0,-1) -- (0,4) node[above]{$f(x)$}; 
- 
-  % Plot f 
-  \draw[name path=function,blue,smooth,domain=1:4] 
-    plot (\x,{0.1*(\x-3)^3+0.5}); 
- 
-  % Points A and B 
-  \coordinate (A) at (1,{0.1*(1-3)^3+0.5}); 
-  \coordinate (B) at (4,{0.1*(4-3)^3+0.5}); 
-  \fill (A) circle (1.5pt) (B) circle (1.5pt); 
- 
-  % Secant AB 
-  \draw[name path=secant,red] (A) -- (B); 
- 
-  % Intersection C = false-position 
-  \draw[name intersections={of=secant and function, by=C}]; 
-  \draw[dashed] (C) -- (C|-0,0) node[below]{$c$}; 
-  \fill (C) circle (1.5pt); 
-\end{tikzpicture} 
- 
-\end{document} 
-</tikzjax> 
  
  
 +{{:statnice:bakalar:pasted:20250607-130029.png?450}}
  
 ==== 5. Metoda prosté iterace ==== ==== 5. Metoda prosté iterace ====
Line 352: Line 259:
 **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$ \\ **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): **Visualizace** (Cobweb diagram):
- 
-<tikzjax> 
-\usepackage{amsmath} 
-\usepackage{pgfplots} 
-\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} 
-\begin{document} 
-\begin{tikzpicture}[thick,xscale=1,yscale=1] 
-  % Axes 
-  \draw[->] (0,0) -- (4,0) node[right]{$x$}; 
-  \draw[->] (0,0) -- (0,4) node[above]{$y$}; 
- 
-  % y = g(x) and y = x 
-  \draw[blue,smooth,domain=0:4] 
-    plot (\x,{1+0.5*(\x-1)}) node[above]{$y=g(x)$}; 
-  \draw[black,domain=0:4] plot (\x,\x) node[right]{$y=x$}; 
- 
-  % One cobweb iteration from x0=1 
-  \coordinate (P0) at (1,0); 
-  \coordinate (P1) at (1,{1+0.5*(1-1)}); 
-  \coordinate (P2) at ({1+0.5*(1-1)},{1+0.5*(1-1)}); 
-  \draw[dashed] (P0) -- (P1) -- (P2); 
-  \fill (P1) circle (1.5pt) (P2) circle (1.5pt); 
-\end{tikzpicture} 
- 
-\end{document} 
-</tikzjax> 
- 
  
  
 +{{:statnice:bakalar:pasted:20250607-130215.png?450}}
 ==== Problematika separace kořenů ==== ==== Problematika separace kořenů ====
  
Line 396: Line 277:
     * Nespojitosti, periodické funkce – vyžadují speciální algoritmy (např. kombinace s derivacemi)      * Nespojitosti, periodické funkce – vyžadují speciální algoritmy (např. kombinace s derivacemi) 
  
-===== Numerické řešení soustav lineárních rovnic =====+==== Numerické řešení soustav lineárních rovnic ====
  
-**Numerické řešení soustav lineárních rovnic, možné problémy, argumenty pro použití finitních nebo iteračních metod.**+**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.**
  
 +=== Přímé (finitní) metody ===
  
 +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.
  
-===== Numerická integrace =====+  - **LU rozklad**: 
 +    * Rozklad $A = LU$ na **dolní ($L$)** a **horní ($U$) trojúhelníkovou matici**.\\
  
-**Numerická integrace - princip, možné problémy, volba metody, problematika odhadu chyb.**+    * Řeší se dvě soustavy: 
 +      * $L\vec{y} = \vec{b}$ (dopředná substituce),\\
  
-==== Princip numerické integrace ====+      * $U\vec{x} = \vec{y}$ (zpětná substituce).\\
  
-Numerická integrace je postup přibližného výpočtu **definitního integrálu**\\ +    * Efektivní pro opakované výpočty s různými $\vec{b}$ 
-$$ +
-\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ů**.+
  
-==== Hlavní metody numerické integrace ====+=== Iterační metody ===
  
-=== 1. Obdélníková metoda (Rectangle Rule) ===+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 
  
-  * **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ě).\\+  - **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)$ \\
  
-  * **Formule**:\\ +    * Rychlejší konvergence než JIM, ale sekvenční výpočet  
-$$ +  - **Superrelaxační metoda (SOR)**: 
-\int_{a}^{b} f(x) \, dx \approx \frac{b - a}{n} \sum_{i=1}^{n} f(x_i) +    * 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}$ \\ 
-kde $x_i$ je bod v $i$-tém podintervalu (např. střed = **střední metoda**).\\+ 
 +    * Pro $\omega = 1$ přechází na GSM. Optimální $\omega$ zrychluje konvergenci, ale špatná volba způsobí divergenci  
 + 
 +=== Problémy a kritéria volby metod === 
 + 
 +  * **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**: 
 + 
 +^**Parametr**             ^**Přímé metody**               ^**Iterační metody**                       ^ 
 +|**Velikost matice**      |Malé až střední systémy        |Velké systémy ($n > 10^3$)                | 
 +|**Struktura matice**     |Plné nebo řídké                |Řídké (např. diskretizace PDE)            | 
 +|**Přesnost**             |Vysoká (teoreticky přesné)     |Přibližná (kontrola rezidua $\|\vec{r}\|$)| 
 +|**Vícenásobná $\vec{b}$**|Efektivní (jednorázový rozklad)|Výhodné s dobrým počátečním odhadem       | 
 +|**Paměťová náročnost**   |Vyšší (např. LU: $O(n^2)$)     |Nižší (např. JIM: $O(n)$)                 |
  
-  * **Řá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)$)+=== Odhady chyb a optimalizace ===
  
-  * **Výhody**: Jednoduchost, malá početní náročnost.\\+  * **Reziduální odhad**: $\vec{r} = \vec{b} - A\vec{x}_c$ umožňuje zpřesnění řešení \\
  
-  * **Nevýhody**: Malá přesnost, nevhodné pro funkcí s rychlým zrychlením.+  * **Složitost**: 
 +    * Přímé metody: $O(n^3)$ pro GEM, $O(n^2)$ pro zpětný chod.\\
  
-=== 2. Lichoběžníková metoda (Trapezoidal Rule) ===+    * Iterační metody: $O(n^2)$ na iteraci (pro husté matice), $O(n)$ pro řídké 
  
-  * **Princip**: Interval rozdělí na $n$ podintervalů, které aproximuje **lichoběžníky** (lineární interpolace).\\ 
  
-  * **Formule**:\\+===== Numerická integrace ===== 
 + 
 +**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.** 
 + 
 +==== Metody numerické integrace ==== 
 + 
 +  - **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}$:\\
 $$ $$
-\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}+I_L = h \sum_{i=0}^{n-1} f(x_i), \quad x_i = a + i \cdot h.
 $$\\ $$\\
  
-  * **Řád metody**: 2 (chyba $O(h^2)$).\\+    * **Řád metody:** 1 (přesná pro polynomy stupně 0, např. konstantní funkce). 
 +  - **Metoda středních obdélníků** 
 +    * **Myšlenka:** Funkce se aproximuje hodnotou ve **středu** každého podintervalu.\\
  
-  * **Výhody**: Lépe přesná než obdélníková, stabilní pro hladké funkce.\\+    * **Matematicky:**\\ 
 +$$ 
 +I_S = h \sum_{i=0}^{n-1} f\left(x_i + \frac{h}{2}\right). 
 +$$\\
  
-  * **Nevýhody**: Chyba se zvětšuje pro funkce s velkými druhými derivacemi.+    * **Řád metody:** 2 (přesná pro lineární polynomy, např. $x^1$). 
 +  - **Lichoběžníková metoda (Trapezoid)** 
 +    * **Myšlenka:** Funkce se aproximuje **lineárně** mezi konci podintervalu (plocha lichoběžníku).\\
  
-=== 3. Simpsonova metoda (Simpson’s Rule) ===+    * **Matematicky:**\\ 
 +$$ 
 +I_T = \frac{h}{2} \left[ f(a) + 2 \sum_{i=1}^{n-1} f(x_i) + f(b) \right]. 
 +$$\\
  
-  * **Princip**: Užívá **parabolické interpolace** (kvadratické polynomy) na párových podintervalech.\\+    * **Řád metody:** 2 (přesná pro lineární polynomy). 
 +  - **Simpsonova metoda** 
 +    * **Myšlenka:** Funkce se aproximuje **kvadratickou** parabolou přes dvojice podintervalů.\\
  
-  * **Formule**:\\+    * **Matematicky (pro sudé $n$):**\\
 $$ $$
-\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]+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].
 $$\\ $$\\
-(vyžaduje sudé $n$).\\ 
  
-  * **Řád metody**: 4 (chyba $O(h^4)$).\\+    * **Řád metody:** 4 (přesná pro kubické polynomy, např. $x^3$). 
 +  - **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]$.\\
  
-  * **Výhody**: Vysoká přesnost pro hladké funkce.\\+    * **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.\\
  
-  * **Nevýhody**: Závislost na počtu podintervalů, složitější výpočet -> velmi pomalé.+    * **Řád metody:** $2n-1$ (pro $n$ bodů přesná pro polynomy stupně $\leq 2n-1$).
  
 === 4. Newton-Cotesovy vzorce === === 4. Newton-Cotesovy vzorce ===
Line 474: Line 414:
  
 ==== Problémy a optimalizace ==== ==== Problémy a optimalizace ====
 +  * **Problémy:** Numerické chyby (zaokrouhlovací, metody), singularity, oscilace funkce.\\
  
-=== 1. Odhad chyby a kompozitní metody ===+=== Metoda polovičního kroku a odhad chyby ===
  
-  * **Kompozice**: Rozdělení $[a, b]$ na $n$ podintervalů a aplikace metody na každý.\\ +  * **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:\\
- +
-  * **Chyba trapezoidální metody**:\\+
 $$ $$
-E \approx -\frac{(b - a)^3}{12n^2} f''(\xi), \quad \xi \in [a,b]+E_h \approx \frac{I_h - I_{h/2}}{2^p - 1}.
 $$\\ $$\\
  
-  * **Chyba Simpsonovy metody**:\\ +  * **Vylepšení integrálu:**\\
-$$ +
-E \approx -\frac{(b - a)^5}{180n^4} f^{(4)}(\xi)+
 $$ $$
 +I_{\text{lepšené}} = I_{h/2} + \frac{I_{h/2} - I_h}{2^p - 1}.
 +$$\\
  
-=== 2. Richardsonova extrapolace ===+  * **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 
  
-Sloučení dvou odhadů s různými kroky $h$ a $h/2$ pro odstranění vedení v chybě.\\ +=== Řád metody === 
-- **Příklad**: U trapezoidální metody:\\ + 
-$$ +  * **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žší).\\ 
-  I(h/2) = I(h) + \frac{E(h)}{4} \Rightarrow \text{vyšší řád} O(h^4) + 
-  $$+  * **Chyba metody:** Pro krok $h$ a řád $p$ je globální chyba $O(h^p)$. 
 + 
 + 
 +==== Řád chyby ==== 
 + 
 +  * **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$.
  
-=== 3. Adaptivní kvadratura ===+=== Adaptivní kvadratura ===
  
 Metody jako **Gauss-Kronrod** automaticky rozdělují intervaly podle lokálního chybového odhadu (lepší efektivita pro funkcí s různými charakteristikami). Metody jako **Gauss-Kronrod** automaticky rozdělují intervaly podle lokálního chybového odhadu (lepší efektivita pro funkcí s různými charakteristikami).
Line 523: Line 468:
 ==== Kritéria volby metody ==== ==== Kritéria volby metody ====
  
-  - **Hladkost funkce**: Pro funkce s velkými derivacemi preferovat metody s vysokým řádem (např. Simpsonova).\\ +  - **Hladkost funkce**: Pro funkce s velkými derivacemi preferovat metody s vysokým řádem (např. Simpsonova). 
- +  - **Interval délky**: Pro velké intervaly nebo singulární body použít adaptivní metody nebo substituci.
-  - **Interval délky**: Pro velké intervaly nebo singulární body použít adaptivní metody nebo substituci.\\ +
   - **Výpočetní náročnost**: Obdélníková je nejrychlejší, ale malá přesnost.   - **Výpočetní náročnost**: Obdélníková je nejrychlejší, ale malá přesnost.
  

Trace:

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b01num (generated for current page)