Wiki ТНТУ - Внесок користувача [uk]

Метод Девідона – Флетчера – Пауела

2012-03-06T13:02:47Z

Ulllasya:

Рототабельне планування

2012-03-06T12:26:24Z

Ulllasya:

{{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}}
{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНм-51
|-
| '''Залікова книжка''' || СНм-11-253
|}

= [[Рототабельне планування]] =

У зв'язку з тим, що дисперсії коефіцієнтів рівняння регресії при ОЦКП нерівномірні, ортогональність матриці часто не є досить сильним критерієм оптимальності планування другого порядку. Його заміняють критерієм ротоптабельності, тобто однаковості дисперсій коефіцієнтів при повороті координатних осей на будь-який кут. Зазначимо, що при плануванні першого порядку ортогональність матриці просто збігається з її рототабельністю, тому ПФЕ доцільно називати рототабельним.
Щоб зробити план другого порядку рототабельним, вибирають для сфери, на якій розташовуються зіркові точки, радіус (зіркове плече) за формулою

<center><math>\alpha ={{2}^{n/2}}.</math></center>

Інша умова рототабельності — збільшення числа дослідів на поверхні нульової сфери, тобто в центрі плану. У зв'язку з цим виникає повна назва методу: ''центральне композиційне рототабельне планування'' (ЦКРП).
Таким чином ЦКРП багато в чому нагадує ортогональне планування, проте метод рототабельного планування експерименту дає змогу дістати точніший математичний опис поверхні відклику порівняно з ОЦКП, завдяки збільшенню числа дослідів у центрі плану і спеціальному вибору величини зіркового плеча α.
Як і для ОЦКП, основні характеристики матриць рототабельного планування табульовані (табл. 1). При ЦКРП, починаючи з n = 5, можна застосувати ДФЕ(дробовий факторний експеримент).

<table width="90%" border="1">

<tr>
<th scope="col">n </th>
<th scope="col"><math>{{\operatorname{N}}_{n}}</math> </th>
<th scope="col"><math>{{\operatorname{N}}_{\alpha }}</math> </th>
<th scope="col"><math>{{\operatorname{N}}_{0}}</math> </th>
<th scope="col">N </th>
<th scope="col"><math>\alpha </math> </th>
</tr>
<tr>
<td>2 </td>
<td>5 </td>
<td>4 </td>
<td>4 </td>
<td>13 </td>
<td>1,414 </td>
</tr>
<tr>
<td>3 </td>
<td>6 </td>
<td>8 </td>
<td>6 </td>
<td>20 </td>
<td>1,680 </td>
</tr>
<tr>
<td>4 </td>
<td>7 </td>
<td>16 </td>
<td>8 </td>
<td>31 </td>
<td>2,000 </td>
</tr>
<tr>
<td>5 </td>
<td>10 </td>
<td>32 </td>
<td>10 </td>
<td>52 </td>
<td>2,378 </td>
</tr>
<tr>
<td>6 </td>
<td>15 </td>
<td>64 </td>
<td>12 </td>
<td>91 </td>
<td>1,828 </td>
</tr>
<tr>
<td>7 </td>
<td>21 </td>
<td>128 </td>
<td>14 </td>
<td>163 </td>
<td>1,333 </td>
</tr>
</table>
<caption>
Таблиця 1 – Підготовка ЦКРП другого порядку
</caption>
При рототабельному плануванні для обчислення коефіцієнтів моделі і відповідних оцінок дисперсій знаходять спеціальні комплекси:

<center><math>\begin{align}
& B=\frac{nN}{(n+2)(N-{{N}_{0}})}; \\
& A=\frac{1}{2B[(n+2)B-n]}; \\
& C=\frac{N}{N-{{N}_{0}}}, \\
\end{align}</math></center>

де n-число факторів; N-загальне число дослідів у плануванні; N0-число дослідів у центрі плану.
За результатами експериментів обчислюють такі суми:

<center><math>\begin{align}
& {{S}_{0}}=\sum\limits_{g=1}^{N}{{{y}_{g}}}; \\
& {{S}_{i}}=\sum\limits_{g=1}^{N}{{{y}_{g}}}{{z}_{gi}};i=1,2,...,n; \\
& {{S}_{ik}}=\sum\limits_{g=1}^{N}{{{z}_{gi}}{{z}_{gk}}{{y}_{g}}};i\ne k; \\
& {{S}_{ii}}=\sum\limits_{g=1}^{N}{z_{gi}^{2}{{y}_{g}}};i=1,2,...,n. \\
\end{align}</math></center>

Коефіцієнти моделі тут розраховують за формулами

<center><math>\begin{align}
& {{b}_{0}}=\frac{2AB}{N}[{{S}_{0}}B(n+2)-C\sum{{{S}_{ii}}}]; \\
& {{b}_{i}}=\frac{C{{S}_{i}}}{N}; \\
& {{b}_{ik}}=\frac{{{C}^{2}}{{S}_{ik}}}{BN},i\ne k; \\
& {{b}_{ii}}=\frac{AC}{N}\{{{S}_{ii}}[B(n+2)-n]+C(1-B)\sum\limits_{i=1}^{n}{{{S}_{ii}}-2B{{S}_{0}}}\}. \\
& \\
\end{align}</math></center>

Оцінки дисперсій для обчислених коефіцієнтів знаходять за такими формулами:

<center><math>\begin{align}
& S_{b0}^{2}=\frac{2AB(n+2)}{N}S_{y}^{2}; \\
& S_{bi}^{2}=\frac{S_{y}^{2}}{N-{{N}_{0}}};i=1,2,...,n; \\
& S_{bik}^{2}=\frac{{{C}^{2}}S_{y}^{2}}{N},i\ne k; \\
& {{S}_{bii}}=\frac{A{{C}^{2}}S_{y}^{2}}{N}[B(n+1)-(n-1)]. \\
\end{align}</math></center>

У цих формулах дисперсія відтворюваності <math>S_{y}^{2}</math> визначається за результатами дослідів у нульовій точці

<center><math>\begin{align}
& S_{y}^{2}=\frac{1}{{{N}_{0}}-1}\sum\limits_{g=1}^{{{N}_{0}}}{{{({{y}_{ge}}-\overset{-}{y}\,)}^{2}}}; \\
& \overset{-}{y}\,=\frac{1}{{{N}_{0}}}\sum\limits_{g=1}^{{{N}_{0}}}{{{y}_{ge.}}} \\
\end{align}</math></center>

Дисперсія адекватності оцінюється за формулою

<center><math>S_{adekv}^{2}=\frac{\sum\limits_{g=1}^{N}{{{({{y}_{ge}}-{{y}_{grozr}})}^{2}}-S_{y}^{2}({{N}_{0}}-1)}}{N-\frac{(n+2)(n+1)}{2}(N-1)},</math></center>

якшо число ступенів вільності

<center><math>{{f}_{adekv}}={{N}_{0}}-\frac{(n+2)(n+1)}{2}-({{N}_{0}}-1).</math></center>
==Приклад==

Скласти матрицю ЦКРП на прикладі побудови математичної моделі технологічного процесу крупоутворення (див.: Пищевая технология.— 1976.— № 4.— С. 121—124).

'''Розв'язання'''. Як функції відклику прийнято <math>y_1</math>, % — середня зольність крупи пшениці після перших трьох систем для дертя (швидкість обертання рифлених вальців усіх систем 6 м/с); <math>y_2</math>, % — сумарний вихід всіх крупок, які добуваються в процесі крупоутворення; <math>y_3</math>, кДж/(кг • %) — витрата енергії на одержання 1 % продукту з 1 кг зерна.
Незалежними змінними є, %: <math>x_1</math> — вихід крупи на першій системі для дертя; <math>x_2</math> — те ж на другій системі; <math>x_3</math> — те ж, для трьох систем для дертя. Інтервал варіювання для всіх <math>x_i</math>, вибрано з умови охоплення області їхньої реальної зміни. Рівні змінних становили, %:

<table width="90%" border="1">
<tr>
<th scope="col">Незалежні змінні </th>
<th scope="col">Нижній </th>
<th scope="col">Основний </th>
<th scope="col">Верхній </th>
</tr>
<tr>
<th scope="row"><math>X_1</math> </th>
<td><center>5</center> </td>
<td><center>10</center> </td>
<td><center>15</center> </td>
</tr>
<tr>
<th scope="row"><math>X_2</math> </th>
<td><center>30</center> </td>
<td><center>40</center> </td>
<td><center>50</center> </td>
</tr>
<tr>
<th scope="row"><math>X_3</math> </th>
<td><center>65</center> </td>
<td><center>70</center> </td>
<td><center>75</center> </td>
</tr>
</table>

У зв'язку з тим, що режими крупоутворення вивчалися досить детально, стало можливим ставити експерименти в області факторного простору, для якої значення всіх у близькі до оптимальних, а для опису цієї області застосувати відразу планування другого порядку. Було реалізовано центральний композиційний рототабельний план, який включає ПФЕ <math>2^3</math>, шість зіркових та шість центральних точок. Послідовність проведення дослідів була рандомізована, кожен дослід проводився тричі. У табл. 2 наведено матрицю планування та середні значення функцій відклику для кожного її рядка.
За вищенаведеними формулами розраховані такі коефіцієнти в рівняннях регресії для всіх функцій відклику:

<center>
<math>\begin{align}
& {{y}_{1}}=0,65+0,0084{{z}_{1}}+0,0048{{z}_{2}}+0,0630{{z}_{3}}+0,0150{{z}_{1}}{{z}_{2}}-0,0050{{z}_{1}}{{z}_{3}}- \\
& -0,0400{{z}_{2}}{{z}_{3}}+0,0038z_{1}^{2}+0,0076z_{2}^{2}+0,0314z_{3}^{2}; \\
& {{y}_{2}}=43,5+1,37{{z}_{1}}+0,34{{z}_{2}}+0,89{{z}_{3}}-1,41{{z}_{1}}{{z}_{2}}-0,61{{z}_{1}}{{z}_{3}}+ \\
& +0,74{{z}_{2}}{{z}_{3}}-0,83z_{1}^{2}-1,71z_{2}^{2}-1,52z_{3}^{2}; \\
& {{y}_{3}}=6,4-0,28{{z}_{1}}-0,11{{z}_{2}}+0,61{{z}_{3}}+0,03{{z}_{1}}{{z}_{2}}-0,03{{z}_{1}}{{z}_{3}}- \\
& -0,05{{z}_{2}}{{z}_{3}}+0,33z_{1}^{2}+0,68z_{2}^{2}+0,69z_{3}^{2}. \\
\end{align}</math>
</center>

Оцінки дисперсій для коефіцієнтів у цих рівняннях наведено в табл. 3.
Коефіцієнти при <math>z^2</math> на порядок перевищують помилку в їхньому визначенні для всіх функцій відклику, отже, лінійними рівняннями описати їх не можна. Адекватність утворених нелінійних рівнянь було перевірено за F-критерієм.

<table width="90%" border="1">

<tr>
<th scope="col"> </th>
<th scope="col"><math>z_0</math> </th>
<th scope="col"><math>z_1</math> </th>
<th scope="col"><math>z_2</math> </th>
<th scope="col"><math>z_3</math> </th>
<th scope="col"><math>z_1^2</math> </th>
<th scope="col"><math>z_2^2</math> </th>
<th scope="col"><math>z_3^2</math> </th>
<th scope="col"><math>z_1*z_2</math> </th>
<th scope="col"><math>z_1*z_3</math> </th>
<th scope="col"><math>z_2*z_3</math> </th>
<th scope="col"><math>y_1c</math> </th>
<th scope="col"><math>y_2c</math> </th>
<th scope="col"><math>y_3c</math> </th>
</tr>
<tr>
<td><center>1</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>0,75</center> </td>
<td><center>40,5</center> </td>
<td><center>8,4</center> </td>
</tr>
<tr>
<td><center>2</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>0,68</center> </td>
<td><center>36,7</center> </td>
<td><center>7,3</center> </td>
</tr>
<tr>
<td><center>3</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>0,78</center> </td>
<td><center>41,3</center> </td>
<td><center>8,7</center> </td>
</tr>
<tr>
<td><center>4</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>0,61</center> </td>
<td><center>42,7</center> </td>
<td><center>7,3</center> </td>
</tr>
<tr>
<td><center>5</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>0,72</center> </td>
<td><center>41,0</center> </td>
<td><center>8,7</center> </td>
</tr>
<tr>
<td><center>6</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>0,61</center> </td>
<td><center>37,0</center> </td>
<td><center>7,9</center> </td>
</tr>
<tr>
<td><center>7</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>0,78</center> </td>
<td><center>38,2</center> </td>
<td><center>9,2</center> </td>
</tr>
<tr>
<td><center>8</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>0,62</center> </td>
<td><center>34,9</center> </td>
<td><center>8,0</center> </td>
</tr>
<tr>
<td><center>9</center> </td>
<td><center>+</center> </td>
<td><center>+1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,67</center> </td>
<td><center>44,7</center> </td>
<td><center>6,8</center> </td>
</tr>
<tr>
<td><center>10</center> </td>
<td><center>+</center> </td>
<td><center>-1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,66</center> </td>
<td><center>39,4</center> </td>
<td><center>7,7</center> </td>
</tr>
<tr>
<td><center>11</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>+1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,86</center> </td>
<td><center>40,7</center> </td>
<td><center>9,3</center> </td>
</tr>

<tr>
<td><center>12</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>-1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,65</center> </td>
<td><center>37,8</center> </td>
<td><center>8,5</center> </td>
</tr>
<tr>
<td><center>13</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,86</center> </td>
<td><center>40,7</center> </td>
<td><center>9,3</center> </td>
</tr>
<tr>
<td><center>14</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>-1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,63</center> </td>
<td><center>39,3</center> </td>
<td><center>7,0</center> </td>
</tr>
<tr>
<td><center>15</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,65</center> </td>
<td><center>41,6</center> </td>
<td><center>6,4</center> </td>
</tr>
<tr>
<td><center>16</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,63</center> </td>
<td><center>42,7</center> </td>
<td><center>6,6</center> </td>
</tr>
<tr>
<td><center>17</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,66</center> </td>
<td><center>44,5</center> </td>
<td><center>6,2</center> </td>
</tr>
<tr>
<td><center>18</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,66</center> </td>
<td><center>42,9</center> </td>
<td><center>6,1</center> </td>
</tr>
<tr>
<td><center>19</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,65</center> </td>
<td><center>44,5</center> </td>
<td><center>6,8</center> </td>
</tr>
<tr>
<td><center>20</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,65</center> </td>
<td><center>44,0</center> </td>
<td><center>6,5</center> </td>
</tr>
</table>
<caption>
Таблиця 2 – Реалізація матриці ЦКРП другого порядку
</caption>

<table width="90%" border="1">

<tr>
<th scope="col"><math>{{\operatorname{y}}_{i}}</math> </th>
<th scope="col"><math>{{\operatorname{S}}_{b0}}</math> </th>
<th scope="col"><math>{{\operatorname{S}}_{b1}}</math> </th>
<th scope="col"><math>{{\operatorname{S}}_{b2}}</math> </th>
<th scope="col"><math>{{\operatorname{S}}_{b3}}</math> </th>
</tr>
<tr>
<td><math>y_1</math> </td>
<td>0,0053 </td>
<td>0,0035 </td>
<td>0,0034 </td>
<td>0,0046 </td>
</tr>
<tr>
<td><math>y_2</math> </td>
<td>0,48 </td>
<td>0,31 </td>
<td>0,30 </td>
<td>0,41 </td>
</tr>
<tr>
<td><math>y_3</math> </td>
<td>0,13 </td>
<td>0,8 </td>
<td>0,8 </td>
<td>0,11 </td>
</tr>

</table>
<caption>
Таблиця 3 – Оцінка дисперсій коефіцієнтів рівняння регресії за ЦКРП
</caption>

= Перелік літератури =
#Аністратенко В.О., Федоров В.Г. Математичне планування експериментів в АПК ст.200

[[Категорія:Планування експерименту]]

Метод крутого сходження

2012-03-06T12:24:25Z

Ulllasya:

Метод крутого сходження

2012-03-06T12:23:06Z

Ulllasya:

Метод крутого сходження

2012-03-06T12:17:45Z

Ulllasya:

Файл:Рис 1.GIF

2012-03-06T10:56:38Z

Ulllasya:

Метод крутого сходження

2012-03-05T21:38:49Z

Ulllasya:

Метод крутого сходження

2012-03-05T21:25:34Z

