Вычислительные методы алгебры и оценивания. Семушин И.В. - 154 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

8 Итерационные методы
Метод сопряженных градиентов
Этот метод исходит из задачи минимизации функции
J(x) =
1
2
(Ax, x) − (b, x) , (8.34)
решение которой совпадает с решением системы
Ax = f , A = A
T
> 0 . (8.35)
Полный вывод метода сопряженных градиентов можно найти в [12]. Опус-
кая детали, приведем окончательный результат.
Метод сопряженных градиентов для решения сис т емы Ax = f состоит в
вычислениях по следующим формулам:
r
k
= b − Ax
k
, k = 0, 1, . . . ,
p
k+1
= r
k
+ β
k+1
p
k
, k = 1, 2, . . . , p
1
= r
0
,
x
k+1
= x
k
+ α
k+1
p
k+1
, k = 0, 1, . . . , x
0
= 0 ,
α
k+1
= (r
k
, p
k+1
)/(p
k+1
, Ap
k+1
) , k = 0 , 1, . . . ,
β
k+1
= −(Ap
k
, r
k
)/(Ap
k
, p
k
) , k = 1, 2, . . . .
(8.36)
Теорема 8.8 ( [12]). Для метода сопряженных градиентов (8.36) спра-
ведливо
kx
k
− xk
A
≤ 2
h
(1 −
p
λ
min
/λ
max
)/(1 +
p
λ
min
/λ
max
)
i
k
kxk
A
,
где λ
min
и λ
max
— минимальное и макс имальное собственные з начения мат-
рицы A.
Следуя [12], преобразуем соотношения (8.36). В этих соотношениях наибо-
лее трудоемкими являются две операции: вычисление векторов Ax
k
и Ap
k
.
Однако операцию вычисления вектора Ax
k
можно исключить. Поскольку
этот вектор нужен только для вычислении невязки r
k
, то можно заменить
первую из формул (8.36) на
r
k
= r
k−1
− α
k
Ap
k
, k = 1, 2, . . . , r
0
= b . (8.37)
Преобразуем формулы для вычисления параме т ров α
k+1
и β
k+1
. Подставляя
второе из соотношений (8.36) в четвертое, найдем
α
k+1
= (r
k
, r
k
)/(p
k+1
, αp
k+1
) , k = 0, 1, . . . . (8.38)
154

Страницы