Cтраница 2
Например, Келлп ( 1960), сравнивая три варианта метода сопряженных градиентов и метод переменной метрики, делает вывод о том, что последний метод обеспечивает существенно более быструю сходимость, чем любой из методов сопряженных градиентов, но в большей мере подвержен влиянию ошибок вычислений. Колли модифицировал метод переменной метрики, сохранив его преимущества по скорости сходимости перед методами сопряженных направлений, но уменьшив чувствительность к накоплению ошибок. Снижение чувствительности по отношению к накоплению ошибок осуществлено систематическим гашением накопленных ошибок через каждые п шагов. [16]
В случае, когда для выпуклой функции ф ( лг) выполняются условия 1 и 2, справедливы оценки скорости сходимости методов спуска, в том числе градиентного спуска и метода сопряженных направлений, а так же методов случайного покоординатного спуска и метода случайного спуска, аналогичные тем, которые приводились в пп. При этом константы в этих оценках будут иными, но порядок скорости сходимости остается прежним. [17]
Как видно, перемещение осуществляется из хп в xn l в сторону противоположную направлению градиента. Более сложным обобщением градиентного метода является алгоритм переменной метрики. Аналогичные добавки получаются и в методе сопряженных направлений. [18]
Преимущество методов сопряженных градиентов по сравнению с методами сопряженных направлений состоит в том, что они требуют хранения только вектора, в то время как методы сопряженных направлений требуют хранения п X -матрицы. Это особенно важно при решении задач большой размерности. В то же время практический опыт показывает, что методы сопряженных направлений, как правило, обеспечивают большую скорость сходимости, чем методы сопряженных градиентов. [19]
Если схема корректировки в (5.2.19) излишне сложна, то способ выбора направления спуска слишком прост. Значительно более совершенные алгоритмы получаются с использованием приведенных градиентов в комбинации с квазиньютоновскими методами и методами сопряженных направлений. Два из них, рассчитанные на задачи с линейными ограничениями, представлены в предыдущей главе. Оба опираются на метод Флетчера - Ривза. Аналогичный алгоритм, но для задач с нелинейными ограничениями подробно описан в цитированной выше работе Абади и Кар-пентье. [20]
Примером этого является рассматриваемый в следующем разделе метод сопряженных градиентов, где сопряженные векторы образуются из вектор-градиентов. Если функция и ее градиенты определены только численно так, что нет возможности построить матрицу Q, то задача построения множества ( - сопряженных векторов становится более трудной. Этот случай позже в данной главе будет рассмотрен подробно при описании метода сопряженных градиентов и метода переменной метрики. В случав неквадратичной функции метод сопряженных направлений становится итеративным и обычно не заканчивается за п шагов. Неквадратичные функции локально аппроксимируют последовательность квадратичных функций, р-векторы определяются в соответствии с квадратичными аппроксимациями этих неквадратичных функций. Поэтому при функциях, локальные квадратичные аппроксимации которых быстро изменяются от итерации к итерации или для которых матрица Гессе перестает быть положительно определенной, метод сопряженных направлений может не сходиться. [21]
Сопряженные направления в точке представляют собой искомые пути движения при минимизации целевой функции. Для представленных в этом подразделе методов сопряженных направлений требуется определение только первых производных. Однако благодаря использованию накопленной информации о предыдущих итерациях скорость сходимости метода увеличивается при прибли жении к минимуму. Вообще говоря, в процессе численной реализации методов осуществляется приближенное построение матрицы вторых производных. Все методы сопряженных направлений основаны на идее, заключающейся в том, что если метод хорошо работает в задаче минимизации положительно определенной квадратичной формы, то он должен хорошо работать и для любой гладкой целевой функции. [22]
Особенностью задачи (5.1) является то, что само вычисление функции Ф1, как правило, требует осуществления большого числа операций, т.е. является весьма трудоемким. Часто трудоемко уже вычисление по модели значений выходной координаты У I при заданном входном воздействии. Например, если объект описывается дифференциальными уравнениями, то для нахождения Lj часто приходится численно решать систему дифференциальных уравнений. К их числу относятся, например, симплексный метод и метод сопряженных направлений. Рассмотрим - схему применения одного из них - метода сопряженных направлений. [23]
Рассмотренные выше методы переменной метрики предполагают нахождение точного минимума функции на каждом направлении поиска. Однако поиск с высокой точностью минимума на каждом направлении связан с вычислением значений функции в достаточно большом числе точек, что приводит к значительному увеличению затрат времени ЭВМ на решение задачи. Поэтому в последнее время был развит ряд поисковых методов, не требующих точного линейного поиска. К первой относятся методы, в которых, несмотря на отсутствие точной одномерной минимизации, минимум квадратичной функции достигается за конечное число шагов. Ко второй группе относятся методы, не обладающие указанным свойством. Здесь рассмотрен только один представитель последней группы методов ( см. с. Основное же внимание уделено первой группе методов, которую удобно разбить на две подгруппы: методы сопряженных направлений без точного линейного поиска и квазиньютоновские методы без точного линейного поиска. [24]