Ulllasya: Створена сторінка: {{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}} {|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5…

2011-2012рр - Індивідуальні завдання для виступу на семінарах з предмету "Планування експерименту Design Of Experiment (DOE)"

2012-03-05T21:24:35Z

Ulllasya:

# (30.12.2011р.) [[Користувач:andry_ad|ст.гр.СНм-51 Дереш А. З.]]: Оптимізація. [[Математичне програмування]].
# (14.01.2012р.) [[Користувач:lenalunak|ст.гр.СНм-51 Лунак О.М.]]:[[Огляд видів експертних систем та їх класифікація]].
# (14.01.2012h.) [[Користувач:Bilinska lida|ст.гр.СНм-51 Білінська Л.В.]]:[[Історичний огляд методів дослідження електрофізіологічних сигналів в офтальмології]].
# (30.12.2011р.) [[Користувач: Тетяна|ст.гр.СНм-51 Паньків.Т.В.]]:[[Огляд моделей обробки енергетичних сигналів]].
# (24.01.2011р.) [[Користувач: bodyk_bs|ст.гр.СНм-51 Сікач Б.Я.]]:[[Методи виявлення розладки випадкових процесів]].
# (17.02.2012р.) [[Користувач: core_st|ст.гр.СНм-51 Стойко В.І.]]:[[Розпізнавання образів: від теорії до практики]].
# (21.02.2012р.) [[Користувач: Natalochka|ст.гр.СНм-51 Чура Н.Я.]]:[[Методи прогнозування водоспоживання]].
# (21.02.2012р.) [[Користувач: Svetik_B7|ст.гр.СНм-51 Барабаш С.Б.]]:[[Симплекс-метод оптимізації]].
# (16.02.2012р.) [[Користувач: Morituri|ст.гр.СН-51 Федчук М.І.]]:[[Коефіцієнт конкордації]].
# (18.02.2012р.) [[Користувач: Sanjok|ст.гр.СН-51 Грушицький О.О.]]:[[Критерій Вальда]].
# (22.02.2012р.) [[Користувач: Марія|ст.гр.СНм-51 Прошина М.Ю.]]:[[Розпізнавання образів]].
# (24.02.2012р.) [[Користувач:GalkaPr|ст.гр.СНм-51 Пригодська Г.М.]]:[[Критерії згоди]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Метод Девідона – Флетчера – Пауела]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Рототабельне планування]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Метод крутого сходження]].
# (28.02.2012р.) [[Користувач: Sanjok|ст.гр.СН-51 Грушицький О.О.]]:[[Мислений експеримент]].
# (29.02.2012р.) [[Користувач: Natalochka|ст.гр.СНм-51 Чура Н.Я.]]:[[Сингулярне розкладання]].
# (01.03.2012р.) [[Користувач: Віка|ст.гр.СНм-51 Савула В.Р.]]:[[Статистичний аналіз вибіркових сукупностей]].
# (04.03.2012р.) [[Користувач: Vova|ст.гр.СН-51 Шостак В.М.]]:[[Критерій Фішера]].
# (04.03.2012р.) [[Користувач: Vova|ст.гр.СН-51 Шостак В.М.]]:[[Непараметрична регресія]].
# (04.03.2012р.) [[Користувач: Natalya Priyan|ст.гр.СНм-51 Пріян Н.М.]]:[[Виродження задачі оптимізації після ПФЕ або ДФЕ]].
# (04.03.2012р.) [[Користувач: Natalya Priyan|ст.гр.СНм-51 Пріян Н.М.]]:[[Інші застосування критеріїв згоди]].

2011-2012рр - Індивідуальні завдання для виступу на семінарах з предмету "Планування експерименту Design Of Experiment (DOE)"

2012-03-05T21:20:12Z

Ulllasya:

# (30.12.2011р.) [[Користувач:andry_ad|ст.гр.СНм-51 Дереш А. З.]]: Оптимізація. [[Математичне програмування]].
# (14.01.2012р.) [[Користувач:lenalunak|ст.гр.СНм-51 Лунак О.М.]]:[[Огляд видів експертних систем та їх класифікація]].
# (14.01.2012h.) [[Користувач:Bilinska lida|ст.гр.СНм-51 Білінська Л.В.]]:[[Історичний огляд методів дослідження електрофізіологічних сигналів в офтальмології]].
# (30.12.2011р.) [[Користувач: Тетяна|ст.гр.СНм-51 Паньків.Т.В.]]:[[Огляд моделей обробки енергетичних сигналів]].
# (24.01.2011р.) [[Користувач: bodyk_bs|ст.гр.СНм-51 Сікач Б.Я.]]:[[Методи виявлення розладки випадкових процесів]].
# (17.02.2012р.) [[Користувач: core_st|ст.гр.СНм-51 Стойко В.І.]]:[[Розпізнавання образів: від теорії до практики]].
# (21.02.2012р.) [[Користувач: Natalochka|ст.гр.СНм-51 Чура Н.Я.]]:[[Методи прогнозування водоспоживання]].
# (21.02.2012р.) [[Користувач: Svetik_B7|ст.гр.СНм-51 Барабаш С.Б.]]:[[Симплекс-метод оптимізації]].
# (16.02.2012р.) [[Користувач: Morituri|ст.гр.СН-51 Федчук М.І.]]:[[Коефіцієнт конкордації]].
# (18.02.2012р.) [[Користувач: Sanjok|ст.гр.СН-51 Грушицький О.О.]]:[[Критерій Вальда]].
# (22.02.2012р.) [[Користувач: Марія|ст.гр.СНм-51 Прошина М.Ю.]]:[[Розпізнавання образів]].
# (24.02.2012р.) [[Користувач:GalkaPr|ст.гр.СНм-51 Пригодська Г.М.]]:[[Критерії згоди]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Метод Девідона – Флетчера – Пауела]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Рототабельне планування]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[]].
# (28.02.2012р.) [[Користувач: Sanjok|ст.гр.СН-51 Грушицький О.О.]]:[[Мислений експеримент]].
# (29.02.2012р.) [[Користувач: Natalochka|ст.гр.СНм-51 Чура Н.Я.]]:[[Сингулярне розкладання]].
# (01.03.2012р.) [[Користувач: Віка|ст.гр.СНм-51 Савула В.Р.]]:[[Статистичний аналіз вибіркових сукупностей]].
# (04.03.2012р.) [[Користувач: Vova|ст.гр.СН-51 Шостак В.М.]]:[[Критерій Фішера]].
# (04.03.2012р.) [[Користувач: Vova|ст.гр.СН-51 Шостак В.М.]]:[[Непараметрична регресія]].
# (04.03.2012р.) [[Користувач: Natalya Priyan|ст.гр.СНм-51 Пріян Н.М.]]:[[Виродження задачі оптимізації після ПФЕ або ДФЕ]].
# (04.03.2012р.) [[Користувач: Natalya Priyan|ст.гр.СНм-51 Пріян Н.М.]]:[[Інші застосування критеріїв згоди]].

2011-2012рр - Індивідуальні завдання для виступу на семінарах з предмету "Планування експерименту Design Of Experiment (DOE)"

2012-03-05T21:16:24Z

Ulllasya:

# (30.12.2011р.) [[Користувач:andry_ad|ст.гр.СНм-51 Дереш А. З.]]: Оптимізація. [[Математичне програмування]].
# (14.01.2012р.) [[Користувач:lenalunak|ст.гр.СНм-51 Лунак О.М.]]:[[Огляд видів експертних систем та їх класифікація]].
# (14.01.2012h.) [[Користувач:Bilinska lida|ст.гр.СНм-51 Білінська Л.В.]]:[[Історичний огляд методів дослідження електрофізіологічних сигналів в офтальмології]].
# (30.12.2011р.) [[Користувач: Тетяна|ст.гр.СНм-51 Паньків.Т.В.]]:[[Огляд моделей обробки енергетичних сигналів]].
# (24.01.2011р.) [[Користувач: bodyk_bs|ст.гр.СНм-51 Сікач Б.Я.]]:[[Методи виявлення розладки випадкових процесів]].
# (17.02.2012р.) [[Користувач: core_st|ст.гр.СНм-51 Стойко В.І.]]:[[Розпізнавання образів: від теорії до практики]].
# (21.02.2012р.) [[Користувач: Natalochka|ст.гр.СНм-51 Чура Н.Я.]]:[[Методи прогнозування водоспоживання]].
# (21.02.2012р.) [[Користувач: Svetik_B7|ст.гр.СНм-51 Барабаш С.Б.]]:[[Симплекс-метод оптимізації]].
# (16.02.2012р.) [[Користувач: Morituri|ст.гр.СН-51 Федчук М.І.]]:[[Коефіцієнт конкордації]].
# (18.02.2012р.) [[Користувач: Sanjok|ст.гр.СН-51 Грушицький О.О.]]:[[Критерій Вальда]].
# (22.02.2012р.) [[Користувач: Марія|ст.гр.СНм-51 Прошина М.Ю.]]:[[Розпізнавання образів]].
# (24.02.2012р.) [[Користувач:GalkaPr|ст.гр.СНм-51 Пригодська Г.М.]]:[[Критерії згоди]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Метод Девідона – Флетчера – Пауела]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Рототабельне планування]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Критерій узгодженості Фішера]].
# (28.02.2012р.) [[Користувач: Sanjok|ст.гр.СН-51 Грушицький О.О.]]:[[Мислений експеримент]].
# (29.02.2012р.) [[Користувач: Natalochka|ст.гр.СНм-51 Чура Н.Я.]]:[[Сингулярне розкладання]].
# (01.03.2012р.) [[Користувач: Віка|ст.гр.СНм-51 Савула В.Р.]]:[[Статистичний аналіз вибіркових сукупностей]].
# (04.03.2012р.) [[Користувач: Vova|ст.гр.СН-51 Шостак В.М.]]:[[Критерій Фішера]].
# (04.03.2012р.) [[Користувач: Vova|ст.гр.СН-51 Шостак В.М.]]:[[Непараметрична регресія]].
# (04.03.2012р.) [[Користувач: Natalya Priyan|ст.гр.СНм-51 Пріян Н.М.]]:[[Виродження задачі оптимізації після ПФЕ або ДФЕ]].
# (04.03.2012р.) [[Користувач: Natalya Priyan|ст.гр.СНм-51 Пріян Н.М.]]:[[Інші застосування критеріїв згоди]].

Рототабельне планування

2012-03-05T21:14:39Z

Ulllasya:

{{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}}
{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНм-51
|-
| '''Залікова книжка''' || СНм-11-253
|}

= [[Рототабельне планування]] =

У зв'язку з тим, що дисперсії коефіцієнтів рівняння регресії при ОЦКП нерівномірні, ортогональність матриці часто не є досить сильним критерієм оптимальності планування другого порядку. Його заміняють критерієм ротоптабельності, тобто однаковості дисперсій коефіцієнтів при повороті координатних осей на будь-який кут. Зазначимо, що при плануванні першого порядку ортогональність матриці просто збігається з її рототабельністю, тому ПФЕ доцільно називати рототабельним.
Щоб зробити план другого порядку рототабельним, вибирають для сфери, на якій розташовуються зіркові точки, радіус (зіркове плече) за формулою

<center><math>\alpha ={{2}^{n/2}}.</math></center>

Інша умова рототабельності — збільшення числа дослідів на поверхні нульової сфери, тобто в центрі плану. У зв'язку з цим виникає повна назва методу: ''центральне композиційне рототабельне планування'' (ЦКРП).
Таким чином ЦКРП багато в чому нагадує ортогональне планування, проте метод рототабельного планування експерименту дає змогу дістати точніший математичний опис поверхні відклику порівняно з ОЦКП, завдяки збільшенню числа дослідів у центрі плану і спеціальному вибору величини зіркового плеча α.
Як і для ОЦКП, основні характеристики матриць рототабельного планування табульовані (табл. 1). При ЦКРП, починаючи з n = 5, можна застосувати ДФЕ(дробовий факторний експеримент).

<table width="90%" border="1">

<tr>
<th scope="col">n </th>
<th scope="col"><math>{{\operatorname{N}}_{n}}</math> </th>
<th scope="col"><math>{{\operatorname{N}}_{\alpha }}</math> </th>
<th scope="col"><math>{{\operatorname{N}}_{0}}</math> </th>
<th scope="col">N </th>
<th scope="col"><math>\alpha </math> </th>
</tr>
<tr>
<td>2 </td>
<td>5 </td>
<td>4 </td>
<td>4 </td>
<td>13 </td>
<td>1,414 </td>
</tr>
<tr>
<td>3 </td>
<td>6 </td>
<td>8 </td>
<td>6 </td>
<td>20 </td>
<td>1,680 </td>
</tr>
<tr>
<td>4 </td>
<td>7 </td>
<td>16 </td>
<td>8 </td>
<td>31 </td>
<td>2,000 </td>
</tr>
<tr>
<td>5 </td>
<td>10 </td>
<td>32 </td>
<td>10 </td>
<td>52 </td>
<td>2,378 </td>
</tr>
<tr>
<td>6 </td>
<td>15 </td>
<td>64 </td>
<td>12 </td>
<td>91 </td>
<td>1,828 </td>
</tr>
<tr>
<td>7 </td>
<td>21 </td>
<td>128 </td>
<td>14 </td>
<td>163 </td>
<td>1,333 </td>
</tr>
</table>
<caption>
Таблиця 1 – Підготовка ЦКРП другого порядку
</caption>
При рототабельному плануванні для обчислення коефіцієнтів моделі і відповідних оцінок дисперсій знаходять спеціальні комплекси:

<center><math>\begin{align}
& B=\frac{nN}{(n+2)(N-{{N}_{0}})}; \\
& A=\frac{1}{2B[(n+2)B-n]}; \\
& C=\frac{N}{N-{{N}_{0}}}, \\
\end{align}</math></center>

де n-число факторів; N-загальне число дослідів у плануванні; N0-число дослідів у центрі плану.
За результатами експериментів обчислюють такі суми:

<center><math>\begin{align}
& {{S}_{0}}=\sum\limits_{g=1}^{N}{{{y}_{g}}}; \\
& {{S}_{i}}=\sum\limits_{g=1}^{N}{{{y}_{g}}}{{z}_{gi}};i=1,2,...,n; \\
& {{S}_{ik}}=\sum\limits_{g=1}^{N}{{{z}_{gi}}{{z}_{gk}}{{y}_{g}}};i\ne k; \\
& {{S}_{ii}}=\sum\limits_{g=1}^{N}{z_{gi}^{2}{{y}_{g}}};i=1,2,...,n. \\
\end{align}</math></center>

Коефіцієнти моделі тут розраховують за формулами

<center><math>\begin{align}
& {{b}_{0}}=\frac{2AB}{N}[{{S}_{0}}B(n+2)-C\sum{{{S}_{ii}}}]; \\
& {{b}_{i}}=\frac{C{{S}_{i}}}{N}; \\
& {{b}_{ik}}=\frac{{{C}^{2}}{{S}_{ik}}}{BN},i\ne k; \\
& {{b}_{ii}}=\frac{AC}{N}\{{{S}_{ii}}[B(n+2)-n]+C(1-B)\sum\limits_{i=1}^{n}{{{S}_{ii}}-2B{{S}_{0}}}\}. \\
& \\
\end{align}</math></center>

Оцінки дисперсій для обчислених коефіцієнтів знаходять за такими формулами:

<center><math>\begin{align}
& S_{b0}^{2}=\frac{2AB(n+2)}{N}S_{y}^{2}; \\
& S_{bi}^{2}=\frac{S_{y}^{2}}{N-{{N}_{0}}};i=1,2,...,n; \\
& S_{bik}^{2}=\frac{{{C}^{2}}S_{y}^{2}}{N},i\ne k; \\
& {{S}_{bii}}=\frac{A{{C}^{2}}S_{y}^{2}}{N}[B(n+1)-(n-1)]. \\
\end{align}</math></center>

У цих формулах дисперсія відтворюваності <math>S_{y}^{2}</math> визначається за результатами дослідів у нульовій точці

<center><math>\begin{align}
& S_{y}^{2}=\frac{1}{{{N}_{0}}-1}\sum\limits_{g=1}^{{{N}_{0}}}{{{({{y}_{ge}}-\overset{-}{y}\,)}^{2}}}; \\
& \overset{-}{y}\,=\frac{1}{{{N}_{0}}}\sum\limits_{g=1}^{{{N}_{0}}}{{{y}_{ge.}}} \\
\end{align}</math></center>

Дисперсія адекватності оцінюється за формулою

<center><math>S_{adekv}^{2}=\frac{\sum\limits_{g=1}^{N}{{{({{y}_{ge}}-{{y}_{grozr}})}^{2}}-S_{y}^{2}({{N}_{0}}-1)}}{N-\frac{(n+2)(n+1)}{2}(N-1)},</math></center>

якшо число ступенів вільності

<center><math>{{f}_{adekv}}={{N}_{0}}-\frac{(n+2)(n+1)}{2}-({{N}_{0}}-1).</math></center>
==Приклад==

Скласти матрицю ЦКРП на прикладі побудови математичної моделі технологічного процесу крупоутворення (див.: Пищевая технология.— 1976.— № 4.— С. 121—124).

'''Розв'язання'''. Як функції відклику прийнято <math>y_1</math>, % — середня зольність крупи пшениці після перших трьох систем для дертя (швидкість обертання рифлених вальців усіх систем 6 м/с); <math>y_2</math>, % — сумарний вихід всіх крупок, які добуваються в процесі крупоутворення; <math>y_3</math>, кДж/(кг • %) — витрата енергії на одержання 1 % продукту з 1 кг зерна.
Незалежними змінними є, %: <math>x_1</math> — вихід крупи на першій системі для дертя; <math>x_2</math> — те ж на другій системі; <math>x_3</math> — те ж, для трьох систем для дертя. Інтервал варіювання для всіх <math>x_i</math>, вибрано з умови охоплення області їхньої реальної зміни. Рівні змінних становили, %:

<table width="90%" border="1">
<tr>
<th scope="col">Незалежні змінні </th>
<th scope="col">Нижній </th>
<th scope="col">Основний </th>
<th scope="col">Верхній </th>
</tr>
<tr>
<th scope="row"><math>X_1</math> </th>
<td><center>5</center> </td>
<td><center>10</center> </td>
<td><center>15</center> </td>
</tr>
<tr>
<th scope="row"><math>X_2</math> </th>
<td><center>30</center> </td>
<td><center>40</center> </td>
<td><center>50</center> </td>
</tr>
<tr>
<th scope="row"><math>X_3</math> </th>
<td><center>65</center> </td>
<td><center>70</center> </td>
<td><center>75</center> </td>
</tr>
</table>

У зв'язку з тим, що режими крупоутворення вивчалися досить детально, стало можливим ставити експерименти в області факторного простору, для якої значення всіх у близькі до оптимальних, а для опису цієї області застосувати відразу планування другого порядку. Було реалізовано центральний композиційний рототабельний план, який включає ПФЕ <math>2^3</math>, шість зіркових та шість центральних точок. Послідовність проведення дослідів була рандомізована, кожен дослід проводився тричі. У табл. 2 наведено матрицю планування та середні значення функцій відклику для кожного її рядка.
За вищенаведеними формулами розраховані такі коефіцієнти в рівняннях регресії для всіх функцій відклику:

<center>
<math>\begin{align}
& {{y}_{1}}=0,65+0,0084{{z}_{1}}+0,0048{{z}_{2}}+0,0630{{z}_{3}}+0,0150{{z}_{1}}{{z}_{2}}-0,0050{{z}_{1}}{{z}_{3}}- \\
& -0,0400{{z}_{2}}{{z}_{3}}+0,0038z_{1}^{2}+0,0076z_{2}^{2}+0,0314z_{3}^{2}; \\
& {{y}_{2}}=43,5+1,37{{z}_{1}}+0,34{{z}_{2}}+0,89{{z}_{3}}-1,41{{z}_{1}}{{z}_{2}}-0,61{{z}_{1}}{{z}_{3}}+ \\
& +0,74{{z}_{2}}{{z}_{3}}-0,83z_{1}^{2}-1,71z_{2}^{2}-1,52z_{3}^{2}; \\
& {{y}_{3}}=6,4-0,28{{z}_{1}}-0,11{{z}_{2}}+0,61{{z}_{3}}+0,03{{z}_{1}}{{z}_{2}}-0,03{{z}_{1}}{{z}_{3}}- \\
& -0,05{{z}_{2}}{{z}_{3}}+0,33z_{1}^{2}+0,68z_{2}^{2}+0,69z_{3}^{2}. \\
\end{align}</math>
</center>

Оцінки дисперсій для коефіцієнтів у цих рівняннях наведено в табл. 3.
Коефіцієнти при <math>z^2</math> на порядок перевищують помилку в їхньому визначенні для всіх функцій відклику, отже, лінійними рівняннями описати їх не можна. Адекватність утворених нелінійних рівнянь було перевірено за F-критерієм.

<table width="90%" border="1">

<tr>
<th scope="col"> </th>
<th scope="col"><math>z_0</math> </th>
<th scope="col"><math>z_1</math> </th>
<th scope="col"><math>z_2</math> </th>
<th scope="col"><math>z_3</math> </th>
<th scope="col"><math>z_1^2</math> </th>
<th scope="col"><math>z_2^2</math> </th>
<th scope="col"><math>z_3^2</math> </th>
<th scope="col"><math>z_1*z_2</math> </th>
<th scope="col"><math>z_1*z_3</math> </th>
<th scope="col"><math>z_2*z_3</math> </th>
<th scope="col"><math>y_1c</math> </th>
<th scope="col"><math>y_2c</math> </th>
<th scope="col"><math>y_3c</math> </th>
</tr>
<tr>
<td><center>1</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>0,75</center> </td>
<td><center>40,5</center> </td>
<td><center>8,4</center> </td>
</tr>
<tr>
<td><center>2</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>0,68</center> </td>
<td><center>36,7</center> </td>
<td><center>7,3</center> </td>
</tr>
<tr>
<td><center>3</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>0,78</center> </td>
<td><center>41,3</center> </td>
<td><center>8,7</center> </td>
</tr>
<tr>
<td><center>4</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>0,61</center> </td>
<td><center>42,7</center> </td>
<td><center>7,3</center> </td>
</tr>
<tr>
<td><center>5</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>0,72</center> </td>
<td><center>41,0</center> </td>
<td><center>8,7</center> </td>
</tr>
<tr>
<td><center>6</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>0,61</center> </td>
<td><center>37,0</center> </td>
<td><center>7,9</center> </td>
</tr>
<tr>
<td><center>7</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>0,78</center> </td>
<td><center>38,2</center> </td>
<td><center>9,2</center> </td>
</tr>
<tr>
<td><center>8</center> </td>
<td><center>+</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>-</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>+</center> </td>
<td><center>0,62</center> </td>
<td><center>34,9</center> </td>
<td><center>8,0</center> </td>
</tr>
<tr>
<td><center>9</center> </td>
<td><center>+</center> </td>
<td><center>+1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,67</center> </td>
<td><center>44,7</center> </td>
<td><center>6,8</center> </td>
</tr>
<tr>
<td><center>10</center> </td>
<td><center>+</center> </td>
<td><center>-1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,66</center> </td>
<td><center>39,4</center> </td>
<td><center>7,7</center> </td>
</tr>
<tr>
<td><center>11</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>+1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,86</center> </td>
<td><center>40,7</center> </td>
<td><center>9,3</center> </td>
</tr>

<tr>
<td><center>12</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>-1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,65</center> </td>
<td><center>37,8</center> </td>
<td><center>8,5</center> </td>
</tr>
<tr>
<td><center>13</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,86</center> </td>
<td><center>40,7</center> </td>
<td><center>9,3</center> </td>
</tr>
<tr>
<td><center>14</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>-1,68</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>+2,83</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,63</center> </td>
<td><center>39,3</center> </td>
<td><center>7,0</center> </td>
</tr>
<tr>
<td><center>15</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,65</center> </td>
<td><center>41,6</center> </td>
<td><center>6,4</center> </td>
</tr>
<tr>
<td><center>16</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,63</center> </td>
<td><center>42,7</center> </td>
<td><center>6,6</center> </td>
</tr>
<tr>
<td><center>17</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,66</center> </td>
<td><center>44,5</center> </td>
<td><center>6,2</center> </td>
</tr>
<tr>
<td><center>18</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,66</center> </td>
<td><center>42,9</center> </td>
<td><center>6,1</center> </td>
</tr>
<tr>
<td><center>19</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,65</center> </td>
<td><center>44,5</center> </td>
<td><center>6,8</center> </td>
</tr>
<tr>
<td><center>20</center> </td>
<td><center>+</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0</center> </td>
<td><center>0,65</center> </td>
<td><center>44,0</center> </td>
<td><center>6,5</center> </td>
</tr>
</table>
<caption>
Таблиця 2 – Реалізація матриці ЦКРП другого порядку
</caption>

<table width="90%" border="1">

<tr>
<th scope="col"><math>{{\operatorname{y}}_{i}}</math> </th>
<th scope="col"><math>{{\operatorname{S}}_{b0}}</math> </th>
<th scope="col"><math>{{\operatorname{S}}_{b1}}</math> </th>
<th scope="col"><math>{{\operatorname{S}}_{b2}}</math> </th>
<th scope="col"><math>{{\operatorname{S}}_{b3}}</math> </th>
</tr>
<tr>
<td><math>y_1</math> </td>
<td>0,0053 </td>
<td>0,0035 </td>
<td>0,0034 </td>
<td>0,0046 </td>
</tr>
<tr>
<td><math>y_2</math> </td>
<td>0,48 </td>
<td>0,31 </td>
<td>0,30 </td>
<td>0,41 </td>
</tr>
<tr>
<td><math>y_3</math> </td>
<td>0,13 </td>
<td>0,8 </td>
<td>0,8 </td>
<td>0,11 </td>
</tr>

</table>
<caption>
Таблиця 3 – Оцінка дисперсій коефіцієнтів рівняння регресії за ЦКРП
</caption>

= Перелік використаних джерел =
#Аністратенко В.О., Федоров В.Г. Математичне планування експериментів в АПК
[[Категорія:Планування експерименту]]

2011-2012рр - Індивідуальні завдання для виступу на семінарах з предмету "Планування експерименту Design Of Experiment (DOE)"

2012-03-05T20:46:46Z

Ulllasya:

# (30.12.2011р.) [[Користувач:andry_ad|ст.гр.СНм-51 Дереш А. З.]]: Оптимізація. [[Математичне програмування]].
# (14.01.2012р.) [[Користувач:lenalunak|ст.гр.СНм-51 Лунак О.М.]]:[[Огляд видів експертних систем та їх класифікація]].
# (14.01.2012h.) [[Користувач:Bilinska lida|ст.гр.СНм-51 Білінська Л.В.]]:[[Історичний огляд методів дослідження електрофізіологічних сигналів в офтальмології]].
# (30.12.2011р.) [[Користувач: Тетяна|ст.гр.СНм-51 Паньків.Т.В.]]:[[Огляд моделей обробки енергетичних сигналів]].
# (24.01.2011р.) [[Користувач: bodyk_bs|ст.гр.СНм-51 Сікач Б.Я.]]:[[Методи виявлення розладки випадкових процесів]].
# (17.02.2012р.) [[Користувач: core_st|ст.гр.СНм-51 Стойко В.І.]]:[[Розпізнавання образів: від теорії до практики]].
# (21.02.2012р.) [[Користувач: Natalochka|ст.гр.СНм-51 Чура Н.Я.]]:[[Методи прогнозування водоспоживання]].
# (21.02.2012р.) [[Користувач: Svetik_B7|ст.гр.СНм-51 Барабаш С.Б.]]:[[Симплекс-метод оптимізації]].
# (16.02.2012р.) [[Користувач: Morituri|ст.гр.СН-51 Федчук М.І.]]:[[Коефіцієнт конкордації]].
# (18.02.2012р.) [[Користувач: Sanjok|ст.гр.СН-51 Грушицький О.О.]]:[[Критерій Вальда]].
# (22.02.2012р.) [[Користувач: Марія|ст.гр.СНм-51 Прошина М.Ю.]]:[[Розпізнавання образів]].
# (24.02.2012р.) [[Користувач:GalkaPr|ст.гр.СНм-51 Пригодська Г.М.]]:[[Критерії згоди]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Метод Девідона – Флетчера – Пауела]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Рототабельне планування]].
# (28.02.2012р.) [[Користувач: Sanjok|ст.гр.СН-51 Грушицький О.О.]]:[[Мислений експеримент]].
# (29.02.2012р.) [[Користувач: Natalochka|ст.гр.СНм-51 Чура Н.Я.]]:[[Сингулярне розкладання]].
# (01.03.2012р.) [[Користувач: Віка|ст.гр.СНм-51 Савула В.Р.]]:[[Статистичний аналіз вибіркових сукупностей]].
# (04.03.2012р.) [[Користувач: Vova|ст.гр.СН-51 Шостак В.М.]]:[[Критерій Фішера]].
# (04.03.2012р.) [[Користувач: Vova|ст.гр.СН-51 Шостак В.М.]]:[[Непараметрична регресія]].
# (04.03.2012р.) [[Користувач: Natalya Priyan|ст.гр.СНм-51 Пріян Н.М.]]:[[Виродження задачі оптимізації після ПФЕ або ДФЕ]].
# (04.03.2012р.) [[Користувач: Natalya Priyan|ст.гр.СНм-51 Пріян Н.М.]]:[[Інші застосування критеріїв згоди]].

2011-2012рр - Індивідуальні завдання для виступу на семінарах з предмету "Планування експерименту Design Of Experiment (DOE)"

2012-03-05T20:45:28Z

Ulllasya:

# (30.12.2011р.) [[Користувач:andry_ad|ст.гр.СНм-51 Дереш А. З.]]: Оптимізація. [[Математичне програмування]].
# (14.01.2012р.) [[Користувач:lenalunak|ст.гр.СНм-51 Лунак О.М.]]:[[Огляд видів експертних систем та їх класифікація]].
# (14.01.2012h.) [[Користувач:Bilinska lida|ст.гр.СНм-51 Білінська Л.В.]]:[[Історичний огляд методів дослідження електрофізіологічних сигналів в офтальмології]].
# (30.12.2011р.) [[Користувач: Тетяна|ст.гр.СНм-51 Паньків.Т.В.]]:[[Огляд моделей обробки енергетичних сигналів]].
# (24.01.2011р.) [[Користувач: bodyk_bs|ст.гр.СНм-51 Сікач Б.Я.]]:[[Методи виявлення розладки випадкових процесів]].
# (17.02.2012р.) [[Користувач: core_st|ст.гр.СНм-51 Стойко В.І.]]:[[Розпізнавання образів: від теорії до практики]].
# (21.02.2012р.) [[Користувач: Natalochka|ст.гр.СНм-51 Чура Н.Я.]]:[[Методи прогнозування водоспоживання]].
# (21.02.2012р.) [[Користувач: Svetik_B7|ст.гр.СНм-51 Барабаш С.Б.]]:[[Симплекс-метод оптимізації]].
# (16.02.2012р.) [[Користувач: Morituri|ст.гр.СН-51 Федчук М.І.]]:[[Коефіцієнт конкордації]].
# (18.02.2012р.) [[Користувач: Sanjok|ст.гр.СН-51 Грушицький О.О.]]:[[Критерій Вальда]].
# (22.02.2012р.) [[Користувач: Марія|ст.гр.СНм-51 Прошина М.Ю.]]:[[Розпізнавання образів]].
# (24.02.2012р.) [[Користувач:GalkaPr|ст.гр.СНм-51 Пригодська Г.М.]]:[[Критерії згоди]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Метод Девідона – Флетчера – Пауела]].
# (25.02.2012р.) [[Користувач: ulllasya|ст.гр.СНм-51 Храплива У.В.]]:[[Рототабельне]].
# (28.02.2012р.) [[Користувач: Sanjok|ст.гр.СН-51 Грушицький О.О.]]:[[Мислений експеримент]].
# (29.02.2012р.) [[Користувач: Natalochka|ст.гр.СНм-51 Чура Н.Я.]]:[[Сингулярне розкладання]].
# (01.03.2012р.) [[Користувач: Віка|ст.гр.СНм-51 Савула В.Р.]]:[[Статистичний аналіз вибіркових сукупностей]].
# (04.03.2012р.) [[Користувач: Vova|ст.гр.СН-51 Шостак В.М.]]:[[Критерій Фішера]].
# (04.03.2012р.) [[Користувач: Vova|ст.гр.СН-51 Шостак В.М.]]:[[Непараметрична регресія]].
# (04.03.2012р.) [[Користувач: Natalya Priyan|ст.гр.СНм-51 Пріян Н.М.]]:[[Виродження задачі оптимізації після ПФЕ або ДФЕ]].
# (04.03.2012р.) [[Користувач: Natalya Priyan|ст.гр.СНм-51 Пріян Н.М.]]:[[Інші застосування критеріїв згоди]].

Рототабельне планування

2012-03-01T12:33:35Z

Метод Девідона – Флетчера – Пауела

2012-02-29T22:10:51Z

Ulllasya:

Метод Девідона – Флетчера – Пауела

2012-02-29T14:20:04Z

Ulllasya:

Метод Девідона – Флетчера – Пауела

2012-02-29T14:19:44Z

Ulllasya:

Метод Девідона – Флетчера – Пауела

2012-02-29T14:15:48Z

Ulllasya:

{{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}}
{{Студент | [[Файл:Sunset.jpg]] | Surname=Храплива | Name=Уляна | FatherNAme=Вікторівна |Faculti=ФІС | Group=СНм-51 | Zalbook=СНм-11-253}}

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

= Початковий етап =
Нехай <math>$\varepsilon \succ 0$</math> - константа для зупинки. Вибрати точку <math>${x_1}$</math> і початково симетричну позитивно визначену матрицю <math>${D_1}$</math>. Покласти <math>${y_1} = {x_1}$</math>, k = j = 1 і перейти до основного етапу.

= Основний етап =
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1. 
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином: 
<center><math>${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$</math>(1)</center> 
<center>де <math>${p_i} = {\lambda _i}{d_i},$</math>(2)</center> 
<center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math>(3)</center> 
Замінити j на j+1 і перейти до кроку 1.

=Приклад=
Мінімізувати <math>${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$</math> 
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1. 
<center>
<table width="382" border="1">

<tr>
<th scope="row">k</th>
<td width="65" bgcolor="#BDE0BA"><math>${x_k}$</math> <math>$f({x_k})$</math></td>
<td width="18" bgcolor="#BDE0BA">j</td>
<td width="65" bgcolor="#BDE0BA"><math>${y_j}$</math> <math>$f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\nabla f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$</math></td>
<td width="65" bgcolor="#BDE0BA">D</td>
<td width="75" bgcolor="#BDE0BA"><math>${d_j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${\lambda _j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${y_{j + 1}}$</math></td>

</tr>
<tr>
<th scope="row">1</th>
<td bgcolor="">(0.00,3.00) (52.00)</td>

<td bgcolor="">1</td>
<td bgcolor="">(0.00,3.00) (52.00)</td>
<td bgcolor="">(-44.00,24.00)</td>
<td bgcolor="">50.12</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(44.00,-24.00)</td>
<td bgcolor="">0.062</td>
<td bgcolor="">(2.70, 1.51)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.70,1.51) (0.34)</td>
<td bgcolor="">(0.73,1.28)</td>
<td bgcolor="">1.47</td>
<td bgcolor=""><math>$\left[
0.25|0.38\\
0.38|0.71 \right]$</math></td>
<td bgcolor="">(-0.67,-1.31)</td>
<td bgcolor="">0.22</td>
<td bgcolor="">(2.55,1.22)</td>
</tr>

<tr>
<th scope="row">2</th>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">(0.89,-0.44)</td>
<td bgcolor="">0.99</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.89,0.44)</td>
<td bgcolor="">0.11</td>
<td bgcolor="">(2.45,1.27)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.45,1.27) (0.0490)</td>
<td bgcolor="">(0.18,0.36)</td>
<td bgcolor="">0.40</td>
<td bgcolor=""><math>$\left[
0.65|0.45\\
0.45|0.46 \right]$</math></td>
<td bgcolor="">(-0.28,-0.25)</td>
<td bgcolor="">0.64</td>
<td bgcolor="">(2.27,1.11)</td>
</tr>
<tr>
<th scope="row">3</th>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">(0.18,-0.20)</td>
<td bgcolor="">0.27</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.18,0.20)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.25,1.13)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.25,1.13) (0.004)</td>
<td bgcolor="">(0.04,0.04)</td>
<td bgcolor="">0.06</td>
<td bgcolor=""><math>$\left[
0.80|0.38\\
0.38|0.31 \right]$</math></td>
<td bgcolor="">(-0.05,-0.03)</td>
<td bgcolor="">2.64</td>
<td bgcolor="">(2.12,1.05)</td>
</tr>
<tr>
<th scope="row">4</th>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">(0.05,-0.08)</td>
<td bgcolor="">0.09</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.05,0.08)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.115,1.058)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.115,1.058) (0.0002)</td>
<td bgcolor="">(0.004,0.004)</td>
<td bgcolor="">0.006</td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>

