book1989

Итерационный метод (2) с параметрами т*, определенными со­ гласно (3), (4), называется явным итерационным методом с чебышевским набором параметров.

З а м е ч а н и е .			В сл у ч а е п = 1		м е т о д	( 2 ) — (4 ) с о в п а д а е т		с м е т о д о м п р остой
и терац и и
гд е
			т = т0=			2
					^•min (^) Т" ^шах (^)
И з теор ем ы		1 с л е д у е т , что т = т 0			я в л я ет ся оп ти м ал ьн ы м		зн ач ен и ем		п ар ам ет р а т
в м е т о д е	п р остой		и терац и и . О ц ен к а ( 5 ),			(6 ) в с л у ч а е я = 1		п р и н и м ает в и д
				11*1— * 1 К р о И * о — *11-
Т оч н о так	ж е д л я		л ю бой	и терац и и	k сп р а в ед л и в а оц ен к а
о т к у д а				Il*ft+1—*1Кро||*Ц—*11,
				И*Й ---* II =£ Ро II *0 — * В-
Э т а о ц ен к а		п огр еш н ости		м е т о д а	п р остой	и терац и и бы л а	п ол уч ен а		д р у ги м с п о ­
с о б о м в §	4	(оц ен к а (1 3 )		и з § 4 ) .

Подсчитаем число итераций, достаточное для получения задан­ ной точности е при использовании явного метода с чебышевским на­ бором параметров. Из оценки (5) получим, что

I U , — * l l < e i i * „ — * | | ,

если qn<Ze, где qn определено согласно (6). Таким образом прихо­ дим к неравенству

1 + рГ ^ 2

решая которое относительно 2 = р1" > 1 , получим

_1_ . 1 -Ц Л — Е2

р? е

Последнее неравенство будет выполнено, если потребовать 1/р">

^	2/е,	т. е.	">,цМНг^-		<12>
	В	наиболее	неблагоприятном случае,		когда отношение | =
=	Я , т ! а ( ^ ) Д т а х ( ^ )		МЭЛО, И М ввМ
			In — = = l n	« 2	/ 1
			Pi	V1 -/S /
					111

и из (12 ) получим следующее приближенное выражение для числа итераций:

«0 (е)	In (2/е)	(13)

2 V I

Таким образом, при малых £ явный итерационный метод с чебышевским набором параметров требует_для достижения заданной

точности е числа итераций л0(£) =0(1/У!). Именно в этом состоит его преимущество перед методом простой итерации, для которого согласно (14) из § 4 имеем л0(|) = 0 ( Щ ) .

2. Численная устойчивость итерационного метода с чебышевским набором параметров. Как уже отмечалось в примере 2 из п. 4 § 5 оценка погрешности (5) остается одной и той же при различ­ ном упорядочении набора итерационных параметров (3). Теорети­ чески эти параметры можно использовать в любом порядке. Напри­ мер, можно взять их в том порядке, как это указано в формуле (3). Можно использовать параметры в обратном порядке, т. е. поло­ жить

	ТА:	То	* = 1	,2.	п.
		Pc/n-j■к+1
	1 +

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

zk+l= (Е тii+iA)zk.

Норма оператора перехода Е—тй+1Л данного итерационного мето­ да может оказаться больше единицы для нескольких соседних ите­ раций, что и приведет к возрастанию погрешности. Иногда вычис­ лительная погрешность возрастает настолько сильно, что происхо­ дит переполнение арифметического устройства ЭВМ.

Здесь можно провести аналогию с вычислением произведения нескольких чисел. Рассмотрим следующий пример. Пусть на неко­ торой ЭВМ машинным нулем является число Л4„=10~р, а машин­ ной бесконечностью — число = 10р, где р > 0. Попытаемся вычис­ лить на этой ЭВМ произведение пяти чисел 10р/2, 10р/4, 10_р/\ 103р/4, 10_3р/1. Это произведение равно 10р/4 и принадлежит допу­ стимому интервалу чисел (М0,М„).

Однако результат вычисления на ЭВМ будет зависеть от того,

вкаком порядке перемножаются данные числа. При перемножении

впорядке убывания

103р/4• 10Р/2 ■10Р/4■10_р/2 ■10-3р/4

