Řekneme, že posloupnost $\brackets{e_k}$ konverguje **rychleji** (*pomaleji*) než $\brackets{h_k}$, pokud existuje index $\tilde k \in \N_0$ takový, že
Nechť je dána posloupnost $\brackets{e_ k}_ {k = 0}^\infty$ splňující $e_k \in [0, \infty)$ a $e_k \to 0$. Řekneme, že posloupnost $\brackets{e_k}$ konverguje
@@ 73,12 77,13 @@
> Unimodalita **neimplikuje** konvexnost (*ani se spojitostí*), pouze **kvazikonvexnost**
>
> Naopak, *konvexní* funkce **nemusí** nutně být *unimodální* (ale **ostrá konvexnost** $\implies$ **unimodalita**)
-
> > Konvexní funkce nemusí být např. jen rostoucí, ale i **neklesající**
-
+
> > Konvexní funkce nemusí být např. jen rostoucí, ale i **neklesající**
V této části budeme řešit úlohu
-
$$f(x) \to \min, \qquad x \in I := [a,b] \eqT{3.1.1}$$
+
```math
+
f(x) \to \min, \qquad x \in I := [a,b] \eqT{3.1.1}
+
```
##### **Lemma** $\secT{3.1.2}$
Nechť $f: I \to \R$ je **unimodální** na $I$ a $x_1, x_2 \in I$ jsou takové, že $x_1 < x_2$.
@@ 89,7 94,6 @@
***Upozornění:*** \
Dále uvažujme <a style="color: red">***POUZE UNIMODÁLNÍ***</a> funkce.
-
Navíc nechť $N$ značí **povolený počet vyčíslení** a **přesnost** těchto metod je dáno jako $|\bar x - x^*|$, kde $x^*$ je **přesné** řešení úlohy $\eqRef{3.1.1}$ a $\bar x$ jeho nalezená aproximace.
### Metoda prostého dělení
@@ 98,67 102,61 @@
Podle parity $N$ určíme dělící body intervalu $I$.
-
<center>
-
-
| $N$ **liché** | $N$ **sudé**
-
| -- | --
-
$$x_i := a + {b - a \over N + 1} i, \quad i=1, \dots, N = 2k - 1$$ | $$x_{2i} := a + {b - a \over k + 1} i \quad \and \quad x_{2i - 1} := x_{2i} - \delta, \\ i = 1, \dots, k := N/2,$$
-
-
</center>
-
+
|$N$ **liché**|$N$ **sudé**|
+
|-------------|------------|
+
|$x_i := a + {b - a \over N + 1} i, \quad i=1, \dots, N = 2k - 1$ | $x_{2i} := a + {b - a \over k + 1} i \quad \and \quad x_{2i - 1} := x_{2i} - \delta, \quad i = 1, \dots, k := N/2,$ |
+
kde $\delta$ je *vhodné malé číslo.*
-
Poté vyčíslíme $f(x_1), \dots, f(x_N)$ (což v případě $N$ **sudého** a $\delta \in \set{0, {b-a \over k+ 1}}$ znamená **pouze** $k$ vyčíslení) a nechť v $x_j$ nastává nejmenší hodnota, tj.
-
$$f(x_j) = \min_{1 \leq i \leq N} f(x_i)$$
+
```math
+
f(x_j) = \min_{1 \leq i \leq N} f(x_i)
+
```
Pak z **Lemma** $\secRef{3.1.2}$ plyne, že $x^*\in [x_{j-1}, x_{j+1}]$ a tento interval nazveme **interval lokalizace minima (ILM)** a za aproximaci $x^*$ vezmeme *střed* ILM, tj. $\bar x := {x_{j-1} + x_{j+1} \over 2}$
-
Pro **délku** $l_N$ *intervalu lokalizace minima* platí
-
$$l_N := \max_{1 \leq i \leq N} (x_{i+1} - x_{i-1}) = \lcases{2 {b - a \over N+1}, & N = 2k - 1 \\ {b - a \over (N/2) + 1} + \delta, & N = 2k}$$
+
```math
+
l_N := \max_{1 \leq i \leq N} (x_{i+1} - x_{i-1}) = \lcases{2 {b - a \over N+1}, & N = 2k - 1 \\ {b - a \over (N/2) + 1} + \delta, & N = 2k}
+
```
> Pro $N$ **sudé** je **poslední** interval delší, proto dostáváme takový tvar $l_N$
> Přesnost této metody je dána **polovinou ILM**, tj. ${l_N \over 2}$
-
Rychlost konvergence této metody je **sublineární**, navíc je tento algoritmus **pasivní**, tj. volba $x_{m+1}$ **nezáleží** na $x_1, \dots, x_m$ (závisí pouze na $N$, či na $N$ a $\delta$).
> Při rovnosti funkčních hodnot **preferujeme konec** (*teoreticky by to mělo být jedno*)
### Metoda půlení intervalu <a name="mpi"></a>
-
Nechť nyní $N = 2k$. Položme $a_0 = a$, $b_0 = b$ a
kde $\delta > 0$ je *dostatečně malé* a $i = 1, \dots, k$. Vyčíslíme funkci v $x_i^-, x_i^+$, tj. dostaneme $f(x_i^-), f(x_i^+)$. Pak
- jestliže $f(x_i^-) < f(x_i^+)$, pak podle **Lemma** $\secRef{3.1.2}$ je **ILM** $[a_{i-1}, x_i^+] \implies a_i = a_{i-1}, b_i = x_i^+$
- jestliže $f(x_i^-) > f(x_i^+)$, pak podle **Lemma** $\secRef{3.1.2}$ je **ILM** $[x_i^-, b_{i-1}] \implies a_i = x_i^-, b_i = b_{i-1}$
-
Takto můžeme tento proces opakovat ($k$-krát, jelikož máme $N = 2k$ povolených vyčíslení), kdy za $a,b$ volíme krajní body *ILM* pro každý krok. Zřejmě, jako aproximaci $x^*$ v $k$-tém kroku bereme *střed ILM* pro $k$-tý krok.
přičemž $\delta \in [0, {b-a\over 2}]$ a navíc pro $k \to \infty$ je $l_k \to 2\delta$.
> Z tohoto vyplývá, že čím menší $\delta$, tím je metoda přesnější. Nicméně ve skutečnosti se můžeme dostat k zaokrouhlovacím chybám, které dokonce mohou způsobit, že špatně určíme velikosti $f(x_i^-), f(x_i^+)$ (tím pádem bychom řekli, že $x^*$ je v opačném intervalu, než je ve skutečnosti)
-
Tato metoda konverguje **lineárně** s rychlostí $1/2$.
> Při rovnosti funkčních hodnot **zapomínáme konec** (*teoreticky by to mělo být jedno*)
### Metoda zlatého řezu<a name="mzr"></a>
-
Myšlenka metody zlatého řezu "*vylepšuje*" metodu půlení intervalu tak, že každá další iterace umožňuje pouze **jedno** další vyčíslení.
> Zde $\tau$ je řešení rovnice $\tau^2 - \tau - 1 = 0$, tj. a $\frac 1 \tau \approx 0.618$
-
Mějme funkci $f$, interval $[a,b]$, přesnost $\ve$ nebo počet vyčíslení $N \geq 2$:
1. (*Inicializace*) Položíme $a_0 := a, b_0 := b$ a $k := 1$. Vypočteme
Tato metoda konverguje **lineárně** s rychlostí $\frac 1 \tau \approx 0.618$, tj. *stejně* jako [metoda zlatého řezu](#mzr)
> Fibonacciho metoda je (*mírně*) přesnější, než *metoda zlatého řezu* (která lze vnímat jako *limitní varianta* Fibonacciho metody). Nicméně u Fibonacciho metody je při změně $N$ potřeba **všechny body přepočítat**, což u metody zlatého řezu **není**.
