Градієнтний метод.

.

Нехай задана функція . В точці , у якій , напрямок найшвидшого зростання функції співпадає з напрямком градієнту в цій точці, а напрямок найшвидшого спадання – з напрямком антиградієнту .Це випливає з формули (1.2) і нерівності Коші-Буняковського: , якщо врахувати, що права нерівність перетворюється у рівність тільки при , ліва – тільки при .

Ця властивість градієнту лежить в основі ряду ітераційних методів мінімізації функцій, зокрема градієнтного методу, до описання якого ми і переходимо. Цей метод, як і всі ітераційні методи передбачає вибір початкового наближення – деякої точки . Загальних правил вибору , на жаль, немає. У тих випадках, коли є апріорна інформація про область розташування шуканої точки мінімуму, точку намагаються вибрати у цій області.

Будемо вважати, що початкова точка вже вибрана. Тоді градієнтний метод полягає у побудові послідовності за правилом

Якщо , то можна підібрати таке , щоб . Дійсно, з формули (1, 2) з врахуванням випливає при будь-яких достатньо малих . Якщо , то – стаціонарна точка і у цьому випадку процес припиняється і при необхідності проводиться додаткове дослідження поведінки функції у околі точки для вияснення того, досягається у точці мінімум чи ні.

Існують різні способи вибору величини у формулі. У залежності від способу вибору можна одержати різні варіанти градієнтного методу. Наведемо деякі з них.

Метод найшвидшого спуску передбачає вибір з умови

.

Звідси відразу маємо

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

Припустимо, що деякий метод вибору у вже вибраний. Тоді на практиці ітерації продовжують доти, поки не буде виконуватися деякій критерій закінчення рахунку. Тут часто використовують наступні критерії:

де – задані числа.

У теоретичних питаннях, коли досліджується збіжність методу, вважається, що процес продовжується необмежено і приводить до послідовності .Тут виникають питання, чи буде одержана послідовність мінімізуючею для задачі, чи буде вона збігатися до множини точок мінімуму, або інакше кажучи, чи виконуються співвідношення ?

Для одержання позитивної відповіді на ці питання на функцію крім умови , приходиться накладати додаткові досить жорсткі умови.

Приклад 1. Методом найшвидшого спуску з точністю до розв’яжемо таку задачу мінімізації, взявши за умову закінчення ітераційного процесу обчислень таку умову

.

Розв’язування. За початкове наближення ітераційного процесу візьмемо точку . Знайдемо

.

Тоді на першому кроці отримаємо

.

Оскільки

,

то

при .

Тепер

.

У цьому випадку . Координати цього вектора не задовольняють умову (5), тому необхідно продовжувати ітераційний процес за описаною вище схемою, узявши за початкову точку .

На шостому кроці отримаємо

,

тобто задана точність обчислень забезпечена.

Отже розв’язок задачі запишемо у вигляді

.