book1989

в которых матрица В и числовой параметр т не зависят от номера

итерации п.

Погрешность итерационного метода (3) vn = xn—х, где х — точ­ ное решение системы (1 ), удовлетворяет уравнению

В —------т

+ Лу„ = 0, п = 0 , 1 , . . . , v0 = x0 — x,

(4)

которое отличается от уравнения (3) лишь тем, что является одно­ родным.

Сходимость итерационного метода (3) означает, что >-0 в не­ которой норме при п->-оо. Переписывая уравнение (4) в разрешен­ ной относительно ип+1 форме

vn+l = Svn,	(5)
где	(6)
S = E—хВ~‘А,

видим, что свойство сходимости итерационного метода целиком оп­ ределяется матрицей S. Необходимые и достаточные условия схо­ димости в терминах матрицы 5 приведены ниже в п. 3. Матрица S называется матрицей перехода от п-й итерации к ( я + 1)-й.

2. Норма матрицы. При исследовании сходимости будем рас­ сматривать векторы хп и х как элементы m-мерного линейного про­ странства Н, в котором введена норма ||х|| вектора х. Нормой мат­ рицы А, подчиненной данной норме вектора, называется число

IIА 1 = sup	Ах\
хфа	II* И

Норму вектора в пространстве Н можно ввести различным обра­ зом. Нам прежде всего потребуется норма

IIX||с= 1шах |ЛГ;|.

Подчиненная ей норма матрицы А выражается через элементы мат­ рицы А следующим образом:

\\А\\с= шах 2 К | -

/=1

Докажем это утверждение. Для любого вектора х справедливо неравенство

Ах ||с = шах	2	ачxi	SI	max	| х- |	max 2	\ a,, | =
				IS/S"!	1 IS'S'7! I_x
							=	l	max 2 K /l II* lb
									iS'S”i .
», е.									l=i
				'	шах	2 1 K /l	»II*Нс-		(7)
						i=i
									91

Ч тобы зав ер ш и ть		д о к а за т ел ь ст в о , д о ст а т о ч н о п острои ть вектор
= (*J,	.............* т ) Г> д л я	к о то р о го в ы п ол н яется р ав ен ств о

		I!Ахо1с =	(	"lax S			aiiI	U II*0lie
						/=1			J
П у ст ь	ф ун кц и я
		in
		Фг = 2 I аи I’				i = 1. 2,
		/=1
д о с т и г а е т	м ак си м ум а	при i=kt т. e.
			m				in
		ш ах V			| A y | = 2			I « */ I-
		l<i<m Г- 1					.
			/=1				1=1
Р а ссм о т р и м век тор Xo, и м ею щ и й			к оор ди н аты
		x„ _ l		!■		е с л и а Л/. >			0 ,
		1	I —	1,		есл и	akl-<		0 .
О ч ев и д н о, что ll-^oll с =		1- О ц ен и м	с н и зу			в ы р аж ен и е			д л я 1И *о||с. И м еем

*0=

(8)

О)

(Ю)

	1 Аха||с = ш ах	m	>	m
		2 ачх)		2	аыА
	l^i^m
		i=i		1=1

Д а л е е , и сх о д я и з оп р ед ел ен и я (1 0 )

т

2 V i

I=I

и, сл ед о в а т ел ь н о ,

т

иАхоНе > 2■ /=1

век тор а XQ, п олучи м

тт

2 % - * ° = 2

/=1 /=1

т

I aki I = тах 2 I ai/ 1• l^i<m ./=1

П о с л е д н е е	р ав ен ств о сп р а в ед л и в о			в си л у		( 9 ) . Т ем	сам ы м наш ли	век тор xQt
д л я к отор ого
				т
		l Axo\\> m ax		Y	К	/ I Их ° Нс
			1	.
				/=1
П оск ол ь к у	д л я	к а ж д о г о	в ек тор а	х сп р а в ед л и в о п р о т и в о п о л о ж н о е				н ер ав ен ­
ств о ( 7 ), зак л ю ч аем ,		что д л я	ха сп р а в ед л и в о		р ав ен ст в о		( 8 ) .

3.Теорема о сходимости итерационного метода. Справедлива

Т е о р е м а 1. Итерационный метод (3) сходится при любом начальном приближении тогда и только тогда, когда все собствен­ ные значения матрицы S= E —тВ~1А по модулю меньше единицы.

