Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Градиентный метод. Метод наискорейшего спуска.




Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки x[k] будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче :

Другими словами, выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис. 3). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны.

Рис.3 Геометрическая интерпретация метода наискорейшего спуска. На каждом шаге выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L.

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

В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.

 


 

Метод Ньютона

Перейдем к изложению метода второго порядка, использующего вторые частные производные минимизируемой функции f(x). Рассматриваемый далее метод является прямым обобщением метода Ньютона для отыскания решения системы уравнений ɸ(x)=0, где ɸ:Rn→Rn. Возьмем линейную аппроксимацию функции ɸ(x) в окрестности точки xk и перепишем векторное уравнение в следующем виде:

Отбрасывая последний член в этом разложении, получим линейную систему уравнений относительно нового приближения xk+1. Таким образом, метод Ньютона для отыскания решения системы уравнений описывается следующей формулой:

Пусть функция ɸ(x) является градиентом некоторой функции f(x). Формула метода Ньютона для решения уравнения f’(x)=0 выглядит так:

В этом случае метод Ньютона можно интерпретировать как поиск точки минимума квадратичной аппроксимации функции f(x) в окрестности точки xk.

Пусть последовательность {xk}kεN получена с помощью метода Ньютона и точка x* – глобальный минимум функции f. Следующая теорема дает условия квадратичной скорости сходимости метода.

Теорема 4. Пусть дважды непрерывно дифференцируемая функция f сильно выпукла с константой l > 0, вторая производная удовлетворяет условию Липшица

и Тогда xk→x* при k→∞, и метод Ньютона имеет квадратичную скорость сходимости

 


 






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных