book1989

на ЭВМ с плавающей запятой приводит к тому, что искомое реше­ ние определяется с относительной погрешностью

-Ц -- *! = 0{\ЛА • т ■2~1).

(24)

1И

Отметим, что для машины БЭСМ-6 число 2~‘ равно приблизи­ тельно 10-12.

Рассмотрим пример применения оценки (24). Пусть методом конечных раз­ ностей решается краевая задача

и"(х)= —f(x), 0 < х < 1 ,

и(0) =«( 1) = 0 .

(25)

Введем равномерную сетку

шл= {xi = ih, i'=0, 1, ..., N, hN= 1}

и заменим (25) разностной схемой второго порядка точности

'	ui+1	ui-1	Wo =	= 0.	(26)
	~j~^	— fit i — 1, 2, . . . , N — 1,

Казалось бы, чем меньше возьмем шаг Л, тем с большей точностью получим ре­

шение задачи	(25).	Однако	порядок m = N— 1 системы линейных алгебраиче­
ских уравнений	(26)	обратно	пропорционален шагу h. Значит, уменьшение ша­

га h приведет согласно (24) к увеличению погрешностей округления, и при не­ котором значении h погрешности округления могут превзойти погрешность разностного метода, пропорциональную №. Оценка (24) позволяет выбрать по­ рядок шага Л, при котором погрешность округления еще не превосходит по­ грешности метода. Остановимся на этом подробнее.

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

		МА= ^•тах (А)
			Vin (А)
Как известно	(см. п. 4 § 4 ч. I), для данной матрицы
		л h						nh
	^Ш1п (А) = ^ 7 sin2		2 ■	.(А)		= — cos2
							№
поэтому
		. л h _ 4 ____/_1_
		МА = ctg2		: я2/г2	° [ Л2
Отсюда	видно, что	при малых	h система		(26)		плохо	обусловлена. Далее,
т = 0 (Л"
		МА^ = 0 \ - ^
Поэтому правая часть		равенства	(24)	оценивается			как	0(2- ‘А- *). Для ТОГО

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

ностного метода,	достаточно	потребовать	2~‘h~3 =-=0(№),	т.	е. h —0 ( 2~ЧЬ).
В частности, при	2- i = 1 0 -12	приходим к	выводу о том,	что	нецелесообразно

брать шаг h меньше, чем 0,001, так как в противном случае накопление по­ грешностей округления может оказаться слишком велико.

81

Г Л А В А 2

ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

§ 1. Примеры и канонический вид итерационных методов решения систем линейных алгебраических уравнений

1. Итерационные методы Якоби и Зейделя. Перейдем к изуче­ нию итерационных методов решения систем линейных алгебраиче­ ских уравнений. Будем рассматривать систему

Ax = f,	(1)
где матрица Л = 1ау], i, /= 1, 2 ,	m, имеет обратную, х =

= О,, х2, . . . , хт)т, /= (f4, f2, . . . , fm)T.

Рассмотрим сначала два примера итерационных методов. Для

их построения предварительно преобразуем систему				(1 ) к виду
i_1 a-	m	a--	f-		(2)
X; —■ У . ~ ^ х , ~	V	- l L X l + ± , i = l , 2 ,		. . . . пг
fii аи	1=И-1	аи	*и

(при этом предполагается, что все ад отличны от нуля).

Условимся, как обычно, считать значение суммы равным нулю, если верхний предел суммирования меньше нижнего. Так, уравне­ ние (2 ) при /= 1 имеет вид

В дальнейшем верхний индекс будет указывать номер итерации, например

X	„	■—	/ п	у	п	rt \Т
						...» Хпг) ,

где х”— п-я итерация i-й компоненты вектора х.

В методе Якоби исходят из записи системы в виде (2), причем итерации определяются следующим образом:

л=0, 1, . . . , я0, 1 = 1 , 2 , . .., т.

Начальные значения х“, t=l , 2, . . . , т задаются произвольно.

Окончание итераций определяется либо заданием максимального числа итераций па, либо условием

шах | х — х" | < е,

где е > 0 — заданное число. Позже в § 2 будет показано, что при определенных условиях на матрицу А метод Якоби сходится, т. е. ||х"—х||->-0 при л->оо (здесь х — точное решение системы ( 1), а хп— приближенное решение, полученное на п-й итерации).

82

И т ер ац и он н ы й мет од З е й д е л я и м еет вид

r ?+1 =	• . v	JL хпы _ у			J L xn + lL
	^	а„	1	. 4 1	а,,	'	а,-,
	i=1			/=4-1
