Изменения
→Коэффициент аппроксимации
Рассмотрим <tex>\alpha = (\frac{A}{a})^{\frac{1}{n}}</tex>, тогда <tex>x_i=a \alpha^i(i=1 \ldots n)</tex>.
<tex>\{x_i\}</tex> - <tex>\alpha</tex>-аппроксимация, т.к. <tex>\forall x \in [x_i, x_{i+1}]: f(x) \leq \alpha f(x_i)</tex>.
Следовательно , <tex>\alpha_{opt} \leq \alpha</tex>.
}}
Рассмотрим <tex>\alpha = (\frac{B}{b})^{\frac{1}{n}}</tex> и <tex>x_i=f^{-1}(B \alpha^{-i})(i=1 \ldots n)</tex>.
Тогда <tex>f(x_i) \geq B \alpha^{-i}</tex>.
Следовательно , <tex>\not \exists x: f(x_i)>f(x)>B \alpha^{-1}</tex>.Т.о. Таким образом, <tex>\{x_i\}</tex> - <tex>\alpha</tex>-аппроксимация, т.к. так как <tex>B \alpha^{-i} \leq f(x) \leq B \alpha^{-i+1}</tex>.
}}
|about=3
|statement=
<tex>\forall n \geq \log (\min ( \frac{A}{a}, \frac{B}{b})) / \varepsilon </tex>, где <tex>\varepsilon \in (0,1)</tex>, выполняется:
*<tex>\alpha_{opt} \geq 1 + \frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex>
*<tex>\alpha_{opt} \leq 1 + (1+\varepsilon)\frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex>
Для доказательства первого утверждения достаточно заметить, что <tex>\forall x \in \mathbb{R}: e^x\geq 1+x </tex>.
}}
