Реферат: Выбор оптимального места строительства очистного сооружения

--PAGE_BREAK--1.1 Градиентные методы
Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом <img border=«0» width=«46» height=«15» src=«ref-2_1810015808-317.coolpic» alt="-\nabla F" v:shapes="_x0000_i1040">:

<img border=«0» width=«245» height=«24» src=«ref-2_1810016125-1084.coolpic» alt="\overrightarrow{x}^{[j+1]}=\overrightarrow{x}^{[j]}-\lambda^{[j]}\nabla F(\overrightarrow{x}^{[j]}) " v:shapes="_x0000_i1041">

где λ[j] выбирается

·                     постоянной, в этом случае метод может расходиться;

·                     дробным шагом, то есть длина шага в процессе спуска делится на некое число;

·                     наискорейшим спуском: <img border=«0» width=«303» height=«24» src=«ref-2_1810017209-1434.coolpic» alt="\lambda^{[j]}=\mathrm{argmin}_{\lambda} \,F(\vec{x}^{[j]}-\lambda^{[j]}\nabla F(\vec{x}^{[j]})) " v:shapes="_x0000_i1042">
1.2 Метод наискорейшего спуска (метод градиента)
Выбирают <img border=«0» width=«98» height=«45» src=«ref-2_1810018643-716.coolpic» alt=«v^{[j]}_i = -\frac{\partial F}{\partial x_i}» v:shapes="_x0000_i1043">, где все производные вычисляются при <img border=«0» width=«67» height=«26» src=«ref-2_1810019359-447.coolpic» alt=«x_i = x^{[j]}_i» v:shapes="_x0000_i1044">, и уменьшают длину шага λ[j] по мере приближения к минимуму функции F.

Для аналитических функций F и малых значений fi тейлоровское разложение F(λ[j]) позволяет выбрать оптимальную величину шага

<img border=«0» width=«257» height=«59» src=«ref-2_1810019806-1943.coolpic» alt="\lambda^{[j]}=\frac{\sum_{k=1}^n(\frac{\partial F}{\partial x_k})^2}{\sum_{k=1}^n\sum_{h=1}^n\frac{\partial^2 F}{\partial x_kdx_h}\frac{\partial F}{\partial x_k}\frac{\partial F}{\partial x_h}}" v:shapes="_x0000_i1045">(5)

где все производные вычисляются при <img border=«0» width=«67» height=«26» src=«ref-2_1810019359-447.coolpic» alt=«x_i = x^{[j]}_i» v:shapes="_x0000_i1046">. Параболическая интерполяция функции F(λ[j]) может оказаться более удобной.
Алгоритм

1.                 Задаются начальное приближение и точность расчёта <img border=«0» width=«55» height=«22» src=«ref-2_1810022196-354.coolpic» alt="\vec{x}^0, \quad \epsilon" v:shapes="_x0000_i1047">

2.                 Рассчитывают <img border=«0» width=«245» height=«24» src=«ref-2_1810016125-1084.coolpic» alt="\overrightarrow{x}^{[j+1]}=\overrightarrow{x}^{[j]}-\lambda^{[j]}\nabla F(\overrightarrow{x}^{[j]}) " v:shapes="_x0000_i1048">, где <img border=«0» width=«303» height=«24» src=«ref-2_1810017209-1434.coolpic» alt="\lambda^{[j]}=\mathrm{argmin}_{\lambda} \,F(\vec{x}^{[j]}-\lambda^{[j]}\nabla F(\vec{x}^{[j]})) " v:shapes="_x0000_i1049">

3.                 Проверяют условие останова:

o                     Если <img border=«0» width=«138» height=«24» src=«ref-2_1810025068-686.coolpic» alt="|\vec{x}^{[j+1]}-\vec{x}^{[j]}|>\epsilon" v:shapes="_x0000_i1050">, то j = j + 1 и переход к шагу 2.

o                     Иначе <img border=«0» width=«80» height=«19» src=«ref-2_1810025754-443.coolpic» alt="\vec{x}=\vec{x}^{[j+1]}" v:shapes="_x0000_i1051">и останов.
1.3 Метод покоординатного спуска (Гаусса—Зейделя)
Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые <img border=«0» width=«41» height=«15» src=«ref-2_1810026197-303.coolpic» alt="\lambda \quad n" v:shapes="_x0000_i1052">раз за один шаг.
Алгоритм

1.                 Задаются начальное приближение и точность расчёта <img border=«0» width=«55» height=«24» src=«ref-2_1810026500-391.coolpic» alt="\vec{x}^0_0, \quad \epsilon" v:shapes="_x0000_i1053">

