23
правки
Изменения
Нет описания правки
Рассмотрим функции вида: <tex>f:[a,A] \rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(a)=B, f(A)=b</tex>.
|id=definition1
|about=1
|definition=Множество решений <tex>\mathrm{X=(\{x_1,x_2, \ldots , x_n)\}}</tex> называется <tex>\alpha</tex>-аппроксимацией функции <tex>f \in \mathbb{F}</tex>, если:<tex>\mathrm{\forall x \in [a,A] \exists x_i \in X : (x \leq \alpha x_i) \bigwedge (f(x) \leq \alpha f(x_i))}</tex>.
}}
Множество всех множеств решений обозначим через <tex>\mathbb{X}</tex>
|about=2
|definition=Коэффициентом аппроксимации функции <tex>f</tex> на <tex>X</tex> называется
<tex>\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha</tex> -аппроксимация <tex>f \}</tex>.
}}
|id=definition3
|about=3
|definition=Оптимальный коэффициент аппроксимации <tex>\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{x X \in \mathbb{X}} \alpha (f, X)</tex>.
}}
|statement=<tex>\alpha_{opt} \leq (\frac{A}{a})^{\frac{1}{n}}</tex>
|proof=
Рассмотрим <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(\alpha x_i)</tex>.
Следовательно <tex>\alpha_{opt} \leq \alpha</tex>.
}}
|statement=<tex>\alpha_{opt} \leq (\frac{B}{b})^{\frac{1}{n}}</tex>
|proof=
Рассмотрим <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>.
}}
Пусть <tex>\forall i \in \{0, 1, \ldots, n\} f(x)=B(B/b)^{-i/n}</tex> на интервале <tex>(a(A/a)^{(i-1)/n}, a(A/a)^{i/n}]</tex>.
Теперь <tex>f</tex> - это фронт Парето из <tex>n+1</tex> слоя. Предложим, множество решений <tex>(\{x_1,x_2, \ldots , x_n)\}</tex> из <tex>n</tex> точек. По принципу Дирихле получается, что хотя бы на одном уровне нет ни одного решения. Это означает, что нижняя верхняя граница этого уровня аппроксимируется значением <tex>\min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}</tex>.
}}
Для доказательства первого утверждения достаточно заметить, что <tex>\forall x \in \mathbb{R}: e^x\geq 1+x </tex>.
Для доказательства второго - <tex>\forall x \in [0, \varepsilon]: e^x \leq 1+(1+\varepsilon)x </tex>.
}}
'''Следствие:''' <tex>\alpha_{opt} = 1 + \Theta(1/n)</tex>. == Индикатор Гиперобъема ==
Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
Тогда существует, не обязательно единственное, множество решений <tex>X \in \mathbb{X}</tex>, которое максимизирует значение <tex>HYP(X)</tex> на <tex>\mathbb{X}</tex>
|proof=
<tex>X=(\{x_1, x_2, \ldots,x_n)\}</tex>
<tex>HYP(X)=\sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r)</tex>
Рассмотрим ряд множеств решений <tex>\{X^i\}: \lim\limits_{i \rightarrow \infty} (X^i) = X</tex>. <tex>\lim\limits_{j \rightarrow \infty} HYP(X^j) = \lim\limits_{i \rightarrow \infty} \sum\limits_{i = 1}^{n} (x_i^j-x_{i-1}^j)(f(x_i^j) - r) =</tex> <tex>= \sum\limits_{i = 1}^{n} (x_i-x_{i-1})(\lim\limits_{i \rightarrow \infty} f(x_i^j) - r) = \sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r) = HYP(X)</tex>
Получается, что <tex>HYP(X)</tex> - верхняя полунепрерывная, следовательно экстремум <tex>HYP</tex> достигается на компакте.
}}
|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реднее гармоническое меньше среднего арифметического, тогда:
{{Теорема
|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_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>.
После подстановки получим:
