Правила ввода функций :

Формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции.
Определение . Два n -мерных вектора х и у называют сопряженными по отношению к матрице A (или A-сопряженными), если скалярное произведение (x, Aу) = 0 . Здесь A - симметрическая положительно определенная матрица размером n х n .

Схема алгоритма метода сопряженных градиентов

Метод Флетчера-Ривса

Алгоритм метода Флетчера-Ривса

Сходимость метода

Пример . Найти минимум функции методом сопряженных градиентов: f(X) = 2x 1 2 +2x 2 2 +2x 1 x 2 +20x 1 +10x 2 +10 .
Решение. В качестве направления поиска выберем вектор градиент в текущей точке:

Метод Ньютона и квазиньютоновские методы, обсуждавшиеся в предыдущем параграфе, весьма эффективны как средство решения задач безусловной минимизации. Однако они предъявляют довольно высокие требования к объему используемой памяти ЭВМ. Это связано с тем, что выбор направления поиска требует решения систем линейных уравнений, а также с возникающей необходимостью хранения матриц типа Поэтому при больших использование этих методов может оказаться невозможным. В существенной степени от этого недостатка избавлены методы сопряженных направлений.

1. Понятие о методах сопряженных направлений.

Рассмотрим задачу минимизации квадратичной функции

с симметричной положительно определенной матрицей А Напомним, что для ее решения требуется один шаг метода Ньютона и не более чем шагов квазиньютоновского метода Методы сопряженных направлений также позволяют найти точку минимума функции (10.33) не более чем за шагов. Добиться этого удается благодаря специальному выбору направлений поиска.

Будем говорить, что ненулевые векторы являются взаимно сопряженными (относительно матрицы А), если для всех

Под методом сопряженных направлений для минимизации квадратичной функции (10.33) будем понимать метод

в котором направления взаимно сопряжены, а шаги

получаются как решение задач одномерной минимизации:

Теорема 10.4. Метод сопряженных направлений позволяет найти точку минимума квадратичной функции (10 33) не более чем за шагов.

Методы сопряженных направлений отличаются один от другого способом построения сопряженных направлений. Наиболее известным среди них является метод сопряженных градиентов

2. Метод сопряженных градиентов.

В этом методе направления строят правилу

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

сопряженными относительно матрицы А. Более того, градиенты оказываются взаимно ортогональными.

Пример 10.5. Применим метод сопряженных градиентов для минимизации квадратичной функции - из примера 10.1. Запишем виде где

Возьмем начальное приближение

1-й шаг метода совпадает с первым шагом метода наискорейшего спуска. Поэтому (см. пример 10.1)

2-й шаг. Вычислим

Так как то и решение оказалось найденным за два шага.

3. Метод сопряженных градиентов для минимизации неквадратичных функций.

Для того чтобы указанный метод можно было применить для минимизации произвольной гладкой функции формулу (10.35) для вычисления коэффициента преобразуют к виду

или к виду

Преимущество формул (10 36), (10.37) в том, что они не содержат явным образом матрицу А.

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

Коэффициенты вычисляют по одной из формул (10.36), (10.37).

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

Решение задач одномерной минимизации (10.40) приходится осуществлять численно. Отметим также то, что часто в методе сопряженных градиентов при коэффициент не вычисляют по формулам (10.36), (10.37), а полагают равным нулю. При этом очередной шаг производят фактически методом наискорейшего спуска. Такое "обновление" метода позволяет уменьшить влияние вычислительной погрешности.

Для сильно выпуклой гладкой функции при некоторых дополнительных условиях метод сопряженных градиентов обладает высокой сверхлинейной скоростью сходимости. В то же время его трудоемкость невысока и сравнима с трудоемкостью метода наискорейшего спуска. Как показывает вычислительная практика, он незначительно уступает по эффективности квазиньютоновским методам, но предъявляет значительно меньшие требования к используемой памяти ЭВМ. В случае, когда решается задача минимизации функции с очень большим числом переменных, метод сопряженных градиентов, по-видимому, является единственным подходящим универсальным методом.

Вычислительные эксперименты для оценки эффективности параллельного варианта метода верхней релаксации проводились при условиях, указанных во введении. С целью формирования симметричной положительно определенной матрицы элементы подматрицы генерировались в диапа-зоне от 0 до 1, значения элементов подматрицы получались из симметрии матриц и , а элементы на главной диагонали (подматрица ) генерировались в диапазоне от до , где – размер матрицы.

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

Эксперименты демонстрируют неплохое ускорение (порядка 4 на 8-и потоках).

Метод сопряженных градиентов

Рассмотрим систему линейных уравнений (7.49) с симметричной, положительно определенной матрицей размера . Основой метода сопряженных градиентов является следующее свойство: решение системы линейных уравнений (7.49) с симметричной положительно определенной матрицей эквивалентно решению задачи минимизации функции

Обращается в ноль. Таким образом, решение системы (7.49) можно искать как решение задачи безусловной минимизации (7.56).

Последовательный алгоритм

С целью решения задачи минимизации (7.56) организуется следующий итерационный процесс.

Подготовительный шаг () определяется формулами

