Boyarshinov_ChM_T1

Для установления условий сходимости определим величину погрешности метода формулой z(n) x(n) x, тогда из формулы (2.13) для стационарного итерационного метода можно получить

B z(n 1)	x z(n) x Az(n) Ax f ,
Bz(n 1) z(n)		Az(n) 0,	n 01,,...	(2.14)

Теорема 2.4. Пусть А - симметричная положительно определенная матрица, A > 0;

итерационные параметры удовлетворяют соотношению

B 05, A 0,

0.

Тогда стационарный итерационный метод сходится.

Доказательство. Для доказательства теоремы следует показать, что погрешность

метода z(n) 0 при любой начальной погрешности z0 .

n

Построим числовую последовательность вида Jn Az(n),z(n) .

Из формулы (2.14) следует

	z(n 1) z(n) B 1Az(n),
	Az(n 1)	Az(n) AB 1Az(n) .
Теперь можно подсчитать
Jn 1 Az(n 1),z(n 1) Az(n) AB 1Az(n) , z(n) B 1Az(n)
Az(n),z(n) AB 1Az(n) , z(n) Az(n) , B 1Az(n) 2 AB 1Az(n) , B 1Az(n) .
	Вследствие симметрии матрицы А имеем
m	m m m
AB 1Az(n) , z(n) ai jb j		1kak t z(tn) z(in);
i 1	j 1 k 1 t 1	m m m m
m	m m m

Az(n) ,

B 1Az(n) ap q zq(n)bp1rar

sz(sn)

a j ib j

1kak t z(tn) z(in),

a j i

ai j.

p 1 q 1 r 1 s 1

j 1 i 1 k 1 t 1

Иначе говоря, AB 1Az(n)

, z(n) Az(n) , B 1Az(n) . Отсюда получаем

Jn 1 Az(n),z(n) 2 Az(n) , B 1Az(n) 2 AB 1Az(n) , B 1Az(n)

Jn 2 Az

(n)

2

AB

1

Az

(n)

, B

1

Az

(n)

Jn

1

Az

(n)

, B

1

Az

(n)

2 B

A B

2

Jn

(n)

, u

(n)

(n)

B

1

Az

(n)

.

2 B

A u

, u

2

51

			(n)	, u	(n)	0	u	(n)	, откуда следует, что	Jn 1 Jn
В силуусловия теоремы B	2	A u

, то есть построенная последовательность является монотонно убывающей и, кроме того, в

силу Jn 1 Az(n 1),z(n 1) 0, ограничена снизу. Отсюда следует, что существует предел

этой последовательности J limJn .

n

Из положительной определенности (B - 0,5 A) > 0 следует существование константы

>0 такой, что имеет место

1

(n)

, B

1

Az

(n)

1

Az

(n)

2

B

A B

Az

B

.

2

Теперь предыдущее соотношение может быть переписано в форме неравенства:

1

Az

(n)

, B

1

(n)

1

Az

(n)

2

Jn 1 Jn 2 B

2

A B

Az

Jn 2 B

.

При n

из последнего выражения получаем J J 2 lim

B

1

(n) 2

Az

. Очевидно, что

n

неравенство lim

B

1

(n)

2

Az

0 может выполняться лишь при условии, что

n

lim

B 1Az(n)

lim

u(n)

0.

n

n

С другой

стороны,

z(n)

A 1Bu(n) ,

причем

A 1 существует в

силу положительной

определенности матрицы А по условию теоремы. Оценим норму погрешности:

z(n)

A 1Bu(n)

A 1B u(n) .

Теперь

становится

очевидным,

что

вследствие

lim

u(n)

0

имеет место

n

z(n) 0

, что и требовалось доказать.

n

Следствие 1. Пусть

А -

симметричная положительно определенная матрица. Тогда

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

D wA1

x(n 1) x(n)

Ax(n) f,

w 0

w

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

