Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Московский государственный университет приборостроения и информатики

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Численные методы.doc

Скачиваний:

Добавлен:

06.08.2019

Размер:

1.68 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 67 / 77

Градиентные методы.

Требуют знания значения функции и ее градиента. Ясно, что основная идея метода заключается в отказе от “слепого” поиска вдоль фиксированных осей координат и переходе к движению сразу в направление возрастания функции (противоположное – убывание функции). Пусть сделан переход от точки х к точке х +hd , где d-некоторое направление , а h – шаг. Следовательно, перемещение происходит от точки (х_1, х₂,…, х_n) в точку (х₁ +δх₁ , х₂+δx₂,…, х_n+δx_n), где δх_i=hd_i

d_i– косинусы направления d (проекции направления d на оси координат) такие, что

Изменения значения функции df=f(х₁ +δх₁,…, х_n+δx_n) - f(х₁,…, х_n)=

Частные производные (0) вычисляются по ряду Тейлора f(x₀+h) - f(x₀)=

Наискорейший спуск

Возникает задача как выбрать направление d , чтобы получить наибольшее изменение функции df при

соблюдении условия (*) т.е. с ограничением.

Используем метод множетелей Лагранжа для поиска функции

или

На основе метода df достигает max , если φ достигает max. Берем производную от φ

(j=1,2,…,n) и приравниваем ее нулю , получаем ,

следовательно,

. “Направления” совпадают с градиентами функции f(x) в точке x, или g(x).

Для min - f(x) или – g(x). Уравнение (0) можно записать так , где Θ – угол между векторами g(x) и dx. Угол выбран Θ=180⁰, чтобы обеспечить направление – g(x):

Значения λ_i, минимизирующее функцию φ может быть найдено любым методом одномерного поиска. В чистом виде метод работает медленно и не надежно. Но прежде чем перейти к более эффективным методам , рассмотрим свойства квадратичных функций.

F(x)= , где a – константа , b – постоянный вектор , G – положительно определенная симметрическая матрица.

min в точке .

Поставим задачу так, что в окресности точки х₀любую функцию φ(х) можно аппроксимировать

квадратичной функцией:

Пусть min φ(x) находится в точке х_m

Берем производную и приравниваем ее к нулю.

, откуда :

, т.е. в итерационном виде:

, а с учетом множителей Лагранжа:

Видим, что по сравнению с методом наискорейшего спуска требуется умножение на G^-1(x_i), а это самая трудоемкая операция метода.

Но если проводить умножение на H_i , а не G^-1(x_i) , то получим метод Давидона – Флетчера – Пауэлла (ДФП). - симметрическая положительно определенная матрица. В ходе вычислений она приближается к матрице