Numerické metody v R
$$ \xdef\scal#1#2{\langle #1, #2 \rangle} \xdef\norm#1{\left\lVert #1 \right\rVert} \xdef\dist{\rho} \xdef\and{\&}\xdef\brackets#1{\left\{ #1 \right\}} \xdef\parc#1#2{\frac {\partial #1}{\partial #2}} \xdef\mtr#1{\begin{pmatrix}#1\end{pmatrix}} \xdef\bm#1{\boldsymbol{#1}} \xdef\mcal#1{\mathcal{#1}} \xdef\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\th{\vartheta} \xdef\a{\alpha} \xdef\tagged#1{(\text{#1})} \xdef\tagged*#1{\text{#1}} \xdef\tagEqHere#1#2{\href{#2\#eq-#1}{(\text{#1})}} \xdef\tagDeHere#1#2{\href{#2\#de-#1}{\text{#1}}} \xdef\tagEq#1{\href{\#eq-#1}{(\text{#1})}} \xdef\tagDe#1{\href{\#de-#1}{\text{#1}}} \xdef\T#1{\htmlId{eq-#1}{#1}} \xdef\D#1{\htmlId{de-#1}{\vv{#1}}} \xdef\conv#1{\mathrm{conv}\, #1} \xdef\cone#1{\mathrm{cone}\, #1} \xdef\aff#1{\mathrm{aff}\, #1} \xdef\lin#1{\mathrm{Lin}\, #1} \xdef\span#1{\mathrm{span}\, #1} \xdef\O{\mathcal O} \xdef\ri#1{\mathrm{ri}\, #1} \xdef\rd#1{\mathrm{r}\partial\, #1} \xdef\interior#1{\mathrm{int}\, #1} \xdef\proj{\Pi} \xdef\epi#1{\mathrm{epi}\, #1} \xdef\grad#1{\mathrm{grad}\, #1} \xdef\hess#1{\nabla^2\, #1} \xdef\subdif#1{\partial #1} \xdef\co#1{\mathrm{co}\, #1} $$
Definice $\D{3.1.1}$ (Unimodální funkce)
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^* $).
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í
V této části budeme řešit úlohu $$ f(x) \to \min, \qquad x \in I := [a,b] \tag{\T{3.1.1}} $$
Lemma $\D{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$.
- 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 POUZE UNIMODÁLNÍ funkce.
Metoda prostého dělení
Tato metoda není efektivní a je to de facto hrubá síla
Podle parity $N$ určíme dělící body intervalu $I$.
| $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,$$ |
kde $\delta$