Рішення оформляється в форматі Word.
Метод сполучених градієнтів формує напрями пошуку, в більшій мірі відповідають геометрії мінімізується.
Визначення. Два n -мірних вектора х і у називають сполученими по відношенню до матриці A (або A-сполученими), якщо скалярний добуток (x, Aу) = 0. Тут A - симетрична позитивно певна матриця розміром n х n.
Схема алгоритму методу сполучених градієнтів
Покласти k = 0.
Ш. 1 Нехай x 0 - початкова точка; ,
d0 = -g0; k = 0.
Ш. 2 Визначити x k +1 = x k + λk dk. де
.
Потім dk + 1 = -gk + 1 + βk dk,
,
βk знаходиться з умови dk + 1 Adk = 0 (пов'язані щодо матриці A).
Ш. 3 Покласти k = k + 1 → Ш. 2.
Критерій зупинки одновимірного пошуку уздовж кожного з напрямків dk записується у вигляді:.
Значення вибираються таким чином, щоб напрямок dk було A-пов'язане з усіма побудованими раніше напрямками.
Метод Флетчера-Ривса
Стратегія методу Флетчера-Ривса полягає в побудові послідовності точок, k = 0, 1, 2. таких, що f (x k +1)
x k +1 = x k -tk dk. k = 0, 1, 2, ...
dk = # 9661; f (x k) + bk-1 # 9661; f (x k -1)
Величина кроку вибирається з умови мінімуму функції f (х) по t в напрямку руху, т. Е. В результаті рішення задачі одновимірної мінімізації:
f (x k -tk dk) → min (tk> 0)
У разі квадратичної функції f (x) = (х, Нх) + (b, х) + а напрямки dk. dk-1 будуть H-сполученими, тобто (Dk. Hdk-1) = 0
При цьому в точках послідовності градієнти функції f (x) взаємно перпендикулярні, тобто (# 9661; f (x k +1), # 9661; f (x k)) = 0, k = 0, 1, 2 ...
При мінімізації неквадратічних функцій метод Флетчера-Ривса не є кінцевим. Для неквадратічних функцій використовується наступна модифікація метод Флетчера-Ривса (метод Полак-Рібьер), коли величина bk-1 обчислюється таким чином:
Тут I- безліч індексів: I =, т. Е. Метод Полак-Рібьер передбачає використання ітерації найшвидшого градієнтного спуску через кожні n кроків із заміною x 0 на x n +1.
Побудова послідовності закінчується в точці, для якої | # 9661; f (x k) |<ε.
Геометричний сенс методу сполучених градієнтів полягає в наступному. З заданої початкової точки x 0 здійснюється спуск в напрямку d0 = # 9661; f (x 0) .В точці x 1 визначається вектор-градієнт # 9661; f (x 1) .Оскільки x 1 є точкою мінімуму функції в напрямку d0. то # 9661; f (x 1) ортогонален вектору d0. Після цього знаходиться вектор d1. H-зв'язаний до d0. Далі відшукується мінімум функції вздовж напрямку d1 і т. Д.
Алгоритм методу Флетчера-Ривса
Початковий етап.
Задати x 0. # 949;> 0.
Знайти градієнт функції в довільній точці
k = 0.
основний етап
Крок 1. Обчислити # 9661; f (x k)
Крок 2. Перевірити виконання критерію зупину | # 9661; f (x k) |<ε
а) якщо критерій виконаний, розрахунок закінчено, x * = x k
б) якщо критерій не виконаний, то перейти до кроку 3, якщо k = 0, інакше до кроку 4.
Крок 3. Визначити d0 = # 9661; f (x 0)
Крок 4. Визначити чи в разі неквадратічной функції
Крок 5. Визначити dk = # 9661; f (x k) + bk-1 # 9661; f (x k -1)
Крок 6. Обчислити величину кроку tk з умови f (x k - tk dk) → min (tk> 0)
Крок 7. Обчислити x k + 1 = x k -tk dk
Крок 8. Покласти k = k +1 і перейти до кроку 1.
збіжність методу
Теорема 1. Якщо квадратична функція f (x) = (х, Нх) + (b, х) + а з неотрицательно певної матрицею Н досягає свого мінімального значення на R n. то метод Флетчера-Ривса забезпечує відшукання точки мінімуму не більше ніж за n кроків.
Теорема 2. Нехай функція f (x) диференційована і обмежена знизу на R m. а її градієнт задовольняє умові Ліпшиця. Тоді при довільній початковій точці для методу Полак-Рібьер маємо
Теорема 2 гарантує збіжність послідовності до стаціонарної точці x *. де # 9661; f (x *) = 0. Тому знайдена точка x * потребує додаткового дослідження для її класифікації. Метод Полак-Рібьер гарантує збіжність послідовності до точки мінімуму тільки для сильно опуклих функцій.
Оцінка швидкості збіжності отримана тільки для сильно опуклих функцій. в цьому випадку послідовність сходиться до точки мінімуму функції f (x) зі швидкістю: | x k + n - x * | ≤ C | x k - x * |, k =
Приклад. Знайти мінімум функції методом сполучених градієнтів: f (X) = 2x1 2 + 2x2 2 + 2x1 x2 + 20x1 + 10x2 +10.
Рішення. Як спрямовуючу силу пошуку виберемо вектор градієнт в поточній точці: