Cтраница 3
Таким образом, метод сопряженных градиентов обладает высокой скоростью сходимости. В то же время его трудоемкость сравнительно невелика. Так, например, метод (3.22) по трудоемкости и памяти лишь незначительно превосходит метод наискорейшего спуска. Все это позволяет отнести метод сопряженных градиентов к числу наиболее эффективных алгоритмов первого порядка. Вычислительная практика показывает, что этот метод незначительно уступает по эффективности квазиньютоновским методам; в то же время он предъявляет меньшие требования к объему занимаемой памяти ЭВМ. Следует отметить, что в настоящее время построено и применяется много различных вариантов метода сопряженных градиентов. [31]
Третье семейство образуют метод сопряженных градиентов conjugate gradient methods. Среди них выделяются методы Флет-чера - Ривза и тесно примыкающие к ним методы Полака-Рибьера. Они тяготеют к группе наиболее эффективных методов в смысле скорости и памяти ( порядка п), но требуют вычисления частных производных первого порядка. [32]
Предназначена для отыскания методом сопряженных градиентов максимума функции W ( a), а 0, в подпространстве, соответствующем группе выделенных пар векторов. В случае, когда максимум функции W ( a) в поло-жителыюм квадранте превышает заданную величину WO, группа векторов считается неразделимой гиперплоскостью и работа подпрограммы заканчивается. [33]
Существуют различные вычислительные схемы метода сопряженных градиентов, отличающиеся видом расчетных формул. Будучи формально эквивалентными, эти разные схемы отличаются друг от друга объемом хранимой в процессе вычислений информации, числом операций на стандартный шаг и степенью чувствительности алгоритма к ошибкам округления. Все эти факторы становятся особенно важными при решении задач достаточно высокой размерности. [34]
Отметим две важные особенности метода сопряженных градиентов, проявляющиеся при решении конкретных вычислительных задач. Во-первых, реализация одного шага метода сопряженных градиентов требует большее ( иногда значительно) число арифметических и логических действий по сравнению с одним шагом чебышевского итерационного метода. Во-вторых, при реализации ( особенно на первых итерациях) метод сопряженных градиентов в соответствующей норме значительно быстрее минимизирует Л - норму вектора ошибки, чем это показывает оценка. [35]
Этот алгоритм под названием метода сопряженных градиентов был предложен в [680] для решения систем линейных алгебраических уравнений с положительно определенной матрицей. [36]
Наиболее благоприятна для применения метода сопряженных градиентов ситуация, когда известно, что число обусловленности 1л ( А) невелико, но границы спектра неизвестны, а порядок п системы много больше того числа итераций р, при котором погрешность е удовлетворяет поставленному перед вычислителем требованию точности. [37]
В этом параграфе будет изложен метод сопряженных градиентов, относящийся к группе методов сопряженных направлений. Однако метод сопряженных градиентов выгодно отличается от градиентных методов более высокой скоростью сходимости, которая, при определенных предположениях относительно минимизируемой функции, приближается к скорости сходимости метода Ньютона. Положительно определенная квадратичная форма п переменных минимизируется методом сопряженных градиентов за п или менее шагов. Так как любая гладкая функция в окрестности точки своего минимума хорошо аппроксимируется квадратичной, метод сопряженных градиентов с успехом применяется для минимизации и неквадратичных функций. Правда, при этом метод перестает быть конечным, а становится итеративным. [38]
Подчеркнем еще раз, что метод сопряженных градиентов при этом является методом первого порядка. [39]
Из (16.3.2) видно, что метод сопряженных градиентов является двушаговым. [40]
Метод имеет некоторое сходство с методом сопряженных градиентов и отличается от него критерием выбора допустимого направления. [41]
При больших числах итераций скорости сходимости метода сопряженных градиентов и ускорения по Чебы-щеву асимптотически выравниваются, хотя абсолютные значения невязок асимптотически в методе сопряженных градиентов, как правило, оказываются по норме существенно меньшими именно за счет быстрой сходимости на первых итерациях. [42]
На этом заканчивается первая часть обсуждения методов сопряженных градиентов. Скорость их сходимости мы обсудим в разд. [43]
Немиров с кий А. С. О регуляризирующих свойствах метода сопряженных градиентов на некорректных задачах / / ЖВМ и МФ. [44]
Таким образом, / г-й шаг метода сопряженных градиентов на квадратичном объекте всегда в принципе приводит к цели. Однако в практических задачах поисковой оптимизации этого не бывает. [45]