2.                 Рассчитывают <img border=«0» width=«278» height=«98» src=«ref-2_1810026891-3155.coolpic» alt="\left\{\begin{array}{lcr}\vec{x}^{[j]}_1 & = & \vec{x}^{[j]}_0-\lambda^{[j]}_1\frac{\partial F(\vec{x}^{[j]}_0)}{\partial x_1}\vec{e}_1 \\\ldots & & \\\vec{x}^{[j]}_n & = & \vec{x}^{[j]}_{n-1}-\lambda^{[j]}_n\frac{\partial F(\vec{x}^{[j]}_{n-1})}{\partial x_n}\vec{e}_n \end{array} \right. " v:shapes="_x0000_i1054">, где <img border=«0» width=«351» height=«61» src=«ref-2_1810030046-2337.coolpic» alt="\lambda^{[j]}_i=\mathrm{argmin}_{\lambda} \,F\left( \vec{x}^{[j]}_{i-1}-\lambda^{[j]}\frac{\partial F(\vec{x}^{[j]}_{i-1})}{\partial x_{i-1}} \vec{e}_i \right) " v:shapes="_x0000_i1055">

3.                 Проверяют условие останова:

o                     Если <img border=«0» width=«120» height=«27» src=«ref-2_1810032383-730.coolpic» alt="|\vec{x}^{[j]}_n-\vec{x}^{[j]}_0|>\epsilon" v:shapes="_x0000_i1056">, то <img border=«0» width=«203» height=«27» src=«ref-2_1810033113-844.coolpic» alt="\vec{x}^{[j+1]}_0=\vec{x}^{[j]}_n,\quad j=j+1" v:shapes="_x0000_i1057">и переход к шагу 2.

o                     Иначе <img border=«0» width=«62» height=«24» src=«ref-2_1810033957-428.coolpic» alt="\vec{x}=\vec{x}^{[j]}_n" v:shapes="_x0000_i1058">и останов.
    продолжение
--PAGE_BREAK--1.4 Метод сопряжённых градиентов
Метод сопряженных градиентов— метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в <img border=«0» width=«23» height=«15» src=«ref-2_1810034385-298.coolpic» alt="\mathbb{R}^n" v:shapes="_x0000_i1059">минимум находится за n шагов.

Определим терминологию:

Пусть <img border=«0» width=«172» height=«24» src=«ref-2_1810034683-820.coolpic» alt="\vec{S_1},\ldots,\vec{S_n} \in \mathbb{X} \subset \mathbb{R}^n\!" v:shapes="_x0000_i1060">.

Введём на <img border=«0» width=«14» height=«14» src=«ref-2_1810035503-254.coolpic» alt="\mathbb{X}\!" v:shapes="_x0000_i1061">целевую функцию <img border=«0» width=«112» height=«23» src=«ref-2_1810035757-763.coolpic» alt=«f(\vec{x})\in \mathrm{C^2}(\mathbb{X})\!» v:shapes="_x0000_i1062">.

Вектора <img border=«0» width=«83» height=«24» src=«ref-2_1810036520-491.coolpic» alt="\vec{S_1},\ldots,\vec{S_n}\!" v:shapes="_x0000_i1063">называются сопряжёнными, если:

·                     <img border=«0» width=«313» height=«29» src=«ref-2_1810037011-1156.coolpic» alt="\vec{S_i}^T H \vec{S_j}=0, \quad i\neq j, \quad i,j=1,\ldots,n\!" v:shapes="_x0000_i1064">

·                     <img border=«0» width=«225» height=«27» src=«ref-2_1810038167-954.coolpic» alt="\vec{S_i}^T H \vec{S_i}\geqslant 0, \quad i=1,\ldots,n\!" v:shapes="_x0000_i1065">

где <img border=«0» width=«18» height=«14» src=«ref-2_1810039121-258.coolpic» alt=«H\!» v:shapes="_x0000_i1066">— матрица Гессе <img border=«0» width=«36» height=«20» src=«ref-2_1810039379-400.coolpic» alt=«f(\vec{x})\!» v:shapes="_x0000_i1067">.
1.4.1 Обоснование метода Нулевая итерация

<img border=«0» width=«300» height=«446» src=«ref-2_1810040520-10264.coolpic» v:shapes="_x0000_i1071">
Рисунок 2 — Иллюстрация последовательных приближений метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная ломаная) к точке экстремума.

Пусть <img border=«0» width=«186» height=«25» src=«ref-2_1810050784-833.coolpic» alt="\vec{S_0}=-\nabla f(\vec{x_0})\qquad (1)\!" v:shapes="_x0000_i1072">

