<div style="visibility:hidden;height:0;overflow:hidden;margin:0;padding:0">

</div>

Nechť jsou dány 2 posloupnosti $\brackets{e_ k}_ {k = 0}^\infty$ a $\brackets{h_ k}_ {k = 0}^\infty$ takové, že

Ř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

- **alespoň lineárně s rychlostí** $\beta \in (0,1)$, pokud konverguje **rychleji** než **geometrická** posloupnost se členy tvaru $q \bar \beta^k$, kde $q > 0$ a $\bar \beta \in (\beta, 1)$.

- čím **větší** $\bar \beta$, tím **pomaleji** jde tato geometrická posloupnost k nule - tj. konverguje rychleji než geometrická posloupnost s $\bar \beta$ větší než $\beta$

- **nejvýše lineárně s rychlostí** $\beta \in (0,1)$, pokud konverguje **pomaleji** než **geometrická** posloupnost se členy tvaru $q \bar \beta^k$, kde $q > 0$ a $\bar \beta \in (0, \beta)$.

- **lineárně s rychlostí** $\beta \in (0,1)$, pokud konverguje **nejvýše** a současně **alespoň** lineárně s rychlostí $\beta$.

- **superlineárně (*sublineárně*)**, pokud konverguje **rycheji** (*pomaleji*) než libovolná geometrická posloupnost se členy tvaru $q \beta^k$, kde $q > 0$ a $\beta \in (0,1)$.

Nechť je dána posloupnost $\brackets{e_ k}_ {k = 0}^\infty$ splňující $e_k \in [0, \infty)$ a $e_k \to 0$, přičemž $\brackets{e_k}$ konverguje **superlineárně**. Řekneme, že posloupnost $\brackets{e_k}$ konverguje

- **alespoň superlineárně s řádem** $p > 1$, pokud konverguje **rychleji** než všechny posloupnosti se členy tvaru $q \beta^{\bar p^k}$, kde $q > 0$ a $\beta \in (0,1)$ a $\bar p \in (1, p)$

- čím **větší** $\bar p$, tím **rychleji** posloupnost $q \beta^{\bar p^k}$ konverguje - tj. $\brackets{e_k}$ konverguje rychleji než všechny posloupnosti s **menším** $p$

- **nejvýše superlineárně s řádem** $p > 1$, pokud konverguje **pomaleji** než všechny posloupnosti se členy tvaru $q \beta^{\bar p^k}$, kde $q > 0$ a $\beta \in (0,1)$ a $\bar p \in (p, \infty)$

- **superlineárně s řádem** $p > 1$, pokud konverguje **nejvýše** a současně **alespoň** superlineárně s *řádem* $p$.

- **superlineárně s řádem** $p = 1$, pokud konverguje **pomaleji** než všechny posloupnosti se členy tvaru $q \beta^{\bar p^k}$, kde $q > 0$ a $\beta \in (0,1)$ a $\bar p \in (1, \infty)$

Nechť je dán interval $I \subset \R$ a funkce $f: I \to \R$. Řekneme, že $f$ je ***unimodální*** na $I$, jestliže existuje $x^*\in I$ takové, že

- $f(x_1) > f(x_2)$ pro libovolná $x_1, x_2 \in I$ splňující $x^*> x_1 > x_2$

- $f(x_1) < f(x_2)$ pro libovolná $x_1, x_2 \in I$ splňující $x^*< x_1 < x_2$

---

Jinými slovy, **unimodální** funkce je **klesající** na $(-\infty, x^*) \cap I$ (tj. *nalevo* od $x^*$) a **rostoucí** na $I \cap (x^*, \infty)$ (tj. *napravo* od $x^*$).

Nechť $f: I \to \R$ je **unimodální** na $I$ a $x_1, x_2 \in I$ jsou takové, že $x_1 < x_2$.

- Je-li $f(x_1) \leq f(x_2)$, pak $x^*\leq x_2$

- Je-li $f(x_1) \geq f(x_2)$, pak $x^*\geq x_1$

---

***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.

Podle parity $N$ určíme dělící body intervalu $I$.

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.

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í

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

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.

Délka *ILM* je v tomto případě

přičemž $\delta \in [0, {b-a\over 2}]$ a navíc pro $k \to \infty$ je $l_k \to 2\delta$.

Tato metoda konverguje **lineárně** s rychlostí $1/2$.

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í.

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

2. Je-li $k = N$, pokračujeme částí 5., jinak následuje krok 3.

3. Vyčíslíme $f(\l_k)$ a $f(\mu_k)$. Jestliže $f(\l_k) \geq f(\mu_k)$:

1. Položíme $a_k := \l_k, b_k = b_{k-1}, \l_{k+1} := \mu_k$ a

a pokračujeme na krok 4.

2. Položíme $a_k := a_{k-1}, b_k := \mu_k, \mu_{k+1} := \l_k$ a

a pokračujeme na krok 4.

4. Položíme $k := k+1$ a pokračujeme krokem 2.

5. Stanovíme poslední *ILM* jako $[a_{k-1}, b_{k-1}]$ a vypočteme $\bar x := {a_{k-1} + b_{k-1} \over 2}$. **KONEC**

Tato metoda konverguje **lineárně** s rychlostí $\frac 1 \tau \approx 0.618$

V této poslední metodě uvažujme, že zkrácení $\delta$ může být **jiné** v každé kroku metody.

Máme povoleno $N$ vyčíslení, takže $M = N - 1$ a