Д о к а з а т е л ь	с т в о . Представим уравнение (4) для погреш­
ности ц„=хп—х в	виде (5) —(6). Докажем сначала необходимость

условий теоремы	1. Предположим, что матрица 5 имеет собствен ­
ное число s, для	которого | s | > l , и покажем, что в этом случае

можно так подобрать начальное приближение х0, чтобы погреш­ ность vn = xn—х неограниченно возрастала при /г-*-оо. Пусть р — собственный вектор матрицы S, отвечающий собственному числу

92

s, | s | > l .	Возьмем	в качестве начального	приближения вектор
*0= х+|х,	так что начальная погрешность и0= р,. Тогда из уравне­
ния (5) получим		ц„= Snv0= s"u0= S"|X
и ||и„||'= |s|"||p||->oo		при п-*-оо. Если |s | = 1,	то ЦиГ1|| = ||[х||т^О при
П—>-оо.

Доказательство достаточности условий теоремы 1 проведем сначала в предположении, что матрица S имеет т линейно неза­

висимых	собственных векторов.	Пусть	sk, k= \, 2, ..... m,— собст­
венные	числа матрицы S и	6=1,	2,	т,— отвечающие им

линейно независимые собственные векторы. Разложим начальную погрешность va= x0—х по векторам р*:

vo—2 k—i

Тогда получим

т

y„ =	S”y0=	2	ckSnkVk.
		k=i
В любой норме справедлива оценка
1М	^ р п2	1^	11! п*II.	(П)
	Й=1
где р = max | s* | —спектральный		радиус матрицы		S. Из оценки

( 1 1 ) в силу предположения теоремы 1 о том, что р < 1, и следует сходимость метода.

4. Продолжение доказательства. В общем случае, когда систе­ ма собственных векторов матрицы S не является полной, доказа­ тельство достаточности условий теоремы 1 проводится с помощью приведения S к жордановой форме. Напомним (см. [12], стр. 147), что для любой квадратной матрицы S порядка т существует невы­ рожденная матрица Р такая, что матрица 5 = P~lSP имеет жорданову каноническую форму

г *	0	. ..	0	'
0	S,	. ..	0
5 =

0 0 . •

где Sk либо собственное число матрицы S, либо жорданова клетка, т. е. матрица вида

г®*	1	0	0 .	. 0		-1
0	sk	1	0 .	.	0
Sk =			0 .	.
0	0	0			1	J
Lo	0	0	0 .		Sk

a sk— собственные числа матрицы S.

93

Помимо обычной жордановой формы нам потребуется еще так называемая модифицированная жорданова форма матрицы S. Она строится следующим образом.

Применим к матрице S преобразование подобия D~lSD с диа­

гональной матрицей Z)= diag[l, е,				ет“']> где е — любое поло­
жительное число. Нетрудно убедиться, что матрица
S = D-<SD
имеет ту же блочно-диагональную			структуру, что и матрица S,
однако жордановы клетки имеют теперь следующий вид:
Г 5/0	е	0	0 .	.	о -
0	ч	£	0 .	.	0
& =
0	0	0	0 .	.	Б
L o	0	0	0 .		S* J
Матрицы S и S связаны равенством
S = Q-1SQ,			Q = PD.			(12)

Матрица S имеет в каждой строке не более двух отличных от нуля элементов, поэтому

|] 5 ||с ^ р (5) + е,

(13)

где p(S) — спектральный радиус матрицы S, т. е.

p(S) = max | Sk\. l<Lk<Lm

Напомним, что согласно (10) из § 6 гл. 1 подчиненная норма матрицы удовлетворяет неравенству

IIS||>p(S). (И)

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

утверждение.

Л е м м а 1. Для любого е > 0 существует норма ||-||, вектора такая, что для подчиненной нормы матрицы справедливо неравен'

ство	(15)
||iS||.^p(S)+e.
Д о к а з а т е л ь с т в о . Воспользуемся преобразованием	(12) и
определим норму вектора ||-|1*равенством