</tr>
</table>
</center> 
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1. 
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла. 
<center>[[Файл:Рисунок_1.gif]]</center> 

Лема показує, що кожна матриця <math>${d_j}$</math> позитивно визначена і <math>${d_j}$</math> є напрямом спуску. Для доказу леми нам знадобиться : 
'''Теорема 1.''' Нехай S - непорожня безліч в Еn, точка <math>$x \in cl$</math> S. Конусом можливих напрямів в точці x називається безліч <math>$D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$</math>при всіх <math>$\lambda \in (0,\delta )$</math> для деякого <math>$\delta > 0}$</math>. 
'''Визначення.'''Нехай x і y - вектори з Еn і <math>$\left| {{x^T}y} \right|$</math> - абсолютне значення скалярного відтворення <math>$\left {{x^T}y} \right$</math>. Тоді виконується наступна нерівність, звана нерівністю Шварца: 
<center> <math>$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$</math></center>. 

=Лема 1=
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску. 

'''Доведення''' 
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math>
\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) < 0</math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math> j \le n - 1</math>, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо 
<center><math>{x^T}{D_{j + 1}}x = {x^T}{D_j}x + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{D_j}{q_j}}}}</math>(4)</center> 
Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця <math>D_j^{1/2}</math>, така, що <math>{D_j} = D_j^{1/2}D_j^{1/2}</math>. Нехай <math>a = D_j^{1/2}x</math> і <math>b = D_j^{1/2}{q_j}</math>. Тоді <math>{x^T}{D_j}x = {a^T}a,q_j^T{D_j}{q_j} = {b^T}b,{x^T}{D_j}{q_j} = {a^T}b</math>. Підставляючи ці вирази в (4), отримуємо: 
<center><math>{x^T}{D_{j + 1}}x = {\textstyle{{({a^T}a)({b^T}b) - {{({a^T}b)}^2}} \over {{b^T}b}}} + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{q_j}}}}</math>(5)</center> 
По нерівності Шварця маємо <math>({a^T}a)({b^T}b) \ge {({a^T}b)^2 </math>. Так, щоб довести, що<math>{x^T}{D_{j + 1}}x \ge 0</math>, досить показати, що <math>p_j^T{q_j} \ge 0,{b^T}b > 0</math>. З (2) і (3) витікає, що 
<center><math>p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]</math>(6)</center>. 
По припущенню <math>\nabla f({y_j}) \ne 0</math>, і Dj позитивно визначена, так що<math>\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) > 0</math>
Крім того, dj - напрямок спуску, і <math>{\lambda _j} > 0</math>. Тоді із (6) слідує, що <math>p_j^T{q_j} > 0</math>. Крім того <math>{q_j} \ne 0</math> і <math>{b^T}b = q_j^T{D_j}{q_j} > 0</math> 
Видно тепер, що <math>{x^T}{D_{j + 1}}x > 0</math>. Взяти <math>{x^T}{D_{j + 1}}x = 0</math>. Це можливо тільки в тому випадку якщо <math>({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0</math>. Видно, що <math>({a^T}a)({b^T}b) = {({a^T}b)^2}</math> тільки при <math>a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}</math>. Таким чином <math>x = \lambda {q_i}</math>. Так як <math>x \ne 0</math>то<math>\lambda \ne 0</math>. Дальше, <math>0 = p_j^Tx = \lambda p_j^T{q_j}</math>заперечує тому, що <math>p_j^T{q_j} > 0,\lambda \ne 0</math>. 
Отже, <math>{x^T}{D_{j + 1}}x > 0</math>, матриця <math>{D_{j + 1}}</math> позитивно визначена. 
Оскільки <math>\nabla f({y_{j + 1}}) \ne 0</math> і Dj+1 позитивно визначена, маємо <math>\nabla f{({y_{j + 1}})^T}{d_{j + 1}} = - \nabla f{({y_{j + 1}})^T}{D_{j + 1}}\nabla f({y_{j + 1}}) < 0</math>. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску. 
'''Лема доведена!!!''' 

= Список використаної літератури =

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982 
2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975 
[[Категорія:Планування експерименту]]

Файл:Sunset.jpg

2012-02-29T14:13:45Z

Ulllasya:

Метод Девідона – Флетчера – Пауела

2012-02-29T14:10:05Z

Ulllasya:

{{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}}
{{Surname=Храплива | Name=Уляна | FatherNAme=Вікторівна |Faculti=ФІС | Group=СНм-51 | Zalbook=СНм-11-253}}

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

= Початковий етап =
Нехай <math>$\varepsilon \succ 0$</math> - константа для зупинки. Вибрати точку <math>${x_1}$</math> і початково симетричну позитивно визначену матрицю <math>${D_1}$</math>. Покласти <math>${y_1} = {x_1}$</math>, k = j = 1 і перейти до основного етапу.

= Основний етап =
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1. 
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином: 
<center><math>${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$</math>(1)</center> 
<center>де <math>${p_i} = {\lambda _i}{d_i},$</math>(2)</center> 
<center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math>(3)</center> 
Замінити j на j+1 і перейти до кроку 1.

=Приклад=
Мінімізувати <math>${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$</math> 
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1. 
<center>
<table width="382" border="1">

<tr>
<th scope="row">k</th>
<td width="65" bgcolor="#BDE0BA"><math>${x_k}$</math> <math>$f({x_k})$</math></td>
<td width="18" bgcolor="#BDE0BA">j</td>
<td width="65" bgcolor="#BDE0BA"><math>${y_j}$</math> <math>$f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\nabla f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$</math></td>
<td width="65" bgcolor="#BDE0BA">D</td>
<td width="75" bgcolor="#BDE0BA"><math>${d_j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${\lambda _j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${y_{j + 1}}$</math></td>

</tr>
<tr>
<th scope="row">1</th>
<td bgcolor="">(0.00,3.00) (52.00)</td>

<td bgcolor="">1</td>
<td bgcolor="">(0.00,3.00) (52.00)</td>
<td bgcolor="">(-44.00,24.00)</td>
<td bgcolor="">50.12</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(44.00,-24.00)</td>
<td bgcolor="">0.062</td>
<td bgcolor="">(2.70, 1.51)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.70,1.51) (0.34)</td>
<td bgcolor="">(0.73,1.28)</td>
<td bgcolor="">1.47</td>
<td bgcolor=""><math>$\left[
0.25|0.38\\
0.38|0.71 \right]$</math></td>
<td bgcolor="">(-0.67,-1.31)</td>
<td bgcolor="">0.22</td>
<td bgcolor="">(2.55,1.22)</td>
</tr>

<tr>
<th scope="row">2</th>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">(0.89,-0.44)</td>
<td bgcolor="">0.99</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.89,0.44)</td>
<td bgcolor="">0.11</td>
<td bgcolor="">(2.45,1.27)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.45,1.27) (0.0490)</td>
<td bgcolor="">(0.18,0.36)</td>
<td bgcolor="">0.40</td>
<td bgcolor=""><math>$\left[
0.65|0.45\\
0.45|0.46 \right]$</math></td>
<td bgcolor="">(-0.28,-0.25)</td>
<td bgcolor="">0.64</td>
<td bgcolor="">(2.27,1.11)</td>
</tr>
<tr>
<th scope="row">3</th>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">(0.18,-0.20)</td>
<td bgcolor="">0.27</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.18,0.20)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.25,1.13)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.25,1.13) (0.004)</td>
<td bgcolor="">(0.04,0.04)</td>
<td bgcolor="">0.06</td>
<td bgcolor=""><math>$\left[
0.80|0.38\\
0.38|0.31 \right]$</math></td>
<td bgcolor="">(-0.05,-0.03)</td>
<td bgcolor="">2.64</td>
<td bgcolor="">(2.12,1.05)</td>
</tr>
<tr>
<th scope="row">4</th>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">(0.05,-0.08)</td>
<td bgcolor="">0.09</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.05,0.08)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.115,1.058)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.115,1.058) (0.0002)</td>
<td bgcolor="">(0.004,0.004)</td>
<td bgcolor="">0.006</td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>

