Определение. Пусть на множестве u, состоящем из элементов u линейного
u*, если существует его конечная $$\varepsilon$$ - окрестность, в которой выполнено$$\Phi (u^*) \le \Phi (u), \left\|{u - u^*}\right\| \le \varepsilon$$
u на элементе u* (строгий, абсолютный минимум), если имеет место равенство$$\Phi (u^*) = \inf\limits_U\Phi (u)$$
Замечание. Если u — u — n - мерное векторное пространство, имеется задача на нахождение минимума функции n переменных, если u —
Если к (4.1) или (4.2) добавляются условия
$$\begin{gather*} u_k^0 \le u_k \le u_k^1, k = 1, \ldots , K \\ F_i^0 \le \Phi_i (u) \le F_i^1, i = 1, \ldots , i, \end{gather*}$$( $$u_k^{0,1} , F_i^{0,1}$$ — числа, a $$\Phi _{i}$$ — заданные функции), то это задача поиска условного минимума, если подобные ограничения отсутствуют, то это задача поиска безусловного минимума. Причем, если функции $$\Phi _{i}(u)$$ линейны, задача поиска условного минимума называется задачей линейного программирования, если хотя бы одна из этих функций нелинейна, то имеется задача
Говорится о поиске минимума функции, не ограничивая общности, так как максимум функции $$\Phi (u)$$ является минимумом функции $$- \Phi (u).$$
$$\Phi (u)$$ называют
Отметим связь между задачами вычисления корней системы нелинейных алгебраических уравнений (СНАУ) и задачи минимизации.
Пусть на множестве $$U \in L^n$$ решается
f1(u1, ..., un) = 0, ... fn(u1, ..., un) = 0.
Определим
В области U справедливо $$\Phi (u) \ge 0,$$ причем
минимальное значение $$\Phi (u)$$ имеет при u = u*, где u* — корень рассмотренной системы. Поэтому ее решение эквивалентно поиску минимума $$\Phi (u)$$ в U. Если $$\Phi (u)$$ строго больше нуля, то система решений не имеет.
Теперь положим, что необходимо найти минимум
Точка, являющаяся решением указанной СНАУ, называется
Следующую теорему приведем без доказательства.
Теорема. Пусть функция $$\Phi (u)$$ дважды непрерывно
дифференцируема. Тогда достаточным условием того, чтобы u* была точкой локального минимума, является положительная определенность матрицы Гессе
Отметим, что методы отыскания минимума $$\Phi (u)$$ нередко оказываются более эффективными, чем методы численного решения СНАУ.
Пусть U = [a, b] , т.е. отрезок числовой оси. Разобьем его на n равных частей с узлами в точках ui = a + i(b - a)/n;
i = 0, ..., n.
Вычислив значение $$\Phi (u)$$ в этих точках, найдем путем сравнения точку u*, в которой
Далее полагаем: $$u^{*} \approx u_{min}, \Phi ^{*} \approx \Phi (u^{*}).$$ Погрешность в определении u* этого простейшего метода не превосходит числа
Этот метод прост, но неэкономичен, особенно когда ищется минимум функции многих переменных. Например, в гиперкубе $$U = \left\{{0 \le u_i \le 1,1 \le i \le 10}\right\}$$ с разбиением каждого из отрезков (по каждой из координат) на 10 частей, с быстродействием $$10^6$$ операций в секунду потребуется около 107 с (примерно 4 месяца) для нахождения $$\min\limits_U\Phi (u),$$ если предположить, что количество арифметических действий, необходимое для вычисления значений $$\Phi (u)$$ в каждой точке требует тысячи арифметических операций. Этот метод можно сделать более эффективным, если сначала определить минимум с грубым шагом, затем уже искать минимум с меньшим шагом на том из отрезков [xi, xi + 1], на котором
предполагается наличие минимума; можно и далее уточнять решение задачи таким же образом.
Усовершенствованием этого метода являются методы исключения отрезков,
дихотомии (деления отрезка пополам) и [a, b] делится на 4 части выбором внутри отрезка точек u1, u2, в которых вычисляются значения [a, u2], если $$\Phi (u_1) \le \Phi (u_2)$$ или [u1, b], если $$\Phi (u_1) \ge \Phi (u_2).$$ Эту процедуру можно продолжить.
В u1, u2 выбираются близко к середине отрезка $$$ u_1 = \frac{b + a - \Delta }{2}, u_2 = \frac{b + a + \Delta }{2}, $$$ где $$\Delta$$ достаточно мало. Поскольку отношение $$$ \frac{b - u_1}{b - a},\frac{u_2 - a}{b - a} $$$ близко к 1/2, такой выбор объясняется стремлением обеспечить максимальное относительное уменьшение отрезков.
В конце вычисления в качестве приближенного значения u* берется середина последнего отрезка. В результате n итераций длина отрезка будет $$$ \Delta_n = \frac{b - a}{2^n} + (\frac{1}{2^n} + \frac{1}{2^{n - 1}} + \ldots + \frac{1}{2})\Delta = \frac{b - a}{2^n} + (1 - \frac{1}{2^n})\Delta $,$$ т.е. точность определения u* составляет $$\varepsilon _{n} = \Delta _{n}/2.$$
Находя n из условия $$\varepsilon_n \le \varepsilon ,$$ получим количество итераций, необходимое для достижения данной точности
Если в предыдущем неравенстве положить $$\Delta$$ малой, то
$$$ \varepsilon_n \approx \frac{b - a}{2^{n + 1}}. $$$Расположим точки u1, u2 на [a, b] так, чтобы одна из них стала бы также пробной, но уже на новом отрезке, после исключения части исходного отрезка. Это позволит уменьшить количество вычислений, поскольку необходимо будет вычислить значение $$\Phi (u)$$ лишь в одной из пробных точек, так как во второй оно уже известно.
Найдем расположение таких точек, для чего рассмотрим отрезок [0, 1] и, для определенности, положим, что при его уменьшении исключается его правая часть.
(рис 4.1) Пусть $$u_{2} = \tau,$$ тогда симметрично расположенная относительно центра отрезка точка имеет координату $$u_{1} = 1 - \tau$$ (рис. 4.1).
Пробная точка u1 отрезка [0, 1] перейдет в пробную точку $$u_2^1 = 1 - \tau$$ нового отрезка $$[0, \tau ].$$ Условием деления отрезков [0, 1] и $$[0, \tau ]$$ в одном и том же отношении точками $$u_{2} = \tau$$ и $$u_2^1 = 1 - \tau$$ является равенство
откуда находим положительный корень
$$$ \tau = \frac{\sqrt{5} - 1}{2} \approx 0,61803 \ldots , $$$т.е. $$$ u_1 = 1 - \tau = \frac{3 - \sqrt{5}}{2} $,$$ $$$ u_2 = \tau = \frac{\sqrt{5} - 1}{2}. $$$
Для отрезка [a, b]
Замечания.
u1, u2 обладают следующим свойством: каждая из них делит отрезок [a, b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей части. Точки, обладающие таким свойством, называются точками золотого сечения, введенного Леонардо да Винчи.$$$ \tau = \frac{\sqrt{5} - 1}{2}, $$$
поэтому в результате n итераций длина становиться равной
Следовательно, точность $$\varepsilon _{n}$$ определения точки u* после n итераций равна
а условие окончания вычислительного процесса будет $$\varepsilon_n \le \varepsilon .$$
Методы, использующие исключение отрезков, основаны на сравнении функций в двух точках пробного отрезка, учитываются лишь значения функции в этих точках.
Учесть информацию о значениях функции между точками позволяют методы полиномиальной аппроксимации. Их основная идея заключена в том, что функция $$\Phi (u)$$ аппроксимируется полиномом, а точка его минимума служит приближением к u*. Разумеется, в этом случае кроме свойства унимодальности (т.е. наличия единственного минимума на рассматриваемом отрезке), необходимо на $$\Phi (u)$$ наложить и требования достаточной гладкости для ее полиномиальной аппроксимации.
Для повышения точности поиска u* можно как увеличивать степень полинома, так и уменьшать пробный отрезок. Поскольку первый прием приводит к заметному увеличению вычислительной работы и появлению дополнительных экстремумов, обычно пользуются полиномами второй (
Алгоритм поиска минимума состоит в следующем.
Выбираем на пробном отрезке три точки u1, u2, u3 такие, что u1 < u2 < u3 и $$u_1 \le u^* \le u_3.$$
Построим параболу (квадратичный полином)
Q(u) = a0 + a1 (u - u1) + a2 (u - u1)(u - u2),
график которой проходит через точки (u1,f(u1)), (u2,f(u2)), (u3,f(u3)).
Коэффициенты ak, k = 1, 2, 3 находим из системы уравнений
Q(u1) = f(u1), Q(u2) = f(u2), Q(u3) = f(u3),
откуда
$$\begin{gather*} a_0 = f(u_1), a_1 = \frac{f(u_2) - f(u_1)}{u_2 - u_1}, \\ a_2 = \frac{1}{u_3 - u_2} \left[{\frac{f(u_3) - f(u_1)}{u_3 - u_1} - \frac{f(u_2) - f(u_1)}{u_2 - u_1}}\right]. \end{gather*}$$Точку $$$ \bar u$$$ минимума Q(u) находим, приравнивания его производную к нулю:
Далее полагаем: $$u^* \approx \bar u$$ (очередное приближение точки минимума). Эту процедуру можно продолжить до достижения необходимой точности, выбирая новые точки uk, k = 1, 2, 3. Для этого можно использовать методы исключения отрезков, используя в качестве двух пробных точек u2 и $$\bar u,$$ таких, что u2, $$\bar u \in [u_1,u_3].$$
Основная идея методов спуска состоит в том, чтобы построить алгоритм, позволяющий перейти из точки начального приближения $$u_0 = \{u_0^1, \ldots ,u_0^n\}$$ в следующую точку $$u_1 = \{u_1^1, \ldots ,u_1^n\}$$ таким
образом, чтобы значение
Этот метод является редукцией поиска функции многих переменных к
Рассмотрим $$\Phi (u_0) = \Phi (u_0^1, \ldots ,u_0^n)$$ как функцию
одной переменной u1 при фиксированных $$u_2^0, \ldots , u_n^0$$ и находим одним из приведенных методов поиска минимума функции одной переменной
Полученное значение u1, доставляющее минимум $$\Phi (u_{1}),$$ обозначим $$u_1^1$$ ; при этом
Далее, при фиксированных значениях $$u_1^1, u_3^0, \ldots , u_n^0$$ ищем
$$\min\limits_{u_2 \in U}\Phi (u_1^1,u_1^2,x_0^3, \ldots ,u_0^n ),$$как функции от u2 ; соответствующее значение u2 обозначим $$u_2^1 $$ ; при этом
Этот процесс продолжаем аналогичным образом и для оставшихся координат; в результате получим
$$\Phi (u_1^1, \ldots ,u_1^n ) \le \Phi (u_1^1, \ldots ,u_0^n).$$Таким образом, переходим из точки u0 в точку u1. Этот процесс повторяется до тех пор, пока не будет выполнено условие выхода из итераций, например:
где $$\varepsilon > 0$$ — заданная точность.
Пример. Найти минимум функции двух переменных
$$\Phi (u) = u_1^2 + u_2^2$$
(рис 4.2) Выбрав некоторую точку начального приближения, например, u0 = (2,2), получим минимум
Если же
которая поворотом системы координат на угол $$- 45^{\circ}$$ и преобразованием
$$$ u_1 = \frac{v_1 + v_2}{\sqrt{2}} ; u_2 = \frac{(- v_1 + v_2)}{\sqrt{2}} $$$приводится к виду $$\Phi^{\prime}(v) = v_1^2 + 9v_2^2,$$ то ее линиями уровня являются эллипсы $$v_1^2/9 + v_2^2 = c^2$$ поэтому спуск будет иметь иной характер (рис. 4.3).
(рис 4.3) Можно показать, что
Рельеф овражного типа имеет либо точки излома (рис. 4.4), либо участки с большей кривизной ("разрешимый овраг"). Если линии уровня — кусочно - гладкие, то выделим на них точки излома, геометрическое место которых назовем истинным "оврагом", если угол направлен в сторону возрастания функции — и "гребнем", если в сторону убывания (рис. 4.5).\vspace{- 4mm}
(рис 4.4) Примером разрешимого оврага является функция $$\Phi (u_1,u_2) = 10(u - \sin {u_1})^2 + 0,1u_1^2$$ (рис. 4.6 ).
(рис 4.6) (рис 4.5) Неупорядоченный тип рельефа характеризуется наличием многих экстремумов; примером может служить функция $$\Phi (u_{1},u_{2}) = (1 + \sin 2u_{1})x (1 + \sin 2u_{2})$$ (рис. 4.7).
(рис 4.8) (рис 4.7) Метод оврагов используется в случае, если "дно" оврага узкое, а "склоны" крутые. В этом случае спустимся из двух точек P0 и P1, например, с помощью метода координатного или r0 или r1, не требуя высокой точности сходимости. Проведем через эти две точки прямую и выберем на ней новую точку
где h = const > 0 — "овражный шаг", который
выбирается для каждой функции путем расчета (рис. 4.8). Точка лежит на "склоне" оврага. Из нее спускаемся на "дно" и попадаем в некую точку r2, через точки r1 и r2 проводим прямую и находим точку P3, из которой возможно опуститься в точку r3.
Процесс продолжается до тех пор, пока значения
Напомним, что
Построим итерационный процесс следующим образом:
$$u_{k + 1} = u_k - \tau \cdot grad \Phi , u_0 = a,$$где $$\tau$$ — шаг спуска (итерационный параметр). Итерации продолжим до выполнения заданного условия окончания процесса поиска минимума, например
$$\left\| {grad \Phi (u_{k + 1})}\right\| \le \varepsilon > 0.$$Пример. Рассмотрим функцию двух переменных $$$ \Phi (u_1,u_2) = \frac{(u^1)^2}{4} + (u^2)^2 $.$$
В соответствии с методом
Пусть начальное приближение u0 = {1;1} ; $$\tau = 0,1.$$
Тогда u1 = {0,95; 0,80} ; u2 =
{0,9025; 0,6400} ; u3 = {0,8574; 0,5120} ; $$\Phi (u_{1}) = 1,25$$ ; $$\Phi (u_{3}) = 0,446.$$
Если взять $$\tau = 2,$$ то u1 = {0; - 3} и $$\Phi (u_{1}) = 9,$$ в то время как $$\min\limits_U\Phi (u) = 0.$$ Выбор шага оказывается существенным в этом методе, поэтому чаще используются методы с переменным шагом.
В методе
В предыдущем примере выбор шага в точке u0 сводится к задаче о поиске минимума функции
откуда $$\tau = 10/9,$$ поскольку
$$$ \Phi (u^1) = \frac{1}{4}(u_0^1 - \tau\frac{u_0^1}{2})^2 + {(u_0^2 - 2\tau u_0^2)}^2 = \frac{1}{4}{(1 - \frac{\tau }{2})}^2 + {(1 - 2\tau )}^2, u_0^1 = u_0^2 = 1. $$$На следующих шагах $$\tau$$ будет зависеть от $$u_k^i , k > 0, i = 1, 2.$$
Общий случай этого метода, а также
Отметим следующее важное обстоятельство. Решение экстремальных задач в Ln зачастую сопряжено со значительными трудностями, особенно для многоэкстремальных задач. Некоторые из этих трудностей исчезают, если ограничиться рассмотрением только выпуклых функций на
Определение. Функция $$\Phi (u),$$ заданная на выпуклом множестве $$U \in L^n,$$ называется выпуклой, если для любых точек $${u,v} \in U$$ и любого $$\alpha \in \left[ {0,1}\right]$$ выполнено:
$$\Phi \left[{\alpha u + (1 - \alpha )v}\right] \le \alpha \Phi (u) + (1 - \alpha )\Phi (v).$$Определение. Функция $$\Phi (u)$$ называется строго выпуклой, если для всех $$\alpha \in (0,1)$$ выполнено строгое неравенство
$$\Phi \left[{\alpha u + (1 - \alpha )v}\right] <\alpha \Phi (u) + (1 - \alpha )\Phi (v).$$Это определение имеет наглядный геометрический смысл: график функции $$\Phi (u)$$ на интервале, соединяющем точки u, v лежит ниже
Для дважды непрерывно дифференцируемой функции $$\Phi (u)$$ положительная определенность матрицы Гессе $$\Phi ''_{u}(u)$$ есть достаточное условие строгой выпуклости.
(рис 4.9) Теорема. Пусть $$\Phi (u)$$ — выпуклая функция на
U, $$u \in U.$$ Тогда любой ее локальный минимум на U является одновременно и глобальным.
Глобальный минимум U достигается в единственной точке.
Доказательство.
Предположим противное, т.е. u0 — точка локального, а u* — глобального минимума $$\Phi (u)$$ на U, $$u^* \ne u_0$$ и $$\Phi (u_{0}) > \Phi (u^{*}).$$ Отсюда, с учетом выпуклости $$\Phi (u)$$ имеем
При $$\alpha \to + 0$$ точка $$u = \alpha u^* + (1 - \alpha )u^0$$ попадает в сколь угодно малую окрестность u0. Поэтому полученное неравенство $$\Phi (u) < \Phi (u_{0})$$ противоречит предположению о том, что u0 — точка локального минимума (первая часть теоремы доказана).
Пусть u(1), u(2) — две различные точки глобального минимума. Из строгой выпуклости $$\Phi (u)$$ следует, что для всех $$\alpha \in \left[{0,1}\right]$$ выполняется строгое неравенство $$\Phi \left[{\alpha u^{(1)} + (1 - \alpha )u^{(2)}}\right] < \alpha \Phi (u^{(1)}) + (1 - \alpha )\Phi (u^{(2)}) =\\
= \Phi * = \min\limits_U\Phi (u),$$ что противоречит предположению о
том, что u(1), u(2) — точки глобального минимума.
Под линейным программированием понимают часть экстремальных задач, рассматривающую минимизацию линейных функций и переменных при наличии дополнительных линейных условий трех типов:
$$\begin{gather*} \min\Phi (u);\Phi (u) = \sum\limits_{i = 1}^n{c_iu_i }; \\ u_i \ge 0; 1 \le i \le n; \\ \sum\limits_{i = 1}^n{a_{ij} u_i } = b_j ,1 \le j \le J_1 \\ \sum\limits_{i = 1}^n{c_{ij} u_i \le b_j } , 1_1 < j \le J_2 \\ \end{gather*} $$Каждое из этих условий определяет полупространство, ограниченное гиперплоскостью; вместе эти условия определяют выпуклый n -мерный
многогранник J', являющейся пересечением полупространств. Условия типа равенств выделяют из n - мерного пространства (n - m) -мерную плоскость. Ее пересечение с M дает выпуклый (n - m) -мерный многогранник G. Таким образом, задача состоит в том, чтобы найти минимум линейной функции $$\Phi (u)$$ в многограннике G.
G — выпуклый многогранник (возможно и неограниченный),
поэтому внутри него линейная функция $$\Phi (u)$$ не может достигать минимума. Показывается, что ее минимум, если он существует, достигается в какой-то
из его вершин. Теоретически задача линейного программирования достаточно проста: необходимо вычислить значение функций в конечном числе точек — вершинах
многогранника, сравнить их между собой и найти среди них наименьшее. Однако трудность заключается в том, что в экономических задачах количество переменных порядка $$10^{2} \div 10^{4},$$ поэтому решение оказывается достаточно
сложным.
Пример. Рассмотрим следующую простую задачу линейной оптимизации на плоскости: найти $$min\Phi (u) = c_{1}u_{1} + c_{2}u_{2}$$ при ограничениях
$$\left\{ \begin{array}{l} a_{11} u_1 + a_{12} u_2 = b_1 \\ a_{21} u_1 + a_{22} u_2 = b_2 \\ u_1 \ge 0,u_2 \ge 0. \\ \end{array} \right.$$
(рис 4.11) (рис 4.10) Неравенства $$u_1 \ge 0$$ и $$u_2 \ge 0$$ выделяют I квадрант плоскости (u1, u2), а линейная функция $$\Phi (u) = c_{1}u_{1} + c_{2}u_{2}$$ при определенных c1, c2 задает в этом квадранте семейство прямых уравнением c1u1 + c2u2 = d ( d неизвестно) (рис. 4.10).
Вообще говоря, ограничения в форме равенств могут быть следующего типа: отсутствует, одно ограничение, два ограничения (последний случай соответствуют рассматриваемому). Пусть СЛАУ в данном примере имеет единственное решение $$u^* = (u_1^*,u_2^*).$$
Если выполнены неравенства $$u_1 \ge 0, u_2 \ge 0,$$ то u* и есть решение задачи линейной оптимизации, а $$\min\Phi (u) = c_1 u_1^* + c_2 u^*_2$$ (рис. 4.11).
Если же, например, $$u_1^* < 0$$ и $$u_2^* < 0$$ то задача линейного программирования неразрешима, так как по условию решения находится внутри первого квадранта. В данном случае ограничения определяют единственное решение рассматриваемой задачи, а
Пример. Графическое решение задачи
$$\begin{gather*} \min\Phi (u) = - 3u_1 - 3u_2, \\ u_1 + 2u_2 \le 7, \\ 2u_1 + u_2 \le 8, \\ u_2 \le 3, \\ u_2 \le 3, \\ u_1 \ge 0, \\ u_2 \ge 0 \end{gather*}$$приводит к решению u* = (3, 2) и $$\Phi (u^{*}) = - 15.$$ Для решения задачи рассматриваются линии уровня функции $$\Phi (u),$$ т.е. семейство параллельных прямых - 3u1 - 3u2 = d = const.
Нормальный к этим прямым вектор $$- \Phi '_{u}(u)$$ указывает направление убывания u* является одна из вершин многогранника, образованного прямыми системы неравенств.
$$\left\{ \begin{array}{l} u - 5 \cdot 10^{- 2} e^{{uv}} = 0, \\ v - 5 \cdot 10^{- 2} e^{- (u + v)} = 0, \\ \end{array} \right.$$
к вариационной задаче в области $$\Omega = \{|u - 0,1| \le 0,1; |v - 0,1| \le 0,1\}.$$
Решение. Решение системы сводится к нахождению условий минимума
$$\Phi ({u,v}) = u^4 + v^4 - u^2 - v^2 \mbox{ в области } \Omega > \{|u| \le 1; |v| \le 1\}.$$
к решению системы алгебраических уравнений.
Решение. Задача о нахождении минимума функции $$\Phi (u,v)$$ сводится к решению системы уравнений $$$ \frac{\partial\Phi }{\partial u} = 0 $,$$ $$$ \frac{\partial\Phi }{\partial v} = 0 $.$$
{x, y}, при которых достигается минимум функции f(x,y) = x3 + y3 - 3xy.Решение. Вычислим частные производные $$$ \frac{\partial f}{\partial x} $,$$ $$$ \frac{\partial f}{\partial y} $$$ и приравняем их к нулю. Получим систему двух нелинейных уравнений 3x2 - 3y = 0, - 3x + 3y2 = 0. Решениями этой системы являются пары {0, 0}, {1, 1}. Подстановкой убеждаемся, что вторая точка является точкой глобального минимума.
f(x) = x3 + e - x - x на отрезке [0, 1] с точностью $$\varepsilon = 10^{ - 2}.$$Решение. Обозначим границы отрезка a0 = 0, b0 = 1 и зададим $$$ \frac{\Delta }{2} = \delta = 10^{- 3} $.$$
Вычислим $$$ f \left({\frac{a_0 + b_0 - \Delta }{2}}\right) \approx 0,2324 $$$ и $$$ f \left({\frac{a_0 + b_0 + \Delta }{2}}\right) \approx 0,2307 $.$$ Так как второе значение меньше первого, то положим {a1, b1 } = {0.4990, 1} . Продолжая далее, получим {a2, b2 } = {0,4990; 0,7505}, {a3, b3} = {0,6238; 0,7505}, {a4, b4} = {0,6861; 0,7505}, {a5, b5 } = {0,6861; 0,7191}, {a6, b6 } = {0,7016; 0,7191}, {a7, b7 } = {0,7101; 0,7198} .
F(t) = sin t -
cos t, t0 = - 0,5.Решение. Найдем точку минимума функции F(t) как корень уравнения F'(t) = 0. Для этого построим итерационный процесс Ньютона:
При t0 = - 0,5 имеем $$F'(t_{0}) = \cos t + \sin t \approx 0,3982,$$ $$F''(t_{0}) = - \sin t_{0} + \cos t_{0} \approx 1,3570,$$ $$$ t_1 = t_0 - \frac{0,3982}{0,1357} \approx - 0,7934 $.$$ Дальнейшие вычисления дают t2 = - 0,7854, t3 = - 0,7854.
$$\begin{gather*} f(x,y) = 3x^2 - 2x\sqrt y + y - 8x + 8, \\ f(x,y) = x^3 + 8y^3 - 6xy + 1, \\ f(x,y) = x^2 + y^2 + xy + x - y + 1, \\ f(x,y) = 2x^3 - xy^2 + 5x^2 + y^2. \end{gather*}$$
$$\begin{gather*} f(t) = 2x^2 - \ln x, \\ f(t) = \frac{t^3}{3} + t^2, \\ f(t) = \frac{t^4}{4} - 2t^2, \\ f(t) = t{\kern 1pt} e^{- \frac{t^2}{2}} , \\ f(t) = 3t^4 - 8t^3 + 6t^2, \\ f(t) = (t - 5)e^{t} , \\ f(t) = \frac{t^2 - 3}{{t + 2}}. \end{gather*}$$
используя методы дихотомии и сведения вариационной задачи к решению алгебраического уравнения.
$$\begin{gather*} f(x,y) = (x^2 + y - 11)^2 + (x + y^2 - 7)^2, \\ f(x,y) = (x^2 + y^2 - 1)^2 + (y - x\sin x)^2, \\ f(x,y) = x^3 + 8y^3 - 6xy + 1, \\ f(x,y) = (x - 3)^2 + (y - 2)^2 + (x - y - 4)^2, \\ f(x,y) = 2x^3 - xy^2 + 5x^2 + y^2 \end{gather*}$$
Определение. Пусть на множестве u, состоящем из элементов u линейного
u*, если существует его конечная $$\varepsilon$$ - окрестность, в которой выполнено$$\Phi (u^*) \le \Phi (u), \left\|{u - u^*}\right\| \le \varepsilon$$
u на элементе u* (строгий, абсолютный минимум), если имеет место равенство$$\Phi (u^*) = \inf\limits_U\Phi (u)$$
Замечание. Если u — u — n - мерное векторное пространство, имеется задача на нахождение минимума функции n переменных, если u —
Если к (4.1) или (4.2) добавляются условия
$$\begin{gather*} u_k^0 \le u_k \le u_k^1, k = 1, \ldots , K \\ F_i^0 \le \Phi_i (u) \le F_i^1, i = 1, \ldots , i, \end{gather*}$$( $$u_k^{0,1} , F_i^{0,1}$$ — числа, a $$\Phi _{i}$$ — заданные функции), то это задача поиска условного минимума, если подобные ограничения отсутствуют, то это задача поиска безусловного минимума. Причем, если функции $$\Phi _{i}(u)$$ линейны, задача поиска условного минимума называется задачей линейного программирования, если хотя бы одна из этих функций нелинейна, то имеется задача
Говорится о поиске минимума функции, не ограничивая общности, так как максимум функции $$\Phi (u)$$ является минимумом функции $$- \Phi (u).$$
$$\Phi (u)$$ называют
Отметим связь между задачами вычисления корней системы нелинейных алгебраических уравнений (СНАУ) и задачи минимизации.
Пусть на множестве $$U \in L^n$$ решается
f1(u1, ..., un) = 0, ... fn(u1, ..., un) = 0.
Определим
В области U справедливо $$\Phi (u) \ge 0,$$ причем
минимальное значение $$\Phi (u)$$ имеет при u = u*, где u* — корень рассмотренной системы. Поэтому ее решение эквивалентно поиску минимума $$\Phi (u)$$ в U. Если $$\Phi (u)$$ строго больше нуля, то система решений не имеет.
Теперь положим, что необходимо найти минимум
Точка, являющаяся решением указанной СНАУ, называется
Следующую теорему приведем без доказательства.
Теорема. Пусть функция $$\Phi (u)$$ дважды непрерывно
дифференцируема. Тогда достаточным условием того, чтобы u* была точкой локального минимума, является положительная определенность матрицы Гессе
Отметим, что методы отыскания минимума $$\Phi (u)$$ нередко оказываются более эффективными, чем методы численного решения СНАУ.
Пусть U = [a, b] , т.е. отрезок числовой оси. Разобьем его на n равных частей с узлами в точках ui = a + i(b - a)/n;
i = 0, ..., n.
Вычислив значение $$\Phi (u)$$ в этих точках, найдем путем сравнения точку u*, в которой
Далее полагаем: $$u^{*} \approx u_{min}, \Phi ^{*} \approx \Phi (u^{*}).$$ Погрешность в определении u* этого простейшего метода не превосходит числа
Этот метод прост, но неэкономичен, особенно когда ищется минимум функции многих переменных. Например, в гиперкубе $$U = \left\{{0 \le u_i \le 1,1 \le i \le 10}\right\}$$ с разбиением каждого из отрезков (по каждой из координат) на 10 частей, с быстродействием $$10^6$$ операций в секунду потребуется около 107 с (примерно 4 месяца) для нахождения $$\min\limits_U\Phi (u),$$ если предположить, что количество арифметических действий, необходимое для вычисления значений $$\Phi (u)$$ в каждой точке требует тысячи арифметических операций. Этот метод можно сделать более эффективным, если сначала определить минимум с грубым шагом, затем уже искать минимум с меньшим шагом на том из отрезков [xi, xi + 1], на котором
предполагается наличие минимума; можно и далее уточнять решение задачи таким же образом.
Усовершенствованием этого метода являются методы исключения отрезков,
дихотомии (деления отрезка пополам) и [a, b] делится на 4 части выбором внутри отрезка точек u1, u2, в которых вычисляются значения [a, u2], если $$\Phi (u_1) \le \Phi (u_2)$$ или [u1, b], если $$\Phi (u_1) \ge \Phi (u_2).$$ Эту процедуру можно продолжить.
В u1, u2 выбираются близко к середине отрезка $$$ u_1 = \frac{b + a - \Delta }{2}, u_2 = \frac{b + a + \Delta }{2}, $$$ где $$\Delta$$ достаточно мало. Поскольку отношение $$$ \frac{b - u_1}{b - a},\frac{u_2 - a}{b - a} $$$ близко к 1/2, такой выбор объясняется стремлением обеспечить максимальное относительное уменьшение отрезков.
В конце вычисления в качестве приближенного значения u* берется середина последнего отрезка. В результате n итераций длина отрезка будет $$$ \Delta_n = \frac{b - a}{2^n} + (\frac{1}{2^n} + \frac{1}{2^{n - 1}} + \ldots + \frac{1}{2})\Delta = \frac{b - a}{2^n} + (1 - \frac{1}{2^n})\Delta $,$$ т.е. точность определения u* составляет $$\varepsilon _{n} = \Delta _{n}/2.$$
Находя n из условия $$\varepsilon_n \le \varepsilon ,$$ получим количество итераций, необходимое для достижения данной точности
Если в предыдущем неравенстве положить $$\Delta$$ малой, то
$$$ \varepsilon_n \approx \frac{b - a}{2^{n + 1}}. $$$Расположим точки u1, u2 на [a, b] так, чтобы одна из них стала бы также пробной, но уже на новом отрезке, после исключения части исходного отрезка. Это позволит уменьшить количество вычислений, поскольку необходимо будет вычислить значение $$\Phi (u)$$ лишь в одной из пробных точек, так как во второй оно уже известно.
Найдем расположение таких точек, для чего рассмотрим отрезок [0, 1] и, для определенности, положим, что при его уменьшении исключается его правая часть.
(рис 4.1) Пусть $$u_{2} = \tau,$$ тогда симметрично расположенная относительно центра отрезка точка имеет координату $$u_{1} = 1 - \tau$$ (рис. 4.1).
Пробная точка u1 отрезка [0, 1] перейдет в пробную точку $$u_2^1 = 1 - \tau$$ нового отрезка $$[0, \tau ].$$ Условием деления отрезков [0, 1] и $$[0, \tau ]$$ в одном и том же отношении точками $$u_{2} = \tau$$ и $$u_2^1 = 1 - \tau$$ является равенство
откуда находим положительный корень
$$$ \tau = \frac{\sqrt{5} - 1}{2} \approx 0,61803 \ldots , $$$т.е. $$$ u_1 = 1 - \tau = \frac{3 - \sqrt{5}}{2} $,$$ $$$ u_2 = \tau = \frac{\sqrt{5} - 1}{2}. $$$
Для отрезка [a, b]
Замечания.
u1, u2 обладают следующим свойством: каждая из них делит отрезок [a, b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей части. Точки, обладающие таким свойством, называются точками золотого сечения, введенного Леонардо да Винчи.$$$ \tau = \frac{\sqrt{5} - 1}{2}, $$$
поэтому в результате n итераций длина становиться равной
Следовательно, точность $$\varepsilon _{n}$$ определения точки u* после n итераций равна
а условие окончания вычислительного процесса будет $$\varepsilon_n \le \varepsilon .$$
Методы, использующие исключение отрезков, основаны на сравнении функций в двух точках пробного отрезка, учитываются лишь значения функции в этих точках.
Учесть информацию о значениях функции между точками позволяют методы полиномиальной аппроксимации. Их основная идея заключена в том, что функция $$\Phi (u)$$ аппроксимируется полиномом, а точка его минимума служит приближением к u*. Разумеется, в этом случае кроме свойства унимодальности (т.е. наличия единственного минимума на рассматриваемом отрезке), необходимо на $$\Phi (u)$$ наложить и требования достаточной гладкости для ее полиномиальной аппроксимации.
Для повышения точности поиска u* можно как увеличивать степень полинома, так и уменьшать пробный отрезок. Поскольку первый прием приводит к заметному увеличению вычислительной работы и появлению дополнительных экстремумов, обычно пользуются полиномами второй (
Алгоритм поиска минимума состоит в следующем.
Выбираем на пробном отрезке три точки u1, u2, u3 такие, что u1 < u2 < u3 и $$u_1 \le u^* \le u_3.$$
Построим параболу (квадратичный полином)
Q(u) = a0 + a1 (u - u1) + a2 (u - u1)(u - u2),
график которой проходит через точки (u1,f(u1)), (u2,f(u2)), (u3,f(u3)).
Коэффициенты ak, k = 1, 2, 3 находим из системы уравнений
Q(u1) = f(u1), Q(u2) = f(u2), Q(u3) = f(u3),
откуда
$$\begin{gather*} a_0 = f(u_1), a_1 = \frac{f(u_2) - f(u_1)}{u_2 - u_1}, \\ a_2 = \frac{1}{u_3 - u_2} \left[{\frac{f(u_3) - f(u_1)}{u_3 - u_1} - \frac{f(u_2) - f(u_1)}{u_2 - u_1}}\right]. \end{gather*}$$Точку $$$ \bar u$$$ минимума Q(u) находим, приравнивания его производную к нулю:
Далее полагаем: $$u^* \approx \bar u$$ (очередное приближение точки минимума). Эту процедуру можно продолжить до достижения необходимой точности, выбирая новые точки uk, k = 1, 2, 3. Для этого можно использовать методы исключения отрезков, используя в качестве двух пробных точек u2 и $$\bar u,$$ таких, что u2, $$\bar u \in [u_1,u_3].$$
Основная идея методов спуска состоит в том, чтобы построить алгоритм, позволяющий перейти из точки начального приближения $$u_0 = \{u_0^1, \ldots ,u_0^n\}$$ в следующую точку $$u_1 = \{u_1^1, \ldots ,u_1^n\}$$ таким
образом, чтобы значение
Этот метод является редукцией поиска функции многих переменных к
Рассмотрим $$\Phi (u_0) = \Phi (u_0^1, \ldots ,u_0^n)$$ как функцию
одной переменной u1 при фиксированных $$u_2^0, \ldots , u_n^0$$ и находим одним из приведенных методов поиска минимума функции одной переменной
Полученное значение u1, доставляющее минимум $$\Phi (u_{1}),$$ обозначим $$u_1^1$$ ; при этом
Далее, при фиксированных значениях $$u_1^1, u_3^0, \ldots , u_n^0$$ ищем
$$\min\limits_{u_2 \in U}\Phi (u_1^1,u_1^2,x_0^3, \ldots ,u_0^n ),$$как функции от u2 ; соответствующее значение u2 обозначим $$u_2^1 $$ ; при этом
Этот процесс продолжаем аналогичным образом и для оставшихся координат; в результате получим
$$\Phi (u_1^1, \ldots ,u_1^n ) \le \Phi (u_1^1, \ldots ,u_0^n).$$Таким образом, переходим из точки u0 в точку u1. Этот процесс повторяется до тех пор, пока не будет выполнено условие выхода из итераций, например:
где $$\varepsilon > 0$$ — заданная точность.
Пример. Найти минимум функции двух переменных
$$\Phi (u) = u_1^2 + u_2^2$$(рис 4.2) Выбрав некоторую точку начального приближения, например, u0 = (2,2), получим минимум
Если же
которая поворотом системы координат на угол $$- 45^{\circ}$$ и преобразованием
$$$ u_1 = \frac{v_1 + v_2}{\sqrt{2}} ; u_2 = \frac{(- v_1 + v_2)}{\sqrt{2}} $$$приводится к виду $$\Phi^{\prime}(v) = v_1^2 + 9v_2^2,$$ то ее линиями уровня являются эллипсы $$v_1^2/9 + v_2^2 = c^2$$ поэтому спуск будет иметь иной характер (рис. 4.3).
(рис 4.3) Можно показать, что
Рельеф овражного типа имеет либо точки излома (рис. 4.4), либо участки с большей кривизной ("разрешимый овраг"). Если линии уровня — кусочно - гладкие, то выделим на них точки излома, геометрическое место которых назовем истинным "оврагом", если угол направлен в сторону возрастания функции — и "гребнем", если в сторону убывания (рис. 4.5).\vspace{- 4mm}
(рис 4.4) Примером разрешимого оврага является функция $$\Phi (u_1,u_2) = 10(u - \sin {u_1})^2 + 0,1u_1^2$$ (рис. 4.6 ).
(рис 4.6) (рис 4.5) Неупорядоченный тип рельефа характеризуется наличием многих экстремумов; примером может служить функция $$\Phi (u_{1},u_{2}) = (1 + \sin 2u_{1})x (1 + \sin 2u_{2})$$ (рис. 4.7).
(рис 4.8) (рис 4.7) Метод оврагов используется в случае, если "дно" оврага узкое, а "склоны" крутые. В этом случае спустимся из двух точек P0 и P1, например, с помощью метода координатного или r0 или r1, не требуя высокой точности сходимости. Проведем через эти две точки прямую и выберем на ней новую точку
где h = const > 0 — "овражный шаг", который
выбирается для каждой функции путем расчета (рис. 4.8). Точка лежит на "склоне" оврага. Из нее спускаемся на "дно" и попадаем в некую точку r2, через точки r1 и r2 проводим прямую и находим точку P3, из которой возможно опуститься в точку r3.
Процесс продолжается до тех пор, пока значения
Напомним, что
Построим итерационный процесс следующим образом:
$$u_{k + 1} = u_k - \tau \cdot grad \Phi , u_0 = a,$$где $$\tau$$ — шаг спуска (итерационный параметр). Итерации продолжим до выполнения заданного условия окончания процесса поиска минимума, например
$$\left\| {grad \Phi (u_{k + 1})}\right\| \le \varepsilon > 0.$$Пример. Рассмотрим функцию двух переменных $$$ \Phi (u_1,u_2) = \frac{(u^1)^2}{4} + (u^2)^2 $.$$
В соответствии с методом
Пусть начальное приближение u0 = {1;1} ; $$\tau = 0,1.$$
Тогда u1 = {0,95; 0,80} ; u2 =
{0,9025; 0,6400} ; u3 = {0,8574; 0,5120} ; $$\Phi (u_{1}) = 1,25$$ ; $$\Phi (u_{3}) = 0,446.$$
Если взять $$\tau = 2,$$ то u1 = {0; - 3} и $$\Phi (u_{1}) = 9,$$ в то время как $$\min\limits_U\Phi (u) = 0.$$ Выбор шага оказывается существенным в этом методе, поэтому чаще используются методы с переменным шагом.
В методе
В предыдущем примере выбор шага в точке u0 сводится к задаче о поиске минимума функции
откуда $$\tau = 10/9,$$ поскольку
$$$ \Phi (u^1) = \frac{1}{4}(u_0^1 - \tau\frac{u_0^1}{2})^2 + {(u_0^2 - 2\tau u_0^2)}^2 = \frac{1}{4}{(1 - \frac{\tau }{2})}^2 + {(1 - 2\tau )}^2, u_0^1 = u_0^2 = 1. $$$На следующих шагах $$\tau$$ будет зависеть от $$u_k^i , k > 0, i = 1, 2.$$
Общий случай этого метода, а также
Отметим следующее важное обстоятельство. Решение экстремальных задач в Ln зачастую сопряжено со значительными трудностями, особенно для многоэкстремальных задач. Некоторые из этих трудностей исчезают, если ограничиться рассмотрением только выпуклых функций на
Определение. Функция $$\Phi (u),$$ заданная на выпуклом множестве $$U \in L^n,$$ называется выпуклой, если для любых точек $${u,v} \in U$$ и любого $$\alpha \in \left[ {0,1}\right]$$ выполнено:
$$\Phi \left[{\alpha u + (1 - \alpha )v}\right] \le \alpha \Phi (u) + (1 - \alpha )\Phi (v).$$Определение. Функция $$\Phi (u)$$ называется строго выпуклой, если для всех $$\alpha \in (0,1)$$ выполнено строгое неравенство
$$\Phi \left[{\alpha u + (1 - \alpha )v}\right] <\alpha \Phi (u) + (1 - \alpha )\Phi (v).$$Это определение имеет наглядный геометрический смысл: график функции $$\Phi (u)$$ на интервале, соединяющем точки u, v лежит ниже
Для дважды непрерывно дифференцируемой функции $$\Phi (u)$$ положительная определенность матрицы Гессе $$\Phi ''_{u}(u)$$ есть достаточное условие строгой выпуклости.
(рис 4.9) Теорема. Пусть $$\Phi (u)$$ — выпуклая функция на
U, $$u \in U.$$ Тогда любой ее локальный минимум на U является одновременно и глобальным.
Глобальный минимум U достигается в единственной точке.
Доказательство.
Предположим противное, т.е. u0 — точка локального, а u* — глобального минимума $$\Phi (u)$$ на U, $$u^* \ne u_0$$ и $$\Phi (u_{0}) > \Phi (u^{*}).$$ Отсюда, с учетом выпуклости $$\Phi (u)$$ имеем
При $$\alpha \to + 0$$ точка $$u = \alpha u^* + (1 - \alpha )u^0$$ попадает в сколь угодно малую окрестность u0. Поэтому полученное неравенство $$\Phi (u) < \Phi (u_{0})$$ противоречит предположению о том, что u0 — точка локального минимума (первая часть теоремы доказана).
Пусть u(1), u(2) — две различные точки глобального минимума. Из строгой выпуклости $$\Phi (u)$$ следует, что для всех $$\alpha \in \left[{0,1}\right]$$ выполняется строгое неравенство $$\Phi \left[{\alpha u^{(1)} + (1 - \alpha )u^{(2)}}\right] < \alpha \Phi (u^{(1)}) + (1 - \alpha )\Phi (u^{(2)}) =\\
= \Phi * = \min\limits_U\Phi (u),$$ что противоречит предположению о
том, что u(1), u(2) — точки глобального минимума.
Под линейным программированием понимают часть экстремальных задач, рассматривающую минимизацию линейных функций и переменных при наличии дополнительных линейных условий трех типов:
$$\begin{gather*} \min\Phi (u);\Phi (u) = \sum\limits_{i = 1}^n{c_iu_i }; \\ u_i \ge 0; 1 \le i \le n; \\ \sum\limits_{i = 1}^n{a_{ij} u_i } = b_j ,1 \le j \le J_1 \\ \sum\limits_{i = 1}^n{c_{ij} u_i \le b_j } , 1_1 < j \le J_2 \\ \end{gather*} $$Каждое из этих условий определяет полупространство, ограниченное гиперплоскостью; вместе эти условия определяют выпуклый n -мерный
многогранник J', являющейся пересечением полупространств. Условия типа равенств выделяют из n - мерного пространства (n - m) -мерную плоскость. Ее пересечение с M дает выпуклый (n - m) -мерный многогранник G. Таким образом, задача состоит в том, чтобы найти минимум линейной функции $$\Phi (u)$$ в многограннике G.
G — выпуклый многогранник (возможно и неограниченный),
поэтому внутри него линейная функция $$\Phi (u)$$ не может достигать минимума. Показывается, что ее минимум, если он существует, достигается в какой-то
из его вершин. Теоретически задача линейного программирования достаточно проста: необходимо вычислить значение функций в конечном числе точек — вершинах
многогранника, сравнить их между собой и найти среди них наименьшее. Однако трудность заключается в том, что в экономических задачах количество переменных порядка $$10^{2} \div 10^{4},$$ поэтому решение оказывается достаточно
сложным.
Пример. Рассмотрим следующую простую задачу линейной оптимизации на плоскости: найти $$min\Phi (u) = c_{1}u_{1} + c_{2}u_{2}$$ при ограничениях
$$\left\{ \begin{array}{l} a_{11} u_1 + a_{12} u_2 = b_1 \\ a_{21} u_1 + a_{22} u_2 = b_2 \\ u_1 \ge 0,u_2 \ge 0. \\ \end{array} \right.$$(рис 4.11) (рис 4.10) Неравенства $$u_1 \ge 0$$ и $$u_2 \ge 0$$ выделяют I квадрант плоскости (u1, u2), а линейная функция $$\Phi (u) = c_{1}u_{1} + c_{2}u_{2}$$ при определенных c1, c2 задает в этом квадранте семейство прямых уравнением c1u1 + c2u2 = d ( d неизвестно) (рис. 4.10).
Вообще говоря, ограничения в форме равенств могут быть следующего типа: отсутствует, одно ограничение, два ограничения (последний случай соответствуют рассматриваемому). Пусть СЛАУ в данном примере имеет единственное решение $$u^* = (u_1^*,u_2^*).$$
Если выполнены неравенства $$u_1 \ge 0, u_2 \ge 0,$$ то u* и есть решение задачи линейной оптимизации, а $$\min\Phi (u) = c_1 u_1^* + c_2 u^*_2$$ (рис. 4.11).
Если же, например, $$u_1^* < 0$$ и $$u_2^* < 0$$ то задача линейного программирования неразрешима, так как по условию решения находится внутри первого квадранта. В данном случае ограничения определяют единственное решение рассматриваемой задачи, а
Пример. Графическое решение задачи
$$\begin{gather*} \min\Phi (u) = - 3u_1 - 3u_2, \\ u_1 + 2u_2 \le 7, \\ 2u_1 + u_2 \le 8, \\ u_2 \le 3, \\ u_2 \le 3, \\ u_1 \ge 0, \\ u_2 \ge 0 \end{gather*}$$приводит к решению u* = (3, 2) и $$\Phi (u^{*}) = - 15.$$ Для решения задачи рассматриваются линии уровня функции $$\Phi (u),$$ т.е. семейство параллельных прямых - 3u1 - 3u2 = d = const.
Нормальный к этим прямым вектор $$- \Phi '_{u}(u)$$ указывает направление убывания u* является одна из вершин многогранника, образованного прямыми системы неравенств.
$$\left\{ \begin{array}{l} u - 5 \cdot 10^{- 2} e^{{uv}} = 0, \\ v - 5 \cdot 10^{- 2} e^{- (u + v)} = 0, \\ \end{array} \right.$$
к вариационной задаче в области $$\Omega = \{|u - 0,1| \le 0,1; |v - 0,1| \le 0,1\}.$$
Решение. Решение системы сводится к нахождению условий минимума
$$\Phi ({u,v}) = u^4 + v^4 - u^2 - v^2 \mbox{ в области } \Omega > \{|u| \le 1; |v| \le 1\}.$$
к решению системы алгебраических уравнений.
Решение. Задача о нахождении минимума функции $$\Phi (u,v)$$ сводится к решению системы уравнений $$$ \frac{\partial\Phi }{\partial u} = 0 $,$$ $$$ \frac{\partial\Phi }{\partial v} = 0 $.$$
{x, y}, при которых достигается минимум функции f(x,y) = x3 + y3 - 3xy.Решение. Вычислим частные производные $$$ \frac{\partial f}{\partial x} $,$$ $$$ \frac{\partial f}{\partial y} $$$ и приравняем их к нулю. Получим систему двух нелинейных уравнений 3x2 - 3y = 0, - 3x + 3y2 = 0. Решениями этой системы являются пары {0, 0}, {1, 1}. Подстановкой убеждаемся, что вторая точка является точкой глобального минимума.
f(x) = x3 + e - x - x на отрезке [0, 1] с точностью $$\varepsilon = 10^{ - 2}.$$Решение. Обозначим границы отрезка a0 = 0, b0 = 1 и зададим $$$ \frac{\Delta }{2} = \delta = 10^{- 3} $.$$
Вычислим $$$ f \left({\frac{a_0 + b_0 - \Delta }{2}}\right) \approx 0,2324 $$$ и $$$ f \left({\frac{a_0 + b_0 + \Delta }{2}}\right) \approx 0,2307 $.$$ Так как второе значение меньше первого, то положим {a1, b1 } = {0.4990, 1} . Продолжая далее, получим {a2, b2 } = {0,4990; 0,7505}, {a3, b3} = {0,6238; 0,7505}, {a4, b4} = {0,6861; 0,7505}, {a5, b5 } = {0,6861; 0,7191}, {a6, b6 } = {0,7016; 0,7191}, {a7, b7 } = {0,7101; 0,7198} .
F(t) = sin t -
cos t, t0 = - 0,5.Решение. Найдем точку минимума функции F(t) как корень уравнения F'(t) = 0. Для этого построим итерационный процесс Ньютона:
При t0 = - 0,5 имеем $$F'(t_{0}) = \cos t + \sin t \approx 0,3982,$$ $$F''(t_{0}) = - \sin t_{0} + \cos t_{0} \approx 1,3570,$$ $$$ t_1 = t_0 - \frac{0,3982}{0,1357} \approx - 0,7934 $.$$ Дальнейшие вычисления дают t2 = - 0,7854, t3 = - 0,7854.
$$\begin{gather*} f(x,y) = 3x^2 - 2x\sqrt y + y - 8x + 8, \\ f(x,y) = x^3 + 8y^3 - 6xy + 1, \\ f(x,y) = x^2 + y^2 + xy + x - y + 1, \\ f(x,y) = 2x^3 - xy^2 + 5x^2 + y^2. \end{gather*}$$
$$\begin{gather*} f(t) = 2x^2 - \ln x, \\ f(t) = \frac{t^3}{3} + t^2, \\ f(t) = \frac{t^4}{4} - 2t^2, \\ f(t) = t{\kern 1pt} e^{- \frac{t^2}{2}} , \\ f(t) = 3t^4 - 8t^3 + 6t^2, \\ f(t) = (t - 5)e^{t} , \\ f(t) = \frac{t^2 - 3}{{t + 2}}. \end{gather*}$$
используя методы дихотомии и сведения вариационной задачи к решению алгебраического уравнения.
$$\begin{gather*} f(x,y) = (x^2 + y - 11)^2 + (x + y^2 - 7)^2, \\ f(x,y) = (x^2 + y^2 - 1)^2 + (y - x\sin x)^2, \\ f(x,y) = x^3 + 8y^3 - 6xy + 1, \\ f(x,y) = (x - 3)^2 + (y - 2)^2 + (x - y - 4)^2, \\ f(x,y) = 2x^3 - xy^2 + 5x^2 + y^2 \end{gather*}$$
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.