i=	1, 2, ...,		m,	п = 0, 1, ...,		п0-	(4)

Чтобы понять, как находятся отсюда значения х?+1, г = 1, 2, ...

. . . , т , запишем подробнее первые два уравнения системы (4):

Первая компонента х"т1 вектора xn+l находится из уравнения

(5) явным образом, для ее вычисления нужно знать вектор хп и значение /у. При нахождении х"+1 из уравнения (6) используются

только что		найденное значение х"+1 и известные значения хf,
/ = 3, . . . , пг,		с предыдущей итерации. Таким образом, компоненты
je?+1	вектора xn+i находятся из уравнения (4) последовательно, на­
чиная с i=l .
2.	Матричная запись методов Якоби и Зейделя. Для исследова­

ния сходимости итерационных	методов удобнее записывать их не в
координатной, а в матричной	форме. Представим матрицу А си­
стемы (1 ) в виде суммы трех матриц
A = A l-\-D-\-A1,		(7)

где D = diaglau, a22, amm] — диагональная матрица с той же главной диагональю, что и матрица А, матрица А, — нижняя тре­ угольная и матрица Аг— верхняя треугольная с нулевыми главны­ ми диагоналями.

Например, при т = 3 матрицы А ь Аг, D имеют вид
'0	0	0“	'0	ап	а 13	аи	0	0	"
Аг — °21	0	0 » А2 —	0	0	аЧ3 . D =	0	а22	0
- а31	а32	0.	_0	0	0 „	_0	0	Язз.

Представление системы (1) в форме (2) эквивалентно ее запи­ си в виде матричного уравнения

x = —D-lAix—D~lAix+D - */.

Отсюда видно, что метод Якоби (3) в векторной записи выглядит следующим образом:

xn+i = —ZJ-MiX"—£>-М2л;п+ Д -7 ,

или, что то же самое,

DxnJrl+ (A i-\-A1)xn = f.	(8)
	83

Метод Зейделя (4) записывается в виде
*"+' = _ Z )-yi1A-n+1^ D - 4 2*n+ D -7
или	(9)
(D+Al)x*+l+ A i*" = f.

Учитывая (7), методы (8) и (9) можно переписать соответст­ венно в виде

	D (хп« —хп) + Ах'1= f,	(10)
(D +	(хп^ — хп) + Ахп = }.	(И)

Из этой записи видно, что если итерационный метод сходится, то он сходится к решению исходной системы уравнений.

Очень часто для ускорения сходимости в итерационные методы вводят числовые параметры, которые зависят, вообще говоря, от номера итерации. Например, в методы (10), (11) можно ввести

итерационные параметры T n + i следующим образом:

D	+ Ax*=f,
	Я+1

уЛ-И __ rn

(DA-А,)------- -— \- Ахп= /. Tn+1

Способ выбора итерационных параметров выясняется при ис­ следовании сходимости. В теории итерационных методов сущест­ вует два круга вопросов: а) при каких значениях параметров ме­ тод сходится, б) при каких значениях параметров сходимость бу­ дет наиболее быстрой (соответствующие параметры называются оптимальными). В дальнейшем (см. § 4) мы подробнее остановим­ ся на этих вопросах в связи с конкретными итерационными мето­ дами.

Приведенные выше методы Якоби и Зейделя относятся к одно­ шаговым итерационным методам, когда для нахождения хп+' тре­ буется помнить только одну предыдущую итерацию хп. Иногда ис­ пользуются и многошаговые итерационные методы, в которых x'l+l