</tr>
</table>
</center> 
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1. 
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла. 
<center>[[Файл:Рисунок_1.gif]]</center> 

Лема показує, що кожна матриця <math>${d_j}$</math> позитивно визначена і <math>${d_j}$</math> є напрямом спуску. Для доказу леми нам знадобиться : 
'''Теорема 1.''' Нехай S - непорожня безліч в Еn, точка <math>$x \in cl$</math> S. Конусом можливих напрямів в точці x називається безліч <math>$D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$</math>при всіх <math>$\lambda \in (0,\delta )$</math> для деякого <math>$\delta > 0}$</math>. 
'''Визначення.'''Нехай x і y - вектори з Еn і <math>$\left| {{x^T}y} \right|$</math> - абсолютне значення скалярного відтворення <math>$\left {{x^T}y} \right$</math>. Тоді виконується наступна нерівність, звана нерівністю Шварца: 
<center> <math>$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$</math></center>. 

=Лема 1=
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску. 

'''Доведення''' 
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math>
\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) < 0</math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math> j \le n - 1</math>, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо 
<center><math>{x^T}{D_{j + 1}}x = {x^T}{D_j}x + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{D_j}{q_j}}}}</math>(4)</center> 
Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця <math>D_j^{1/2}</math>, така, що <math>{D_j} = D_j^{1/2}D_j^{1/2}</math>. Нехай <math>a = D_j^{1/2}x</math> і <math>b = D_j^{1/2}{q_j}</math>. Тоді <math>{x^T}{D_j}x = {a^T}a,q_j^T{D_j}{q_j} = {b^T}b,{x^T}{D_j}{q_j} = {a^T}b</math>. Підставляючи ці вирази в (4), отримуємо: 
<center><math>{x^T}{D_{j + 1}}x = {\textstyle{{({a^T}a)({b^T}b) - {{({a^T}b)}^2}} \over {{b^T}b}}} + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{q_j}}}}</math>(5)</center> 
По нерівності Шварця маємо <math>({a^T}a)({b^T}b) \ge {({a^T}b)^2 </math>. Так, щоб довести, що<math>{x^T}{D_{j + 1}}x \ge 0</math>, досить показати, що <math>p_j^T{q_j} \ge 0,{b^T}b > 0</math>. З (2) і (3) витікає, що 
<center><math>p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]</math>(6)</center>. 
По припущенню <math>\nabla f({y_j}) \ne 0</math>, і Dj позитивно визначена, так що<math>\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) > 0</math>
Крім того, dj - напрямок спуску, і <math>{\lambda _j} > 0</math>. Тоді із (6) слідує, що <math>p_j^T{q_j} > 0</math>. Крім того <math>{q_j} \ne 0</math> і <math>{b^T}b = q_j^T{D_j}{q_j} > 0</math> 
Видно тепер, що <math>{x^T}{D_{j + 1}}x > 0</math>. Взяти <math>{x^T}{D_{j + 1}}x = 0</math>. Це можливо тільки в тому випадку якщо <math>({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0</math>. Видно, що <math>({a^T}a)({b^T}b) = {({a^T}b)^2}</math> тільки при <math>a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}</math>. Таким чином <math>x = \lambda {q_i}</math>. Так як <math>x \ne 0</math>то<math>\lambda \ne 0</math>. Дальше, <math>0 = p_j^Tx = \lambda p_j^T{q_j}</math>заперечує тому, що <math>p_j^T{q_j} > 0,\lambda \ne 0</math>. 
Отже, <math>{x^T}{D_{j + 1}}x > 0</math>, матриця <math>{D_{j + 1}}</math> позитивно визначена. 
Оскільки <math>\nabla f({y_{j + 1}}) \ne 0</math> і Dj+1 позитивно визначена, маємо <math>\nabla f{({y_{j + 1}})^T}{d_{j + 1}} = - \nabla f{({y_{j + 1}})^T}{D_{j + 1}}\nabla f({y_{j + 1}}) < 0</math>. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску. 
'''Лема доведена!!!''' 

= Список використаної літератури =

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982 
2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975 
[[Категорія:Планування експерименту]]

Метод Девідона – Флетчера – Пауела

2012-02-29T14:09:47Z

Ulllasya:

{{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}}
{{ Surname=Храплива | Name=Уляна | FatherNAme=Вікторівна |Faculti=ФІС | Group=СНм-51 | Zalbook=СНм-11-253}}

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

= Початковий етап =
Нехай <math>$\varepsilon \succ 0$</math> - константа для зупинки. Вибрати точку <math>${x_1}$</math> і початково симетричну позитивно визначену матрицю <math>${D_1}$</math>. Покласти <math>${y_1} = {x_1}$</math>, k = j = 1 і перейти до основного етапу.

= Основний етап =
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1. 
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином: 
<center><math>${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$</math>(1)</center> 
<center>де <math>${p_i} = {\lambda _i}{d_i},$</math>(2)</center> 
<center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math>(3)</center> 
Замінити j на j+1 і перейти до кроку 1.

=Приклад=
Мінімізувати <math>${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$</math> 
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1. 
<center>
<table width="382" border="1">

<tr>
<th scope="row">k</th>
<td width="65" bgcolor="#BDE0BA"><math>${x_k}$</math> <math>$f({x_k})$</math></td>
<td width="18" bgcolor="#BDE0BA">j</td>
<td width="65" bgcolor="#BDE0BA"><math>${y_j}$</math> <math>$f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\nabla f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$</math></td>
<td width="65" bgcolor="#BDE0BA">D</td>
<td width="75" bgcolor="#BDE0BA"><math>${d_j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${\lambda _j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${y_{j + 1}}$</math></td>

</tr>
<tr>
<th scope="row">1</th>
<td bgcolor="">(0.00,3.00) (52.00)</td>

<td bgcolor="">1</td>
<td bgcolor="">(0.00,3.00) (52.00)</td>
<td bgcolor="">(-44.00,24.00)</td>
<td bgcolor="">50.12</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(44.00,-24.00)</td>
<td bgcolor="">0.062</td>
<td bgcolor="">(2.70, 1.51)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.70,1.51) (0.34)</td>
<td bgcolor="">(0.73,1.28)</td>
<td bgcolor="">1.47</td>
<td bgcolor=""><math>$\left[
0.25|0.38\\
0.38|0.71 \right]$</math></td>
<td bgcolor="">(-0.67,-1.31)</td>
<td bgcolor="">0.22</td>
<td bgcolor="">(2.55,1.22)</td>
</tr>

<tr>
<th scope="row">2</th>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">(0.89,-0.44)</td>
<td bgcolor="">0.99</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.89,0.44)</td>
<td bgcolor="">0.11</td>
<td bgcolor="">(2.45,1.27)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.45,1.27) (0.0490)</td>
<td bgcolor="">(0.18,0.36)</td>
<td bgcolor="">0.40</td>
<td bgcolor=""><math>$\left[
0.65|0.45\\
0.45|0.46 \right]$</math></td>
<td bgcolor="">(-0.28,-0.25)</td>
<td bgcolor="">0.64</td>
<td bgcolor="">(2.27,1.11)</td>
</tr>
<tr>
<th scope="row">3</th>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">(0.18,-0.20)</td>
<td bgcolor="">0.27</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.18,0.20)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.25,1.13)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.25,1.13) (0.004)</td>
<td bgcolor="">(0.04,0.04)</td>
<td bgcolor="">0.06</td>
<td bgcolor=""><math>$\left[
0.80|0.38\\
0.38|0.31 \right]$</math></td>
<td bgcolor="">(-0.05,-0.03)</td>
<td bgcolor="">2.64</td>
<td bgcolor="">(2.12,1.05)</td>
</tr>
<tr>
<th scope="row">4</th>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">(0.05,-0.08)</td>
<td bgcolor="">0.09</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.05,0.08)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.115,1.058)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.115,1.058) (0.0002)</td>
<td bgcolor="">(0.004,0.004)</td>
<td bgcolor="">0.006</td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>

</tr>
</table>
</center> 
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1. 
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла. 
<center>[[Файл:Рисунок_1.gif]]</center> 

Лема показує, що кожна матриця <math>${d_j}$</math> позитивно визначена і <math>${d_j}$</math> є напрямом спуску. Для доказу леми нам знадобиться : 
'''Теорема 1.''' Нехай S - непорожня безліч в Еn, точка <math>$x \in cl$</math> S. Конусом можливих напрямів в точці x називається безліч <math>$D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$</math>при всіх <math>$\lambda \in (0,\delta )$</math> для деякого <math>$\delta > 0}$</math>. 
'''Визначення.'''Нехай x і y - вектори з Еn і <math>$\left| {{x^T}y} \right|$</math> - абсолютне значення скалярного відтворення <math>$\left {{x^T}y} \right$</math>. Тоді виконується наступна нерівність, звана нерівністю Шварца: 
<center> <math>$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$</math></center>. 