уже выполнение первого умножения приводит к переполнению, так

112

как 105p/4>Afoo. После этого вычисления прекращаются, и мы про­ сто не сможем вычислить все произведение. При перемножении в порядке возрастания

10-3р/4 ■10 -р/2 • 10Р/4• 10р/2 • 103p/i

после первого умножения получаем число 10~5p/i< M 0r которое по­ лагается равным нулю, следовательно, равным нулю оказывается и все произведение. Если же расположить сомножители в таком порядке:

10_3р/410Р/2103р/410~р/210р/4,

то удается довести вычисления до конца и получить правильный результат.

В настоящее время известен алгоритм построения такого упо­ рядоченного набора итерационных параметров (3), для которого итерационный метод (2) является устойчивым. Подробное изложе­ ние этого алгоритма можно найти в [32].

3. Неявный чебышевский итерационный метод. Скорость схо­ димости явного метода (2 ), (3) зависит, как мы видели, от отно­ шения | = ^т|п('4)/ХтЭх(>1) минимального собственного числа матри­ цы А к максимальному: чем больше |, тем выше скорость сходи­ мости. Рассмотрим теперь неявный итерационный метод

В — -----— + Axk = f, ^ = 0,1, ... , х0 задан,	(14)
Т/г+1

с симметричной положительно определенной матрицей В и пере­ менными параметрами т*+1. Как и в случае стационарных методов (см. § 4), скорость сходимости метода (14) будет определяться уже не отношением собственных чисел матрицы А, а отношением \ = ^m\n{B~lA)lXm!iX(B~lA) минимального и максимального собствен­ ных чисел обобщенной задачи

.4ц	= лВ|ы.	(15)
При соответствующем выборе	матрицы	В это отношение будет

больше чем Ят|11(А)Дтах(А), а следовательно, итерационный метод (14) будет сходиться быстрее, чем явный метод (2).

Теория неявных итерационных методов легко сводится к теории

явного метода.	Для неявного чебышевского метода справедлива
Т е о р е м а	2. Пусть А и В — симметричные положительно опре­

деленные матрицы, а kmi„(B_1A), Xmas(B- 1A) — соответственно наи­ меньшее и наибольшее собственные значения задачи (15). Пусть задано число итераций п. Метод (14) имеет минимальную погреш­ ность \\хп—х\\в, если параметры xk определить согласно (3), (4), где

При этом справедлива оценка
\\хп—	х\\в,	(16)
		из

где

Яп.	2pf	О =	[~ V l	*mln (g ~M )	(17)
	+ рГ '
1		pl	1+Vi

Д о к а з а т е л ь с т в о . Погрешность zk=xk—х удовлетворяет од­ нородному уравнению

В —

+ Azk = О, Л = 0, 1, . . . . z0= *0— *.

(18)

Т£+1

Умножим уравнение (18) на матрицу В~иг и обозначим vk = Binzh. Тогда получим уравнение

+Ct>t = 0, й = 0, 1 , . . v0 = Bv‘ (x0- x ) , (19)

TA+1

где С= B~inAB~i/2. Уравнение (19) отличается только обозначе­ ниями от уравнения (7), которому удовлетворяет погрешность яв­ ного итерационного метода. Поэтому нам остается лишь проверить выполнение условий теоремы 1 по отношению к матрице С.

Матрица С является симметричной и положительно определен­ ной, причем ее спектр совпадает со спектром обобщенной задачи на собственные значения (15). В частности, Xmin(5_1A) является ми­ нимальным собственным числом A,min(C) матрицы С, а Хтзк(В~1А )— максимальным. Следуя теореме 1, выберем параметры т* согласно (3), (4), где l=^min(C)AmaДС). Тогда для решения уравнения (19) будет выполняться оценка

Подставляя сюда vk=Bl/2zh, k = 0, п, получим

т. е. придем к требуемой оценке (16). Теорема 2 доказана.

З а м е ч а н и е . При условиях теоремы 2 наряду с оценкой (16) справед­

лива и оценка

(Un—х|| A^^nlUo—*IU.

Для доказательства достаточно переписать уравнение (18) в виде (19), где vk= A ' llZh, С = А '1>В-1А'1’, и повторить рассуждения теоремы 2.

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

4. Случай, когда точные границы спектра неизвестны. В теоре­ мах 1 и 2 фигурируют точные границы спектра матриц А и В~1А соответственно. Очень часто минимальные и максимальные собст­ венные значения не известны точно, а известны лишь оценки для них. Например, если выполнены матричные неравенства

'(1В ^ . А ^ ^ гВ

( 20)

114

с некоторыми константами 'y2>Y i> 0, то можно утверждать, что

^mln( В - 'А ) ^ ч 1» i^mas ( В ~ 'А ) ^ Ь .

Приведем теорему о сходимости итерационного метода (14) при условиях (20).

Т е о р е м а 3. Пусть А и В — симметричные положительно опре­ деленные матрицы, удовлетворяющие условию (20). Пусть задано число итераций п. Если параметры тк определить согласно (3), (4),

где	4,/-^, то для погрешности будет справедлива оценка
где		\\xn—x\\B^ q n\\x—x\\B,		(2 1 )
	Яп =	эр;	pi = i - K i	(22)
		1 + рГ *	i + n ’
	Д о к а з а т е л ь с т в о . Как и при доказательстве теоремы 2, за­
пишем уравнение для погрешности в виде (19). Из				(19) получим

v„= Tnv0,

где Т„=(Е—тлС)(Е—тп-,С) ... (£—т,С). Отсюда следует ||о„1К

<\\т,\\Ш\.

Пусть Cj— у-е собственное число матрицы С, / = 1, 2, ..., т. Так как Тп— симметричная матрица, норма ИГЛ совпадает с максиму­ мом из модулей ее собственных значений

шах	| (1 — т„с/) (1 — тп-±с/)		... (1 — тхс/) |
1<f^m
и не превосходит величины
шах	] (1 — тпс) (1 — тn-ic)		... (1 — ххс) |.	(23)
0<Vi<cS7.
Выбирая Тй, k= \,	2, ...,	п+ 1, согласно	(3), (4) при %=	мы
минимизируем величину		(23) и приходим к оценке IITJI sg:</п, где

qn определено согласно (22). Наконец, замечая, что ||iUI = IUn—х||в, приходим к требуемой оценке (2 1 ).

З а м е ч а н и е . Хотя	теорема 3 н не гарантирует оптимальности итераци­
онного метода, из оценки	(21) следует сходимость метода, причем при малых \

число итераций, достаточных для достижения заданной точности е, оценивается как

In (2/е)

По(?) = 2 V I ‘

§7. Итерационные методы вариационного типа *)

Впредыдущих параграфах рассматривались такие итерацион­

ные методы реш ения системы

Ax=f,

( 1)

*) При первом чтении этот параграф можно пропустить.

115

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

Б Хкн~'Хк + Ах/г= /,	(2)
тйи

в которых параметры xk+i выбираются из условия минимума по­ грешности IjXfc+t—xj|D при заданной погрешности \\хк—x[|D. Здесь D — заданная симметричная положительно определенная матрица,

||о||D= y(Dv, v). В зависимости от выбора матриц D и В получим различные итерационные методы. Скорость сходимости таких мето­ дов не выше, чем у чебышевского итерационного метода. Преиму­ ществом их является то, что они не требуют знания границ спектра матрицы А.

1.	Метод минимальных невязок. Рассмотрим систему (1) с сим­
метричной положительно определенной матрицей А.		Обозначим
через	гк=Ахк—f	(3)

невязку, которая получается при подстановке приближенного зна­ чения xh, полученного на й-й итерации, в уравнение (1). Заметим, что погрешность zk = xk—х и невязка rh связаны равенством Azh = rk.

Рассмотрим явный итерационный метод

** + A xk = f	(4)
TA+l
и перепишем его в виде	(5)
Xh+i = Xb Th+ifh.

Методом минимальных невязок называется итерационный ме­ тод (4), в котором параметр тА+1 выбирается из условия минимума Ikfc+il! при заданной норме ||rj. Получим явное выражение для ите­

рационного параметра тй+1. Из (5)	получаем
Axk+l = Axh—xk+lArh
и, следовательно,
1~к+1= Гk	Tk+iArк,	(6)

т. е. невязка rk удовлетворяет тому же уравнению, что и погреш­

ность Zh = XA— X.

Возводя обе части уравнения (6) скалярно в квадрат, получим

I! rk+l ||2= IrkI2 — 2тй+1 (rk, Ark) + т®+1 II Arkf.	(7)
Отсюда видно, что ||rft+1|] достигает минимума, если
(4'fe, rk)	(8)
1 --

II Ark f

Таким образом, в методе минимальных невязок переход от k-н итерации к (&+1)-й осуществляется следующим образом. По най­ денному значению хк вычисляется вектор невязки гк=Ахк—f и по

116

формуле (8) находится параметр rftfl. Затем по формуле (5) до­

считывается вектор x,l+t.

Метод минимальных невязок (5), (8) сходится с той же ско­ ростью, что и метод простой итерации с оптимальным параметром

т.Справедлива

Те о р е м а 1. Пусть А — симметричная положительно опреде­ ленная матрица. Для погрешности метода минимальных невязок выполняется оценка

\\А (хЛ—х) ||	\\А(х0—х) ||, и= 0,		1,...,	(9)
где		*min №
Ро	1 =			(10)
	1 + 1 ’	(Л)
Д о к а з а т е л ь с т в о .	Рассмотрим	тождество	(7). При	задан­

ном векторе rh правая часть этого тождества достигает минимума, если tft+i выбрать согласно ( 8 ) . При любом другом значении Tft+i правая часть тождества (7) может только увеличиться. Поэтому, полагая в (7) Tft+i= T0, где

U	w ^	+ w ^ )	*			(И)
получим неравенство
\\rk+A\2^ \ \ ( E - x 0A)rk\\*
и, следовательно,
[к,+1!|^]|£-тоЛ И 1кЛ.					( 12 )
Согласно следствию 2 теоремы 1 из § 4 имеем				Ц£—Т0Л|| = р о ,		ПО-
этому при всех k справедливо неравенство
	ik f t - i ll s S p o i k J ,				(13)
или, что то же самое, неравенство
IIЛ (xk+l—х) |]Сро1|Л {xk—x) II.
Отсюда и следует оценка (9).
З а м е ч а н и е . Используя	доказательство теоремы 1,			можно	получить	по­
лезное неравенство
(У> У)г ^ (Ау, У) (А-'у, у) ^		j ( V I + Y	| - ) 2 (У, У)г,			( И)

справедливое для симметричных положительно определенных матриц А и лю­ бого вектора уфО. Для доказательства (14) запишем тождество (7) при т*+1,

определенном согласно (8). Тогда получим

		II rk+i II2	=	II г'. II2 ‘	rk)
					\A'kf
	Учитывая неравенство (13),	получаем
	0			(Ark, rk)2	+ 21Ы !2
				l l ^ f
	(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)
где гА—Axk—f — невязка. Вектор
wh=B-'rh
называется поправкой на (й+1)-й итерации. Поправка	удовле­
творяет тому же уравнению, что и погрешность zh = xh—х	неявного
метода, т. е. уравнению
—wb	(16)
В——----—+ Awk = 0.
Tfe+i

Будем предполагать, что В — симметричная положительно опре­ деленная матрица. Методом минимальных поправок называется не­ явный итерационный метод (2 ), в котором параметр тЛ+) выбира­

ется из условия минимума нормы ||ш»Л.м Ji = (Вш*+), wh+,) u2 при за­ данном векторе wk. В случае В = £ метод минимальных поправок совпадает с методом минимальных невязок.

Найдем выражение для итерационного параметра тй+). Пере­ пишем (16) в виде

wk+l= wh—тЛ+,В-Мш*

и вычислим

