book1989

Л е м м а 1. Пусть А и В — симметричные положительно опре­ деленные матрицы и р > 0 — число. Матричные неравенства

т В < A sg т В

(20)

необходимы и достаточны для того, чтобы при любых v0<=H для решения задачи (18) выполнялась оценка

IIU n + ilL C p IlfJ U ,

п = 0, 1, . . .

(21)

Д о к а з а т е л ь с т в о . Оценку (21) можно записать в виде

II Wn+I|| < pllojjl1,	(22)
где wn = A l/2vn, ||и>п||=У(и>„, wn). Из (19)	получим, что функция
wn удовлетворяет уравнению
w„+t= Swn,	(23)

где S = A i/2SA~i/2 = E—тС, С= А1/2В~'А,/2. Для решения этого урав­ нения в силу симметричности матрицы S имеем

||шп+1||2= (5wn, Swn) = (S2wn, wn).

Тем самым оценка (22) эквивалентна неравенству

32^ р 2Е

(24)

и остается доказать эквивалентность неравенств (20) и (24). Согласно свойству 4) из п. 3, неравенство (24) эквивалентно

двум матричным неравенствам

—р Е ^ З ^ р Е

или

тт

Так как С=А1/2В~’А,/2— симметричная положительно определен­ ная матрица, согласно свойству 8) из п. 3, в этих неравенствах можно перейти к обратным матрицам, т. е. записать, что

С' 1 < Е <	С~\
X	X
Подставляя сюда выражение для С, получим
А~'лВА~'а s c f s c	А~'ЛВА~'/г.
т	т

Умножая последние неравенства слева и справа на А1П (см. свой­

ство 6) из п. 3), приходим к неравенствам (20). Лемма	1 доказана.
Л е м м а 2. При тех же условиях что и в лемме 1, неравенства
(20) необходимы и достаточны для выполнения оценки
II*VH IIB< P III' J B, я = 0, 1, ...	(25)
	101

Доказательство проводится почти так же, как и в лемме 1, только в качестве wn надо взять вектор Bl/2vn, а в качестве С — матрицу

Для доказательства теоремы 1 теперь достаточно заметить, что матричные неравенства (5) можно переписать в виде (20), где

- 5

		i + i ’	Та	Vi + Та
После этого замечания			утверждение	теоремы	1 следует из
лемм 1 и 2 .		погрешности в случае несимметричной матрицы В.
5.	Оценка
Пусть	задана	любая симметричная положительно			определенная
матрица D. Обозначим через S матрицу перехода итерационного
метода	(4), т. е. S = E—хВ~'А, и через			— погрешность метода,
vn = xn—х. Для		исследования сходимости итерационных методов в

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

	следующая	простая
	Л е м м а	3.	Если В~1 существует, то для выполнения оценок
				H«n+illD<pllfnL,		п = 0,		1, . . .	(26)
	необходимо и достаточно выполнение матричного неравенства
					р2D ^ S TDS.				(27)
	Д о к а з а т е л ь с т в о .				Учитывая	уравнение			для погрешности
	(19), перепишем (26) в виде
	или			(DSvn, Svn)^sp2(Dvn, vn)
		р2(Dvn, vn) ^ ( S TDSvn, vn),					n = 0,		1, ...
	Так как vaпроизвольно, отсюда следует (27).
	Обратно, если выполнено (27), то
	||Van|]Ъ=		(Dvn+1, Van) = (STDSvn, vn) <				p2 (Dun, vn) = p21 Vn|D,
	T . e. приходим к (26).				сформулированы			достаточные условия
	В следующей			теореме
	сходимости метода (4) в случае несимметричной матрицы В.
	Т е о р е м а		2.	Пусть А —симметричная				положительно опреде­
	ленная матрица			и В — невырожденная			матрица. Если выполнено
	матричное неравенство
				В— ЬЁ — —A 5 s		2т	BTA~1B		(28)
				2	2

сконстантой р е ( 0, 1), не зависящей от п, то итерационный метод

(4)сходится и для погрешности справедлива оценка

IU„—л:||а^ рп||а-0—х||л.			(29)
Д о к а з а т е л ь с т в о . Достаточно	показать,	что	выполнены
условия леммы 3 при D = A. Запишем	неравенство	(27)	для D = A
102

в виде