=Лема 1=
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску. 

'''Доведення''' 
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math>
\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) < 0</math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math> j \le n - 1</math>, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо 
<center><math>{x^T}{D_{j + 1}}x = {x^T}{D_j}x + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{D_j}{q_j}}}}</math>(4)</center> 
Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця <math>D_j^{1/2}</math>, така, що <math>{D_j} = D_j^{1/2}D_j^{1/2}</math>. Нехай <math>a = D_j^{1/2}x</math> і <math>b = D_j^{1/2}{q_j}</math>. Тоді <math>{x^T}{D_j}x = {a^T}a,q_j^T{D_j}{q_j} = {b^T}b,{x^T}{D_j}{q_j} = {a^T}b</math>. Підставляючи ці вирази в (4), отримуємо: 
<center><math>{x^T}{D_{j + 1}}x = {\textstyle{{({a^T}a)({b^T}b) - {{({a^T}b)}^2}} \over {{b^T}b}}} + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{q_j}}}}</math>(5)</center> 
По нерівності Шварця маємо <math>({a^T}a)({b^T}b) \ge {({a^T}b)^2 </math>. Так, щоб довести, що<math>{x^T}{D_{j + 1}}x \ge 0</math>, досить показати, що <math>p_j^T{q_j} \ge 0,{b^T}b > 0</math>. З (2) і (3) витікає, що 
<center><math>p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]</math>(6)</center>. 
По припущенню <math>\nabla f({y_j}) \ne 0</math>, і Dj позитивно визначена, так що<math>\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) > 0</math>
Крім того, dj - напрямок спуску, і <math>{\lambda _j} > 0</math>. Тоді із (6) слідує, що <math>p_j^T{q_j} > 0</math>. Крім того <math>{q_j} \ne 0</math> і <math>{b^T}b = q_j^T{D_j}{q_j} > 0</math> 
Видно тепер, що <math>{x^T}{D_{j + 1}}x > 0</math>. Взяти <math>{x^T}{D_{j + 1}}x = 0</math>. Це можливо тільки в тому випадку якщо <math>({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0</math>. Видно, що <math>({a^T}a)({b^T}b) = {({a^T}b)^2}</math> тільки при <math>a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}</math>. Таким чином <math>x = \lambda {q_i}</math>. Так як <math>x \ne 0</math>то<math>\lambda \ne 0</math>. Дальше, <math>0 = p_j^Tx = \lambda p_j^T{q_j}</math>заперечує тому, що <math>p_j^T{q_j} > 0,\lambda \ne 0</math>. 
Отже, <math>{x^T}{D_{j + 1}}x > 0</math>, матриця <math>{D_{j + 1}}</math> позитивно визначена. 
Оскільки <math>\nabla f({y_{j + 1}}) \ne 0</math> і Dj+1 позитивно визначена, маємо <math>\nabla f{({y_{j + 1}})^T}{d_{j + 1}} = - \nabla f{({y_{j + 1}})^T}{D_{j + 1}}\nabla f({y_{j + 1}}) < 0</math>. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску. 
'''Лема доведена!!!''' 

= Список використаної літератури =

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982 
2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975 
[[Категорія:Планування експерименту]]

Метод Девідона – Флетчера – Пауела

2012-02-29T14:08:45Z

Ulllasya:

{{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}}
{{Студент | Surname=Храплива | Name=Уляна | FatherNAme=Вікторівна |Faculti=ФІС | Group=СНм-51 | Zalbook=СНм-11-253}}

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

= Початковий етап =
Нехай <math>$\varepsilon \succ 0$</math> - константа для зупинки. Вибрати точку <math>${x_1}$</math> і початково симетричну позитивно визначену матрицю <math>${D_1}$</math>. Покласти <math>${y_1} = {x_1}$</math>, k = j = 1 і перейти до основного етапу.

= Основний етап =
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1. 
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином: 
<center><math>${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$</math>(1)</center> 
<center>де <math>${p_i} = {\lambda _i}{d_i},$</math>(2)</center> 
<center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math>(3)</center> 
Замінити j на j+1 і перейти до кроку 1.

=Приклад=
Мінімізувати <math>${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$</math> 
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1. 
<center>
<table width="382" border="1">

<tr>
<th scope="row">k</th>
<td width="65" bgcolor="#BDE0BA"><math>${x_k}$</math> <math>$f({x_k})$</math></td>
<td width="18" bgcolor="#BDE0BA">j</td>
<td width="65" bgcolor="#BDE0BA"><math>${y_j}$</math> <math>$f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\nabla f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$</math></td>
<td width="65" bgcolor="#BDE0BA">D</td>
<td width="75" bgcolor="#BDE0BA"><math>${d_j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${\lambda _j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${y_{j + 1}}$</math></td>

</tr>
<tr>
<th scope="row">1</th>
<td bgcolor="">(0.00,3.00) (52.00)</td>

<td bgcolor="">1</td>
<td bgcolor="">(0.00,3.00) (52.00)</td>
<td bgcolor="">(-44.00,24.00)</td>
<td bgcolor="">50.12</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(44.00,-24.00)</td>
<td bgcolor="">0.062</td>
<td bgcolor="">(2.70, 1.51)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.70,1.51) (0.34)</td>
<td bgcolor="">(0.73,1.28)</td>
<td bgcolor="">1.47</td>
<td bgcolor=""><math>$\left[
0.25|0.38\\
0.38|0.71 \right]$</math></td>
<td bgcolor="">(-0.67,-1.31)</td>
<td bgcolor="">0.22</td>
<td bgcolor="">(2.55,1.22)</td>
</tr>

<tr>
<th scope="row">2</th>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">(0.89,-0.44)</td>
<td bgcolor="">0.99</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.89,0.44)</td>
<td bgcolor="">0.11</td>
<td bgcolor="">(2.45,1.27)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.45,1.27) (0.0490)</td>
<td bgcolor="">(0.18,0.36)</td>
<td bgcolor="">0.40</td>
<td bgcolor=""><math>$\left[
0.65|0.45\\
0.45|0.46 \right]$</math></td>
<td bgcolor="">(-0.28,-0.25)</td>
<td bgcolor="">0.64</td>
<td bgcolor="">(2.27,1.11)</td>
</tr>
<tr>
<th scope="row">3</th>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">(0.18,-0.20)</td>
<td bgcolor="">0.27</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.18,0.20)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.25,1.13)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.25,1.13) (0.004)</td>
<td bgcolor="">(0.04,0.04)</td>
<td bgcolor="">0.06</td>
<td bgcolor=""><math>$\left[
0.80|0.38\\
0.38|0.31 \right]$</math></td>
<td bgcolor="">(-0.05,-0.03)</td>
<td bgcolor="">2.64</td>
<td bgcolor="">(2.12,1.05)</td>
</tr>
<tr>
<th scope="row">4</th>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">(0.05,-0.08)</td>
<td bgcolor="">0.09</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.05,0.08)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.115,1.058)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.115,1.058) (0.0002)</td>
<td bgcolor="">(0.004,0.004)</td>
<td bgcolor="">0.006</td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>

</tr>
</table>
</center> 
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1. 
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла. 
<center>[[Файл:Рисунок_1.gif]]</center> 

Лема показує, що кожна матриця <math>${d_j}$</math> позитивно визначена і <math>${d_j}$</math> є напрямом спуску. Для доказу леми нам знадобиться : 
'''Теорема 1.''' Нехай S - непорожня безліч в Еn, точка <math>$x \in cl$</math> S. Конусом можливих напрямів в точці x називається безліч <math>$D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$</math>при всіх <math>$\lambda \in (0,\delta )$</math> для деякого <math>$\delta > 0}$</math>. 
'''Визначення.'''Нехай x і y - вектори з Еn і <math>$\left| {{x^T}y} \right|$</math> - абсолютне значення скалярного відтворення <math>$\left {{x^T}y} \right$</math>. Тоді виконується наступна нерівність, звана нерівністю Шварца: 
<center> <math>$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$</math></center>. 

=Лема 1=
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску. 

'''Доведення''' 
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math>
\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) < 0</math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math> j \le n - 1</math>, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо 
<center><math>{x^T}{D_{j + 1}}x = {x^T}{D_j}x + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{D_j}{q_j}}}}</math>(4)</center> 
Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця <math>D_j^{1/2}</math>, така, що <math>{D_j} = D_j^{1/2}D_j^{1/2}</math>. Нехай <math>a = D_j^{1/2}x</math> і <math>b = D_j^{1/2}{q_j}</math>. Тоді <math>{x^T}{D_j}x = {a^T}a,q_j^T{D_j}{q_j} = {b^T}b,{x^T}{D_j}{q_j} = {a^T}b</math>. Підставляючи ці вирази в (4), отримуємо: 
<center><math>{x^T}{D_{j + 1}}x = {\textstyle{{({a^T}a)({b^T}b) - {{({a^T}b)}^2}} \over {{b^T}b}}} + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{q_j}}}}</math>(5)</center> 
По нерівності Шварця маємо <math>({a^T}a)({b^T}b) \ge {({a^T}b)^2 </math>. Так, щоб довести, що<math>{x^T}{D_{j + 1}}x \ge 0</math>, досить показати, що <math>p_j^T{q_j} \ge 0,{b^T}b > 0</math>. З (2) і (3) витікає, що 
<center><math>p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]</math>(6)</center>. 
По припущенню <math>\nabla f({y_j}) \ne 0</math>, і Dj позитивно визначена, так що<math>\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) > 0</math>
Крім того, dj - напрямок спуску, і <math>{\lambda _j} > 0</math>. Тоді із (6) слідує, що <math>p_j^T{q_j} > 0</math>. Крім того <math>{q_j} \ne 0</math> і <math>{b^T}b = q_j^T{D_j}{q_j} > 0</math> 
Видно тепер, що <math>{x^T}{D_{j + 1}}x > 0</math>. Взяти <math>{x^T}{D_{j + 1}}x = 0</math>. Це можливо тільки в тому випадку якщо <math>({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0</math>. Видно, що <math>({a^T}a)({b^T}b) = {({a^T}b)^2}</math> тільки при <math>a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}</math>. Таким чином <math>x = \lambda {q_i}</math>. Так як <math>x \ne 0</math>то<math>\lambda \ne 0</math>. Дальше, <math>0 = p_j^Tx = \lambda p_j^T{q_j}</math>заперечує тому, що <math>p_j^T{q_j} > 0,\lambda \ne 0</math>. 
Отже, <math>{x^T}{D_{j + 1}}x > 0</math>, матриця <math>{D_{j + 1}}</math> позитивно визначена. 
Оскільки <math>\nabla f({y_{j + 1}}) \ne 0</math> і Dj+1 позитивно визначена, маємо <math>\nabla f{({y_{j + 1}})^T}{d_{j + 1}} = - \nabla f{({y_{j + 1}})^T}{D_{j + 1}}\nabla f({y_{j + 1}}) < 0</math>. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску. 
'''Лема доведена!!!''' 

= Список використаної літератури =

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982 
2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975 
[[Категорія:Планування експерименту]]

Метод Девідона – Флетчера – Пауела

2012-02-29T14:08:06Z

Ulllasya:

{{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}}

{Студент | Surname=Храплива | Name=Уляна | FatherNAme=Вікторівна |Faculti=ФІС | Group=СНм-51 | Zalbook=СНм-11-253}

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

= Початковий етап =
Нехай <math>$\varepsilon \succ 0$</math> - константа для зупинки. Вибрати точку <math>${x_1}$</math> і початково симетричну позитивно визначену матрицю <math>${D_1}$</math>. Покласти <math>${y_1} = {x_1}$</math>, k = j = 1 і перейти до основного етапу.

= Основний етап =
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1. 
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином: 
<center><math>${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$</math>(1)</center> 
<center>де <math>${p_i} = {\lambda _i}{d_i},$</math>(2)</center> 
<center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math>(3)</center> 
Замінити j на j+1 і перейти до кроку 1.

=Приклад=
Мінімізувати <math>${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$</math> 
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1. 
<center>
<table width="382" border="1">

<tr>
<th scope="row">k</th>
<td width="65" bgcolor="#BDE0BA"><math>${x_k}$</math> <math>$f({x_k})$</math></td>
<td width="18" bgcolor="#BDE0BA">j</td>
<td width="65" bgcolor="#BDE0BA"><math>${y_j}$</math> <math>$f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\nabla f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$</math></td>
<td width="65" bgcolor="#BDE0BA">D</td>
<td width="75" bgcolor="#BDE0BA"><math>${d_j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${\lambda _j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${y_{j + 1}}$</math></td>

</tr>
<tr>
<th scope="row">1</th>
<td bgcolor="">(0.00,3.00) (52.00)</td>

<td bgcolor="">1</td>
<td bgcolor="">(0.00,3.00) (52.00)</td>
<td bgcolor="">(-44.00,24.00)</td>
<td bgcolor="">50.12</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(44.00,-24.00)</td>
<td bgcolor="">0.062</td>
<td bgcolor="">(2.70, 1.51)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.70,1.51) (0.34)</td>
<td bgcolor="">(0.73,1.28)</td>
<td bgcolor="">1.47</td>
<td bgcolor=""><math>$\left[
0.25|0.38\\
0.38|0.71 \right]$</math></td>
<td bgcolor="">(-0.67,-1.31)</td>
<td bgcolor="">0.22</td>
<td bgcolor="">(2.55,1.22)</td>
</tr>

<tr>
<th scope="row">2</th>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">(0.89,-0.44)</td>
<td bgcolor="">0.99</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.89,0.44)</td>
<td bgcolor="">0.11</td>
<td bgcolor="">(2.45,1.27)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.45,1.27) (0.0490)</td>
<td bgcolor="">(0.18,0.36)</td>
<td bgcolor="">0.40</td>
<td bgcolor=""><math>$\left[
0.65|0.45\\
0.45|0.46 \right]$</math></td>
<td bgcolor="">(-0.28,-0.25)</td>
<td bgcolor="">0.64</td>
<td bgcolor="">(2.27,1.11)</td>
</tr>
<tr>
<th scope="row">3</th>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">(0.18,-0.20)</td>
<td bgcolor="">0.27</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.18,0.20)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.25,1.13)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.25,1.13) (0.004)</td>
<td bgcolor="">(0.04,0.04)</td>
<td bgcolor="">0.06</td>
<td bgcolor=""><math>$\left[
0.80|0.38\\
0.38|0.31 \right]$</math></td>
<td bgcolor="">(-0.05,-0.03)</td>
<td bgcolor="">2.64</td>
<td bgcolor="">(2.12,1.05)</td>
</tr>
<tr>
<th scope="row">4</th>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">(0.05,-0.08)</td>
<td bgcolor="">0.09</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.05,0.08)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.115,1.058)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.115,1.058) (0.0002)</td>
<td bgcolor="">(0.004,0.004)</td>
<td bgcolor="">0.006</td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>

</tr>
</table>
</center> 
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1. 
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла. 
<center>[[Файл:Рисунок_1.gif]]</center> 

Лема показує, що кожна матриця <math>${d_j}$</math> позитивно визначена і <math>${d_j}$</math> є напрямом спуску. Для доказу леми нам знадобиться : 
'''Теорема 1.''' Нехай S - непорожня безліч в Еn, точка <math>$x \in cl$</math> S. Конусом можливих напрямів в точці x називається безліч <math>$D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$</math>при всіх <math>$\lambda \in (0,\delta )$</math> для деякого <math>$\delta > 0}$</math>. 
'''Визначення.'''Нехай x і y - вектори з Еn і <math>$\left| {{x^T}y} \right|$</math> - абсолютне значення скалярного відтворення <math>$\left {{x^T}y} \right$</math>. Тоді виконується наступна нерівність, звана нерівністю Шварца: 
<center> <math>$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$</math></center>. 

=Лема 1=
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску. 

