Лабораторна робота 12
Мета роботи: Вивчення чисельних методів першого порядку безумовної мінімізації функцій багатьох змінних - методу якнайшвидшого спуску, методу сполучених градієнтів; порівняльний аналіз методів різного порядку.
12.1.Короткі теоретичні відомості
Алгоритми відшукання екстремуму функцій багатьох змінних чисельними методами полягають у побудові послідовності векторівX(k)>,задовольняють умові:f(X(0)) > f(X(1)) >…> f(X(n)). Елементи послідовностіX(k)>обчислюються за формулою
ДеP(k)- напрямок спуску; ak-Довжина кроку в цьому напрямку. Як початкова точкаX(0)може бути обрана будь-яка, проте необхідно використовувати всю наявну інформацію про поведінку функціїF(X), щобX(0)розташовувалася не надто далеко від точки мінімуму. Потім необхідно вибрати напрямок, уздовж якого передбачається розташувати наступну точку, і величину кроку вздовж цього напрямку. Насправді застосовуються лише методи, які мають збіжністю. Вони дозволяють за кінцеве число кроків отримати точку мінімуму або інтервал невизначеності, що містить точку мінімуму і має довжину менше деякого заданого числаE.
Градієнтні методи.Як відомо, градієнт функції в деякій точціX(k)спрямований у бік якнайшвидшого локального зростання функції. Отже, спускатися потрібно в напрямку протилежному градієнту. Вектор, протилежний градієнту, називаєтьсяАнтиградієнтом. Вибираючи антиградієнт як напрямок спуску, приходять до ітераційногопроцесу виду
У координатній формі цей процес записується так:
.
Усі методи спуску, у яких векторP(k)збігається з антиградієнтом, називаютьсяГрадієнтними методами. Вони відрізняються один від одного лише способом вибору кроку. У методах зпостійним крокомвибирається деяка постійна всім ітерацій величина кроку. Досить малий крок забезпечить зменшення функції, однак це може призвести до необхідності проводити неприйнятно велику кількість ітерацій для досягнення точки мінімуму. З іншого боку, занадто великий крок може викликати несподіване зростання функції або призвести до коливань близько мінімуму. Через відсутність необхідної інформації для вибору величини кроку, методи з постійним кроком застосовуються рідко. Найбільш економічними в сенсі кількості ітерацій і надійними є градієнтні методи з змінним кроком, серед яких найбільш уживані метод якнайшвидшого спуску і метод дроблення кроку.
Метод якнайшвидшого спуску. Тут кожної ітерації величина кроку вибирається з умови мінімуму функції у бік руху:
, (12.3)
Т. е. на кожному кроці вирішується одномірне завдання мінімізації. Геометрична інтерпретація цього досить проста.
Алгоритм методу якнайшвидшого спуску полягає в наступному:
1) у точціX(0)обчислюються значення градієнтаF(X(0))та кроку шляхом вирішення задачі одновимірної мінімізації (12.3);
2) здійснюється спуск у напрямку антиградієнта з вибраним кроком доти, поки значення функціїF(X)зменшується;
3) якщо на деякомуM-му кроціF(X(M)) > f(X(M-1)), то в точціX(M-1)обчислюються новізначення градієнтаF¢(X(M-1))і кроку і виконується перехід до п.2.
ЯкщоF(X)— обмежена знизу безперервно диференційована функція і для деякої початкової точкиX(0)безлічX: f(X) 2013-06-06