Изменения

{{Определение|id=definition6|about=6|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется <tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>.}} {{Утверждение|id=statement5|about=5|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>, тогда<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>.|proof=Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in В статье [[2,n]</tex> Связь между максимизацией гиперобъема и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,nаппроксимацией Парето-1фронта]</tex>.Подставив в [[#definition6|определение(6)]], получим: <tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} a_i b_i \Leftrightarrow a_i \geq MinCon(X) / b_i \forall i \in [2, n-1]</tex> <tex>\sum \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \sum \limits_{i=2}^{n} a_i = \sum \limits_{i=2}^{n}x_i - \sum \limits_{i=1}^{n-1}x_i=x_n-x_1 </tex> Тогда <tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i}</tex>. Cреднее гармоническое меньше среднего арифметического, поэтому<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-1}b_i}{(n-2)^2} \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>.}} {{Теорема|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex> и <tex>X = \{ x_1, \ldots, x_n \} \in \mathbb{X}</tex>. Тогда<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>.|proof=Допустимпредставлено докательство того, что существует для количества точек <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>.Пусть <tex>x_i < x < x_i+1</tex>, тогда <tex>x > \alpha x_i, f(x) > \alpha f(x_{i+1})</tex>. Известно, что <tex>MinCon(X) \geq (x-x_i)(f(x)оптимальный коэффициент апроксимации для данного Парето-fфронта (x_{i+1}))</tex>. После подстановки получим <tex>MinCon(X) > (\alpha - 1)^2 x_i f(x__{i+1OPT})</tex> (1). Применив [[#statement5|утверждение(5)]]и верхняя граница коэффициента аппроксимации для множества, получим: <tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/максимизирующего значение индикатора гиперобъема (i-2)^2</tex> (2) <tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+1})/(n-i-2)^2</tex> (3) Таким образом, <tex>(\alpha - 1)^2 x_i f(x_{i+1}) < \min \{\frac{x_iB}{(i-2)^2} ,\frac_{A f(x_{i+1HYP})}{(n-i-2)^2}\} \Leftrightarrow</tex> <tex>\alpha < 1 + \min \{\frac{\sqrt{x_iB}}{i-2} ,\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}</tex>. Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убываетодинаковы, а именно <texmath>\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}</tex> монотонно возрастает, то максимальное значение <tex>\min \{\frac{\sqrt{x_iB}}{i-2} ,\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}</tex> достигается при равенстве обоих членов: <tex>\frac{\sqrt{x_iB}}{i-2} = \frac{\sqrt{A f(x_{i+1})}}{n-i-2}\} \Leftrightarrow i = 2 + \frac{(n-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</tex>. Получим верхнюю оценку для <tex>\alpha</tex>: <tex>\alpha < 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>. Вышесказанное верно для <tex>3 \leq i \leq n-3</tex>. Для <tex>i = 1, 2</tex> из Theta (1) и (3) следует, что <tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>, что невозможно по условию теоремы. Для <tex>i = n-2, n-1</tex> по (1) и (2) <tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</texmath>, что тоже невозможно по условию теоремы. }}