'''Доведення''' 
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math>
\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) < 0</math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math> j \le n - 1</math>, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо 
<center><math>{x^T}{D_{j + 1}}x = {x^T}{D_j}x + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{D_j}{q_j}}}}</math>(4)</center> 
Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця <math>D_j^{1/2}</math>, така, що <math>{D_j} = D_j^{1/2}D_j^{1/2}</math>. Нехай <math>a = D_j^{1/2}x</math> і <math>b = D_j^{1/2}{q_j}</math>. Тоді <math>{x^T}{D_j}x = {a^T}a,q_j^T{D_j}{q_j} = {b^T}b,{x^T}{D_j}{q_j} = {a^T}b</math>. Підставляючи ці вирази в (4), отримуємо: 
<center><math>{x^T}{D_{j + 1}}x = {\textstyle{{({a^T}a)({b^T}b) - {{({a^T}b)}^2}} \over {{b^T}b}}} + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{q_j}}}}</math>(5)</center> 
По нерівності Шварця маємо <math>({a^T}a)({b^T}b) \ge {({a^T}b)^2 </math>. Так, щоб довести, що<math>{x^T}{D_{j + 1}}x \ge 0</math>, досить показати, що <math>p_j^T{q_j} \ge 0,{b^T}b > 0</math>. З (2) і (3) витікає, що 
<center><math>p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]</math>(6)</center>. 
По припущенню <math>\nabla f({y_j}) \ne 0</math>, і Dj позитивно визначена, так що<math>\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) > 0</math>
Крім того, dj - напрямок спуску, і <math>{\lambda _j} > 0</math>. Тоді із (6) слідує, що <math>p_j^T{q_j} > 0</math>. Крім того <math>{q_j} \ne 0</math> і <math>{b^T}b = q_j^T{D_j}{q_j} > 0</math> 
Видно тепер, що <math>{x^T}{D_{j + 1}}x > 0</math>. Взяти <math>{x^T}{D_{j + 1}}x = 0</math>. Це можливо тільки в тому випадку якщо <math>({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0</math>. Видно, що <math>({a^T}a)({b^T}b) = {({a^T}b)^2}</math> тільки при <math>a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}</math>. Таким чином <math>x = \lambda {q_i}</math>. Так як <math>x \ne 0</math>то<math>\lambda \ne 0</math>. Дальше, <math>0 = p_j^Tx = \lambda p_j^T{q_j}</math>заперечує тому, що <math>p_j^T{q_j} > 0,\lambda \ne 0</math>. 
Отже, <math>{x^T}{D_{j + 1}}x > 0</math>, матриця <math>{D_{j + 1}}</math> позитивно визначена. 
Оскільки <math>\nabla f({y_{j + 1}}) \ne 0</math> і Dj+1 позитивно визначена, маємо <math>\nabla f{({y_{j + 1}})^T}{d_{j + 1}} = - \nabla f{({y_{j + 1}})^T}{D_{j + 1}}\nabla f({y_{j + 1}}) < 0</math>. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску. 
'''Лема доведена!!!''' 

= Список використаної літератури =

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982 
2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975 
[[Категорія:Планування експерименту]]

Метод Девідона – Флетчера – Пауела

2012-02-29T14:07:04Z

Ulllasya:

{{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}}

{{Студент | Name=Уляна | Surname=Храплива | FatherNAme=Вікторівна |Faculti=ФІС | Group=СНм-51 | Zalbook=СНм-11-253}}

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

= Початковий етап =
Нехай <math>$\varepsilon \succ 0$</math> - константа для зупинки. Вибрати точку <math>${x_1}$</math> і початково симетричну позитивно визначену матрицю <math>${D_1}$</math>. Покласти <math>${y_1} = {x_1}$</math>, k = j = 1 і перейти до основного етапу.

= Основний етап =
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1. 
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином: 
<center><math>${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$</math>(1)</center> 
<center>де <math>${p_i} = {\lambda _i}{d_i},$</math>(2)</center> 
<center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math>(3)</center> 
Замінити j на j+1 і перейти до кроку 1.

=Приклад=
Мінімізувати <math>${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$</math> 
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1. 
<center>
<table width="382" border="1">

<tr>
<th scope="row">k</th>
<td width="65" bgcolor="#BDE0BA"><math>${x_k}$</math> <math>$f({x_k})$</math></td>
<td width="18" bgcolor="#BDE0BA">j</td>
<td width="65" bgcolor="#BDE0BA"><math>${y_j}$</math> <math>$f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\nabla f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$</math></td>
<td width="65" bgcolor="#BDE0BA">D</td>
<td width="75" bgcolor="#BDE0BA"><math>${d_j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${\lambda _j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${y_{j + 1}}$</math></td>

</tr>
<tr>
<th scope="row">1</th>
<td bgcolor="">(0.00,3.00) (52.00)</td>

<td bgcolor="">1</td>
<td bgcolor="">(0.00,3.00) (52.00)</td>
<td bgcolor="">(-44.00,24.00)</td>
<td bgcolor="">50.12</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(44.00,-24.00)</td>
<td bgcolor="">0.062</td>
<td bgcolor="">(2.70, 1.51)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.70,1.51) (0.34)</td>
<td bgcolor="">(0.73,1.28)</td>
<td bgcolor="">1.47</td>
<td bgcolor=""><math>$\left[
0.25|0.38\\
0.38|0.71 \right]$</math></td>
<td bgcolor="">(-0.67,-1.31)</td>
<td bgcolor="">0.22</td>
<td bgcolor="">(2.55,1.22)</td>
</tr>

<tr>
<th scope="row">2</th>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">(0.89,-0.44)</td>
<td bgcolor="">0.99</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.89,0.44)</td>
<td bgcolor="">0.11</td>
<td bgcolor="">(2.45,1.27)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.45,1.27) (0.0490)</td>
<td bgcolor="">(0.18,0.36)</td>
<td bgcolor="">0.40</td>
<td bgcolor=""><math>$\left[
0.65|0.45\\
0.45|0.46 \right]$</math></td>
<td bgcolor="">(-0.28,-0.25)</td>
<td bgcolor="">0.64</td>
<td bgcolor="">(2.27,1.11)</td>
</tr>
<tr>
<th scope="row">3</th>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">(0.18,-0.20)</td>
<td bgcolor="">0.27</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.18,0.20)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.25,1.13)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.25,1.13) (0.004)</td>
<td bgcolor="">(0.04,0.04)</td>
<td bgcolor="">0.06</td>
<td bgcolor=""><math>$\left[
0.80|0.38\\
0.38|0.31 \right]$</math></td>
<td bgcolor="">(-0.05,-0.03)</td>
<td bgcolor="">2.64</td>
<td bgcolor="">(2.12,1.05)</td>
</tr>
<tr>
<th scope="row">4</th>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">(0.05,-0.08)</td>
<td bgcolor="">0.09</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.05,0.08)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.115,1.058)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.115,1.058) (0.0002)</td>
<td bgcolor="">(0.004,0.004)</td>
<td bgcolor="">0.006</td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>

</tr>
</table>
</center> 
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1. 
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла. 
<center>[[Файл:Рисунок_1.gif]]</center> 

Лема показує, що кожна матриця <math>${d_j}$</math> позитивно визначена і <math>${d_j}$</math> є напрямом спуску. Для доказу леми нам знадобиться : 
'''Теорема 1.''' Нехай S - непорожня безліч в Еn, точка <math>$x \in cl$</math> S. Конусом можливих напрямів в точці x називається безліч <math>$D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$</math>при всіх <math>$\lambda \in (0,\delta )$</math> для деякого <math>$\delta > 0}$</math>. 
'''Визначення.'''Нехай x і y - вектори з Еn і <math>$\left| {{x^T}y} \right|$</math> - абсолютне значення скалярного відтворення <math>$\left {{x^T}y} \right$</math>. Тоді виконується наступна нерівність, звана нерівністю Шварца: 
<center> <math>$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$</math></center>. 

=Лема 1=
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску. 

'''Доведення''' 
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math>
\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) < 0</math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math> j \le n - 1</math>, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо 
<center><math>{x^T}{D_{j + 1}}x = {x^T}{D_j}x + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{D_j}{q_j}}}}</math>(4)</center> 
Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця <math>D_j^{1/2}</math>, така, що <math>{D_j} = D_j^{1/2}D_j^{1/2}</math>. Нехай <math>a = D_j^{1/2}x</math> і <math>b = D_j^{1/2}{q_j}</math>. Тоді <math>{x^T}{D_j}x = {a^T}a,q_j^T{D_j}{q_j} = {b^T}b,{x^T}{D_j}{q_j} = {a^T}b</math>. Підставляючи ці вирази в (4), отримуємо: 
<center><math>{x^T}{D_{j + 1}}x = {\textstyle{{({a^T}a)({b^T}b) - {{({a^T}b)}^2}} \over {{b^T}b}}} + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{q_j}}}}</math>(5)</center> 
По нерівності Шварця маємо <math>({a^T}a)({b^T}b) \ge {({a^T}b)^2 </math>. Так, щоб довести, що<math>{x^T}{D_{j + 1}}x \ge 0</math>, досить показати, що <math>p_j^T{q_j} \ge 0,{b^T}b > 0</math>. З (2) і (3) витікає, що 
<center><math>p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]</math>(6)</center>. 
По припущенню <math>\nabla f({y_j}) \ne 0</math>, і Dj позитивно визначена, так що<math>\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) > 0</math>
Крім того, dj - напрямок спуску, і <math>{\lambda _j} > 0</math>. Тоді із (6) слідує, що <math>p_j^T{q_j} > 0</math>. Крім того <math>{q_j} \ne 0</math> і <math>{b^T}b = q_j^T{D_j}{q_j} > 0</math> 
Видно тепер, що <math>{x^T}{D_{j + 1}}x > 0</math>. Взяти <math>{x^T}{D_{j + 1}}x = 0</math>. Це можливо тільки в тому випадку якщо <math>({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0</math>. Видно, що <math>({a^T}a)({b^T}b) = {({a^T}b)^2}</math> тільки при <math>a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}</math>. Таким чином <math>x = \lambda {q_i}</math>. Так як <math>x \ne 0</math>то<math>\lambda \ne 0</math>. Дальше, <math>0 = p_j^Tx = \lambda p_j^T{q_j}</math>заперечує тому, що <math>p_j^T{q_j} > 0,\lambda \ne 0</math>. 
Отже, <math>{x^T}{D_{j + 1}}x > 0</math>, матриця <math>{D_{j + 1}}</math> позитивно визначена. 
Оскільки <math>\nabla f({y_{j + 1}}) \ne 0</math> і Dj+1 позитивно визначена, маємо <math>\nabla f{({y_{j + 1}})^T}{d_{j + 1}} = - \nabla f{({y_{j + 1}})^T}{D_{j + 1}}\nabla f({y_{j + 1}}) < 0</math>. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску. 
'''Лема доведена!!!''' 

= Список використаної літератури =

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982 
2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975 
[[Категорія:Планування експерименту]]

Метод Девідона – Флетчера – Пауела

2012-02-29T14:06:18Z

Ulllasya:

{{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}}

{{Студент | Name=Уляна | Surname=Храплива | FatherNAme=Вікторівна |Faculti=ФІС | Group=СНм-51 | Zalbook=СНм-11-253}}
{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По-батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНм-51
|-
| '''Залікова книжка''' || СНм-11-253
|}

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

= Початковий етап =
Нехай <math>$\varepsilon \succ 0$</math> - константа для зупинки. Вибрати точку <math>${x_1}$</math> і початково симетричну позитивно визначену матрицю <math>${D_1}$</math>. Покласти <math>${y_1} = {x_1}$</math>, k = j = 1 і перейти до основного етапу.

= Основний етап =
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1. 
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином: 
<center><math>${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$</math>(1)</center> 
<center>де <math>${p_i} = {\lambda _i}{d_i},$</math>(2)</center> 
<center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math>(3)</center> 
Замінити j на j+1 і перейти до кроку 1.

=Приклад=
Мінімізувати <math>${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$</math> 
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1. 
<center>
<table width="382" border="1">

<tr>
<th scope="row">k</th>
<td width="65" bgcolor="#BDE0BA"><math>${x_k}$</math> <math>$f({x_k})$</math></td>
<td width="18" bgcolor="#BDE0BA">j</td>
<td width="65" bgcolor="#BDE0BA"><math>${y_j}$</math> <math>$f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\nabla f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$</math></td>
<td width="65" bgcolor="#BDE0BA">D</td>
<td width="75" bgcolor="#BDE0BA"><math>${d_j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${\lambda _j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${y_{j + 1}}$</math></td>

</tr>
<tr>
<th scope="row">1</th>
<td bgcolor="">(0.00,3.00) (52.00)</td>

<td bgcolor="">1</td>
<td bgcolor="">(0.00,3.00) (52.00)</td>
<td bgcolor="">(-44.00,24.00)</td>
<td bgcolor="">50.12</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(44.00,-24.00)</td>
<td bgcolor="">0.062</td>
<td bgcolor="">(2.70, 1.51)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.70,1.51) (0.34)</td>
<td bgcolor="">(0.73,1.28)</td>
<td bgcolor="">1.47</td>
<td bgcolor=""><math>$\left[
0.25|0.38\\
0.38|0.71 \right]$</math></td>
<td bgcolor="">(-0.67,-1.31)</td>
<td bgcolor="">0.22</td>
<td bgcolor="">(2.55,1.22)</td>
</tr>

<tr>
<th scope="row">2</th>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">(0.89,-0.44)</td>
<td bgcolor="">0.99</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.89,0.44)</td>
<td bgcolor="">0.11</td>
<td bgcolor="">(2.45,1.27)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.45,1.27) (0.0490)</td>
<td bgcolor="">(0.18,0.36)</td>
<td bgcolor="">0.40</td>
<td bgcolor=""><math>$\left[
0.65|0.45\\
0.45|0.46 \right]$</math></td>
<td bgcolor="">(-0.28,-0.25)</td>
<td bgcolor="">0.64</td>
<td bgcolor="">(2.27,1.11)</td>
</tr>
<tr>
<th scope="row">3</th>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">(0.18,-0.20)</td>
<td bgcolor="">0.27</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.18,0.20)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.25,1.13)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.25,1.13) (0.004)</td>
<td bgcolor="">(0.04,0.04)</td>
<td bgcolor="">0.06</td>
<td bgcolor=""><math>$\left[
0.80|0.38\\
0.38|0.31 \right]$</math></td>
<td bgcolor="">(-0.05,-0.03)</td>
<td bgcolor="">2.64</td>
<td bgcolor="">(2.12,1.05)</td>
</tr>
<tr>
<th scope="row">4</th>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">(0.05,-0.08)</td>
<td bgcolor="">0.09</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.05,0.08)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.115,1.058)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.115,1.058) (0.0002)</td>
<td bgcolor="">(0.004,0.004)</td>
<td bgcolor="">0.006</td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>

</tr>
</table>
</center> 
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1. 
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла. 
<center>[[Файл:Рисунок_1.gif]]</center> 

Лема показує, що кожна матриця <math>${d_j}$</math> позитивно визначена і <math>${d_j}$</math> є напрямом спуску. Для доказу леми нам знадобиться : 
'''Теорема 1.''' Нехай S - непорожня безліч в Еn, точка <math>$x \in cl$</math> S. Конусом можливих напрямів в точці x називається безліч <math>$D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$</math>при всіх <math>$\lambda \in (0,\delta )$</math> для деякого <math>$\delta > 0}$</math>. 
'''Визначення.'''Нехай x і y - вектори з Еn і <math>$\left| {{x^T}y} \right|$</math> - абсолютне значення скалярного відтворення <math>$\left {{x^T}y} \right$</math>. Тоді виконується наступна нерівність, звана нерівністю Шварца: 
<center> <math>$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$</math></center>. 

=Лема 1=
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску. 

