В общем случае решение задачи ГП (даже без дополнительных ограничений) требует выполнения довольно сложных вычислительных процедур. Поэтому понятным является желание выделить позиномы специального вида, для которых решение задачи ГП находится просто. Именно такими являются регулярные позиномы, о которых речь пойдет ниже.
Позином
$$g(x)=\sum\limits_{i=1}^{n}c_{i}\prod\limits_{j=1}^{m}{x_{j}}^{a_{ij}}$$называется регулярным позиномом, если выполнены равенства:
$$\sum\limits_{i=1}^{n}c_{i}a_{i j} = 0,\ j=\overline{1,m}$$или в векторной форме записи
$$C A_j = 0,\ j=\overline{1,m}.$$Равенства (24) означают, что для регулярного позинома точка $$x=(1, 1, \dots, 1)$$ является стационарной, то есть точкой, в которой все частные производные позинома $$g(x)$$ равны нулю.
Пример 21 Рассмотрим следующий позином одной переменной:$$g(x) = x + x^{-1}.$$ Докажем, что он регулярный.
Вектор коэффициентов и матрица экспонент позинома $$g(x)$$ имеют вид:
$$C=\left\| \begin{array}{r} 1 \\ 1 \end{array} \right\|,\ A = \left\| \begin{array}{r} 1 \\ -1 \end{array} \right\|.$$Поскольку выполнено равенство $$C A =1\times 1 + 1\times (-1) = 0$$, то позином является регулярным. Мы получим это же равенство, если вычислим значение производной $$g(x)$$ при $$x=1$$:
$$g'(x)|_{x=1} =1-x^{-2}|_{x=1} =0.$$Пример 22 Проверим, что позином$$g(x,y) = 3 x^{-2}y^{-2} + 3 x^{2. 5}y^{4} + 1. 5 x^{-1}y^{-4}$$ - регулярный.
Вектор коэффициентов и матрица экспонент позинома $$g$$ имеют вид:
$$C=\left\| \begin{array}{l} 3 \\ 3 \\ 1. 5 \end{array} \right\|,\ A = \left\| \begin{array}{lr} -2 -2 \\ \hphantom{-} 2. 5 4 \\ -1 -4 \end{array} \right\|.$$Поскольку выполнены равенства$$C A_1=-2\times 3 + 2. 5\times 3 + (-1)\times 1. 5 = 0,$$
$$C A_2=-2\times 3 + 4\times 3 + (-4)\times 1. 5 = 0,$$позином (25) регулярный.
Из определения следует, что позином $$g(x_1,\ldots,x_m)$$ регулярен тогда и только тогда, когда все его компоненты $$g_{j}(x_{j}),\ (j =\overline{1,m})$$ регулярны. Например, у позинома (25) из примера 22 - регулярны обе его компоненты:
$$\begin{array}{rlc} g_{1}(x) = 3 x^{-2} + 3 x^{2. 5} + 1. 5x^{-1}, \\ g_{2}(y) = 3 y^{-2} + 3 y^{4} + 1. 5y^{-4}. \end{array}$$Приведем теорему, которая в ряде случаев упрощает проверку регулярности позинома.
Теорема 4 Если $$g,\ h$$ - регулярные позиномы, то $$\lambda g$$ ( $$\lambda>0$$ ), $$g + h,\ gh$$, $$g^{k}$$ ( $$k \ge 0$$, целое число) - тоже регулярные позиномы.
Пример 23 Докажем, используя теорему 4, что функция$$g(x) = \frac{\left(x+\frac{1}{x}\right)^{n+1}-1}% {x+\frac{1}{x}-1}$$ является регулярным позиномом.
Прежде всего, заметим, что формула (27) является формулой суммы $$(n+1)$$ члена геометрической прогрессии, у которой $$a_0=1$$, а $$q= x+\frac{1}{x}$$:
$$g(x) = \frac{\left(x+\frac{1}{x}\right)^{n+1}-1}% {x+\frac{1}{x}-1}=\sum_{k=0}^{n}\left(x+\frac{1}{x}\right)^{k}.$$В примере 21 было доказано, что позином $$x+\frac{1}{x}$$ регулярный. Следовательно, по теореме 4 функции $$\left(x+\frac{1}{x}\right)^k$$ при целом $$k\ge 0$$ также являются регулярными позиномами. Тогда (по той же теореме) функция $$g(x)$$ является регулярным позиномом как сумма регулярных позиномов.
Наименьшие значения регулярных позиномов легко вычисляются, так как имеет место факт, который мы сформулируем как теорему (см., например, [1]).
Теорема 5 Наименьшее значение регулярного позинома $$g(x_1,\ldots, x_m)$$ равно сумме его коэффициентов и достигается при $$x_1 = x_2 = \ldots =$$ $$= x_m = 1$$:
$$\min g(x_1,\ldots, x_m) = g(1,\ldots, 1) = \sum\limits_{i = 1}^{n}c_{i}.$$Из теоремы 5 не следует, что регулярный позином достигает своего минимума только в точке $$(1, \ldots, 1)$$. Например, для регулярного позинома
$$g(x,y) = x y^{-1} + x^{-1}y$$точкой минимума являются все точки вида $$(a, a)$$ при $$a > 0$$.
Значение позинома $$g(x,y)$$ во всех этих точках равно 2. Однако легко доказать, что регулярный позином одной переменной имеет единственный минимум в точке $$x = 1$$.
Пример 24 Вычислим минимальные значения регулярных позиномов из примеров 22 и 23 соответственно:
$$g(x,y) = 3 x^{-2}y^{-2} + 3 x^{2.5}y^{4} + 1.5 x^{-1}y^{-4},$$ $$g(x) =\frac{\left(x+\frac{1}{x}\right)^{n+1}-1}% {x+\frac{1}{x}-1} .$$В соответствующих примерах было доказано, что обе функции являются регулярными позиномами, поэтому по теореме 5 имеем:
$$\min g(x,y) = g(1,1) = 3 + 3 + 1. 5 = 7. 5,$$ $$\min g(x) = g(1) =\frac{\left(1+1\right)^{n+1}-1}% {1+1-1}=2^{n+1}-1.$$Из теории дифференциального исчисления известно, что необходимыми
условиями того, что точка $$x=(x_1, x_2, \ldots, x_m)$$ -
Точки, которые удовлетворяют условиям (29), называются стационарными.
Не все стационарные точки являются точками экстремума. Установить, является ли стационарная точка экстремумом и каким (максимумом или минимумом), можно с помощью специальных критериев (достаточных условий экстремума). Однако в случае позиномов все гораздо проще: необходимые условия (29) являются и достаточными условиями. Остановимся на этом поподробнее.
Когда функция $$g(x)$$ является позиномом:
$$g(x)=\sum\limits_{i=1}^{n}c_{i}\prod\limits_{j=1}^{m} x_{j}^{a_{ij}},$$условия (29) принимают вид:
$$\sum\limits_{i=1}^{n}c_{i}a_{ij} % x_{1}^{a_{i1}}x_{2}^{a_{i2}}\ldots x_{j}^{a_{ij-1}}\ldots x_{m}^{a_{im}}=0,\ j=\overline{1,m}.$$Умножив каждое уравнение системы (30) на соответствующее ему $$x_j > 0$$, получим эквивалентную систему уравнений:
$$\sum\limits_{i=1}^{n}c_{i}a_{ij} % \prod\limits_{j=1}^{m} x_{j}^{a_{ij}},=0,\ j=\overline{1,m}.$$Теперь мы сформулируем теорему, на которую будем ссылаться как на главную теорему о позиномах. %, а также следствие из нее. То, что мы поместили эту теорему именно в этом месте, объясняется тем, что самое короткое ее доказательство основано на преобразовании произвольного позинома в регулярный позином. Разумеется, речь идет о позиноме, достигающего своего минимума в области определения.
Теорема 6 Все положительные решения системы (31) являются точками глобального минимума позинома $$g(x)$$ .
Учитывая главную теорему о позиномах, мы далее будем говорить о минимумах, опуская прилагательное глобальный.
Задачи, которые рассматриваются в этом курсе, заключаются в нахождении значения минимума позинома и одной или всех точек, в которых он достигается, разумеется, если таковые имеются. Однако в ряде случаев бывает достаточно (или полезно) знать не точное значения минимума, а его оценки. Приведем сначала необходимые определения.
Нижней оценкой функции $$g(x)$$ называется любое вещественное число $$\underline{G}$$, для которого при любом $$x$$ из области определения функции $$g(x)$$ выполнено неравенство $$g(x)\ge \underline{G}$$. Очевидно, что любая нижняя оценка функции является нижней оценкой минимума этой функции и наоборот.
Не так обстоит дело с верхними оценками. Верхней оценкой минимума функции $$g(x)$$ называется любое вещественное число $$\overline{G}$$, для которого выполнено неравенство $$\min g(x)\le \overline{G}$$. Очевидно, что любая верхняя оценка функции является верхней оценкой ее минимума, но не любая верхняя оценка минимума является верхней оценкой функции.
Знание оценок минимума позинома бывает полезно по двум основным причинам. Во-первых, во многих алгоритмах вычисления организованы таким образом, что знание оценок часто сокращает время работы алгоритма. Во-вторых, в ряде случаев, когда разность $$\overline{G} - \underline{G}$$ мала, можно не вычислять точное значение минимума, положив $$\min g(x) \approx \overline{G}$$.
Обсудим сначала получение нижних оценок. Обозначим через $$g_s(x)$$ - позином, являющийся суммой только тех из мономов (образующих позином $$g(x)$$ ), номера которых включены в множество $$S$$:
$$g_s(x)=\sum\limits_{i\in S}u_{i},\ S\subset I.$$Обозначим через
$$\underline{G}_s=\min_{x>0} g_{s}(x).$$Так как $$g(x)\ge g_s(x)$$ при любом $$x>0$$, то любая из величин $$\underline{G}_s$$ является нижней оценкой для минимума $$g(x)$$:
$$\min_{x>0} g(x)\ge \underline{G}_s,\ \forall S\subset I.$$При $$S=\emptyset$$ полагаем $$g_s(x)\equiv 0$$ и получаем тривиальную нижнюю оценку $$\underline{G}=0$$. На практике в качестве $$S$$ следует выбирать подмножества, для которых величина $$\underline{G}_s$$ легко вычисляется, например, когда позином $$g_s(x)$$ является регулярным.
Перейдем теперь к обсуждению верхних оценок. Верхней оценкой минимума позинома является его значение при любом $$x> 0$$. Так как проще всего вычислить значение позинома в точке $$x_1 = x_2 = \ldots = x_m = 1$$, то в качестве тривиальной верхней оценки обычно берут
$$\overline{G}_0 = g(1,\ldots, 1) = \sum\limits_{i = 1}^{n}c_{i}.$$Прежде, чем описать, как можно вычислить более точные верхние оценки позинома, напомним, что компонентами позинома $$g(x)$$ называются позиномы $$g_{j} (x_j)$$:
$$g_{j} (x_j) = \sum\limits_{i=1}^{n}c_{i}x_{j}^{a_{ij}},\ j=\overline{1,m}.$$Заметим, что позиномы $$g_{j} (x_j)$$ получаются в результате выполнения следующей замены переменных:
$$g_{j} (x_j) = g(1,\ldots, 1, x_j, 1, \ldots, 1),\ j=\overline{1,m}.$$Более точную верхнюю оценку можно получить, вычислив минимумы компонент позинома $$g_{j} (x_j)$$, которые являются функциями от одной переменной. Обозначим через
$$\overline{G}_j=\min_{x_j>0} g_{j} (x_j).$$Любая из оценок $$\overline{G}_j\le \overline{G}_0$$, так как справедливо неравенство:
$$\overline{G}_j\le g_{j} (1)=g(1,\ldots, 1)=\overline{G}_0.$$В качестве верхней оценки минимума позинома $$g(x)$$ может быть использована следующая величина:
$$\overline{G}=\min_{j=\overline{1,m}}\overline{G}_j .$$Приведем пример вычисления оценoк позинома.
Пример 25 Вычислим оценки позинома:
$$g(x) = 2x_{1}x_{2}^{-2} + 3 x_{1}^{-1}x_{2} + x_{1}^{2}x_{2}^{-1}.$$Вычислим сначала нижнюю оценку позинома. Для этого представим первый моном $$2x_{1}x_{2}^{-2}$$ как сумму двух равных мономов:
$$g(x) = x_{1}x_{2}^{-2}+ x_{1}x_{2}^{-2} + 3 x_{1}^{-1}x_{2} + x_{1}^{2}x_{2}^{-1}.$$Возьмем $$S=[2, 3, 4]$$. Позином
$$g_s(x)= x_{1}x_{2}^{-2} + 3 x_{1}^{-1}x_{2} + x_{1}^{2}x_{2}^{-1}$$является регулярным, так как для него выполнены следующие равенства:
$$\sum\limits_{i\in S}c_{i}a_{i 1} = 1-3+2=0,$$ $$\sum\limits_{i\in S}c_{i}a_{i 2} = -2+3-1=0.$$Следовательно, его минимум вычисляется по формуле:
$$\underline{G}_s=\min_{x>0} g_s(x) = \sum\limits_{i\in S}c_{i}=1+3+1=5.$$Таким образом, получили нижнюю оценку для позинома $$\underline{G}= \underline{G}_s= 5$$.
Вычислим теперь верхнюю оценку минимума позинома. Позином состоит из двух компонент:
$$\begin{array}{rrl} g_{1}(x_1) = 2 x_{1}+3 x_{1}^{-1}+x_{1}^{2}, \\ g_{2}(x_2)=2 x_{2}^{-2}+3 x_{2}+x_{2}^{-1}. \end{array}$$Вычислим минимумы компонент позинома. Для каждой компоненты запишем производную:
$$\begin{array}{rrl} g_{1}^{'}(x_1) =2-3 x_{1}^{-2}+2 x_{1}, \\ g_{2}^{'}(x_2)=-4 x_{2}^{-3}+3-x_{2}^{-2}. \end{array}$$В точке минимума компоненты ее производная обращается в нуль. Решим уравнения (например, с помощью надстройки Поиск решения (Solver) в Excel ):
$$\begin{array}{lrl} 2-3 x_{1}^{-2}+2 x_{1}=0, \\ -4 x_{2}^{-3}+3-x_{2}^{-2}=0. \end{array}$$Для первой компоненты единственной стационарной точкой в области $$x>0$$ является $$x_{1}^{*} = 0.89$$, следовательно,
$$\overline{G}_{1}=\min_{x_{1}>0} g_{1}(x_1) = g_{1}(0.89)= 5.94.$$Для второй компоненты единственной стационарной точкой в области $$x>0$$ является $$x_{2}^{*} = 1.20$$, следовательно,
$$\overline{G}_{2}=\min_{x_{2}>0} g_{2}(x_2) = g_{2}(1.20) = 5.82.$$Верхняя оценка позинома равна
$$\overline{G} =\min_{j=\overline{1,2}}\overline{G_j} = \min\{5.94,\ 5.82\}=5.82.$$Таким образом, вычислив оценки, мы установили, что
$$5\le \min_{x>0}g(x)\le 5.82.$$Заметим, что в данном примере верхняя оценка $$5.82$$, достаточно близка к минимальному значению позинома, которое равно $$5.74$$. Разность составляет
$$\frac{5.82-5.74}{5.74}= 1.39\%.$$Рассмотрим еще один пример.
Пример 26 Вычислим оценки позинома из примера 9 (лекция 1):
$$g(x) = 4 x_{1}x_{2}^{3}x_{3}^{-2} + 6 x_{1}^{-2}x_{2}^{-1}x_{3}^{2} + 3.8 x_{1}x_{2}^{-2}x_{3}^{-1} + x_{1}^{3}x_{2}x_{3}.$$Вычислим сначала нижнюю оценку позинома. Для этого представим второй моном $$6 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}$$ как сумму двух мономов:
$$6 x_{1}^{-2}x_{2}^{-1}x_{3}^{2} = 5.4 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}+0.6 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}.$$Теперь позином имеет вид:
$$g(x)= 4 x_{1}x_{2}^{3}x_{3}^{-2} +5.4 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}+0.6 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}+3.8 x_{1}x_{2}^{-2}x_{3}^{-1} + x_{1}^{3}x_{2}x_{3}.$$Возьмем $$S=[1, 2, 4 , 5]$$. Позином
$$g_s(x)= 4 x_{1}x_{2}^{3}x_{3}^{-2} +5.4 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}+3.8 x_{1}x_{2}^{-2}x_{3}^{-1} + x_{1}^{3}x_{2}x_{3}$$является регулярным, так как для него выполнены следующие равенства:
$$\sum\limits_{i\in S}c_{i}a_{i 1} = 4-10.8+3.8+3=0,$$ $$\sum\limits_{i\in S}c_{i}a_{i 2} = 12-5.4-7.6+1=0.$$ $$\sum\limits_{i\in S}c_{i}a_{i 3} = -8+10.8-3.8+1=0.$$Следовательно, его минимум вычисляется по формуле:
$$\underline{G}_s=\min_{x>0} g_s(x) = \sum\limits_{i\in S}c_{i}=4+5.4+3.8+1=14.2.$$Таким образом, получили нижнюю оценку для позинома $$\underline{G}= \underline{G}_s= 14.2$$.
Вычислим теперь верхнюю оценку минимума позинома. Позином состоит из трех компонент:
$$\begin{array}{rrl} g_{1}(x_1) = 4 x_{1}+6 x_{1}^{-2}+3.8 x_{1}+x_{1}^{3}, \\ g_{2}(x_2)=4 x_{2}^{3}+6 x_{2}^{-1}+3.8 x_{2}^{-2}+x_{2}, \\ g_{3}(x_3)=4 x_{3}^{-2}+6 x_{3}^{2}+3.8 x_{3}^{-1}+x_{3}, \end{array}$$Вычислим минимумы компонент позинома. Для каждой компоненты запишем производную:
$$\begin{array}{rrl} g_{1}^{'}(x_1) =4-12 x_{1}^{-3}+3.8+3 x_{1}^{2}, \\ g_{2}^{'}(x_2)=12 x_{2}^{2}-6 x_{2}^{-2}-7.6 x_{2}^{-3}+1, \\ g_{3}^{'}(x_3)=-8 x_{3}^{-3}+12 x_{3}-3.8 x_{2}^{-2}+1. \end{array}$$В точке минимума компоненты ее производная обращается в нуль. Решим уравнения (например, с помощью надстройки Поиск решения (Solver) в Excel ):
$$\begin{array}{lrl} 4-12 x_{1}^{-3}+3.8+3 x_{1}^{2}=0, \\ 12 x_{2}^{2}-6 x_{2}^{-2}-7.6 x_{2}^{-3}+1=0, \\ -8 x_{3}^{-3}+12 x_{3}-3.8 x_{3}^{-2}+1=0. \end{array}$$Для первой компоненты единственной стационарной точкой в области $$x>0$$ является $$x_{1}^{*} = 1.03$$, следовательно,
$$\overline{G}_{1}=\min_{x_{1}>0} g_{1}(x_1) = g_{1}( 1.03)= 14.78.$$Для второй компоненты единственной стационарной точкой в области $$x>0$$ является $$x_{2}^{*} = 1.01$$, следовательно,
$$\overline{G}_{2}=\min_{x_{2}>0} g_{2}(x_2) = g_{2}(1.01) = 14.80.$$Для третьей компоненты единственной стационарной точкой в области $$x>0$$ является $$x_{3}^{*} = 0.97$$, следовательно,
$$\overline{G}_{3}=\min_{x_{3}>0} g_{3}(x_3) = g_{3}(0.97) = 14.78.$$Верхняя оценка позинома равна
$$\overline{G} =\min_{j=\overline{1,3}}\overline{G_j} = \min\{14.78, 14.80, 14.78\}=14.78.$$Таким образом, вычислив оценки, мы установили, что
$$14.2\le \min_{x>0}g(x)\le 14.78.$$Заметим, что в данном примере верхняя оценка $$14.78$$ совпала с минимальным значением позинома.
Введено понятие регулярного позинома. Описаны свойства регулярных позиномов. Приведена теорема минимизации регулярных позиномов. Сформулирована главная теорема о позиномах. Описан процесс вычисления оценки минимума позинома.
В общем случае решение задачи ГП (даже без дополнительных ограничений) требует выполнения довольно сложных вычислительных процедур. Поэтому понятным является желание выделить позиномы специального вида, для которых решение задачи ГП находится просто. Именно такими являются регулярные позиномы, о которых речь пойдет ниже.
Позином
$$g(x)=\sum\limits_{i=1}^{n}c_{i}\prod\limits_{j=1}^{m}{x_{j}}^{a_{ij}}$$называется регулярным позиномом, если выполнены равенства:
$$\sum\limits_{i=1}^{n}c_{i}a_{i j} = 0,\ j=\overline{1,m}$$или в векторной форме записи
$$C A_j = 0,\ j=\overline{1,m}.$$Равенства (24) означают, что для регулярного позинома точка $$x=(1, 1, \dots, 1)$$ является стационарной, то есть точкой, в которой все частные производные позинома $$g(x)$$ равны нулю.
Пример 21 Рассмотрим следующий позином одной переменной:$$g(x) = x + x^{-1}.$$ Докажем, что он регулярный.
Вектор коэффициентов и матрица экспонент позинома $$g(x)$$ имеют вид:
$$C=\left\| \begin{array}{r} 1 \\ 1 \end{array} \right\|,\ A = \left\| \begin{array}{r} 1 \\ -1 \end{array} \right\|.$$Поскольку выполнено равенство $$C A =1\times 1 + 1\times (-1) = 0$$, то позином является регулярным. Мы получим это же равенство, если вычислим значение производной $$g(x)$$ при $$x=1$$:
$$g'(x)|_{x=1} =1-x^{-2}|_{x=1} =0.$$Пример 22 Проверим, что позином$$g(x,y) = 3 x^{-2}y^{-2} + 3 x^{2. 5}y^{4} + 1. 5 x^{-1}y^{-4}$$ - регулярный.
Вектор коэффициентов и матрица экспонент позинома $$g$$ имеют вид:
$$C=\left\| \begin{array}{l} 3 \\ 3 \\ 1. 5 \end{array} \right\|,\ A = \left\| \begin{array}{lr} -2 -2 \\ \hphantom{-} 2. 5 4 \\ -1 -4 \end{array} \right\|.$$Поскольку выполнены равенства$$C A_1=-2\times 3 + 2. 5\times 3 + (-1)\times 1. 5 = 0,$$
$$C A_2=-2\times 3 + 4\times 3 + (-4)\times 1. 5 = 0,$$позином (25) регулярный.
Из определения следует, что позином $$g(x_1,\ldots,x_m)$$ регулярен тогда и только тогда, когда все его компоненты $$g_{j}(x_{j}),\ (j =\overline{1,m})$$ регулярны. Например, у позинома (25) из примера 22 - регулярны обе его компоненты:
$$\begin{array}{rlc} g_{1}(x) = 3 x^{-2} + 3 x^{2. 5} + 1. 5x^{-1}, \\ g_{2}(y) = 3 y^{-2} + 3 y^{4} + 1. 5y^{-4}. \end{array}$$Приведем теорему, которая в ряде случаев упрощает проверку регулярности позинома.
Теорема 4 Если $$g,\ h$$ - регулярные позиномы, то $$\lambda g$$ ( $$\lambda>0$$ ), $$g + h,\ gh$$, $$g^{k}$$ ( $$k \ge 0$$, целое число) - тоже регулярные позиномы.
Пример 23 Докажем, используя теорему 4, что функция$$g(x) = \frac{\left(x+\frac{1}{x}\right)^{n+1}-1}% {x+\frac{1}{x}-1}$$ является регулярным позиномом.
Прежде всего, заметим, что формула (27) является формулой суммы $$(n+1)$$ члена геометрической прогрессии, у которой $$a_0=1$$, а $$q= x+\frac{1}{x}$$:
$$g(x) = \frac{\left(x+\frac{1}{x}\right)^{n+1}-1}% {x+\frac{1}{x}-1}=\sum_{k=0}^{n}\left(x+\frac{1}{x}\right)^{k}.$$В примере 21 было доказано, что позином $$x+\frac{1}{x}$$ регулярный. Следовательно, по теореме 4 функции $$\left(x+\frac{1}{x}\right)^k$$ при целом $$k\ge 0$$ также являются регулярными позиномами. Тогда (по той же теореме) функция $$g(x)$$ является регулярным позиномом как сумма регулярных позиномов.
Наименьшие значения регулярных позиномов легко вычисляются, так как имеет место факт, который мы сформулируем как теорему (см., например, [1]).
Теорема 5 Наименьшее значение регулярного позинома $$g(x_1,\ldots, x_m)$$ равно сумме его коэффициентов и достигается при $$x_1 = x_2 = \ldots =$$ $$= x_m = 1$$:
$$\min g(x_1,\ldots, x_m) = g(1,\ldots, 1) = \sum\limits_{i = 1}^{n}c_{i}.$$Из теоремы 5 не следует, что регулярный позином достигает своего минимума только в точке $$(1, \ldots, 1)$$. Например, для регулярного позинома
$$g(x,y) = x y^{-1} + x^{-1}y$$точкой минимума являются все точки вида $$(a, a)$$ при $$a > 0$$.
Значение позинома $$g(x,y)$$ во всех этих точках равно 2. Однако легко доказать, что регулярный позином одной переменной имеет единственный минимум в точке $$x = 1$$.
Пример 24 Вычислим минимальные значения регулярных позиномов из примеров 22 и 23 соответственно:
$$g(x,y) = 3 x^{-2}y^{-2} + 3 x^{2.5}y^{4} + 1.5 x^{-1}y^{-4},$$ $$g(x) =\frac{\left(x+\frac{1}{x}\right)^{n+1}-1}% {x+\frac{1}{x}-1} .$$В соответствующих примерах было доказано, что обе функции являются регулярными позиномами, поэтому по теореме 5 имеем:
$$\min g(x,y) = g(1,1) = 3 + 3 + 1. 5 = 7. 5,$$ $$\min g(x) = g(1) =\frac{\left(1+1\right)^{n+1}-1}% {1+1-1}=2^{n+1}-1.$$Из теории дифференциального исчисления известно, что необходимыми
условиями того, что точка $$x=(x_1, x_2, \ldots, x_m)$$ -
Точки, которые удовлетворяют условиям (29), называются стационарными.
Не все стационарные точки являются точками экстремума. Установить, является ли стационарная точка экстремумом и каким (максимумом или минимумом), можно с помощью специальных критериев (достаточных условий экстремума). Однако в случае позиномов все гораздо проще: необходимые условия (29) являются и достаточными условиями. Остановимся на этом поподробнее.
Когда функция $$g(x)$$ является позиномом:
$$g(x)=\sum\limits_{i=1}^{n}c_{i}\prod\limits_{j=1}^{m} x_{j}^{a_{ij}},$$условия (29) принимают вид:
$$\sum\limits_{i=1}^{n}c_{i}a_{ij} % x_{1}^{a_{i1}}x_{2}^{a_{i2}}\ldots x_{j}^{a_{ij-1}}\ldots x_{m}^{a_{im}}=0,\ j=\overline{1,m}.$$Умножив каждое уравнение системы (30) на соответствующее ему $$x_j > 0$$, получим эквивалентную систему уравнений:
$$\sum\limits_{i=1}^{n}c_{i}a_{ij} % \prod\limits_{j=1}^{m} x_{j}^{a_{ij}},=0,\ j=\overline{1,m}.$$Теперь мы сформулируем теорему, на которую будем ссылаться как на главную теорему о позиномах. %, а также следствие из нее. То, что мы поместили эту теорему именно в этом месте, объясняется тем, что самое короткое ее доказательство основано на преобразовании произвольного позинома в регулярный позином. Разумеется, речь идет о позиноме, достигающего своего минимума в области определения.
Теорема 6 Все положительные решения системы (31) являются точками глобального минимума позинома $$g(x)$$ .
Учитывая главную теорему о позиномах, мы далее будем говорить о минимумах, опуская прилагательное глобальный.
Задачи, которые рассматриваются в этом курсе, заключаются в нахождении значения минимума позинома и одной или всех точек, в которых он достигается, разумеется, если таковые имеются. Однако в ряде случаев бывает достаточно (или полезно) знать не точное значения минимума, а его оценки. Приведем сначала необходимые определения.
Нижней оценкой функции $$g(x)$$ называется любое вещественное число $$\underline{G}$$, для которого при любом $$x$$ из области определения функции $$g(x)$$ выполнено неравенство $$g(x)\ge \underline{G}$$. Очевидно, что любая нижняя оценка функции является нижней оценкой минимума этой функции и наоборот.
Не так обстоит дело с верхними оценками. Верхней оценкой минимума функции $$g(x)$$ называется любое вещественное число $$\overline{G}$$, для которого выполнено неравенство $$\min g(x)\le \overline{G}$$. Очевидно, что любая верхняя оценка функции является верхней оценкой ее минимума, но не любая верхняя оценка минимума является верхней оценкой функции.
Знание оценок минимума позинома бывает полезно по двум основным причинам. Во-первых, во многих алгоритмах вычисления организованы таким образом, что знание оценок часто сокращает время работы алгоритма. Во-вторых, в ряде случаев, когда разность $$\overline{G} - \underline{G}$$ мала, можно не вычислять точное значение минимума, положив $$\min g(x) \approx \overline{G}$$.
Обсудим сначала получение нижних оценок. Обозначим через $$g_s(x)$$ - позином, являющийся суммой только тех из мономов (образующих позином $$g(x)$$ ), номера которых включены в множество $$S$$:
$$g_s(x)=\sum\limits_{i\in S}u_{i},\ S\subset I.$$Обозначим через
$$\underline{G}_s=\min_{x>0} g_{s}(x).$$Так как $$g(x)\ge g_s(x)$$ при любом $$x>0$$, то любая из величин $$\underline{G}_s$$ является нижней оценкой для минимума $$g(x)$$:
$$\min_{x>0} g(x)\ge \underline{G}_s,\ \forall S\subset I.$$При $$S=\emptyset$$ полагаем $$g_s(x)\equiv 0$$ и получаем тривиальную нижнюю оценку $$\underline{G}=0$$. На практике в качестве $$S$$ следует выбирать подмножества, для которых величина $$\underline{G}_s$$ легко вычисляется, например, когда позином $$g_s(x)$$ является регулярным.
Перейдем теперь к обсуждению верхних оценок. Верхней оценкой минимума позинома является его значение при любом $$x> 0$$. Так как проще всего вычислить значение позинома в точке $$x_1 = x_2 = \ldots = x_m = 1$$, то в качестве тривиальной верхней оценки обычно берут
$$\overline{G}_0 = g(1,\ldots, 1) = \sum\limits_{i = 1}^{n}c_{i}.$$Прежде, чем описать, как можно вычислить более точные верхние оценки позинома, напомним, что компонентами позинома $$g(x)$$ называются позиномы $$g_{j} (x_j)$$:
$$g_{j} (x_j) = \sum\limits_{i=1}^{n}c_{i}x_{j}^{a_{ij}},\ j=\overline{1,m}.$$Заметим, что позиномы $$g_{j} (x_j)$$ получаются в результате выполнения следующей замены переменных:
$$g_{j} (x_j) = g(1,\ldots, 1, x_j, 1, \ldots, 1),\ j=\overline{1,m}.$$Более точную верхнюю оценку можно получить, вычислив минимумы компонент позинома $$g_{j} (x_j)$$, которые являются функциями от одной переменной. Обозначим через
$$\overline{G}_j=\min_{x_j>0} g_{j} (x_j).$$Любая из оценок $$\overline{G}_j\le \overline{G}_0$$, так как справедливо неравенство:
$$\overline{G}_j\le g_{j} (1)=g(1,\ldots, 1)=\overline{G}_0.$$В качестве верхней оценки минимума позинома $$g(x)$$ может быть использована следующая величина:
$$\overline{G}=\min_{j=\overline{1,m}}\overline{G}_j .$$Приведем пример вычисления оценoк позинома.
Пример 25 Вычислим оценки позинома:
$$g(x) = 2x_{1}x_{2}^{-2} + 3 x_{1}^{-1}x_{2} + x_{1}^{2}x_{2}^{-1}.$$Вычислим сначала нижнюю оценку позинома. Для этого представим первый моном $$2x_{1}x_{2}^{-2}$$ как сумму двух равных мономов:
$$g(x) = x_{1}x_{2}^{-2}+ x_{1}x_{2}^{-2} + 3 x_{1}^{-1}x_{2} + x_{1}^{2}x_{2}^{-1}.$$Возьмем $$S=[2, 3, 4]$$. Позином
$$g_s(x)= x_{1}x_{2}^{-2} + 3 x_{1}^{-1}x_{2} + x_{1}^{2}x_{2}^{-1}$$является регулярным, так как для него выполнены следующие равенства:
$$\sum\limits_{i\in S}c_{i}a_{i 1} = 1-3+2=0,$$ $$\sum\limits_{i\in S}c_{i}a_{i 2} = -2+3-1=0.$$Следовательно, его минимум вычисляется по формуле:
$$\underline{G}_s=\min_{x>0} g_s(x) = \sum\limits_{i\in S}c_{i}=1+3+1=5.$$Таким образом, получили нижнюю оценку для позинома $$\underline{G}= \underline{G}_s= 5$$.
Вычислим теперь верхнюю оценку минимума позинома. Позином состоит из двух компонент:
$$\begin{array}{rrl} g_{1}(x_1) = 2 x_{1}+3 x_{1}^{-1}+x_{1}^{2}, \\ g_{2}(x_2)=2 x_{2}^{-2}+3 x_{2}+x_{2}^{-1}. \end{array}$$Вычислим минимумы компонент позинома. Для каждой компоненты запишем производную:
$$\begin{array}{rrl} g_{1}^{'}(x_1) =2-3 x_{1}^{-2}+2 x_{1}, \\ g_{2}^{'}(x_2)=-4 x_{2}^{-3}+3-x_{2}^{-2}. \end{array}$$В точке минимума компоненты ее производная обращается в нуль. Решим уравнения (например, с помощью надстройки Поиск решения (Solver) в Excel ):
$$\begin{array}{lrl} 2-3 x_{1}^{-2}+2 x_{1}=0, \\ -4 x_{2}^{-3}+3-x_{2}^{-2}=0. \end{array}$$Для первой компоненты единственной стационарной точкой в области $$x>0$$ является $$x_{1}^{*} = 0.89$$, следовательно,
$$\overline{G}_{1}=\min_{x_{1}>0} g_{1}(x_1) = g_{1}(0.89)= 5.94.$$Для второй компоненты единственной стационарной точкой в области $$x>0$$ является $$x_{2}^{*} = 1.20$$, следовательно,
$$\overline{G}_{2}=\min_{x_{2}>0} g_{2}(x_2) = g_{2}(1.20) = 5.82.$$Верхняя оценка позинома равна
$$\overline{G} =\min_{j=\overline{1,2}}\overline{G_j} = \min\{5.94,\ 5.82\}=5.82.$$Таким образом, вычислив оценки, мы установили, что
$$5\le \min_{x>0}g(x)\le 5.82.$$Заметим, что в данном примере верхняя оценка $$5.82$$, достаточно близка к минимальному значению позинома, которое равно $$5.74$$. Разность составляет
$$\frac{5.82-5.74}{5.74}= 1.39\%.$$Рассмотрим еще один пример.
Пример 26 Вычислим оценки позинома из примера 9 (лекция 1):
$$g(x) = 4 x_{1}x_{2}^{3}x_{3}^{-2} + 6 x_{1}^{-2}x_{2}^{-1}x_{3}^{2} + 3.8 x_{1}x_{2}^{-2}x_{3}^{-1} + x_{1}^{3}x_{2}x_{3}.$$Вычислим сначала нижнюю оценку позинома. Для этого представим второй моном $$6 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}$$ как сумму двух мономов:
$$6 x_{1}^{-2}x_{2}^{-1}x_{3}^{2} = 5.4 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}+0.6 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}.$$Теперь позином имеет вид:
$$g(x)= 4 x_{1}x_{2}^{3}x_{3}^{-2} +5.4 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}+0.6 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}+3.8 x_{1}x_{2}^{-2}x_{3}^{-1} + x_{1}^{3}x_{2}x_{3}.$$Возьмем $$S=[1, 2, 4 , 5]$$. Позином
$$g_s(x)= 4 x_{1}x_{2}^{3}x_{3}^{-2} +5.4 x_{1}^{-2}x_{2}^{-1}x_{3}^{2}+3.8 x_{1}x_{2}^{-2}x_{3}^{-1} + x_{1}^{3}x_{2}x_{3}$$является регулярным, так как для него выполнены следующие равенства:
$$\sum\limits_{i\in S}c_{i}a_{i 1} = 4-10.8+3.8+3=0,$$ $$\sum\limits_{i\in S}c_{i}a_{i 2} = 12-5.4-7.6+1=0.$$ $$\sum\limits_{i\in S}c_{i}a_{i 3} = -8+10.8-3.8+1=0.$$Следовательно, его минимум вычисляется по формуле:
$$\underline{G}_s=\min_{x>0} g_s(x) = \sum\limits_{i\in S}c_{i}=4+5.4+3.8+1=14.2.$$Таким образом, получили нижнюю оценку для позинома $$\underline{G}= \underline{G}_s= 14.2$$.
Вычислим теперь верхнюю оценку минимума позинома. Позином состоит из трех компонент:
$$\begin{array}{rrl} g_{1}(x_1) = 4 x_{1}+6 x_{1}^{-2}+3.8 x_{1}+x_{1}^{3}, \\ g_{2}(x_2)=4 x_{2}^{3}+6 x_{2}^{-1}+3.8 x_{2}^{-2}+x_{2}, \\ g_{3}(x_3)=4 x_{3}^{-2}+6 x_{3}^{2}+3.8 x_{3}^{-1}+x_{3}, \end{array}$$Вычислим минимумы компонент позинома. Для каждой компоненты запишем производную:
$$\begin{array}{rrl} g_{1}^{'}(x_1) =4-12 x_{1}^{-3}+3.8+3 x_{1}^{2}, \\ g_{2}^{'}(x_2)=12 x_{2}^{2}-6 x_{2}^{-2}-7.6 x_{2}^{-3}+1, \\ g_{3}^{'}(x_3)=-8 x_{3}^{-3}+12 x_{3}-3.8 x_{2}^{-2}+1. \end{array}$$В точке минимума компоненты ее производная обращается в нуль. Решим уравнения (например, с помощью надстройки Поиск решения (Solver) в Excel ):
$$\begin{array}{lrl} 4-12 x_{1}^{-3}+3.8+3 x_{1}^{2}=0, \\ 12 x_{2}^{2}-6 x_{2}^{-2}-7.6 x_{2}^{-3}+1=0, \\ -8 x_{3}^{-3}+12 x_{3}-3.8 x_{3}^{-2}+1=0. \end{array}$$Для первой компоненты единственной стационарной точкой в области $$x>0$$ является $$x_{1}^{*} = 1.03$$, следовательно,
$$\overline{G}_{1}=\min_{x_{1}>0} g_{1}(x_1) = g_{1}( 1.03)= 14.78.$$Для второй компоненты единственной стационарной точкой в области $$x>0$$ является $$x_{2}^{*} = 1.01$$, следовательно,
$$\overline{G}_{2}=\min_{x_{2}>0} g_{2}(x_2) = g_{2}(1.01) = 14.80.$$Для третьей компоненты единственной стационарной точкой в области $$x>0$$ является $$x_{3}^{*} = 0.97$$, следовательно,
$$\overline{G}_{3}=\min_{x_{3}>0} g_{3}(x_3) = g_{3}(0.97) = 14.78.$$Верхняя оценка позинома равна
$$\overline{G} =\min_{j=\overline{1,3}}\overline{G_j} = \min\{14.78, 14.80, 14.78\}=14.78.$$Таким образом, вычислив оценки, мы установили, что
$$14.2\le \min_{x>0}g(x)\le 14.78.$$Заметим, что в данном примере верхняя оценка $$14.78$$ совпала с минимальным значением позинома.
Введено понятие регулярного позинома. Описаны свойства регулярных позиномов. Приведена теорема минимизации регулярных позиномов. Сформулирована главная теорема о позиномах. Описан процесс вычисления оценки минимума позинома.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.