Высокопроизводительные вычисления на кластерах. Беликов Д.А - 180 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

180
Достаточным условием сходимости метода сопряженных гради-
ентов являются симметричность и положительная определенность
матрицы
A
, при этом если для спектра матрицы выполняется усло-
вие
0
m A M
, то скорость сходимости можно определить
по формуле
0
2
2
;
1
1
.
1
n
n
n
x x
m M
m M
Скорость сходимости метода сопряженных градиентов выше,
чем скорость сходимости метода Зейделя.
Метод CG имеет то особенно привлекательное свойство, что в
его реализации предусмотрено одновременное хранение в памяти
лишь четырех векторов. Кроме того, в его внутреннем цикле поми-
мо матрично-векторного произведения вычисляются только два
скалярных произведения, три операции типа «saxpy» (сложение век-
тора, умноженного на число, с другим вектором) и небольшое коли-
чество скалярных операций. Таким образом, и необходимая опера-
тивная память, и объем вычислительной работы в методе не очень
велики. В CG алгоритме
1
x
вычисляется с использованием рекур-
рентных соотношений для трех групп векторов. Одновременно в
памяти требуется хранить лишь самые последние векторы из каж-
дой группы, которые переписываются поверх ранее рассчитанных
значений. Первая группа векторов – это приближенные решения
k
. Вторая группа – это невязки
k k
r b Ax
. Третья группа – это
сопряженные градиенты
k
p
. Эти векторы называют градиентами по
следующей причине: шаг метода CG можно рассматривать как вы-
бор числа
new
a a
из условия, чтобы новое приближенное решение
!
k k k
new
x x a a p
минимизировало норму невязки
1
1/2
1T
k k k
A
r r A r
. Иными словами,
k
p
используется как направ-
ление градиентного поиска. Они называются сопряженными или,
точнее, А-сопряженными, потому что
0
T
k j
p Ap
при
j k
.
Параллельную реализацию метода сопряженных градиентов рас-
смотрим на примере приближенного решения уравнения теплопро-

Страницы