1Wk+ifa==I I IJs —2xk+Jl(Awk, w k) + Tt +1 (B~l A w k, A w k).

	Отсюда следует, что Ццц+i	будет минимальной, если положить
		(АЩ, Щ)	(17)
	Tft+1	(В'Мш1А, Awk)

Для реализации метода минимальных поправок требуется на каждой итерации решить систему уравнений Bwh = rk, откуда най­ дем поправку wk, и решить систему уравнений Bvh = Awh, откуда найдем вектор vk = B~lAwh, необходимый для вычисления парамет­

ра Ть+j.

Скорость сходимости метода минимальных поправок определя­ ется границами спектра обобщенной задачи на собственные зна­

чения	(18)
Ах=ХВх.

Т е о р е м а 2. Пусть А, В — симметричные положительно опре­ деленные матрицы и А.ТПП1(В_1Л), ^maI(B- M) — наименьшее и наи-

us

большее собственные значения задачи (18). Для погрешности ме­ тода минимальных поправок выполняется оценка

	1 А (хп—х) ||в_,		р*IА {хй — х) ||B_t,					п == О, 1 , ...	(19)
где
			1 —|		t	Kin (В_М)
		Ро~	1 -К ’		^			*
До к а з а т е л ь с т в о . Перепишем уравнение для поправки (16)
в виде
		— — — + Cvk = 0,							(20)
			TA+i
где vh = B'nwh,		C= B~inAB~in. Выражение (17) для итерационного
параметра x*+i принимает вид									(21)
						vk)
					|сь*Р
Уравнения		(20) и (21)— это те же самые уравнения							(6), (8),
которые возникают в методе минимальных невязок. Поэтому мож­
но воспользоваться теоремой 1					и записать оценку (13), которая те­
перь примет вид			l|y*+illsSpolM,						(22)
где
			1—£		е.-._		>wmin(C)
			И - Г				^шах(С) '
Заметим,	что	Xmla(C) =Xmla(B~lA)				и	Лт«(С) =кша1(В~'А).		Кроме
того,
	||vkI =	|| B 'V |j =	I B-y’rk1=			1'"ftИд-. =		и (**— *) !la-i•
Отсюда и следует оценка (19).
3.	Метод скорейшего			спуска. Рассмотрим явный метод (4) и
выберем итерационный параметр xh+l из условия минимума ||2ft+1|L
при заданном векторе zk, где zh+l=xh+L—х. Поскольку погрешность
zhудовлетворяет уравнению
имеем			^A+i	*-h Та+1Azk,

I 2kri |U — I zk|д — 2т*ц (Azk, Az^) -f- Tk+i (A2Zk, Azk).

Следовательно, Цг^Цл будет минимальной, если положить

(Azk> Azk)

TA+1 — ( А \ , Azk)

ПО

Так как величина zk=xh—х неизвестна (поскольку неизвестно точное решение х), надо учесть, что Azk=rk = Axh—f, и вычисление т*+1 проводить по формуле

Tft+i — irk’ rk)	(23)
(Ark<Tk)

Так же, как и в теореме 1, доказывается, что метод скорейшего спуска сходится с той же скоростью, что и метод простой итерации с оптимальным параметром т = т0. Для погрешности метода ско­ рейшего спуска справедлива оценка

		Н * п —х||а< р£1|*о—х \ \ а , п = О, 1,	(24)
где р0	1 - 5	Kin И)
	1+ 5 ’	^тах (А)

Неявным методом скорейшего спуска называется метод (2), в котором параметр Tfc+i выбирается из условия минимума ||2Л+1||Л. Так как погрешность zk = xk—х удовлетворяет уравнению

2*+r=z4—тмнД-Мг*,

получим
1Zft+1 ||л = II zk (а — 2т4+1 (Azk, B~lAzk) +		т*+1 (АВ^Агь, B^Az^,
или
||z*+i ||л = 1|г*||л	— 2 т й+1 {rk, Wk) +	xl+1 (Awk, wk).
Следовательно, ||г*+1||л	будет минимальной, если положить
	('*» Щ)	(25)
	Д*+1
	(Awk, wk)

При этом для неявного метода скорейшего спуска справедлива оценка (24), где

Лтщ(В-М)

ёятах (S-M) •

4.Метод сопряженных градиентов. Метод сопряженных гради­ ентов является двухшаговым итерационным методом, т. е. для на­ хождения новой итерации хп+1 используются две предыдущие ите­ рации хп и х„_,. Следовательно, здесь возрастает требуемый объем памяти, нужно помнить не только вектор хп, но и х„_,. Применение

двухшаговых методов оправдывается тем, что при правильном вы­ боре итерационных параметров скорость сходимости будет выше,

чем у одношаговых методов, Например, рассматриваемый далее

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

Пусть А — матрица системы (1) и В — симметричная положи­ тельно определенная матрица. Рассмотрим следующий класс не-

120