Радіотехнічний факультет
ЗВІТ
з лабораторної роботи:
Метод багатовимірної нелінійної оптимізації - метод найшвидшого спуску
Самара +2013
Завдання
1 Вивчити особливості методу багатовимірної нелінійної оптимізації - метод найшвидшого спуску;
2 Розробка математичної моделі і алгоритму для обраного методу;
За складеним алгоритмом написати демонстраційний варіант програми, що відображає основні етапи обраного методу на мові програмування Borland Delphi 7.
Реферат
Пояснювальна записка __ с, 6 малюнків, 3 джерела, 1 додаток.
МЕТОД найшвидшого спуску, МІНІМУМ ФУНКЦІЇ, градієнтні методи, НЕЛІНІЙНІ ФУНКЦІЇ.
Мета роботи - вивчення методів знаходження мінімуму функцій градієнтним методом найшвидшого спуску, моделювання методу і знаходження мінімуму функції двох змінних за допомогою ЕОМ.
Часто, при дослідженні функцій сигналів РЕА виникає потреба знаходження екстремуму цієї функції. Такі завдання ставляться до нелінійного програмування. Одними з найбільш реалізованих методів вирішення цих завдань є градієнтні методи, зокрема, метод найшвидшого спуску
Зміст
1. Теоретичні основи методу
2. Алгоритм програми
3. Лістинг програми
4. Контрольний приклад
Висновок
Список використаних джерел
1. Теоретичні основи методу
У цьому методі з деякої початкової точки рух здійснюється вздовж напрямку градієнта до тих пір, поки похідна за цим напрямком не дорівнюватиме нулю. Далі з цієї точки визначаємо новий градієнт і т.д. Відмінність тут в тому, що довжина кроку з точки X k визначається з умови, щоб забезпечити [2]:
Цю допоміжну завдання одномірної оптимізації можна вирішувати на основі розглянутих методів прямого пошуку (дихотомії і т.д.)
найшвидшого і покоординатно методи називають методами з довгим кроком. Крім цього існують методи, що використовують другу похідну для визначення довжини кроку, наприклад, метод Ньютона [2]:
X k + 1 =X k + [F (X k )] - 1 g (X k )
де [F (X k )] - 1 - зворотна матриця других похідних в точці X k .
Розглянемо знаходження мінімуму функції двох змінних
.
Задаємося вихідною точкою (x0; y0).
. Спочатку знайдемо приватні похідні по x і y:
.
нелінійна оптимізація найшвидшого спуску
2. Якщо обидві похідні в точці (x 0; y 0) дорівнюють нулю, то задача вирішена, і мінімум функції знаходиться в цій точці. В іншому випадку необхідно визначити координати нової точки (x 1; y 1):
,
.
. Тепер отримані значення приймаємо за вихідні (x1=x0; y1=y0) і повертаємося до пункту 2.
Крок t знаходиться з умови мінімуму функції:. Тобто необхідно знайти таке значення t, при якому функція має мінімум. У нашому випадку:
;
Мінімум цієї функції знаходиться з рівності першій її похідної за t до нуля:
Звідси знаходимо t:
.
Для деяких нелінійних функцій цей процес не дозволяє знайти такі значення x і y, при яких похідна дорівнювала б нулю. Тому для забезпечення кінцівки числа ітерацій в цьому випадку вводимо точність Е, тоді обчислення припиняються або коли похідна в точці стає рівною нулю (в цьому випадку значення Е задається рівним нулю), або коли | xk - 1 - xk | буде менше наперед заданої точності Е.
2. Алгоритм програми
3. Лістинг програми