р(£—тЛВг-V (Е—хВ-'А).

Раскрывая скобки в правой части этого неравенства, получим

тА (В7- 1+В -1)А > (1 -р 2)А+х*АВ^АВ-*А.

(30)

Согласно свойству 7) матричных неравенств можно умножить каждую часть неравенства (30) справа на матрицу L = A~lB и од­

новременно слева — на матрицу LT= B TA~'. Тогда получим эквива­ лентное (30) неравенство

т (В+Вт) (1—р2)ВтА-'В+т2А , которое совпадает с (28). Таким образом, из (28) следует (27) и

согласно лемме 3 — оценка (29). Поскольку ре(0 ,	1),	из оценки
(29) получаем, что ||х„—JC|L->0 при n-э-оо, т. е. метод	(4)	сходится.
Теорема 2 доказана.

З а м е ч а н и е . Лемма 3 и теорема 2 остаются справедливыми и в случае комплексных матриц А и В, если только заменить ST

и Втна матрицы S* и В \	комплексно сопряженные с матрицами
S и В. В частности, условие (28) принимает вид
В0—	(31)
где Ва= 0,5(В+В').

§5. Многочлены Чебышева

1.Многочлен Чебышева на отрезке [—1, 1]. В ряде вопросов численного анализа, связанных с проблемой минимизации погреш­

ности вычислительного алгоритма, нашли применение многочлены, наименее уклоняющиеся от нуля.

Рассмотрим следующую задачу: среди всех многочленов сте­ пени п со старшим коэффициентом 1 найти такой многочлен Тп(х), для которого величина

max \Тп{х)\

является минимальной. Многочлен, обладающий этим свойством, называется многочленом, наименее уклоняющимся от нуля на от­ резке [—1, 1] или многочленом Чебышева. В этом параграфе бу­ дет показано, что функция

Тп(х) = 2‘“n cos(rc arccos х)	(1)
является многочленом Чебышева.
Рассмотрим сначала функцию
Рп(х) = cos(п arccosх),	(2)

которая отличается от Тп(х) только постоянным множителем. Проводя преобразование

cos ( (n+ 1 ) arccos х) +cos ((п— 1) arccos х) =

= 2 cos (п arccos х) cos (arccos х) =2хРп (х),

103

убеждаемся в том, что справедливо рекуррентное соотношение

		Я„+, (х) —2хРп (х) +Рп-, (х) = 0.						(3)
Кроме того, согласно (2) имеем			Р0(х) = 1, Р1(х)=х. Отсюда					и из
(3)	по индукции легко доказать, что Рп(х) — многочлен степени п
со	старшим	коэффициентом	2”_1, п= 1,			2, ...	Следовательно,
Тп(х) — многочлен степени п со старшим					коэффициентом 1.
	З а м е ч а н и е . Для вещественных		х	правая	часть выражения (1) опреде­
лена	только при	|х |^ 1 . Если |х |^ 1 ,	то	многочлен		Тп (х)	доопределяется	фор­
мулой
		Тп (х) = 2_га ((х + V х ^ Г \ ) п + (х - У				^ Г	\ ) п).

Возможность такого доопределения объясняется тем, что для любого комплекс­ ного числа z справедливо тождество

cos (п arccos z) = 0,5 ((z + У z1— 1)га + (z — У z2 — l)'1).

Корни многочлена Тп(х) расположены в точках
	(2k + 1) к	,	=	л .	— 1,	(4)
Xu = cos ^----—-— ,		6		0, 1
	2n
а экстремумы — в точках
x. =	cos — ,	k =	0,	\,	n,	(5)
R	n
причем	= ( - l ) ft2‘-",		6 = 0, 1, . . . , « .
7’n( ^ )						(6 )
•Следовательно,
	max |Г,г(л')| = 2l_ft.					(7)
	jce[-i,i]

Докажем теперь, что среди всех многочленов степени п со старшим коэффициентом 1 многочлен Тп(х) наименее уклоняется от нуля на отрезке [—1, 1]. Пусть Q„(x)— любой многочлен сте­

пени п со старшим коэффициентом 1. Обозначим
I Qn||=	max	| Q,,(*)|-
*e[—l.i]
Л е м м а 1. Пусть существует система точек
— K * ; s S C i <		<	х[<х'0^ 1	(8)
такая, что
I Qn (x'k) I = I Qn II,	k =		0, 1 ........ n,	(9

причем числа Qn(x'k) имеют чередующиеся знаки. Тогда среди всех многочленов степени п со старшим коэффициентом 1 много­ член Qn(x) наименее уклоняется от нуля.

Д о к а з а т е л ь с т в о . Предположим обратное, т. е. что суще­ ствует многочлен Qn(x) степени п со старшим коэффициентом 1, для которого H^nlKIIQJ и, следовательно,

!<?»(*) | ClIQnll

(Ю)

S04

с константой ре(Д, у , не зависящей от п, то итерационный метод

( 4 ) сх о д и т ся и д л я п о г р е ш н о ст и с п р а в е д л и в а о ц е н к а
\\хп—x lL ^ p nl|x-0—х\\А.			(29)
Д о к а з а т е л ь с т в о . Достаточно	показать,	что	выполнены
условия леммы 3 при D=A. Запишем	неравенство	(27)	для D=A

102

для всех х е [ —1, 1]. Рассмотрим функцию R(x) = Qn(x)—Qn(x), которая является многочленом степени п—-1, отличным от тожде­ ственного нуля. Согласно условию леммы числа Q„ (х^) имеют че­

редующиеся знаки. Пусть для определенности

Q»(%) = ( - i)*||Q4

fe = o, l, .... п

(случай, когда Qn(xk) = (—l) ft+lIIQJI рассматривается аналогично). Тогда

R(x'k) = (— 1)*ilQrtI— Qn(-«*)»	k = 0,	1, . . . , n
и согласно (10) получим, что многочлен R(x)		на отрезке [—1, 1]

меняет знак п раз, т. е. имеет п корней. Но это невозможно пото­ му, что R(x) — многочлен степени п— 1, отличный от тождествен­

ного нуля. Полученное противоречие и доказывает лемму				1.
З а м е ч а н и е . Справедливо утверждение, обратное лемме 1: если				Qn(x) —
многочлен	со	старшим	коэффициентом 1, наименее уклоняющийся от	нуля на
[— 1, 1],	то	найдется	система точек (8), для которой выполняются	равенства
(9), причем числа Qn (x//) имеют чередующиеся знаки.
На доказательстве этого утверждения останавливаться не будем.

Согласно (6), (7) многочлен Тп(х) удовлетворяет всем усло­ виям леммы 1, поэтому он наименее уклоняется от нуля на отрез­ ке [—1, 1 ] среди всех многочленов степени п со старшим коэффи­ циентом 1.

2. Случай произвольного отрезка. Иногда требуется найти мно­ гочлен, наименее уклоняющийся от нуля на заданном отрезке [а, Ь\, среди всех многочленов степени п со старшим коэффициен­ том 1. Эта задача сводится к предыдущей с помощью замены

t — --- X ----1—,
,	2	Ь + а
	b — а	Ь— а

переводящей отрезок а ^ х ^ Ь в отрезок —l ^ ^ c i . При такой за­ мене многочлен Чебышева

Tn(t) =2'~п cos(n arccos t)	(11)
преобразуется к виду
Fn(х) = 21"'1 cos (п arccos -2- ~ ^ь	\ ,

причем коэффициент при хп оказывается равным 2п/(Ь—а)п. Сле­ довательно, многочленом, наименее уклоняющимся от нуля на [а, Ь], среди всех многочленов степени п со старшим коэффициен­ том 1 является многочлен

Тп (х) = —— — cos (п arccos 2х				^b	а	а^
2%n~i	^		ь—
Корни этого многочлена расположены в точках
а-\-Ь . Ь — а ( 2 £ + 1 ) я		,	п	,		п-
Xk — ~ — 1— — cosv	^ — ,	k —	0,
	2п

(12)

(13)

а его

м а к си м а л ь н о е о т к л о н ен и е от нуля

р авно

max

| Т„ (х) | =

(6—Q)_ ^

(14)

хе[а,й]

22л_1

3. Другая нормировка многочленов Чебышева. В теории ите­

рационных

методов возникает

следующая

задача: найти

много­

член Рп(х)

степени п, наименее уклоняющийся от нуля на

[а, b],

среди всех многочленов степени п,

принимающих при х= 0

значе­

ние

1. Ясно, что искомый

многочлен

отличается

от

многочлена

( 12 )

только нормировкой, т. е.

Рл( х ) = ^ ^ - .

(15)

Тп (0)

Будем считать в дальнейшем, что Гп(0)+=0.

Е сли Т п (0 )= 0 , то за д а ч а

не им еет реш ен и я

в

к л ассе

м н огочленов

з а д а н ­

ной степени

л. Н ап р и м ер , д л я

м н огочлен а

п ервой

степ ени

Pi(x) = а х + 1

им еем

m ax Ц Ру (х) |

=

1 + 1 а

|

X < = [ - L ,ll

и м иним ум

д о с т и га е тс я при

я =

0. Н о

при

это м

Р > (х)

п ер естает

бы ть м н огочле­

ном п ервой

степени .

Из (12),

(15) получим при Ь > а > 0,

что

Рп (х) =

рпcos п arccos 2х — (Ь +

а)

(16)

где

b

—

а

)

•

р п =

c o s п a r c c o s

b

+ a

+

- 1

а — b

Обозначая

s = -

i - i

Ро =

(17)

1+ 5

получим

рп =

cos In arccos

(18)

(

-

г )

Для дальнейших преобразований воспользуемся тождествами cos (п arccos (— г)) = (— 1)" cos (пarccos z) —

= ( - l ) n0,5 ((г + V * = T ) n + ( г - Y ? = !)" ) . (19) При 2 = p~‘ имеем

Y z * - i = — - i / r — -	1 -	Y 1 - Pg2
Po V		Po

и, подставляя сюда выражение для р0из (17), получим

z — У г2 — 1	1 - У 1		1+ V I
		— , г + Уг2 — 1	1 - У 1
	■+	/ I

106

Отсюда и из (18), (19) получаем

где Рх = (1 — /£)/(! + VDТаким образом, приходим к следующе­ му выводу: среди всех многочленов степени я, принимающих при

х = 0 значение	1, наименее	уклоняется		от нуля	на отрезке	[а, Ь]
многочлен
Рп (я) = (— 1)" qncos (п arccos ——					) ,	(20)
где			V	Ь— а
	2РГ	P i;	1 -	VI		(21)
	Qn '■ 1 + р“		1 + V I
		6>а>0.
Корни многочлена (20) расположены в точках
я +	b . b — a	12k ■	1)	k = 1, 2	, . ... я.	(22)
Х к : : — ------------ ------------------- C O S		2п

4. Примеры применения многочленов Чебышева.

П р и м е р 1. В теории интерполирования возникает следую­ щая задача. Рассмотрим многочлен

со (х) = (х—х0) (х X,) ■■■(х—х„)

степени л+1. Требуется так подобрать числа хк (среди которых нет совпадающих чисел), принадлежащие заданному отрезку [а, Ь], чтобы минимизировать величину

шах | со (х) |.

хе[а,Ь]

Поскольку старший коэффициент многочлена со(х) равен 1, для решения данной задачи достаточно потребовать, чтобы со(х) совпал с многочленом Чебышева

.(*) =	(Ь-а)"	cos ((я +		1) arccos	2х — (Ь + а)
	22П+1
(см. (12)). Условие	| со (х) | =	| Т„+1 (х) |		будет	выполнено	тогда и
только тогда, когда совпадут все			корни многочленов			со(х)	и
Тп-н(х). Корнями многочлена		ю(х)	являются числа х0, х,, ...,				х„,
а корни Г„+1(х) определяются согласно (13) формулами
а + Ь		(2k + 1) я		= 0 , 1 , . . . , я.			(23)
2		2 (л+ 1) ’
Таким образом, если задать точки xhпо правилу
.	Ь— а	(2k +	1)я	* =	0, 1, . . . . Я,		(24)
+ 6 -1-------- COS		2 (л + 1)
2				’
							107

то величина отклонения многочлена ш(х) от нуля окажется мини­ мальной и равной

max	®(х) I =	(Ь — а)'1+1
		22/1
jce[a,b]
Заметим, что для минимизации		отклонения многочлена а,(х)
от нуля не обязательно точки хк, k = 0, 1, .... п, располагать в том

порядке, который указан формулами (24). Важно лишь, чтобы

множество точек	о совпало с множеством	{xk)l=o корней мно­
гочлена Чебышева.	Такое множество точек	М }*=0 естественно

назвать оптимальным. Если множество {дга}*=о оптимальное, то любая перестановка его элементов приводит также к оптималь­ ному множеству. Потребуем, например, чтобы выполнялось усло­ вие

а< x ns^.b.

Тогда для оптимальности множества {хк}1=о достаточно положить

Xn—ji, h	0, 1«. • ■t			т. е.
	a + b		b— a		(2k + 1) я		k = 0, 1 , ... ,n .
xh—				-COS
					2 (я+ 1)
П р и м е р		2. При		построении оптимальных итерационных па­
раметров рассматривается следующая задача. Для многочлена
		ММ = (1—тД,) (1—т2Я,) ... (1—■тД)								(25)
подобрать параметры				тЛ> 0, k= \,		2, ...,	п, так, чтобы минимизи­
ровать величину					max \fn(Х)|.
Многочлен		(25)	удовлетворяет условию /п(0) = 1. Поэтому дан­
ная задача решается с помощью многочлена Чебышева									(20). Кор­
ни многочлена (25)			М = tk \		k =	1, 2, ... ,п,
должны совпадать с корнями многочлена
	Рп(Л) =		(— l)rt<7« cos (п arccos 2к — (Yi + Та) '							(26)
где							V2	Vl
			2р”
		qn-			Рх =	i - V T		ъ		(27)
			* + рГ			1 + У1 ’ 5		Та
Согласно		(22)	корни многочлена (26)				расположены		в точках
l k --	Yi + Та- -Г- ---- .—IL cosLUD {2k---					1)я,	k = l , 2 ......... n.			(28)
		2		2		2п
Следовательно, если выбрать
Tk1- -	A + J »		+ .У» - J L		cos(2fe ~ И Д - ,		* =	] , 2 ,		(29)
		2		2		2rc
108

то отклонение /„(X) от нуля окажется минимальным и равным

max | fn (X) | = qn,

XetYi.V*]

где qn определено согласно (27). Здесь остается в силе замечание, сделанное в конце предыдущего примера. А именно, для оптималь­

ности набора параметров {т*.}£=1 не обязательно выбирать т„ со­ гласно (29), достаточно, чтобы множество {т*1} ^ совпадало с множеством {^}£=1 корней многочлена Чебышева (26).

§6. Итерационные методы с чебышевским набором параметров

1.Явный итерационный метод. Рассмотрим систему линейных уравнений

Ax=f

(1)

с симметричной положительно определенной матрицей А. Будем решать эту систему с помощью явного нестационарного итераци­ онного метода

—	+ A x k = f, fe = 0, 1 .........	(2)
	xk+i

где хазадан.

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

т

N 1 = 1/(£ " * ) = 2I	12»
/=i

где х>— /-я координата вектора х.

Точная формулировка и решение задачи оптимизации итераци­ онного метода (2 ) содержатся в следующей теореме.

Т е о р е м а 1. Пусть А — симметричная положительно опреде­ ленная матрица, Ятщ(А) > 0 и Ят»х( ^ ) > 0 — ее наименьшее и наи­ большее собственные значения. Пусть задано число итераций п. Среди методов вида (2 ) наименьшую погрешность \\хп—х\\ имеет метод, для которого

— , * = 1 ,2 ......... я,

(3)

1 + Ро+

где

Ро:

Ятт (А) + W

,	(2* — 1) it	.
tk=	cos —-----------*	k
	2n

1	- 1	g=	^min (А)
i + 5			max И)
			(4)
=	1 , 2 ,	...	,n.
			109

	Е с л и вы брат ь	тк с о г л а с н о		( 3 ) , (4 ), то д л я			п огреш н ост и будет		с п р а ­
	в е д л и в а о ц е н к а		И*п—xlIsS <7Л*о—*11',						(5)
	где
	<7я =		2РГ	PI :	■- V	i	1 =	Кы (*)	(6)
			1 + р Г		i + V i
	Д о к а з а т е л ь с т в о .			Для	погрешности			zk=xk—х получаем
	уравнение
	9 . _ 9 .	+	Azk — 0,	k = 0,	1,	, п — 1,		zQ= x0- х .	(7)
	TJt+i
	Из уравнения (7) получим,что
		zh = (Е—ХнА) (E—Tk-iA) ...					(Е—TtA)z0
	для k = 1, 2 , ...,	п и, в частности,
	где			Zn	Т'п^о,
		Тп — (Е—хпА) (Е—тп- 1А )...(Е —т1А).							(8)
	Поскольку Тп— симметричная матрица, ее норма совпадает с ее
	спектральным радиусом (см. § 6 гл.					1 ) и выполняется оценка
				llzJ^M H zoll,					(9)

где v — максимальное по модулю собственное значение матрицы Тп. Оценка (9) неулучшаема, т. е. найдется вектор г0, для которого она выполняется со знаком равенства. Для доказательства теоремы остается подобрать параметры ти та, .. •, т„ так, чтобы минимизи­

ровать |v | .	пг,— собственные числа матрицы		А. Не
Пусть Яь, k= \, 2, ...,
ограничивая общности, можно считать, что
0<Я т1п(Л) =Я,5СЯ2==С... г$Лт =Яш«04).			(10)
Согласно (8) имеем
| v | = шах | (1 — хЛ) (1 — т2?ч) . . . (1 — tnh) |.			(1 1 )
Очевидно, что
	тах	1М Щ
где fn(K) = (1—х,Я) (1—т2Я) ... (1—тД).
Таким образом, приходим к задаче о нахождении
min	max	| f n (Я) |,
tj,Тг.- . .	Хт;п(Л)^Х^Хтах(Л)

уже рассмотренной в примере 2 из п. 4 § 5. Полученные в этом примере формулы (29) для параметров т* совпадают с формулами (3), (4), а величина отклонения при данных параметрах равна | v | —<7„, где qn определяется согласно (6). Теорема 1 доказана.

по