Метод сопряженных градиентов Флетчера – Ривса

Как известно, направление градиента является направлением наискорейшего возрастания функции. Следовательно, противоположное направление является направлением наискорейшего убывания функции. Это свойство антиградиента лежит в основе градиентных методов первого порядка. При этом направление наискорейшего убывания в данной точке не всегда оказывается наилучшим для спуска к точке минимума, поэтому для повышения эффективности вводят различные поправки. При выборе очередного направления используют накопленную информацию о функции из предыдущих спусков. Множество возможностей введения таких поправок определяет многообразие различных методов первого порядка. Широкое распространение получили градиентные методы, основанные на так называемых сопряженных направлениях. Здесь, как и ранее, на каждой к-й итерации решается задача одномерной минимизации целевой функции относительно величины шага , однако, направление поиска рk выбирается с учетом направлений на предыдущих итерациях. Различные способы выбора параметра k приводят к различным модификациям градиентных методов. Очевидно, что при k=0 схема вырождается в метод наискорейшего спуска. В частности, чтобы обеспечить хорошую сходимость рассматриваемых методов, k необходимо выбирать таким образом, чтобы i направляющих векторов (i n) на последующих шагах процесса минимизации были линейно независимыми. Этому условию удовлетворяют сопряженные направления. Алгоритм метода. Задается начальная точка х0 и точность решения задачи минимизации. Вычисляется градиент целевой функции. Вычисляется вектор направления поиска. Решается задача одномерной минимизации целевой функции относительно шага одним из ранее рассмотренных методов.

Вычисляется новая точка Для к=1,2,…, n -1 последовательно повторяются :(это) Вычисляется градиент целевой функции, Вычисляется параметр k. Вычисляется вектор направления поиска Решается задача одномерной минимизации целевой функции. Вычисляется новая точка Проверяется условие сходимости Если заданная точность решения не достигнута, то переходим к п. 2, с заменой x0 на xn. (первого порядка).

Обобщенный метод Ньютона – Рафсона

Эти методы основаны на квадратичной аппроксимации целевой функции и как следствие для своей реализации требуют вычисления производных первого и второго порядков. Одним из таких методов является обобщенный метод Ньютона – Рафсона, в котором на каждой к-й итерации производится одномерный поиск минимума целевой функции относительно шага в направлении. Одним из преимуществ этого метода по сравнению с градиентными методами состоит в том, что он не реагирует на «овражный» характер минимизируемой функции. Градиентные методы, по существу, используют линейную аппроксимацию целевой функции и поэтому менее точно определяют направление на точку минимума. Поэтому метод Ньютона – Рафсона позволяет достичь заданной точности за меньшее число итераций, чем градиентные. Однако каждая итерация метода Ньютона – Рафсона связана с вычислением матрицы вторых производных и последующим еѐ обращением, что требует большего объема вычислений по сравнению с одной итерацией градиентного метода. Кроме того, в ряде случаев производные не могут быть получены в виде аналитических выражений, а вычисление их численными методами осуществляется с ошибками, которые зачастую сводят на нет преимущества этого метода.