дання мінімізації функцій двох змінних - «спуск на дно» поверхні (рис. 2.4), ітераційний метод (2.18) можна назвати методом спуску, якщо вектор при кожному є напрямом спуску (тобто існує таке, що) і якщо множник підбирається так, щоб виконувалася умова релаксації < що означає перехід на кожній ітерації в точку з меншим значенням функції, що мінімізується.
Таким чином, при побудові чисельного методу виду (2.18) мінімізації функції слід відповісти на два головних питання: як вибирати напрямок спуску і як регулювати довжину кроку в обраному напрямку за допомогою скалярного параметра - крокової множника? Наведемо прості міркування з цього приводу.
При виборі напрямку спуску природним є вибір такого напрямку, в якому минимизируемого функція спадає найбільш швидко.
Рисунок 2.5 - Траєкторія найшвидшого спуску для функції (2.17)
Як відомо з математичного аналізу функцій декількох змінних, напрямок найбільшого зростання функції в даній точці показує її градієнт в цій точці. Тому приймемо за напрямок спуску вектор
- антіградіента функції Таким чином, з сімейства методів (2.18) виділяємо градієнтний метод :
(2.19)
Оптимальний крок у напрямку антіградіента - це такий крок, при якому значення - найменше серед усіх інших значень в цьому фіксованому напрямку, тобто коли точка є точкою умовного мінімуму. Отже, можна розраховувати на найбільш швидку збіжність методу (2.19), якщо вважати в ньому
. (2.20)
Такий вибір крокової множника, званий вичерпним спуском, разом з формулою (2.19) визначає метод найшвидшого спуску.
Геометрична інтерпретація цього методу добре видно з малюнка 2.4, 2.5. Характерні девяностоградусного злами траєкторії найшвидшого спуску, що пояснюється вичерпність спуску і властивістю градієнта (а значить, і антіградіента) бути перпендикулярним до лінії рівня у відповідній точці.
Найбільш типовою є ситуація, коли знайти точно (аналітичними методами) оптимальне значення не вдається. Отже, доводиться робити ставку на застосування будь-яких чисельних методів одновимірної мінімізації і знаходити в (2.18) лише приблизно.
Незважаючи на те, що завдання знаходження мінімуму функції однієї змінної набагато простіше, ніж можна вирішити завдання, застосування тих чи інших чисельних методів знаходження значень з тією чи іншою точністю вимагає обчислення декількох значень функції, що мінімізується. Так як це потрібно робити на кожному ітераційному кроці, то при великому числі кроків реалізація методу найшвидшого спуску в чистому вигляді є досить високовитратною. Існують ефективні схеми наближеного обчислення квазіоптимальних, в яких враховується специфіка минимизируемого функцій (типу сум квадратів функцій).
Найчастіше успішною є така стратегія градиентного методу, при якій кроковий множник в (2.18) береться або відразу досить малим постійним, або передбачається його зменшення, наприклад, розподілом навпіл для задоволення умові релаксації на черговому кроці. Хоча кожен окремий крок градієнтного методу при цьому, взагалі кажучи, далекий від оптимального, такий процес за кількістю обчислень функції може виявитися більш ефективним, ніж метод найшвидшого спуску.
Головне достоїнство градієнтних методів вирішення нелінійних систем - глобальна збіжність. Неважко довести, що процес градієнтного спуску призв...