'''Доведення''' 
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math>
\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) < 0</math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math> j \le n - 1</math>, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо 
<center><math>{x^T}{D_{j + 1}}x = {x^T}{D_j}x + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{D_j}{q_j}}}}</math>(4)</center> 
Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця <math>D_j^{1/2}</math>, така, що <math>{D_j} = D_j^{1/2}D_j^{1/2}</math>. Нехай <math>a = D_j^{1/2}x</math> і <math>b = D_j^{1/2}{q_j}</math>. Тоді <math>{x^T}{D_j}x = {a^T}a,q_j^T{D_j}{q_j} = {b^T}b,{x^T}{D_j}{q_j} = {a^T}b</math>. Підставляючи ці вирази в (4), отримуємо: 
<center><math>{x^T}{D_{j + 1}}x = {\textstyle{{({a^T}a)({b^T}b) - {{({a^T}b)}^2}} \over {{b^T}b}}} + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{q_j}}}}</math>(5)</center> 
По нерівності Шварця маємо <math>({a^T}a)({b^T}b) \ge {({a^T}b)^2 </math>. Так, щоб довести, що<math>{x^T}{D_{j + 1}}x \ge 0</math>, досить показати, що <math>p_j^T{q_j} \ge 0,{b^T}b > 0</math>. З (2) і (3) витікає, що 
<center><math>p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]</math>(6)</center>. 
По припущенню <math>\nabla f({y_j}) \ne 0</math>, і Dj позитивно визначена, так що<math>\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) > 0</math>
Крім того, dj - напрямок спуску, і <math>{\lambda _j} > 0</math>. Тоді із (6) слідує, що <math>p_j^T{q_j} > 0</math>. Крім того <math>{q_j} \ne 0</math> і <math>{b^T}b = q_j^T{D_j}{q_j} > 0</math> 
Видно тепер, що <math>{x^T}{D_{j + 1}}x > 0</math>. Взяти <math>{x^T}{D_{j + 1}}x = 0</math>. Це можливо тільки в тому випадку якщо <math>({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0</math>. Видно, що <math>({a^T}a)({b^T}b) = {({a^T}b)^2}</math> тільки при <math>a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}</math>. Таким чином <math>x = \lambda {q_i}</math>. Так як <math>x \ne 0</math>то<math>\lambda \ne 0</math>. Дальше, <math>0 = p_j^Tx = \lambda p_j^T{q_j}</math>заперечує тому, що <math>p_j^T{q_j} > 0,\lambda \ne 0</math>. 
Отже, <math>{x^T}{D_{j + 1}}x > 0</math>, матриця <math>{D_{j + 1}}</math> позитивно визначена. 
Оскільки <math>\nabla f({y_{j + 1}}) \ne 0</math> і Dj+1 позитивно визначена, маємо <math>\nabla f{({y_{j + 1}})^T}{d_{j + 1}} = - \nabla f{({y_{j + 1}})^T}{D_{j + 1}}\nabla f({y_{j + 1}}) < 0</math>. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску. 
'''Лема доведена!!!''' 

= Список використаної літератури =

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982 
2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975 
[[Категорія:Планування експерименту]]

Метод Девідона – Флетчера – Пауела

2012-02-29T14:05:51Z

Ulllasya:

{{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}}

{{Студент | Name=Уляна | Surname=Храплива | FatherNAme=Вікторівна |Faculti=ФІС | Group=СНм-51 | Zalbook=СНм-11-253}}

{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По-батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНм-51
|-
| '''Залікова книжка''' || СНм-11-253
|}

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

= Початковий етап =
Нехай <math>$\varepsilon \succ 0$</math> - константа для зупинки. Вибрати точку <math>${x_1}$</math> і початково симетричну позитивно визначену матрицю <math>${D_1}$</math>. Покласти <math>${y_1} = {x_1}$</math>, k = j = 1 і перейти до основного етапу.

= Основний етап =
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1. 
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином: 
<center><math>${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$</math>(1)</center> 
<center>де <math>${p_i} = {\lambda _i}{d_i},$</math>(2)</center> 
<center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math>(3)</center> 
Замінити j на j+1 і перейти до кроку 1.

=Приклад=
Мінімізувати <math>${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$</math> 
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1. 
<center>
<table width="382" border="1">

<tr>
<th scope="row">k</th>
<td width="65" bgcolor="#BDE0BA"><math>${x_k}$</math> <math>$f({x_k})$</math></td>
<td width="18" bgcolor="#BDE0BA">j</td>
<td width="65" bgcolor="#BDE0BA"><math>${y_j}$</math> <math>$f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\nabla f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$</math></td>
<td width="65" bgcolor="#BDE0BA">D</td>
<td width="75" bgcolor="#BDE0BA"><math>${d_j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${\lambda _j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${y_{j + 1}}$</math></td>

</tr>
<tr>
<th scope="row">1</th>
<td bgcolor="">(0.00,3.00) (52.00)</td>

<td bgcolor="">1</td>
<td bgcolor="">(0.00,3.00) (52.00)</td>
<td bgcolor="">(-44.00,24.00)</td>
<td bgcolor="">50.12</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(44.00,-24.00)</td>
<td bgcolor="">0.062</td>
<td bgcolor="">(2.70, 1.51)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.70,1.51) (0.34)</td>
<td bgcolor="">(0.73,1.28)</td>
<td bgcolor="">1.47</td>
<td bgcolor=""><math>$\left[
0.25|0.38\\
0.38|0.71 \right]$</math></td>
<td bgcolor="">(-0.67,-1.31)</td>
<td bgcolor="">0.22</td>
<td bgcolor="">(2.55,1.22)</td>
</tr>

<tr>
<th scope="row">2</th>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">(0.89,-0.44)</td>
<td bgcolor="">0.99</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.89,0.44)</td>
<td bgcolor="">0.11</td>
<td bgcolor="">(2.45,1.27)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.45,1.27) (0.0490)</td>
<td bgcolor="">(0.18,0.36)</td>
<td bgcolor="">0.40</td>
<td bgcolor=""><math>$\left[
0.65|0.45\\
0.45|0.46 \right]$</math></td>
<td bgcolor="">(-0.28,-0.25)</td>
<td bgcolor="">0.64</td>
<td bgcolor="">(2.27,1.11)</td>
</tr>
<tr>
<th scope="row">3</th>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">(0.18,-0.20)</td>
<td bgcolor="">0.27</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.18,0.20)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.25,1.13)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.25,1.13) (0.004)</td>
<td bgcolor="">(0.04,0.04)</td>
<td bgcolor="">0.06</td>
<td bgcolor=""><math>$\left[
0.80|0.38\\
0.38|0.31 \right]$</math></td>
<td bgcolor="">(-0.05,-0.03)</td>
<td bgcolor="">2.64</td>
<td bgcolor="">(2.12,1.05)</td>
</tr>
<tr>
<th scope="row">4</th>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">(0.05,-0.08)</td>
<td bgcolor="">0.09</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.05,0.08)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.115,1.058)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.115,1.058) (0.0002)</td>
<td bgcolor="">(0.004,0.004)</td>
<td bgcolor="">0.006</td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>

</tr>
</table>
</center> 
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1. 
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла. 
<center>[[Файл:Рисунок_1.gif]]</center> 

Лема показує, що кожна матриця <math>${d_j}$</math> позитивно визначена і <math>${d_j}$</math> є напрямом спуску. Для доказу леми нам знадобиться : 
'''Теорема 1.''' Нехай S - непорожня безліч в Еn, точка <math>$x \in cl$</math> S. Конусом можливих напрямів в точці x називається безліч <math>$D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$</math>при всіх <math>$\lambda \in (0,\delta )$</math> для деякого <math>$\delta > 0}$</math>. 
'''Визначення.'''Нехай x і y - вектори з Еn і <math>$\left| {{x^T}y} \right|$</math> - абсолютне значення скалярного відтворення <math>$\left {{x^T}y} \right$</math>. Тоді виконується наступна нерівність, звана нерівністю Шварца: 
<center> <math>$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$</math></center>. 

=Лема 1=
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску. 

'''Доведення''' 
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math>
\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) < 0</math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math> j \le n - 1</math>, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо 
<center><math>{x^T}{D_{j + 1}}x = {x^T}{D_j}x + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{D_j}{q_j}}}}</math>(4)</center> 
Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця <math>D_j^{1/2}</math>, така, що <math>{D_j} = D_j^{1/2}D_j^{1/2}</math>. Нехай <math>a = D_j^{1/2}x</math> і <math>b = D_j^{1/2}{q_j}</math>. Тоді <math>{x^T}{D_j}x = {a^T}a,q_j^T{D_j}{q_j} = {b^T}b,{x^T}{D_j}{q_j} = {a^T}b</math>. Підставляючи ці вирази в (4), отримуємо: 
<center><math>{x^T}{D_{j + 1}}x = {\textstyle{{({a^T}a)({b^T}b) - {{({a^T}b)}^2}} \over {{b^T}b}}} + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{q_j}}}}</math>(5)</center> 
По нерівності Шварця маємо <math>({a^T}a)({b^T}b) \ge {({a^T}b)^2 </math>. Так, щоб довести, що<math>{x^T}{D_{j + 1}}x \ge 0</math>, досить показати, що <math>p_j^T{q_j} \ge 0,{b^T}b > 0</math>. З (2) і (3) витікає, що 
<center><math>p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]</math>(6)</center>. 
По припущенню <math>\nabla f({y_j}) \ne 0</math>, і Dj позитивно визначена, так що<math>\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) > 0</math>
Крім того, dj - напрямок спуску, і <math>{\lambda _j} > 0</math>. Тоді із (6) слідує, що <math>p_j^T{q_j} > 0</math>. Крім того <math>{q_j} \ne 0</math> і <math>{b^T}b = q_j^T{D_j}{q_j} > 0</math> 
Видно тепер, що <math>{x^T}{D_{j + 1}}x > 0</math>. Взяти <math>{x^T}{D_{j + 1}}x = 0</math>. Це можливо тільки в тому випадку якщо <math>({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0</math>. Видно, що <math>({a^T}a)({b^T}b) = {({a^T}b)^2}</math> тільки при <math>a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}</math>. Таким чином <math>x = \lambda {q_i}</math>. Так як <math>x \ne 0</math>то<math>\lambda \ne 0</math>. Дальше, <math>0 = p_j^Tx = \lambda p_j^T{q_j}</math>заперечує тому, що <math>p_j^T{q_j} > 0,\lambda \ne 0</math>. 
Отже, <math>{x^T}{D_{j + 1}}x > 0</math>, матриця <math>{D_{j + 1}}</math> позитивно визначена. 
Оскільки <math>\nabla f({y_{j + 1}}) \ne 0</math> і Dj+1 позитивно визначена, маємо <math>\nabla f{({y_{j + 1}})^T}{d_{j + 1}} = - \nabla f{({y_{j + 1}})^T}{D_{j + 1}}\nabla f({y_{j + 1}}) < 0</math>. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску. 
'''Лема доведена!!!''' 

= Список використаної літератури =

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982 
2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975 
[[Категорія:Планування експерименту]]

Метод Девідона – Флетчера – Пауела

2012-02-26T14:31:25Z

Ulllasya:

{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По-батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНм-51
|-
| '''Залікова книжка''' || СНм-11-253
|}

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

= Початковий етап =
Нехай <math>$\varepsilon \succ 0$</math> - константа для зупинки. Вибрати точку <math>${x_1}$</math> і початково симетричну позитивно визначену матрицю <math>${D_1}$</math>. Покласти <math>${y_1} = {x_1}$</math>, k = j = 1 і перейти до основного етапу.

= Основний етап =
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1. 
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином: 
<center><math>${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$</math>(1)</center> 
<center>де <math>${p_i} = {\lambda _i}{d_i},$</math>(2)</center> 
<center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math>(3)</center> 
Замінити j на j+1 і перейти до кроку 1.

=Приклад=
Мінімізувати <math>${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$</math> 
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1. 
<center>
<table width="382" border="1">

<tr>
<th scope="row">k</th>
<td width="65" bgcolor="#BDE0BA"><math>${x_k}$</math> <math>$f({x_k})$</math></td>
<td width="18" bgcolor="#BDE0BA">j</td>
<td width="65" bgcolor="#BDE0BA"><math>${y_j}$</math> <math>$f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\nabla f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$</math></td>
<td width="65" bgcolor="#BDE0BA">D</td>
<td width="75" bgcolor="#BDE0BA"><math>${d_j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${\lambda _j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${y_{j + 1}}$</math></td>

</tr>
<tr>
<th scope="row">1</th>
<td bgcolor="">(0.00,3.00) (52.00)</td>

<td bgcolor="">1</td>
<td bgcolor="">(0.00,3.00) (52.00)</td>
<td bgcolor="">(-44.00,24.00)</td>
<td bgcolor="">50.12</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(44.00,-24.00)</td>
<td bgcolor="">0.062</td>
<td bgcolor="">(2.70, 1.51)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.70,1.51) (0.34)</td>
<td bgcolor="">(0.73,1.28)</td>
<td bgcolor="">1.47</td>
<td bgcolor=""><math>$\left[
0.25|0.38\\
0.38|0.71 \right]$</math></td>
<td bgcolor="">(-0.67,-1.31)</td>
<td bgcolor="">0.22</td>
<td bgcolor="">(2.55,1.22)</td>
</tr>

<tr>
<th scope="row">2</th>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">(0.89,-0.44)</td>
<td bgcolor="">0.99</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.89,0.44)</td>
<td bgcolor="">0.11</td>
<td bgcolor="">(2.45,1.27)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.45,1.27) (0.0490)</td>
<td bgcolor="">(0.18,0.36)</td>
<td bgcolor="">0.40</td>
<td bgcolor=""><math>$\left[
0.65|0.45\\
0.45|0.46 \right]$</math></td>
<td bgcolor="">(-0.28,-0.25)</td>
<td bgcolor="">0.64</td>
<td bgcolor="">(2.27,1.11)</td>
</tr>
<tr>
<th scope="row">3</th>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">(0.18,-0.20)</td>
<td bgcolor="">0.27</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.18,0.20)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.25,1.13)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.25,1.13) (0.004)</td>
<td bgcolor="">(0.04,0.04)</td>
<td bgcolor="">0.06</td>
<td bgcolor=""><math>$\left[
0.80|0.38\\
0.38|0.31 \right]$</math></td>
<td bgcolor="">(-0.05,-0.03)</td>
<td bgcolor="">2.64</td>
<td bgcolor="">(2.12,1.05)</td>
</tr>
<tr>
<th scope="row">4</th>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">(0.05,-0.08)</td>
<td bgcolor="">0.09</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.05,0.08)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.115,1.058)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.115,1.058) (0.0002)</td>
<td bgcolor="">(0.004,0.004)</td>
<td bgcolor="">0.006</td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>

</tr>
</table>
</center> 
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1. 
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла. 
<center>[[Файл:Рисунок_1.gif]]</center> 

Лема показує, що кожна матриця <math>${d_j}$</math> позитивно визначена і <math>${d_j}$</math> є напрямом спуску. Для доказу леми нам знадобиться : 
'''Теорема 1.''' Нехай S - непорожня безліч в Еn, точка <math>$x \in cl$</math> S. Конусом можливих напрямів в точці x називається безліч <math>$D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$</math>при всіх <math>$\lambda \in (0,\delta )$</math> для деякого <math>$\delta > 0}$</math>. 
'''Визначення.'''Нехай x і y - вектори з Еn і <math>$\left| {{x^T}y} \right|$</math> - абсолютне значення скалярного відтворення <math>$\left {{x^T}y} \right$</math>. Тоді виконується наступна нерівність, звана нерівністю Шварца: 
<center> <math>$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$</math></center>. 

=Лема 1=
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску. 

'''Доведення''' 
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math>
\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) < 0</math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math> j \le n - 1</math>, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо 
<center><math>{x^T}{D_{j + 1}}x = {x^T}{D_j}x + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{D_j}{q_j}}}}</math>(4)</center> 
Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця <math>D_j^{1/2}</math>, така, що <math>{D_j} = D_j^{1/2}D_j^{1/2}</math>. Нехай <math>a = D_j^{1/2}x</math> і <math>b = D_j^{1/2}{q_j}</math>. Тоді <math>{x^T}{D_j}x = {a^T}a,q_j^T{D_j}{q_j} = {b^T}b,{x^T}{D_j}{q_j} = {a^T}b</math>. Підставляючи ці вирази в (4), отримуємо: 
<center><math>{x^T}{D_{j + 1}}x = {\textstyle{{({a^T}a)({b^T}b) - {{({a^T}b)}^2}} \over {{b^T}b}}} + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{q_j}}}}</math>(5)</center> 
По нерівності Шварця маємо <math>({a^T}a)({b^T}b) \ge {({a^T}b)^2 </math>. Так, щоб довести, що<math>{x^T}{D_{j + 1}}x \ge 0</math>, досить показати, що <math>p_j^T{q_j} \ge 0,{b^T}b > 0</math>. З (2) і (3) витікає, що 
<center><math>p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]</math>(6)</center>. 
По припущенню <math>\nabla f({y_j}) \ne 0</math>, і Dj позитивно визначена, так що<math>\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) > 0</math>
Крім того, dj - напрямок спуску, і <math>{\lambda _j} > 0</math>. Тоді із (6) слідує, що <math>p_j^T{q_j} > 0</math>. Крім того <math>{q_j} \ne 0</math> і <math>{b^T}b = q_j^T{D_j}{q_j} > 0</math> 
Видно тепер, що <math>{x^T}{D_{j + 1}}x > 0</math>. Взяти <math>{x^T}{D_{j + 1}}x = 0</math>. Це можливо тільки в тому випадку якщо <math>({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0</math>. Видно, що <math>({a^T}a)({b^T}b) = {({a^T}b)^2}</math> тільки при <math>a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}</math>. Таким чином <math>x = \lambda {q_i}</math>. Так як <math>x \ne 0</math>то<math>\lambda \ne 0</math>. Дальше, <math>0 = p_j^Tx = \lambda p_j^T{q_j}</math>заперечує тому, що <math>p_j^T{q_j} > 0,\lambda \ne 0</math>. 
Отже, <math>{x^T}{D_{j + 1}}x > 0</math>, матриця <math>{D_{j + 1}}</math> позитивно визначена. 
Оскільки <math>\nabla f({y_{j + 1}}) \ne 0</math> і Dj+1 позитивно визначена, маємо <math>\nabla f{({y_{j + 1}})^T}{d_{j + 1}} = - \nabla f{({y_{j + 1}})^T}{D_{j + 1}}\nabla f({y_{j + 1}}) < 0</math>. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску. 
'''Лема доведена!!!''' 

= Список використаної літератури =

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982 
2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975 
[[Категорія:Планування експерименту]]

Метод Девідона – Флетчера – Пауела

2012-02-26T14:05:10Z

Ulllasya:

{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По-батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНм-51
|-
| '''Залікова книжка''' || СНм-11-253
|}

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

= Початковий етап =
Нехай <math>$\varepsilon \succ 0$</math> - константа для зупинки. Вибрати точку <math>${x_1}$</math> і початково симетричну позитивно визначену матрицю <math>${D_1}$</math>. Покласти <math>${y_1} = {x_1}$</math>, k = j = 1 і перейти до основного етапу.

= Основний етап =
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1. 
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином: 
<center><math>${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$</math>(1)</center> 
<center>де <math>${p_i} = {\lambda _i}{d_i},$</math>(2)</center> 
<center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math>(3)</center> 
Замінити j на j+1 і перейти до кроку 1.

=Приклад=
Мінімізувати <math>${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$</math> 
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1. 
<center>
<table width="382" border="1">

<tr>
<th scope="row">k</th>
<td width="65" bgcolor="#BDE0BA"><math>${x_k}$</math> <math>$f({x_k})$</math></td>
<td width="18" bgcolor="#BDE0BA">j</td>
<td width="65" bgcolor="#BDE0BA"><math>${y_j}$</math> <math>$f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\nabla f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$</math></td>
<td width="65" bgcolor="#BDE0BA">D</td>
<td width="75" bgcolor="#BDE0BA"><math>${d_j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${\lambda _j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${y_{j + 1}}$</math></td>

</tr>
<tr>
<th scope="row">1</th>
<td bgcolor="">(0.00,3.00) (52.00)</td>

<td bgcolor="">1</td>
<td bgcolor="">(0.00,3.00) (52.00)</td>
<td bgcolor="">(-44.00,24.00)</td>
<td bgcolor="">50.12</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(44.00,-24.00)</td>
<td bgcolor="">0.062</td>
<td bgcolor="">(2.70, 1.51)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.70,1.51) (0.34)</td>
<td bgcolor="">(0.73,1.28)</td>
<td bgcolor="">1.47</td>
<td bgcolor=""><math>$\left[
0.25|0.38\\
0.38|0.71 \right]$</math></td>
<td bgcolor="">(-0.67,-1.31)</td>
<td bgcolor="">0.22</td>
<td bgcolor="">(2.55,1.22)</td>
</tr>

<tr>
<th scope="row">2</th>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">(0.89,-0.44)</td>
<td bgcolor="">0.99</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.89,0.44)</td>
<td bgcolor="">0.11</td>
<td bgcolor="">(2.45,1.27)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.45,1.27) (0.0490)</td>
<td bgcolor="">(0.18,0.36)</td>
<td bgcolor="">0.40</td>
<td bgcolor=""><math>$\left[
0.65|0.45\\
0.45|0.46 \right]$</math></td>
<td bgcolor="">(-0.28,-0.25)</td>
<td bgcolor="">0.64</td>
<td bgcolor="">(2.27,1.11)</td>
</tr>
<tr>
<th scope="row">3</th>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">(0.18,-0.20)</td>
<td bgcolor="">0.27</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.18,0.20)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.25,1.13)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.25,1.13) (0.004)</td>
<td bgcolor="">(0.04,0.04)</td>
<td bgcolor="">0.06</td>
<td bgcolor=""><math>$\left[
0.80|0.38\\
0.38|0.31 \right]$</math></td>
<td bgcolor="">(-0.05,-0.03)</td>
<td bgcolor="">2.64</td>
<td bgcolor="">(2.12,1.05)</td>
</tr>
<tr>
<th scope="row">4</th>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">(0.05,-0.08)</td>
<td bgcolor="">0.09</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.05,0.08)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.115,1.058)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.115,1.058) (0.0002)</td>
<td bgcolor="">(0.004,0.004)</td>
<td bgcolor="">0.006</td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>

</tr>
</table>
</center> 
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1. 
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла. 
<center>[[Файл:Рисунок_1.gif]]</center> 

Лема показує, що кожна матриця <math>${d_j}$</math> позитивно визначена і <math>${d_j}$</math> є напрямом спуску. Для доказу леми нам знадобиться : 
'''Теорема 1.''' Нехай S - непорожня безліч в Еn, точка <math>$x \in cl$</math> S. Конусом можливих напрямів в точці x називається безліч <math>$D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$</math>при всіх <math>$\lambda \in (0,\delta )$</math> для деякого <math>$\delta > 0}$</math>. 
'''Визначення.'''Нехай x і y - вектори з Еn і <math>$\left| {{x^T}y} \right|$</math> - абсолютне значення скалярного відтворення <math>$\left {{x^T}y} \right$</math>. Тоді виконується наступна нерівність, звана нерівністю Шварца: 
<center> <math>$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$</math></center>. 

=Лема 1=
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску. 

=Доведення=
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math>
\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) < 0</math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math> j \le n - 1</math>, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо 
<center><math>{x^T}{D_{j + 1}}x = {x^T}{D_j}x + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{D_j}{q_j}}}}</math>(4)</center> 
Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця <math>D_j^{1/2}</math>, така, що <math>{D_j} = D_j^{1/2}D_j^{1/2}</math>. Нехай <math>a = D_j^{1/2}x</math> і <math>b = D_j^{1/2}{q_j}</math>. Тоді <math>{x^T}{D_j}x = {a^T}a,q_j^T{D_j}{q_j} = {b^T}b,{x^T}{D_j}{q_j} = {a^T}b</math>. Підставляючи ці вирази в (4), отримуємо: 
<center><math>{x^T}{D_{j + 1}}x = {\textstyle{{({a^T}a)({b^T}b) - {{({a^T}b)}^2}} \over {{b^T}b}}} + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{q_j}}}}</math>(5)</center> 
По нерівності Шварця маємо <math>({a^T}a)({b^T}b) \ge {({a^T}b)^2 </math>. Так, щоб довести, що<math>{x^T}{D_{j + 1}}x \ge 0</math>, досить показати, що <math>p_j^T{q_j} \ge 0,{b^T}b > 0</math>. З (2) і (3) витікає, що 
<center><math>p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]</math>(6)</center>. 
По припущенню <math>\nabla f({y_j}) \ne 0</math>, і Dj позитивно визначена, так що<math>\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) > 0</math>
Крім того, dj - напрямок спуску, і <math>{\lambda _j} > 0</math>. Тоді із (6) слідує, що <math>p_j^T{q_j} > 0</math>. Крім того <math>{q_j} \ne 0</math> і <math>{b^T}b = q_j^T{D_j}{q_j} > 0</math> 
Видно тепер, що <math>{x^T}{D_{j + 1}}x > 0</math>. Взяти <math>{x^T}{D_{j + 1}}x = 0</math>. Це можливо тільки в тому випадку якщо <math>({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0</math>. Видно, що <math>({a^T}a)({b^T}b) = {({a^T}b)^2}</math> тільки при <math>a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}</math>. Таким чином <math>x = \lambda {q_i}</math>. Так як <math>x \ne 0,то\lambda \ne 0</math>
[[Категорія:Планування експерименту]]

Метод Девідона – Флетчера – Пауела

2012-02-26T00:05:05Z

Ulllasya:

{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По-батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНм-51
|-
| '''Залікова книжка''' || СНм-11-253
|}

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

= Початковий етап =
Нехай <math>$\varepsilon \succ 0$</math> - константа для зупинки. Вибрати точку <math>${x_1}$</math> і початково симетричну позитивно визначену матрицю <math>${D_1}$</math>. Покласти <math>${y_1} = {x_1}$</math>, k = j = 1 і перейти до основного етапу.

= Основний етап =
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1. 
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином: 
<center><math>${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$</math></center> 
<center>де <math>${p_i} = {\lambda _i}{d_i},$</math></center> 
<center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math></center> 
Замінити j на j+1 і перейти до кроку 1.

=Приклад=
Мінімізувати <math>${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$</math> 
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1. 
<center>
<table width="382" border="1">

<tr>
<th scope="row">k</th>
<td width="65" bgcolor="#BDE0BA"><math>${x_k}$</math> <math>$f({x_k})$</math></td>
<td width="18" bgcolor="#BDE0BA">j</td>
<td width="65" bgcolor="#BDE0BA"><math>${y_j}$</math> <math>$f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\nabla f({y_j})$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$</math></td>
<td width="65" bgcolor="#BDE0BA">D</td>
<td width="75" bgcolor="#BDE0BA"><math>${d_j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${\lambda _j}$</math></td>
<td width="65" bgcolor="#BDE0BA"><math>${y_{j + 1}}$</math></td>

</tr>
<tr>
<th scope="row">1</th>
<td bgcolor="">(0.00,3.00) (52.00)</td>

<td bgcolor="">1</td>
<td bgcolor="">(0.00,3.00) (52.00)</td>
<td bgcolor="">(-44.00,24.00)</td>
<td bgcolor="">50.12</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(44.00,-24.00)</td>
<td bgcolor="">0.062</td>
<td bgcolor="">(2.70, 1.51)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.70,1.51) (0.34)</td>
<td bgcolor="">(0.73,1.28)</td>
<td bgcolor="">1.47</td>
<td bgcolor=""><math>$\left[
0.25|0.38\\
0.38|0.71 \right]$</math></td>
<td bgcolor="">(-0.67,-1.31)</td>
<td bgcolor="">0.22</td>
<td bgcolor="">(2.55,1.22)</td>
</tr>

<tr>
<th scope="row">2</th>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.55,1.22) (0.1036)</td>
<td bgcolor="">(0.89,-0.44)</td>
<td bgcolor="">0.99</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.89,0.44)</td>
<td bgcolor="">0.11</td>
<td bgcolor="">(2.45,1.27)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.45,1.27) (0.0490)</td>
<td bgcolor="">(0.18,0.36)</td>
<td bgcolor="">0.40</td>
<td bgcolor=""><math>$\left[
0.65|0.45\\
0.45|0.46 \right]$</math></td>
<td bgcolor="">(-0.28,-0.25)</td>
<td bgcolor="">0.64</td>
<td bgcolor="">(2.27,1.11)</td>
</tr>
<tr>
<th scope="row">3</th>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.27,1.11) (0,008)</td>
<td bgcolor="">(0.18,-0.20)</td>
<td bgcolor="">0.27</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.18,0.20)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.25,1.13)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.25,1.13) (0.004)</td>
<td bgcolor="">(0.04,0.04)</td>
<td bgcolor="">0.06</td>
<td bgcolor=""><math>$\left[
0.80|0.38\\
0.38|0.31 \right]$</math></td>
<td bgcolor="">(-0.05,-0.03)</td>
<td bgcolor="">2.64</td>
<td bgcolor="">(2.12,1.05)</td>
</tr>
<tr>
<th scope="row">4</th>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">1</td>
<td bgcolor="">(2.12,1.05) (0,0005)</td>
<td bgcolor="">(0.05,-0.08)</td>
<td bgcolor="">0.09</td>
<td bgcolor=""><math>$\left[
1|0\\
0|1 \right]$</math></td>
<td bgcolor="">(-0.05,0.08)</td>
<td bgcolor="">0.10</td>
<td bgcolor="">(2.115,1.058)</td>
</tr>
<tr>
<th scope="row"></th>
<td bgcolor=""></td>
<td bgcolor="">2</td>
<td bgcolor="">(2.115,1.058) (0.0002)</td>
<td bgcolor="">(0.004,0.004)</td>
<td bgcolor="">0.006</td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>
<td bgcolor=""></td>

</tr>
</table>
</center> 
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1. 
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла. 
<center>[[Файл:Рисунок_1.gif]]</center> 

Лема показує, що кожна матриця <math>${d_j}$</math> позитивно визначена і <math>${d_j}$</math> є напрямом спуску. Для доказу леми нам знадобиться : 
'''Теорема 1.''' Нехай S - непорожня безліч в Еn, точка <math>$x \in cl$</math> S. Конусом можливих напрямів в точці x називається безліч <math>$D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$</math>при всіх <math>$\lambda \in (0,\delta )$</math> для деякого <math>$\delta > 0}$</math>. 
'''Визначення.'''Нехай x і y - вектори з Еn і <math>$\left| {{x^T}y} \right|$</math> - абсолютне значення скалярного відтворення <math>$\left {{x^T}y} \right$</math>. Тоді виконується наступна нерівність, звана нерівністю Шварца: 
<center> <math>$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$</math></center>. 

=Лема 1=
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску. 

=Доведення=
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math></math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math></math>, і покажемо, що воно справедливе для j+1. Хай x – ненульовий вектор з En, тоді з (1) маємо (4) Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно певна матриця <math></math>, така, що <math></math>. Хай <math></math> і <math></math>. Тоді <math></math>, <math></math> і <math>
</math>. Підставляючи ці вирази в (4), отримуємо : (5) По нерівності Шварця маємо <math></math>. Так, щоб довести, що<math><math>Вставте сюди формулу</math</math>, досить показати, що <math></math> і <math></math>. З (2) і (3) витікає, що <math></math>. (6) По припущенню <math></math>, і Dj позитивно визначена, так що

Файл:Рисунок 1.gif

2012-02-25T23:09:49Z

Ulllasya:

Метод Девідона – Флетчера – Пауела

2012-02-25T23:09:24Z

Ulllasya:

Метод Девідона – Флетчера – Пауела

2012-02-25T22:40:58Z

Ulllasya: Створена сторінка: {|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px" |- | '''Прізвище''' || Храплива |…

Користувачка:Ulllasya

2012-02-25T17:56:45Z

Ulllasya: Створена сторінка: Храплива Уляна Вікторівна, студентка групи СНм-51 (2011/2012)

Храплива Уляна Вікторівна, студентка групи СНм-51 (2011/2012)

2011-2012рр - Індивідуальні завдання для виступу на семінарах з предмету "Планування експерименту Design Of Experiment (DOE)"

2012-02-25T17:53:44Z

Ulllasya:

2011-2012рр - Індивідуальні завдання для виступу на семінарах з предмету "Планування експерименту Design Of Experiment (DOE)"

2012-02-25T17:53:29Z

Ulllasya:

Симплексний метод оптимізації

2012-02-20T22:34:39Z

Ulllasya:

Симплексний метод оптимізації

2012-02-20T22:32:08Z

Файл:Формула4.GIF

2012-02-20T22:11:21Z

Ulllasya:

Файл:Формула3.GIF

2012-02-20T22:08:49Z

Ulllasya:

Файл:Формула2.GIF

2012-02-20T22:02:11Z

Ulllasya:

Файл:Таблиця1.GIF

2012-02-20T21:51:08Z

Ulllasya:

Файл:Формула1.GIF

2012-02-20T21:38:26Z

Ulllasya:

Файл:11112233.GIF

2012-02-20T21:31:21Z

Ulllasya:

Об'єкт системи

2011-05-02T12:08:48Z

Ulllasya:

== Визначення "Об'єкт системи" ==

{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По-батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНс-43
|}
'''Об'єкт системи''' - це елемент ресурсів обчислювальної системи, який знаходиться під керуванням [http://wiki.tntu.edu.ua/index.php?title=%D0%9A%D0%BE%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81_%D0%B7%D0%B0%D1%81%D0%BE%D0%B1%D1%96%D0%B2_%D0%B7%D0%B0%D1%85%D0%B8%D1%81%D1%82%D1%83 комплексу засобів захисту (КЗЗ)] і характеризується визначеними атрибутами й поводженням. 

== Види об'єктів ==
* пасивні об'єкти;
* [[об'єкт-процес]].

Об'єкти-користувачі й об'єкти-процеси є активними об'єктами. Активні об'єкти можуть виконувати дії над пасивними об'єктами. 
У більшості зарубіжних стандартів, зокрема й у сучасному міжнародному стандарті ISO 15408 [8-10], пасивні об'єкти називають ''об'єктами'' (рос. - объект, англ. - object), а активні об'єкти - ''суб'єктами'' (рос. - субъект, англ. - subject). 
Потрібно розуміти, що, як правило, суб'єкт - це об'єкт-процес, який діє від імені певного об'єкта-користувача.

Доступ

2011-04-15T19:11:33Z

Ulllasya:

== Визначення "Доступ" ==

{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По-батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНс-43
|}
'''Доступ''' ''(рос. - доступ, англ. - access)'' - це взаємодія двох об'єктів обчислювальної системи, коли один із них (той, що здійснює доступ) виконує дії над іншим (тим, до якого здійснюється доступ). Результатом такого доступу є змінення стану системи(наприклад,запуск програми на виконання) і (або) утворення інформаційного потоку від одного об'єкта до іншого (наприклад, читання або записування інформації). У випадку, коли утворюється інформаційний потік, кажуть, що здійснюється доступ до інформації. Для забезпечення захисту інформації доступу до об'єктів, які містять інформацію, що підлягає захисту, слід здійснювати з дотриманням визначених правил ([http://wiki.tntu.edu.ua/index.php?title=Правила_розмежування_доступу правил розмежування доступу]).

Правила розмежування доступу

2011-04-15T19:10:01Z

Ulllasya: Створена сторінка: == Визначення "Правила розмежування доступу" == {|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: …

== Визначення "Правила розмежування доступу" ==
{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По-батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНс-43
|}
'''Правила розмежування доступу (ПРД)''' ''(рос. - правила разграничения доступа, англ. - access mediation rules)'' - складова політики безпеки, що регламентує правила доступу користувачів і процесів до пасивних об'єктів.

Доступ

2011-04-15T19:03:50Z

Ulllasya: Створена сторінка: == Визначення "Доступ" == {|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px" |- | …

== Визначення "Доступ" ==

{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По-батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНс-43
|}
'''Доступ''' ''(рос. - доступ, англ. - access)'' - це взаємодія двох об'єктів обчислювальної системи, коли один із них (той, що здійснює доступ) виконує дії над іншим (тим, до якого здійснюється доступ). Результатом такого доступу є змінення стану системи(наприклад,запуск програми на виконання) і (або) утворення інформаційного потоку від одного об'єкта до іншого (наприклад, читання або записування інформації). У випадку, коли утворюється інформаційний потік, кажуть, що здійснюється доступ до інформації. Для забезпечення захисту інформації доступу до об'єктів, які містять інформацію, що підлягає захисту, слід здійснювати з дотриманням визначених правил ([http://wiki.tntu.edu.ua/index.php?title=Правила_розмежування_доступуправил розмежування доступу]).

Комплекс засобів захисту

2011-04-15T17:11:39Z

Ulllasya: Створена сторінка: == Визначення "Комплекс засобів захисту" == {|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; …

== Визначення "Комплекс засобів захисту" ==

{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По-батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНс-43
|}
'''Комплекс засобів захисту (КЗЗ)''' ''(рос. - комплекс средств защиты, англ. - thusteg computing base)'' - сукупність програмно-апаратних засобів, що забезпечують реалізацію політики безпеки інформації. Тобто КЗЗ є складовою обчислювальної системи [http://wiki.tntu.edu.ua/%D0%A4%D0%B0%D0%B9%D0%BB:AC.png (рисунок - Структура автоматизованої системи)]. КЗЗ може бути локалізованим у системі у вигляді одного чи кількох апаратних і програмних компонентів, а може бути розпорошеним по різноманітних програмних засобах.

Об'єкт-користувач

2011-04-15T16:56:45Z

Ulllasya:

== Визначення "Об'єкт-користувач" ==

{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Храплива
|-
| '''Ім'я''' || Уляна
|-
| '''По-батькові''' || Вікторівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНс-43
|}
'''Об'єкт-користувач''' ''(рос. - объект-пользователь, англ. - user object)'' - це подання фізичного користувача в обчислювальній системі, яке утворюється під час його входження в систему і характеризується своїм контекстом(обліковий запис, псевдонім, ідентифікаційний код, повноваження тощо).