определяется через значения xh на двух и более предыдущих ите­ рациях, т. е. xn+i = F[xn, хп~1, . . . , хп~‘\.

3. Каноническая форма одношаговых итерационных методов. На примере методов Якоби и Зейделя видно, что один и тот же итерационный метод можно записать многими различными спосо­ бами. Поэтому целесообразно ввести какую-то стандартную форму записи итерационных методов. Условимся прежде всего записы вать итерационный метод не в координатной форме, а в матричной, Теперь хп будет обозначать вектор, полученный в результате п-й итерации.

Канонической формой одношагового итерационного метода	ре­
шения системы (1 ) называется его запись в виде
Bn+i *n+1 ~~ + Ахп= [, п = 0 , \ , . . . , п о.	(12)
Trt-Hl
84

Здесь Bn+i — матрица, задающая тот или иной итерационный метод, Тя+1 — итерационный параметр. Предполагается, что зада­

но начальное приближение х„ и	что	существуют матрицы В^1,
/1 = 1, 2, . . . , п0—1. Тогда из уравнения		(12)	можно последователь­
но определить все хп, п= 1, 2, . . . , га0. Для			нахождения	хп+1 по из­
вестным / и хп достаточно решить систему уравнений
Bn+1-^n+l	Вл,
где Fn= (Bn+1—Tn+lA)xn+ rn+lf.			(неявным),	если Вп = Е
Итерационный метод называют явным

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

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

Итерационный метод	(12 ) называется		стационарным, если
ВП+1 = В и тп+,= т не зависят от номера		итерации, и нестационар­
ным — в противоположном случае.
Приведем еще несколько примеров итерационных методов. Методом про­
стой итерации называют явный метод
	■Ахп =	f	(13)
с постоянным параметром т. Явный метод
	Axn =	f	(14)
с переменным параметром T„+ I	называется итерационным методом Ричардсона.

Для методов (13), (14) известен способ выбора оптимальных итерационных параметров в том случае, когда А — симметричная положительно определенная матрица (см. § 6).

Обобщением метода Зейделя (11) является метод верхней релаксации

хп+1 Хп

(D + соА ) -------------- + Ахп = /,	(15)
СО

где с о > 0 — заданный числовой параметр. В § 2 будет показано, что в случае симметричной положительно определенной матрицы А метод (15) сходится нри 0 « о < 2 .

Для получения расчетных формул перепишем (15) в виде

(£+соО-1Л|)хп+1=((1-оз)£-соВ-М2)х„+соД-1/.

В покомпонентной записи получим

^	аи
*?+1+ ® S	— 4 rl =
/=i в«		пг	а		х
		= (1 — со) x'l — со ^	—	xf +	со — , / = 1, 2, . . . , /п.
		. .	а,-:	'	а:,-
					85

Отсюда последовательно, начиная с / = 1 , находим все X(n+1:

		т а
		7=2 °U	011
			т	а .	Г
*"+1 =	— со — x?+1 +	(1 — со) х * —	со 2	“	Х1 + “ ~
2	«11	3	" ,	«22	«22
			/—3

и т. д.

§ 2. Исследование сходимости итерационных методов

Рассмотрим систему линейных алгебраических уравнений

Ax = f

(1)

с невырожденной действительной матрицей А и одношаговый ста­ ционарный итерационный метод, записанный в каноническом виде

B x™ Z ± + A x a = f, п = 0, 1, . . . ,

(2)

где хйзадан.

Говорят, что итерационный метод (2) сходится, если \\хп—х\\-+ ->0 при /1->-оо. Под нормой вектора х будем понимать сейчас сред­ неквадратичную норму

/ m \У*

\ Х =

4 2 */

\/=1

Решение х системы (1) будем рассматривать как элемент m-мерного евклидова пространства Н со скалярным произведе­

нием

Ш

(и, о) = 2 UjVh

/=1

При формулировке условий сходимости будут использоваться матричные неравенства. Для действительной матрицы С неравен­ ство С > 0 означает, что (Сх, х) > 0 для всех х е Я , хФО. Из нера­ венства С > 0 следует, что существует константа б > 0 такая, что

{Сх, х)^6\\х\\2.

Действительно, если С > 0 — симметричная матрица, то все ее собственные значения положительны и в качестве б можно взять минимальное собственное значение. Если С > 0 — несимметричная матрица, то для любого х е Я , хФО имеем

(Сх, x ) = j [{Сх, х) + (х, Сх)] > 0,

где С' — матрица, транспонированная к С. Поэтому в качестве б

можно	взять минимальное собственное		значение	матрицы С„ =
= 0,5(С+С*). Из оценки {Сх,		х )^ б ||х ||2	следует,	что существует
матрица	С-1. Неравенство С ^О	означает, что {Сх, х) ^ 0 для всех
Если С^О, то С-1 может и не существовать.
86

Перейдем к исследованию сходимости итерационного метода

(2). Погрешность метода на п-й итерации характеризуется векто­

ром zn = xn—х, который согласно (1 ), (2 ) удовлетворяет однород­ ному уравнению

Б	Zn+1~	2n	+ A zn = 0,	п = 0,	1, . . . ,	г0 = х0— х.	(3)
	т
Т е о р е м а		1.	Пусть А — симметричная			положительно	опреде­
ленная матрица, т > 0 и пусть выполнено неравенство
			В—0,5тЛ>0.				(4)
Тогда итерационный метод (2) сходится.
Д о к а з а т е л ь с т в о . Достаточно					показать, что среднеквадра­
тичная	норма	решения zn уравнения			(3)	стремится к нулю при

/г-voo и при любой начальной погрешности гй. Покажем сначала,

что при условии (4)	числовая последовательность Jn= (Azn,	zn)
является невозрастающей. Из уравнения (3) найдем
zn+l= (E ~xB -'A )zn, Azn+i = (А—xAB~'A)zn,
откуда получим
(Azn+i, zn+l) = (Azn, 2П)	т (AB~iAzn, zn)—
	—T (AZ„, 5 ~M2„ )+ T2(AB~lAzn, AB~lAzn).
Вследствие симметричности матрицы А имеем
(AB-lAzn, z„) = (Azn, B -‘Azn),
поэтому
(Azn+i, zn+l) = (Azn, zn)—2x{{B—Q,bxA)B-lAzn, B~lAzn).		(5)
Отсюда, учитывая условие (4), получаем неравенство
(Azn+i, zn+1) < (Azn, zn) .
Таким образом, числовая последовательность /„= (Az„, zn) мо­
нотонна и ограничена снизу нулем. Следовательно, существует
	lim Jn — J.	(6)
	П —*<х>

Далее, из положительной определенности матрицы В—0,5тЛ следует существование константы 6 > 0 такой, что

((В-0,5тЛ)В-Мг„, B -lAzn)^ b \\B - lAzn\\2.

Отсюда и из (5) получаем неравенство

/„+i—/„ + 2бт||В_1Л2п||2^ 0.

Переходя в этом неравенстве к пределу при м->оо и учитывая (6), убеждаемся в том, что существует

Нш ||wnI = 0,

п-*оо

где ш„= B~'Azn. Наконец, замечая, что А —-положительно опреде

87

ленная и, следовательно, обратимая матрица, получим

zn = A~lBwn, ||2Л < |И - ‘Я||||и»я||

и тем самым

lim [| znI =

0.

Теорема 1 доказана.

З а м е ч а н и е .

К ак

п о к а за н о в [3 2 ,

с.

5 2 7 ],

нри

у сл о в и я х

т еор ем ы 1

дл я

п огр еш н ости г„ = х „ —х и тер ац и он н ого

м е т о д а (2 )

сп р а в ед л и в а оц ен к а

p s ( 0 , 1), ||z n IIл = (Az„,

l | z „ | U

< p n ||z 0|U ,

гд е

tn)'1. Э та оц ен к а о зн а ч а ет , что

м е т о д сх о д и т с я

со

ск ор ость ю геом етр и ч еск ой

п р огр есси и

с о

зн а м ен а т ел ем

р. К он ст ан т а

р =

=

(1 — 2 т б .б /||ВЦ2) ’'1,

гд е

6 —

м и н и м ал ь н ое

со б ст в ен н о е

зн ач ен и е

м атри цы

А

в

6 .

— м и н и м ал ь н ое с о б ст в ен н о е зн ач ен и е

м атри цы

0 ,5 ( В' + В— хА).

Применим теорему 1 к конкретным итерационным методам, рас­ смотренным в предыдущем параграфе. Метод Якоби имеет следую­ щий канонический вид:

	D(xn+i—xn)+ A xn = f,		(7)
где D = diag[au,	а22, . . . , amm]. Таким образом,		в данном случае
B = D, т= 1.	1. Пусть А — симметричная положительно опре­
С л е д с т в и е
деленная матрица с диагональным преобладанием, т. е.
	а ц > 2 1 ач |.	i = l , 2 , . . . , т .	(8)
Тогда метод Якоби сходится.			в данном случае
Д о к а з а т е л ь с т в о . Условие сходимости (4)

имеет вид A<i2D. Покажем, что это матричное неравенство сле­ дует из неравенств (8). Рассмотрим положительно определенную квадратичную форму

(Ах, х) = ^ аИХ#1

1,/=1

и воспользуемся оценками

(Ах,	2	+ 7 2 I ач 1х) =
	l,i= 1	1,/'=1
		= { 2	\а-ч\*] + \ 2 1 °/'1 хг
		и =1	i.i=i

Из условий симметричности и положительной определенности мат­

рицы А имеем ац=ац, а«>0, i, /= 1, 2, . . . ,		пг, и поэтому предыду­
щая оценка приводит к неравенству
m	m		(9)
(Ах, XX 2 1ач Ixi = 2 */(S Iai>I+аи) •
£,/=1	£=1 vVt	/

88

Перепишем условие (8) в виде

an + S I аи I < 2а«> i — 1, 2 , .. т. !¥=1

Тогда из неравенства (9) получим

(Ах, х) < 2 ^ аих] = 2 (Ш, х),

1 = 1

что и требовалось.

С л е д с т в и е 2. Пусть А — симметричная положительно опре­

деленная матрица. Тогда метод верхней релаксации
(D + соА,)	ш	+ Axn = f

сходится при условии 0<со<2. В частности, метод Зейделя (со = 1) сходится.

Д о к а з а т е л ь с т в о .		Метод верхней релаксации приводится к
каноническому виду (2)		с В = 0 + шЛ,, т=ш. Напомним, что исход­
ная матрица	А представляется в виде		суммы A = D+ Al+A2, где
At— нижняя	треугольная, Л2— верхняя		треугольная и D — диаго­

нальная матрицы (см. (7) из § 1). Для симметричной матрицы Л матрица Л2 является транспонированной к Аи поэтому

(Ах, х) = (Dx, х) + (Л,х, х) + (Агх, х) = (Dx, х) + 2 (Л{х, х).

Условие сходимости (4) принимает вид (Вх, х)—0,5со(Лх, х) =

= ((D + (oAt)x, х)—0,5co((Z)x, х)+2 (А,х, х)) = (1—0,5ы) (Dx, л:) > О

и выполняется при 0< м < 2 .

Рассмотрим еще вопрос о сходимости метода простой итерации

хм,л— х„	(10)
^ ---- n- + Axn = f
т

ссимметричной положительно определенной матрицей Л. Согласно

(4)метод сходится при условии

Е—0,5тЛ > 0 .

(11)

Какие ограничения на параметр т накладывает условие (11)? Пусть h, i —1, 2, . . . , m,— собственные значения матрицы Л, рас­ положенные в порядке возрастания. Условие (11) эквивалентно тому, что все собственные значения матрицы Е—0,5тЛ положитель­ ны. Достаточно потребовать положительности минимального соб­ ственного числа этой матрицы, равного 1—0,5тАт. Таким образом, итерационный метод (10) сходится, если

т < 2 Д та1,

(12 )

где Хта1 — максимальное собственное число матрицы Л.

89

Условие (12 ) и необходимо для сходимости метода (10), т. е. если (12 ) нарушено, то найдется начальное приближение ха, при котором ||х„—х||-А0 при п—>-оо.

Докажем последнее утверждение. Возьмем в качестве началь­ ного приближения вектор x0= x-f-p, где х — точное решение зада­ чи (1), а р — собственный вектор матрицы А, отвечающий собст­ венному числу XmaI=X,m, т. е. Лц = Хтр. При таком выборе началь­ ного приближения имеем z0= x0—х=р. Из уравнения (3) при В = Е получим

	zn= (Е—тЛ)"20= (Е—тЛ)пр
и, следовательно, zn= ( 1—г%т)пц, ||z„||= 1 1—тА™|"||р,||.
Если т = 2Хт,	то ||z„|| = | | р | | п р и «->-оо. Если же т > 2

то |1—тЛщ,|>1 и ||zn||-voo при «-»-оо. Таким образом, условие (12) необходимо и достаточно для сходимости метода простой итера­ ции ( 10).

В заключение параграфа отметим, что теория итерационных ме­ тодов не заканчивается исследованием сходимости. При наличии хотя бы двух итерационных методов возникает вопрос о том, какой из этих методов сходится быстрее, т. е. для какого метода погреш­ ность ||хп—х\\ станет меньше заданного числа е при меньшем чис­ ле итераций п. Сюда же примыкает вопрос о нахождении итера­ ционных параметров, минимизирующих число итераций, необходи­ мых для получения заданной точности. Этот круг вопросов будет подробно рассмотрен в следующих параграфах.

§ 3. Необходимое и достаточное условие сходимости стационарных итерационных методов

1. Введение. Некоторые итерационные методы решения систем линейных алгебраических уравнений уже рассматривались в § 1, 2. Напомним необходимые для дальнейшего сведения.

Пусть дана система уравнений

Ax = l

(1)

где Л = 1ой], i, / = 1, 2 , . . . , m,— вещественная квадратная матрица, имеющая обратную, и х= (х„ хг, . . . , хт)Т, /= (fl7 /2, . . . , fm)T. Кано­ нической формой одношагового итерационного метода называется его запись в виде

	Вп+1*п+1~ Хп + A xn=Lf, л =			0 , 1 , . . . ,	(2)
	Тп+1
где п — номер итерации,		х0— заданное начальное			приближение,
хп= (*i>	... , Хт)Т■ Матрицы		Вп+1 и числа т„+,>0 задают тот
или иной конкретный итерационный метод.
В настоящем параграфе подробно рассматриваются стационар­
ные итерационные методы
	в	~ ------	b Ахп =	/,	(3)
		т
90