В рассматриваемом случае, очевидно, B D wA1, w .

Ax,x A1 D A2 x,x A1x,x Dx,x A2x,x Dx,x 2 A1x,x .

Последнее соотношение справедливо в силу симметрии матрицы А:

m	m	m
A1x,x a(1)i jxjxi	a(2)jixjxi	a(2)jixixj A2x,x .
i,j 1	i,j 1	i,j 1

52

Условие сходимости итерационного метода B 05, A 0,

0 теоремы 2.4 принимает

вид:

w

w

Ax,x

Dx,x w A

w

Dx,x 2 A

x,x

B

A x,x Bx,x

2

x,x

2

1

2

1

Dx,x w A1x,x

w

Dx,x w A

w

2

1x,x 1

Dx,x 0.

2

Очевидно, что последнее неравенство выполняется при условии 1 w 0,

0 w 2.

2

Следствие 2. Пусть А - симметричная положительно определенная матрица с диагональным преобладанием, то есть имеет место

ai i ai j ,	i, j 1,m.
i j

Тогда метод Якоби сходится.

Поскольку в рассматриваемом случае B = D, условие сходимости принимает вид неравенства

2D A .

Из неравенств

xi xj 2	xi2 2xixj x2j 0,		xixj		1	x2i	x2j
					2
		следует
m	m	m		1	m			1	m
Ax,x aijxixj	1 aij	x2i 1 aij	x2j		aij x2i				a ji x2i .
i,j 1	2i,j 1	2i,j 1		2i,j 1				2i,j 1

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

m	m		aij	aii
Ax,x aij x2i					x2i .
i,j 1	i 1		j i

Используя предположение следствия, запишем

2ai i ai j	aii,	i 1,m .
i j

Из двух последних неравенств получаем

m

Ax,x 2 aiix2i 2 Dx,x ,

i 1

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

53

Скорость сходимости

Ранее утверждалось, что если итерационный метод в некотором смысле сходится, то он сходится к решению исходной задачи (2.1). Понятно, что быстрота достижения результата существенно зависит от того, насколько удачно (“близко” к решению) выбрано начальное приближение. В общем случае условия сходимости итерационного метода решения системы линейных алгебраических уравнений определяются следующей теоремой,

доказательство которой можно найти, например, в книге [1].

Теорема 2.5. Итерационный метод

Bx(n 1)	x(n)	Ax(n) f,	n 01,,...

сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы E B 1A по модулю меньше единицы.

При практическом использовании итерационных методов важен не только сам факт сходимости последовательности получаемых решений, но и скорость, с которой эта последовательность сходится к точному результату. Если для погрешности используемого

метода имеет место оценка вида
x n	x	qn	x 0	x ,	n 0,1, ,

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

Зададим произвольное число k>0 и потребуем, чтобы после выполнения N итераций

начальная погрешность уменьшилась не менее, чем в k раз, то есть x n				x	1	x 0	x .
Это имеет место в случае qN 1					k
	, откуда получаем
k
	ln k		.
	N ln 1 q

Целая часть этой дроби будет минимальным числом итераций, необходимым для достижения заданной точности. Выражение ln 1q называется скоростью сходимости

итерационного метода. Эта скорость целиком определяется свойствами матрицы перехода

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

54

Полиномы Чебышёва13

Для дальнейшего рассмотрения определим, согласно [8], норму

f max f(x),

x a,b

называемую чебышёвской.

Рассмотрим задачу: среди всех полиномов степени N со старшим коэффициентом,

равным 1, найти такой многочлен TN (x), для которого величина TN maxTN (x)

x 11,

минимальна. Такой многочлен носит название полинома Чебышёва.

Расмотрим функцию

PN (x) cos N arccos x .

(2.15)

Произведем тригонометрические преобразования:

PN 1(x) cos N 1 arccos x cos N arccos x arccos x

cos N arccos x cos arccos x sin N arccos x sin arccos x