11г/||.= [IQ~'«/llc

для любого вектора г/еЯ. Для подчиненной нормы матрицы S имеем

! ^«*= sup	Sy II		WQ-'SyWc
	||У	sup---------- .
Уго		уфо	IIQ 1У 1с

94

Обозначая	Q~ly = x и учитывая		(12),	(13), получим отсюда
	ИQ~lSQx ||с		tS x ||с	= IS ||c ^	p (5) + e,
	sup-----------	sup------
	II х 11с	^ 0	I* He
что и требовалось.						(5)	полу­
Завершим доказательство теоремы 1. Из уравнения
чим	vn = Snv0,		п = 0,1, ...				(16)
Пусть	||-Ц* — норма, для	которой		выполнено	неравенство		(15).
По условию теоремы p ( S ) d , поэтому существует е > 0						такое, что
||5 ||.^p (S ) + е^< 7< 1. Из (16) получим оценку
	|ил|.^ ||5 |П к 1 1 ^ < р |К 1 ..						(17)

из которой следует, что ||и„||,-»-0 при любых начальных приближе­ ниях.

§ 4. Оценки скорости сходимости стационарных итерационных методов

1. Скорость сходимости итерационного метода. При практиче­ ском использовании итерационных методов важен не только сам факт сходимости, но и скорость, с которой приближенное решение сходится к точному. Так как при численном решении всегда осу­ ществляется конечное число итераций, необходимо знать, во сколь­ ко раз уменьшается начальная погрешность после проведения за­ данного числа итераций. Ответить на эти вопросы позволяет ана­ лиз оценок погрешности итерационного метода.

В предыдущем параграфе при доказательстве теоремы 1 была получена оценка (17), которую можно переписать в виде

\\хп—x lld ^ lU n —-VIU,	п = 0, 1, . . . ,	(1 )
где <7G (0, 1). Если для погрешности итерационного метода выпол­
няются оценки вида ( 1), то говорят,	что метод сходится	со ско­
ростью геометрической прогрессии со знаменателем q.

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

заданное число раз. Действительно, зададим	произвольное е > 0
и потребуем, чтобы qn<ie, т. е. чтобы
п > п 0(s) = | - (1/е) .	(2)

Ь (1/9)

Тогда из (1) получим, что

\\хп—х||,Се||*о—*11'.,

т. е. после проведения п0(е) итераций начальная погрешность ||*о—*11. уменьшилась в е-1 раз. Целая часть числа п0(е) называ­ ется минимальным числом итераций, необходимым для получения заданной точности е.

0S

Выражение 1п(1/у), находящееся в знаменателе числа га0(е), называется скоростью сходимости итерационного метода. Ско­ рость сходимости целиком определяется свойствами матрицы пе­ рехода 5 и не зависит ни от номера итерации п, ни от выбора на­ чального приближения Ха, ни от задаваемой точности е. Качество различных итерационных методов сравнивают обычно по их скоро­ сти сходимости: чем выше скорость сходимости, тем лучше метод.

2.Оценки скорости сходимости в случае симметричных матриц

Аи В. Продолжим изучение итерационных методов решения си­ стем линейных алгебраических уравнений

Ax = f.

(3)

Будем по-прежнему рассматривать стационарные одношаговые итерационные методы

+Ax n =f .	(4)
т

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

цы S = E—тВ~1А является,	как правило, более трудной		задачей,
чем решение системы (3).	будет доказана	теорема, в	которой
В настоящем параграфе
условия сходимости формулируются в виде		легко проверяемых
матричных неравенств, связывающих матрицы		А и В. Аналогич­

ная теорема о сходимости была доказана в § 2, однако там не бы­ ли получены оценки скорости сходимости.

Будем рассматривать решение х системы (3) и последователь­ ные приближения хп как элементы конечномерного линейного про­ странства Н, а матрицы А, В и другие — как операторы, действую­

щие	в	пространстве Н. Предположим, что в Н введены скаляр­
ное	произведение			(у, о) и норма ||у||=У(у, у). Для					двух симмет­
ричных		матриц А		я В неравенство А ^ В означает, что {Ах, х
^ {Вх,		х) для всех х еЯ . В случае						симметричной	положительно
определенной			матрицы D		будем обозначать ||у||с= УФу, у).
Т е о р е м а			1.	Пусть	А	и	В — симметричные		положительно
определенные матрицы, для						которых справедливы неравенства
					^ В ^ А ^ г В ,				(5)
где Yi, Чг— положительные постоянные, y2>4iПри
					т= 2/(ч,+ ч2)				(6)
итерационный метод (4)					сходится и для погрешности справедливы
оценки		\\хп — х\\А sSprtK				— -Ф,		п = 0, 1, ... ,	(7)
		I	%п	X|я 5С] рп||Хд			х ||в,	п = 0, 1, . . . ,	(8)
96