Где – произвольное начальное приближение; а коэффициент вычисляется как

) определяются формулами

Здесь – невязка -го приближения, коэффициент находят из условия сопряженности

Направлений и ; является решением задачи минимизации функции по направлению

Анализ расчетных формул метода показывает, что они включают две операции умножения матрицы на вектор, четыре операции скалярного произведения и пять операций над векторами. Однако на каждой итерации произведение достаточно вычислить один раз, а затем использовать сохраненный результат. Общее количество числа операций, выполняемых на одной итерации, составляет

Таким образом, выполнение итераций метода потребует

Операций. Можно показать, что для нахождения точного решения системы линейных уравнений с положительно определенной симметричной матрицей необходимо выполнить не более n итераций, тем самым, сложность алгоритма поиска точного решения имеет порядок . Однако ввиду ошибок округления данный процесс обычно рассматривают как итераци- онный, процесс завершается либо при выполнении обычного условия остановки (7.51) , либо при выполнении условия малости относительной нормы невязки

Организация параллельных вычислений

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

Анализ последовательного алгоритма показывает, что основные затраты на -й итерации состоят в умножении матрицы на вектора и . Как ре- зультат, при организации параллельных вычислений могут быть использованы известные методы параллельного умножения матрицы на вектор.

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

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

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

Где – длина вектора, – число потоков, – накладные расходы на созда- ние и закрытие параллельной секции.

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

Где – число итераций метода.

Результаты вычислительных экспериментов

Вычислительные эксперименты для оценки эффективности параллельного варианта метода сопряженных градиентов для решения систем линейных уравнений с симметричной положительно определенной матрицей прово- дились при условиях, указанных во введении. Элементы на главной диагонали матрицы ) генерировались в диапазоне от до , где – размер матрицы, остальные элементы генерировались симметрично в диапазоне от 0 до 1. В качестве критерия остановки использовался критерий остановки по точности (7.51) с параметром

Результаты вычислительных экспериментов приведены в таблице 7.21 (время работы алгоритмов указано в секундах).

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