Тогда <img border=«0» width=«190» height=«25» src=«ref-2_1810051617-830.coolpic» alt="\vec{x_1}=\vec{x_0}+\lambda_1 \vec{S_0} \qquad (2)\!" v:shapes="_x0000_i1073">.

Определим направление <img border=«0» width=«186» height=«25» src=«ref-2_1810052447-923.coolpic» alt="\vec{S_1}=-\nabla f(\vec{x_1})+\omega_1 \vec{S_0}\!" v:shapes="_x0000_i1074">так, чтобы оно было сопряжено с <img border=«0» width=«18» height=«24» src=«ref-2_1810053370-308.coolpic» alt="\vec{S_0}\!" v:shapes="_x0000_i1075">:

<img border=«0» width=«167» height=«28» src=«ref-2_1810053678-848.coolpic» alt="\vec{S_0}^T H \vec{S_1}=0 \qquad (3)\!" v:shapes="_x0000_i1076">

Разложим <img border=«0» width=«52» height=«20» src=«ref-2_1810054526-468.coolpic» alt="\nabla f(\vec{x})\!" v:shapes="_x0000_i1077">в окрестности <img border=«0» width=«18» height=«19» src=«ref-2_1810054994-286.coolpic» alt="\vec{x_0}\!" v:shapes="_x0000_i1078">и подставим <img border=«0» width=«54» height=«18» src=«ref-2_1810055280-348.coolpic» alt="\vec{x}=\vec{x_1}\!" v:shapes="_x0000_i1079">:

<img border=«0» width=«355» height=«25» src=«ref-2_1810055628-1544.coolpic» alt="\nabla f(\vec{x_1})-\nabla f(\vec{x_0})=H \, (\vec{x_1}-\vec{x_0})=\lambda_1 H \vec{S_0}\!" v:shapes="_x0000_i1080">

Транспонируем полученное выражение и домножаем на <img border=«0» width=«34» height=«18» src=«ref-2_1810057172-302.coolpic» alt=«H^{-1}\!» v:shapes="_x0000_i1081">справа:

<img border=«0» width=«351» height=«28» src=«ref-2_1810057474-1590.coolpic» alt="(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}=\lambda_1 \vec{S_0}^T H^T H^{-1}\!" v:shapes="_x0000_i1082">

В силу непрерывности вторых частных производных <img border=«0» width=«72» height=«18» src=«ref-2_1810059064-398.coolpic» alt=«H^T=H\!» v:shapes="_x0000_i1083">. Тогда:

<img border=«0» width=«271» height=«47» src=«ref-2_1810059462-1469.coolpic» alt="\vec{S_0}^T=\frac{(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}}{\lambda_1}\!" v:shapes="_x0000_i1084">

Подставим полученное выражение в (3):

<img border=«0» width=«287» height=«51» src=«ref-2_1810060931-1584.coolpic» alt="\frac{(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}H\vec{S_1}}{\lambda_1}=0\!" v:shapes="_x0000_i1085">

Тогда, воспользовавшись (1) и (2):

<img border=«0» width=«481» height=«23» src=«ref-2_1810062515-1905.coolpic» alt="(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T (-\nabla f(\vec{x_1})-\omega_1\nabla f(\vec{x_0})))=0\qquad (4)\!" v:shapes="_x0000_i1086">

Если <img border=«0» width=«202» height=«33» src=«ref-2_1810064420-1130.coolpic» alt="\lambda=\arg\min_\lambda f(\vec{x_0}+\lambda \vec{S_0})\!" v:shapes="_x0000_i1087">, то градиент в точке <img border=«0» width=«119» height=«24» src=«ref-2_1810065550-637.coolpic» alt="\vec{x_1}=\vec{x_0}+\lambda \vec{S_0}\!" v:shapes="_x0000_i1088">перпендикулярен градиенту в точке <img border=«0» width=«18» height=«19» src=«ref-2_1810054994-286.coolpic» alt="\vec{x_0}\!" v:shapes="_x0000_i1089">, тогда по правилам скалярного произведения векторов:

<img border=«0» width=«183» height=«20» src=«ref-2_1810066473-994.coolpic» alt="(\nabla f(\vec{x_0}),\nabla f(\vec{x_1}))=0\!" v:shapes="_x0000_i1090">

Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления <img border=«0» width=«12» height=«9» src=«ref-2_1810067467-222.coolpic» alt="\omega\!" v:shapes="_x0000_i1091">:

<img border=«0» width=«141» height=«48» src=«ref-2_1810067689-1181.coolpic» alt="\omega_1=\frac{||\nabla f(\vec{x_1})||^2}{||\nabla f(\vec{x_0})||^2}\!" v:shapes="_x0000_i1092">
    продолжение
--PAGE_BREAK--