xPN x sin N arccos x sin arccos x ;

PN 1(x) cos N 1 arccos x cos N arccos x arccos x

cos N arccos x cos arccos x sin N arccos x sin arccos x

xPN x sin N arccos x sin arccos x .

Складывая почленно два последних равенства, PN 1 PN 1 2xPN,

PN 1 2xPN PN 1,

получаем рекуррентное соотношение для построения функции PN 1. В соответствии с формулой (2.15)

P0(x) cos 0 arccos x 1;

P1(x) cos 1 arccos x x.

И далее, в соответствии с полученной зависимостью

13 Чебышёв Пафнутий Львович [4.5.1821 - 26.11.1894]. В 1841 году закончил Московский университет и там же в 1846 году защитил магистерскую диссертацию. В 1847 году подготовил и защитил диссертацию на право чтения лекций и был утвержден в звании доцента Петербургского университета. В 1849 году защитил докторскую диссертацию; в 1850 году стал профессором Петербургского университета. С 1856 года являлся академиком Петербургской академии наук.

55

		P2 x 2xP1 x P0 x 2x2			1;
		P3 x 2xP2 x P1 x 4x3			3x;
		P4 x 2xP3 x P2 x 8x4			8x2 1;
		P5 x 2xP4 x P3 x 16x5 20x3 5x
На рис. 2.4 показаны некоторые полиномы построенной системы.
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-1	-0.75	-0.5	-0.25	0	0.25	0.5	0.75	1
		Рис. 2.4. Полиномы TN(x) при N= 2, 3, 4, 5, 6

Можно заметить, что в общем случае коэффициент при старшей степени определяется следующим образом:

PN x 2xPN 1 x PN 2 x 2N 1xN	(2.16)
Определим функцию TN (x) в виде
TN (x) 21 N PN (x) 21 N cos N arccos x .	(2.17)

Очевидно, что TN (x) является полиномом степени N со старшим коэффициентом,

равным 1.

Определим корни этого полинома:

56

QN (xp )

cos N arccos x 0,
N arccos x 2k 1 ,	k 1, 2,

2

Поскольку TN (x) является полиномом степени N, он имеет не более N корней,

причем все они различны и лежат на отрезке [-1, 1]:

		xk		cos 2k 1 ,		k 1,N .
				2 N
		Корни полинома TN (x) для N=1, 2, 3, 4, 5, 6 и 7						Таблица 2.4
N=1	N=2	N=3		N=4		N=5	N=6	N=7
0	0,707106781	0,866025404		0,923879533	0,951056516		0,965925826	0,974927912
-	-0,70710678	0		0,382683432	0,587785252		0,707106781	0,781831482
-	-	-0,866025404		-0,382683432	0		0,258819045	0,433883739
-	-	-		-0,923879533	-0,587785252		-0,258819045	0
-	-	-		-	-0,951056516		-0,707106781	-0,433883739
-	-	-		-		-	-0,965925826	-0,781831482
-	-	-		-		-	-	-0,974927912

Вполне очевидно (рис. 2.4), что полиномы TN (x)

принимают экстремальные значения

в тех точках, где функция cos( )

принимает значения +1 или -1.

cos N arccos xp 1;

N arccos xp p ;

xp cos p ,

p 0,N.

N

В

этих

точках

полином

TN (x) принимает

чередующиеся

по знаку значения

T (x

)

1

P

1 N

,

p 0,N; при этом чебышёвская норма равна

T

1 N

.

p

2

2

N

N

Лемма 2.2. Пусть существует система точек 1 xN xN 1 x1 x0 1 такая, что

QN (xp)QN , p 0,N , причем в указанных точках функция имеет

чередующиеся знаки. Тогда среди всех полиномов степени N со старшим коэффициентом,

равным 1, многочлен QN (x) наименее уклоняется от 0.

57

Доказательство.

Пусть

существует

полином

SN (x)

степени

N

со

старшим

