|
З а м е ч а н и е . Используя доказательство теоремы 1, можно получить по
лезное неравенство
(У> У)г ^
(Ау,
У)
(А-'у, у) ^
j (
V I
+ Y | - ) 2 (У, У)г,
( И)
справедливое для симметричных положительно определенных матриц
А и лю
бого вектора
у фО. Для доказательства (14) запишем тождество (7) при т*+
1
,
определенном согласно (8 ). Тогда получим
rk)
II
rk+i
II2 = II г'. II2 ‘
\A'kf
Учитывая неравенство (13), получаем
0
(Ark, rk)2
l l ^ f
+
21
Ы
!2
(Ark, rkf
(
rk, rk) (Ark, rk),
(■
Ark, rft) > > ( L - p 2) (rk, rk) (Ark, Ark).
117
Сделав замену
А Чгг н = у и учитывая, что
1—р02 = 4 | / ( 1 + | ) 2, получим соответ
ственно неравенства
(У. У)* < {А-1 у, у)
(
Ау
,
у),
(У. У)2>
(1
_ ^ ja
(А~1у. у) (Ау, у),
которые совпадают с (14). Обратно, если непосредственно доказать неравенства
(14), то из них можно вывести утверждение теоремы 1.
2
.
Метод минимальных поправок. Запишем неявный итерацион
ный метод (
2
) в виде
xh+l~xh
тВ */■*,
(15)
где гА—
Ax
k—
f
— невязка. Вектор
wh= B -'r h
называется
поправкой
на (й+1)-й итерации. Поправка
удовле
творяет тому же уравнению, что и погрешность
zh = x
h—
х
неявного
метода, т. е. уравнению
—
wb
В——----— +
Awk =
0.
(16)
Tfe+i
Будем предполагать, что
В
— симметричная положительно опре
деленная матрица.
Методом минимальных поправок
называется не
явный итерационный метод (
2
), в котором параметр тЛ+) выбира
ется из условия минимума нормы ||ш»Л.м Ji = (Вш*+),
w
h+, ) u2
при за
данном векторе
wk.
В случае В = £ метод минимальных поправок
совпадает с методом минимальных невязок.
Найдем выражение для итерационного параметра тй+). Пере
пишем (16) в виде
wk+l = wh—
тЛ+,В-Мш*
и вычислим
1
Wk+i
fa == I I IJs —
2 x k+Jl( A w k, w k)
+ T
t +1 (B~l A w k, A w k).
Отсюда следует, что Ццц+i
будет минимальной, если положить
(АЩ, Щ)
Tft+1
(В'Мш1А,
Awk)
(17)
Для реализации метода минимальных поправок требуется на
каждой итерации решить систему уравнений
Bwh = rk,
откуда най
дем поправку
wk,
и решить систему уравнений
Bvh = Awh,
откуда
найдем вектор
vk = B~lAwh,
необходимый для вычисления парамет
ра Ть+j.
Скорость сходимости метода минимальных поправок определя
ется границами спектра обобщенной задачи на собственные зна
чения
Ах=ХВх.
(18)
Т е о р е м а 2.
Пусть А, В
—
симметричные положительно опре
деленные матрицы и
А.ТПП
1
(В_1Л), ^maI(B- M) —
наименьшее и наи-
u s
большее собственные значения задачи
(18). Д ля погрешности ме
тода минимальных поправок выполняется оценка
1
А (хп
—
х)
||в_,
р* I
А {хй — х)
||B_t,
п
== О,
1
, . . .
(19)
где
1
—|
t
Kin
(В_М)
Ро~
1
- К ’ ^
*
Д о к а з а т е л ь с т в о . Перепишем уравнение для поправки (16)
в виде
— — — + Cvk = 0,
(20)
TA+i
где vh = B 'n wh, C = B~inAB~in.
Выражение (17) для итерационного
параметра x*+i принимает вид
vk)
|сь*Р
(
21
)
Уравнения (20) и (2 1 )— это те же самые уравнения (6), (8),
которые возникают в методе минимальных невязок. Поэтому мож
но воспользоваться теоремой 1 и записать оценку (13), которая те
перь примет вид
l|y*+illsSpolM,
(22)
где
1—£
е.-._ >wmin(C)
И - Г
^шах(С) '
Заметим, что Xmla(C) =Xmla(B~lA)
и Лт«(С) =кша1(В~'А).
Кроме
того,
||
vk
I = || B 'V |j = I
B-y’rk
1 = 1 '"ft Ид-. = и (** — *) !la-i •
Отсюда и следует оценка (19).
3.
Метод скорейшего спуска. Рассмотрим явный метод (4) и
выберем итерационный параметр xh+l
из условия минимума ||
2
ft+1|L
при заданном векторе z k,
где zh+l= x h+L—х.
Поскольку погрешность
zh
удовлетворяет уравнению
^A+i
*-h
Т
а
+1
Azk,
имеем
II
2kri
|U
—
II
zk
|д —
2т* ц
(Azk, Az^)
-f-
Tk+i (A2Zk, Azk).
Следовательно, Цг^Цл будет минимальной, если положить
(Azk> Azk)
TA
+1
—
( А \ , Azk)
ПО
Так как величина
zk= x
h—х неизвестна (поскольку неизвестно
точное решение
х),
надо учесть, что
Azk=rk = Axh—f,
и вычисление
т
*+1
проводить по формуле
Tft+i —
irk’ rk)
(Ark< Tk
)
(23)
Так же, как и в теореме 1, доказывается, что метод скорейшего
спуска сходится с той же скоростью, что и метод простой итерации
с оптимальным параметром т = т0. Для погрешности метода ско
рейшего спуска справедлива оценка
Н * п —
х
||
а
<
р
£1|*
о
—
х
\ \
а
,
п =
О,
1
,
(24)
где р
0
1 - 5
1 + 5 ’
Kin И)
^тах
(А)
Неявным методом скорейшего спуска
называется метод (2), в
котором параметр Tfc+i выбирается из условия минимума ||
2
Л+1||Л.
Так как погрешность
zk = xk—х
удовлетворяет уравнению
2
*+r=z
4
—тмнД-Мг*,
получим
1 Zft
+1
||л = II
zk (
а
—
2
т
4+1
(Azk, B~lAzk)
+ т
*+1
(АВ^Агь, B^Az^,
или
||z * + i ||л = 1|г*||л — 2 т й+1
{rk, Wk)
+
xl+1
(
Aw
k,
wk).
Следовательно, ||г*+1||л будет минимальной, если положить
Д
*+1
('*»
Щ)
(Awk, wk)
(25)
При этом для неявного метода скорейшего спуска справедлива
оценка (24), где
Лтщ(В-М)
ё
ятах (S-M) •
4.
Метод сопряженных градиентов. Метод сопряженных гради
ентов является двухшаговым итерационным методом, т. е. для на
хождения новой итерации х
п+1
используются две предыдущие ите
рации
хп
и х„_,. Следовательно, здесь возрастает требуемый объем
памяти, нужно помнить не только вектор
хп,
но и х„_,. Применение
двухшаговых методов оправдывается тем, что при правильном вы
боре итерационных параметров скорость сходимости будет выше,
чем
у
однош аговых методов, Н апример, рассматриваемы й дал ее
метод сопряженных градиентов при любом начальном приближении
сходится за конечное число итераций.
Пусть
А
— матрица системы (1) и
В
— симметричная положи
тельно определенная матрица. Рассмотрим следующий класс не-
120
явных двухшаговых итерационных методов:
(**+1
— **) + (
1
—
ak+
1
)
(хк — xk-
1
)
В-
Ас* = /,
k
=
1
,
2
, . . . (26)
Здесь а„+1, тЬч— итерационные параметры, которые будут опреде
лены далее. Для начала счета необходимо задать два начальных
приближения
х0
и
х,.
Начальное приближение
х„
будем задавать
произвольно, а вектор х, вычислять по одношаговой формуле, ко
торая получается из (26) при
k = 0, a ^ l ,
т. е. по формуле
+ Лх
0
= / .
(27)
Ti
Если параметры
ak+i,
т
Л+1
найдены, то новое приближение
хк+1
выражается через
Do'stlaringiz bilan baham: |
