ТОР 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→∞, и метод Ньютона имеет квадратичную скорость сходимости
Не нашли, что искали? Воспользуйтесь поиском:
|