коэффициентом 1 (рис. 2.5), причем

SN QN ,

то есть SN (x) QN

x [ 11,].

Построим

функцию

R(x) QN (x) SN (x),

отличную

от

нуля

и

являющуюся

полиномом степени (N-1).

0.1

0.05

0

-0.05

-0.1

-1

-0.5

0

0.5

1

Рис. 2.5. Графики полиномов Q5(x), S5(x)

и их разности R(x) Q5(x) S5(x)

В точках экстремумов xp

имеем

Q

N

(x

p

)

1 p

Q

N

,

p 0,N .

Тогда

R(x

p

)

Q

N

S

N

(x

p

), p 0,N и в силу предположения функция R(x)

1 p

на отрезке [-1, 1] меняет знак

N

раз, а значит имеет N

корней,

чего не может быть,

поскольку R(x) является полиномом степени (N-1).

Таким образом, утверждение леммы 2.2 доказано.

Поскольку

построенный

ранее

полином Чебышёва

TN (x)

удовлетворяет всем

требованиям леммы, он является наименее уклоняющимся от нуля на отрезке [-1, 1].

В случае необходимости отыскания полинома, наименее уклоняющегося от нуля на произвольном отрезке [a, b], следует перейти к новой переменной

58

t 2	x b a ,	a x b ,
b a	b a

которая теперь принимает значение t 11, .

В этом случае функция PN(x) принимает вид:

1 N

2x (b a)

PN (x) 2

cos N arccos

b a

.

Формула (2.16) представляется в виде:

PN x 2xPN 1 x PN 2 x 2

N 1 2x (b a) N

22N 1

N x

N

b a

b a

Теперь можно получить полином со старшим коэффициентом 1, то есть полином

Чебышёва для отрезка [a, b]:

b a N

2x (b a)

(2.18)

TN (x)

cos N arccos

b a

.

22N 1

Корни этого многочлена определяются аналогично рассмотренному выше случаю:

2x (b a)

0,

cos N arccos

b a

arccos2x (b a)

2k 1

k 1,N,

,

b a

2 N

2k 1

k 1,N.

xk b a b a cos

,

2

2

2 N

Очевидно, что в этом случае TN

max TN x

b a N

2N 1 .

x a,b

2

Может рассматриваться еще одна задача: найти многочлен степени N, наименее уклоняющийся от нуля на отрезке [a, b] среди многочленов, удовлетворяющих условию

QN (0) 1.

Перенормируем полином (2.18) так, чтобы TN (0) 1,

2x (b a)

PN x

cos N arccos

2x (b a)

b a

,

TN (x)

pN cos N arccos

P

0

a b

b a

N

cos N arccos

a b

pN

1

где

a b .

cos N arccos

a b

59

Корни этого многочлена расположены в точках
			xk b a b a cos						2k 1			,	k 1,N .
						2	2		2N
Введем обозначения:
						a ,	0 1 b a						;
						b		1		b a
Рассмотрим соотношения:
y arccos(z) ;
cos y z - нечетная функция;
cos 2y 2cos2 y 1 2z2						1 - четная функция;
cos 3y cos y 4cos2 y 3 4z3							3z - нечетная функция;
cos 4y 2 2cos2 y 1 2					1 2 2z2 1 2			1 - четная функция;
...
				N							N 1				2			N			2		N
			1						1			2		z z		1				z	z 1
cos N arccos z						cos N arccos z
Положим z 1		, тогда
	0
			z z2 1 1						1	1		1
												1		,
							0		02
			z z2 1 1						1	1 1 .
							0		02			1

1

Вводя обозначение 1 1 , представим определенный выше коэффициент в виде

					N	2 N
p				1		1
						1 2N .
	N
						1

Теперь очевидно, что построенный полином принимает экстремальные значения,

равные

2 N TN maxTN x 1 12N .

x a,b

1

Итерационный метод с чебышёвским набором параметров

60