Метод релаксації

{{{img}}}
Імя	Тарас
Прізвище	Івасюк
По-батькові	Анатолійович
Факультет	ФІС
Група	СН-51
Залікова книжка	СН-10-055

Метод релаксації

Алгоритм методу полягає у відшукуванні осьового напряму, уздовж якого цільова функція зростає найшвидше. Для цього в початковій точці пошуку визначаються її похідні за всіма незалежними параметрами. Осьовому напряму з найшвидшим зростанням цільової функції відповідає найбільша по модулю похідна. Якщо знак похідної додатний, то цільова функція зростає по осі в обраному напрямі, якщо від’ємний — то у зворотньому. За напрямом зростання цільової функції робляться кроки до тих пір, поки не буде утворено максимальне значення за обраним осьовим напрямом. Тоді знову визначаються похідні за всіма параметрами, за винятком того, за яким здійснюється підіймання, і знову знаходиться осьовий напрям найшвидшого зростання цільової функції, за яким робляться подальші кроки, і т. д. Критерієм закінчення пошуку оптимуму є досягнення такої точки, при пересуванні з якої за будь-яким осьовим напрямом подальше зростання функції цілі не відбувається. На практиці, як ознаку оптимуму, часто застосовують умову:

[math]\sum_{i=1}{n}\left[\frac{dy\vec{(x)}}{dx_i}\right]^2[/math]

Якщо ж оптимум лежить на межі області, то названа умова незастосовна, а замість неї слід застосувати умову додатності всіх похідних по припустимих осьових напрямах.

Алгоритм руху

Алгоритм руху в обраному осьовому напрямі записують у вигляді:

[math]x_i_,_k_+_1=x_i_,_k+\triangle x_i_,_ksgn\frac{dy\vec{(x_0)}}{dx_i}[/math]

де [math]x_i_,_k[/math] - значення змінної на k-му кроці руху, [math]\triangle x_i_,_k[/math] - вершина k-го кроку, яка може змінювати своє значення залежно від номеру кроку; [math]x_0[/math] - координата точки, в якій відбувалося обчислення похідних. Швидкість руху до екстремуму залежить від того наскільки вдало обрано крок [math]\triangle x_i_,_k[/math] для зміни незалежних змінних. Тому викликають інтерес спеціальні способи зміни величини кроку в процесі пошуку.

Алгоритм зміни кроку

Найпростіший алгоритм зміни кроку полягає ось у чому. На початку руху за одним з осьових напрямів задається деякий крок \triangle x_i_,_0 який дорівнює, наприклад 0,1, що відповідає зміненню значення фізичної змінної [math]y_1[/math] на 10 % від прийнятого діапазону [math]a_1[/math]. З цим кроком проводиться піднімання за обраним осьовим напрямом доки, поки для двох наступних обчислень значень цільової функції виконується умова:

[math]y(\vec{x}_i_,_k_+_1)\gt y(\vec{x}_i_,_k)[/math]

При порушенні цієї умови на будь-якому кроці напрям піднімання по осі змінюється на зворотний, і рух продовжується з останньої обчислювальної точки із меншою удвічі величиною кроку. Алгоритм зміни кроку записують у вигляді:

[math]\triangle x_i_,_k_+_1=\begin{cases}\triangle x_i_,_k, & \mbox{if}\qquad y(\vec{x}_i_,_k)\ge y(\vec{x}_i_,_k_-_1)\\-\frac {y(\vec{x}_i_,_k)}{2}, & \mbox{if}\qquad y(\vec{x}_i_,_k)\lt y(\vec{x}_i_,_k_-_1)\end{cases}[/math]

У результаті використання такої стратегії крок піднімання за осьовим напрямком зменшуватиметься в районі максимуму цільової функції за цим напрямом, і пошук екстремуму можна припинити, якщо величина кроку [math]\triangle[/math] стане меншою заданої точності визначення максимуму e ([math]e\approx0,1_y_i[/math])в осьовому напрямі. Потім відшукується новий осьовий напрям, і початковий крок можна обрати не як задану частку діапазону зміни незалежної змінної, а як задану частку відстані, пройденої вздовж попереднього осьового напряму. Це дає змогу автоматично зменшувати початковий крок за кожним наступним осьовим напрямом при наближенні до оптимуму цільової функції, в районі якого піднімання по кожній осі відбувається на невелику відстань.

Список використаних джерел

1. Математичне планування експериментів в АПК / В. О. Аністратенко, В. Г. Федоров.-К.:Вища школа,1993.-374с.