Page 150 - 5637

– градієнт функції в точці ; – деяка позитивно визначена

квадратна ( × )-матриця, яка є апроксимацією матриці , зворотної матриці

= ( = 1, … , ).

Основний принцип алгоритму Девідона-Флетчера-Пауелла базується на простому
факті: якщо уявити функцію в околиці точки у вигляді розкладу в ряд Тейлора

( ) ≈ ( ) + 0,5( − ) ( − )

то її градієнт можна Наближено обчислити за формулою ( ) = ( − ). Отже,

= − Н ( ) ≈ − ( ). Це підказує можливий підхід до вирішення задачі
знаходження мінімуму – побудова ітераційного процесу виду

= − ( ), = 1,2, …, (7.7)

де – матриця апроксимації на = м кроці; – позитивне число, обиране так,

щоб в точці i досягався локальний мінімум вздовж напрямку – ( ), тобто

щоб було оптимальним рішенням задачі мінімізації ( − ( )) по

( ≥ 0). рекурентне співвідношення (7.7) пояснює назву алгоритму «змінної
метрики» – матриця змінює метрику в просторі векторів ( ). B результаті

множення на матрицю напрямок градієнта ( ) відхиляється і перетвориться в

( ).

Істотним в алгоритмі Девідона-Флетчера-Пауелла є те, що матриця

обчислюється з використанням тільки перших похідних і так, щоб після кроків

першій же ітерації (п: 1 основного етапу алгоритму) вона збіглася з якщо, б

була квадратичної функцією. Таким чином, відпадає необхідність в безпосередньому

обчисленні і Зверненні матриці Гессе в процесі роботи алгоритму Девідона-Флетчера-

Пауелла мінімізації диференціальної функції декількох змінних (див. також [58, 61]).

Початковий етап. Вибір початкової точки пошуку та початкової наближення

матриці ( – симетрична і позитивно певна), а також параметрів точності

обчислення мінімуму > 0. Приймаються = , = 1, = 1. Переходимо до

основного етапу мінімізації.

Основний етап. 1. Якщо | | ( ) | | < , то , – шукана точка мінімуму і

алгоритм закінчує свою роботу. B іншому випадку обчислюємо = − , ( ) і

вирішуємо задачу мінімізації (по скаляру ≥ 0) функції ( + ). Вважаємо