где ||у ||A = ^ ( A V, V ), \\V \\B= ^ ( B V , V ) U

	P	1	- 6	.Yi	(9)
		1	+ 6	T2

Доказательство теоремы 1 будет дано в п. 4. Сделаем необхо­ димые замечания и приведем следствия из этой теоремы.

Рассмотрим обобщенную задачу на собственные значения

Лр = АДр.		( 10)
Если для матриц А и В выполнены неравенства	(5), то из	(10)
для любого собственного вектора получим неравенства
Tfi(fip, р) < (Лр, р) =М £р, Р-)	Н-)-
Отсюда следует, что
YiSamin(S-M ), Ъ Ж * ЛВ~1А),		(11)
где Хшщ(5- М) и Хтгл{В~1А ) — минимальное и максимальное		соб<
ственные числа задачи (10).

Таким образом, наиболее точными константами, с которыми выполняются неравенства (5), являются константы

Y l = ^ m i n ( 5 - M ) , Y2= 7 , m a x ( S - M ) .

В этом случае параметр

___________________ 2______________

Т° ~ (^ А ) + (В-1А)

называется оптимальным итерационным параметром, так						как он
минимизирует величину
			- 6
			1 + 6 ’
на	множестве всех положительных			у2, удовлетворяющих усло­
виям (1 1 ).			и А,тах(Л)— соответственно		минимальное	и мак­
	Пусть А,тт(Л)
симальное собственные значения матрицы А.
	С л е д с т в и е		1. Если АТ= А > 0,	то для	метода простой ите­
рации
			+ Axn = f			(12)
при Т = Т0 =			справедлива оценка
	^mln М) + ^гпах (А)
			1 Хп— X 1SS pj I Х0— X ||,			(13)
гое	-I	t	^mir(^)
	р0== 1 + 6		■М)
4 А.	А. Самарский.	А.	В. Гулин			97

	С л е д с т в и е		2.	Для симметричной матрицы А и т„=
•=2/(Хт 1п(Л) +А,таДЛ))				справедливо равенство
				\\Е— т0Л|| = р0,
где	р0	i - i		(А)
		1+ 1
	В приложениях часто встречаются задачи с плохо обусловлен­
ной матрицей А,			когда отношение tana* (Л) Ami„(Л) велико. В этом

случае число р„ близко к единице и метод простой итерации схо­ дится медленно. Оценим число итераций п0(е), которое требуется в случае малых £ для достижения заданной точности е, т. е. для получения оценки

[рх„—х||<е||х0—*11-

Из условия р0п*<е получаем, что п ^ п 0(е), где

(е)	In (1/е)
	1п(1/р0)
и при малых | имеем
In (1/£)		(14)
« о (е )	21
Таким образом, метод простой итерации		(12) в случае малых £

является медленно сходящимся методом. Ускорить сходимость итерационных методов можно двумя способами: во-первых, за

счет применения неявных итерационных методов		(4), когда Вф Е,
и, во-вторых, оставаясь в классе явных	методов, можно выбрать
т = тп зависящим от номера итерации и	таким,	чтобы уменьшить

общее число итераций. Применяется и комбинация этих двух спо­

собов,		т	е. используются неявные			итерационные методы с пере­
менными итерационными параметрами.
	Использование неявных итерационных методов (4) объясняет­
ся тем,			что при соответствующем			выборе	матрицы В отношение
с	W S -M )			й й	задачи на		й
6	= - ------- :---- для обобщенной						собственные значения
(	10)	будет больше, чем отношение				^гт,|п(А)
						+iax (А)
	3.		Правила	действий с			неравенствами. Прежде
					матричными

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

1) Если А — вещественная симметричная матрица, то сущест­

вует ортогональная матрица Q (г. е. QT=Q~’) такая, что A = QrAQ, где А — диагональная матрица. На главной диагонали матрицы А находятся собственные значения матрицы А. Доказательство см. в [12, с. 156].

2) Для симметричной матрицы А неравенство Л ^О (Л >0) эквивалентно неотрицательности (положительности) всех ее соб­ ственных значений.

98

Д о к а з а т е л ь с т в о .	Используя свойство 1), получим для лю­
бого х е //, что			т
(Ах, х) = (QTAQx, х) = (AQx, Qx) = ^				ку],
			1 = 1
где %i— собственные числа		матрицы А и г/, — i-я		компонента век­
тора y = Qx. Отсюда сразу		следует,	что если все Х ^ О		(ХЛ>0), то
(Ах, х ) ^ 0 для любого г е / / ((Ах,			х) > 0 для любого х=А=0). Об­
ратно, пусть Xj — любое	собственное число матрицы				А. Зададим

вектор у, у которого все компоненты кроме /-й равны нулю, а у,—

= 1. Так как матрица	Q~l= QT существует, для заданного вектора
у найдется вектор х е Я	такой, что Qx = y. Но тогда

0 < (Ах, х) = (Ау, у) =Х;,

т.е. Xj^O.

3)Если АТ= А >0, т о существует А-1.

До к а з а т е л ь с т в о . Согласно 2) все собственные числа мат­ рицы А положительны, следовательно, detA=A=0 и существует А-1.

4) Для симметричной матрицы S и любого числа р > 0 эквива­ лентны следующие матричные неравенства:

— p E ^ S ^ p E ,	(15)
Sas^p2£.	(16)

Д о к а з а т е л ь с т в о . Согласно свойству 2)условие (15) экви­ валентно неравенствам

|SA|< P , /г= 1, 2, ..., m,

где sk—- собственные числа матрицы S. Отсюда получаем				^ р “,
k= 1, 2 , . . . , m, что в свою очередь эквивалентно			(16).
5) Если АГ=Л и Л^гО	(А >0),	то существует матрица В, об­
ладающая следующими свойствами:
Вг = А,	ВТ = В,	В ^ 0 (В>	0).	(17)
Эта матрица называется квадратным корнем из матрицы А и
обозначается Л1/2.	Пусть Xi — собственные числа			матрицы
Д о к а з а т е л ь с т в о .

Л, t =l , 2, ..., m. Согласно свойству 1)	существует ортогональная
матрица Q такая, что
QAQr = A=diag[X1, Хг,	Xml-

Поскольку все Xi неотрицательны, можно определить матрицу Аиг как

А1/1= diag[УХь У К - ••> УМ-

Тогда матрица B = QTAl,2Q обладает свойствами (17).

6) Пусть ЛТ=Л и L — невырожденная матрица. Тогда эквива­ лентны неравенства

Л^О , LTAL^zO.

4* 09

Аналогично, эквивалентны строгие неравенства

Л > 0, LTA L > 0.

Д о к а з а т е л ь с т в о . Для любого х ^ Н имеем (LTALx, я) =

= (ALx, Lx). Значит, LTAL^O, если ЛТ^О. Докажем обратное. Так как L-1 существует, любой х е Я можно представить в виде x = Ly, где y = L~lx. Тогда получим

(Ах, х) = (LTALy, y )^ z 0,

т. е. Л^О.

7) Если А и В — симметричные и L — невырожденная матри­ цы, то эквивалентны неравенства

Л ^ В , LTA L ^ L TBL.

Доказательство следует немедленно из (6).

8) Пусть СТ= С > 0 и а, (3 — любые действительные числа. Тог­ да эквивалентны неравенства

аС~^$Е, aВ ^ р С -1.

Д о к а з а т е л ь с т в о . Согласно 5) существует матрица С1/2 =

= (С,/2)Г> 0 . Используя свойство 7), перейдем от первого неравен­ ства ко второму с помощью следующей цепочки эквивалентных неравенств:

а (СГ%) С (С'А) р (С~'Л) (С~'л), а (С-'ЛС%) (С%С~%) 5* PC"1,

аЕ Ут;PC-1.

9) Пусть ЛГ= Л > 0, ВТ = В > 0, а и р —любые действительные числа. Тогда эквивалентны неравенства

аЛ^=г[ЗВ,		аВ_1^ р Л _‘.
Д о к а з а т е л ь с т в о .	Умножая первое неравенство слева и
справа на В-1/2, перейдем к эквивалентному неравенству
« С > р £ ,		С= В -1/2ЛВ-1/2.
Согласно 8) последнее	неравенство эквивалентно неравенству
а В ^ р С -1, т. е.	а £ ^ р В 1/2Л -‘5 1/2,

умножая которое слева и справа на В~'п, получим ссВ- 1^ р Л -1. 4. Доказательство теоремы 1. Уравнение для погрешности vn =

= хп—х имеет вид

a ""*1 - - + A v n = 0, л= 0, 1........	(18)
т
и0= х0—х,
откуда получим
цп+1 = 5 у„, S = B—тВ_,Л.	(19)
100