При использовании метода наискорейшего спуска на каждой итерации величина шага а k выбирается из условия минимума функции f(x) в направлении спуска, т. е.
f(x [k ] -a k f"(x [k ])) = f(x [k] - af"(x [k ])) .

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции
j(a) = f(x [k ] - af"(x [k ])) .

Алгоритм метода наискорейшего спуска состоит в следующем.

1. Задаются координаты начальной точки х .

2. В точке х [k ], k = 0, 1, 2, ... вычисляется значение градиента f"(x [k ]) .

3. Определяется величина шага a k , путем одномерной минимизации по а функции j(a) = f(x [k ] - af"(x [k ])).

4. Определяются координаты точки х [k+ 1]:

х i [k+ 1] = x i [k ] - а k f" i (х [k ]), i = 1 ,..., п.

5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х [k ] касается линии уровня в точке x [k+ 1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a k выбирается путем минимизации по а функции ц(a) = f(x [k] - af"(x [k ])) . Необходимое условие минимума функции d j(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

d j(a)/da = -f"(x [k+ 1]f"(x [k ]) = 0.

Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями l i , i =1, …, n , матрицы являются корни характеристического уравнения

Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются, а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

Метод сопряженных градиентов

Рассмотренные выше градиентные методы отыскивают точку минимума функции в общем случае лишь за бесконечное число итераций. Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции. Это существенно увеличивает скорость их сходимости и позволяет, например, минимизировать квадратичную функцию

f(x) = (х, Нх) + (b, х) + а

с симметрической положительно определенной матрицей Н за конечное число шагов п, равное числу переменных функции. Любая гладкая функция в окрестности точки минимума хорошо аппроксимируется квадратичной, поэтому методы сопряженных градиентов успешно применяют для минимизации и неквадратичных функций. В таком случае они перестают быть конечными и становятся итеративными.

По определению, два n -мерных вектора х и у называют сопряженными по отношению к матрице H (или H -сопряженными), если скалярное произведение (x , Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером п хп.

Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента -f(x [k ]) в направление p [k ], H -сопряженное с ранее найденными направлениями р , р , ..., р [k -1]. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.

Направления р [k ] вычисляют по формулам:

p [k ] = -f"(x [k ]) +b k-1 p [k -l], k >= 1;

p = -f "(x ) .

Величины b k -1 выбираются так, чтобы направления p [k ], р [k -1] были H -сопряженными:

(p [k ], Hp [k- 1])= 0.

В результате для квадратичной функции

итерационный процесс минимизации имеет вид

x [k +l] =x [k ] +a k p [k ],

где р [k ] - направление спуска на k- м шаге; а k - величина шага. Последняя выбирается из условия минимума функции f(х) по а в направлении движения, т. е. в результате решения задачи одномерной минимизации:

f(х [k ] + а k р [k ]) = f(x [k ] + ар [k ]) .

Для квадратичной функции

Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.

1. В точке х вычисляется p = -f"(x ) .

2. На k- м шаге по приведенным выше формулам определяются шаг а k . и точка х [k+ 1].

3. Вычисляются величины f(x [k +1]) и f"(x [k +1]) .

4. Если f"(x ) = 0, то точка х [k +1] является точкой минимума функции f(х). В противном случае определяется новое направление p [k +l] из соотношения

и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+ 1)-й итерации процедуры 1-4 циклически повторяются с заменой х на х [п +1] , а вычисления заканчиваются при, где - заданное число. При этом применяют следующую модификацию метода:

x [k +l] = x [k ] +a k p [k ],

p [k ] = -f"(x [k ])+ b k- 1 p [k -l], k >= 1;

p = -f"(x );

f(х [k ] + a k p [k ]) = f(x [k ] + ap [k ];

Здесь I - множество индексов: I = {0, n, 2п, Зп, ...} , т. е. обновление метода происходит через каждые п шагов.

Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис. 2.11). Из заданной начальной точки х осуществляется спуск в направлении р = -f"(x ). В точке х определяется вектор-градиент f"(x ). Поскольку х является точкой минимума функции в направлении р , то f"(х ) ортогонален вектору р . Затем отыскивается вектор р , H -сопряженный к р . Далее отыскивается минимум функции вдоль направления р и т. д.

Рис. 2.11.

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

Градиентные методы, базирующиеся только на вычислении градиента R (x ), являются методами первого порядка, так как на интервале шага они заменяют нелинейную функцию R (x ) линейной.

Более эффективными могут быть методы второго порядка, которые используют при вычислении не только первые, но и вторые производные от R (x ) в текущей точке. Однако у этих методов есть свои труднорешаемые проблемы – вычисление вторых производных в точке, к тому же вдали от оптимума матрица вторых производных может быть плохо обусловлена.

Метод сопряженных градиентов является попыткой объединить достоинства методов первого и второго порядка с исключением их недостатков. На начальных этапах (вдали от оптимума) метод ведет себя как метод первого порядка, а в окрестностях оптимума приближается к методам второго порядка.

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

Алгоритм метода можно записать следующим образом (в векторной форме):

x 1 = x 0 – h grad R(x 0),

x i+1 = x i – h .

Величина α может быть приближенно найдена из выражения

Алгоритм работает следующим образом. Из начальной точки х 0 ищут minR (x ) в направлении градиента (методом наискорейшего спуска), затем, начиная с найденной точки и далее, направление поиска min определяется по второму выражению. Поиск минимума по направлению может осуществляться любым способом: можно использовать метод последовательного сканирования без коррекции шага сканирования при переходе минимума, поэтому точность достижения минимума по направлению зависит от величины шага h .

Для квадратичной функции R (x ) решение может быть найдено за п шагов (п – размерность задачи). Для других функций поиск будет медленнее, а в ряде случаев может вообще не достигнуть оптимума вследствие сильного влияния вычислительных ошибок.

Одна из возможных траекторий поиска минимума двумерной функции методом сопряженных градиентов приведена на рис. 1.

Алгоритм метода сопряжённых градиентов для поиска минимума.

Начальный этап. Выполнение градиентного метода.

Задаём начальное приближение x 1 0 , х 2 0 . Определяем значение критерия R (x 1 0 , х 2 0). Положить k = 0 и перейти к шагу 1 начального этапа.

Шаг 1. и
.

Шаг 2. Если модуль градиента

Шаг 3.

x k+1 = x k – h grad R (x k)).

Шаг 4. R (x 1 k +1 , х 2 k +1). Если R (x 1 k +1 , х 2 k +1) < R (x 1 k , х 2 k), то положить k = k+1 и перейти к шагу 3. Если R (x 1 k +1 , х 2 k +1) ≥ R (x 1 k , х 2 k), то перейти к основному этапу.

Основной этап.

Шаг 1. Вычислить R(x 1 k + g, x 2 k), R(x 1 k – g, x 2 k), R(x 1 k , x 2 k + g), R(x 1 k , x 2 k). В соответствии с алгоритмом с центральной или парной пробы вычислить значение частных производных и . Вычислить значение модуля градиента
.

Шаг 2. Если модуль градиента
, то расчёт остановить, а точкой оптимума считать точку (x 1 k , x 2 k). В противном случае перейти к шагу 3.

Шаг 3. Вычислить коэффициент α в соответствии с формулой:

Шаг 4. Выполнить рабочий шаг, рассчитав по формуле

x k+1 = x k – h .

Шаг 5. Определить значение критерия R (x 1 k +1 , х 2 k +1). Положить k = k+1 и перейти к шагу 1.

Пример.

Для сравнения рассмотрим решение предыдущего примера. Первый шаг делаем по методу наискорейшего спуска (табл. 5).

Таблица 5

Найдена наилучшая точка. Вычисляем производные в этой точке: dR / dx 1 = –2.908; dR / dx 2 =1.600; вычисляем коэффициент α, учитывающий влияние градиента в предыдущей точке: α = 3,31920 ∙ 3,3192/8,3104 2 =0,160. Делаем рабочий шаг в соответствии с алгоритмом метода, получаем х 1 = 0,502, х 2 = 1,368. Далее все повторяется аналогично. Ниже, в табл. 6 приведены текущие координаты поиска следующих шагов.

Таблица 6