Лекции по параллельным вычислениям. Гергель В.П - 155 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

155
рого получения начального приближения, простота организации параллельных
вычислений. Рассмотрим один из наиболее известных итерационных алгорит-
мов – метод сопряженных градиентов.
Будем полагать, что матрица A системы симметричная и положительно оп-
ределенная, т.е. А=А
Т
и x
T
Ax>0. При этом функция
 
cq
TT
bxAxxx
2
1
(11.10)
имеет единственный минимум в точке x
*
, совпадающей с точным решением
системы (11.1). Метод сопряженных градиентов позволяет найти это решение
путем минимизации функции q(x).
Итерация метода сопряженных градиентов состоит в вычислении очеред-
ного приближения к точному решению в соответствии с правилом:
kkkk
s
d
x
x
1
, (11.11)
т.е. новое приближение x
k
вычисляется путем добавления к приближению
1k
x
,
полученному на предыдущем шаге, вектора направления
k
d
, умноженного на
скалярную величину s
k
(шаг).
Перед началом выполнения алгоритма полагают
0
0
x
и
0
0
d
и bg
0
.
Шаг 1: Вычисление градиента:
bAxg
1kk
.
Шаг 2: Вычисление вектора направления:
1
11
k
k
T
k
k
T
k
kk
d
gg
gg
gd ,
где (g
T
g) – скалярное произведение векторов.
Шаг 3: Вычисление величины смещения по выбранному направлению:
k
T
k
k
T
k
k
s
dAd
gd
.

Страницы