book1989

2. Обращение матриц. Соотношение (8) представляет собой не­ линейное разностное уравнение первого порядка для матриц. Его решение можно найти в явном виде.

Рассмотрим сначала числовой аналог уравнения (8), а именно разностное уравнение

Ук = у1л — 2,		* =	1,2, ... , у0 — х,	(10)
где х — заданное число.	ук = ук{х) уравнения (10)			выражается
Покажем, что решение
через многочлен Чебышева, а именно
У*(х) = 2	Т	^ ,	* = 1 , 2 , . . . ,	(11)
где		если	| х | -< 1,
cos (n arccos х),
у[(* + Y я2 — 1)п + (ж — /л :2 — 1)п], если				|ж| > 1.

Из выражения для Тп(х) следует, что

Ты {х)=2{Тп{х)Г— \.

Отсюда при п = 2h~l получаем

Ч т 1 = 2	Л-1	I2 — 1,

т. е. функция (11) удовлетворяет уравнению (10). Корнями многочлена (11) являются числа

Xi,k =	о	(2/ — 1)		я	,	,	. 0
	2 cos v		'			t =	1,2,....

Поэтому функция yh(x), представляющая собой многочлен относи­ тельно л; степени 2й со старшим коэффициентом 1, разлагается в произведение

(2/ — 1) я\ 2^+i J ■

Приведенные выше выводы имеют место и для матричного урав­ нения (8). По индукции легко доказывается, что решением См уравнения (8) является многочлен (относительно матрицы С) степени 2к со старшим коэффициентом 1. Для этого многочлена справедливо представление, аналогичное (11), т. е.

С{к) - -2Т ,k

и справедливо разложение на линейные множители

с {к)	(2/ — 1) я сЛ	( )
	2Ш С) ■	12
		421

Наличие такого разложения позволяет упростить процедуру об­ ращения матриц. В случае разностных аппроксимаций уравнений эллиптического типа матрица С является трехдиагональной, в то время как С(к>— матрицы общей структуры. Благодаря разложе­ нию (12) обращение матрицы С{к> сводится к последовательному обращению трехдиагональных матриц

Ck,i = С — 2 cos 121- " * .£,	/=Т, 2,. .., 2fe.	(13)'
Действительно, пусть требуется решить уравнение
С(',)н='ф,		(14)

где

r,k

1=1

Рассмотрим для наглядности сначала случай, когда k = 2. Тогда (14) принимает вид

Сг,16*2,2612,3О24У ф.

(16)

ОбОЗНаЧИМ Но = ф, ^ ^ 2.2^ 2,3^ 2,i^, У2= О^С^У, Уз = С24У, V^ — V. Тогда получим, что решение системы (15) сводится к последова­ тельному решению четырех систем уравнений

0 2дУ4 У0) 2У2 У1) С>21зУз= У2, 0 24U4=H3,

где о0= ф, у4= у.		в общем случае сводится к
Точно так же решение системы (14)
последовательному решению систем уравнений
С*,,у,=	1=1, 2,	. . . , 2\	(16)

где у0= ф, у„* = у. Если матрицы См трехдиагональные, то каждую

из систем (16) можно решить методом прогонки.

Указанный выше способ обращения матрицы С(к) предполагает определенный порядок выполнения промежуточных этапов: снача­ ла надо обратить матрицу СкЛ, затем — матрицу См и т. д. Одна­ ко, поскольку в матрице С{к) все сомножители перестановочны, мож­ но использовать и другие способы введения промежуточных значе­

ний v,, 1=1, 2, . ... 2к—1. Так, систему	(15)	можно записать в виде
2,4С*2,3С2,2 , 1	“ ф
и заменить системой уравнений
02>4У1=' У0) 0 21зУ2= У1> С22Н3= У2,		С2 11-14= Уз,

где и0= ф, у4= у. Теоретически при любом порядке выполнения про­ межуточных этапов мы должны получить одно и то же решение у. Однако, если число промежуточных этапов велико, то при решении систем уравнений (16) на ЭВМ будет происходить накопление по­ грешностей округления. Рост погрешностей округления зависит от порядка выполнения промежуточных этапов. Здесь имеет место

422

примерно та же ситуация, что и в итерационном методе с чебышевским набором параметров (см. п. 2 § 6 гл. 2 ч. II). Поэтому при реальном решении системы (14) рекомендуется обращать внима­ ние на порядок выполнения промежуточных этапов. Более подроб­ но этот вопрос рассмотрен в книге [35].

3. Вычисление правых частей. В методе редукции правые час­

ти F\k~l) уравнения (7) должны удовлетворять соотношению	(9).
Будем искать F f]в виде
F p = C w p P + q P ,	(17)

где векторы рР, qP подлежат определению. Подставляя (17) в (9), получим

,<*) __ £<*-1)	Ak-1)		,	(k-i)	,
c < V ' + qt	Pc-2*-l + ?;_aA-l+
	I	'(*-1) //-(*-1)			(*—!)	. ( 6 - l K		/-1 Я -1 J ( « - И		I JA( -1)
+ L			(C	Pi		+qi	) +	Б	Pc+2k-1 +	9, „*+!•

Отсюда, учитывая, что Cw = (C1*- '1)2—2E, придем к уравнению

<С(А-1))3 (pf>	'*) _о„(И	Д*-1) _ l _		(*—i)	I
	pi*'1’) Цс = <sp;	+ Pi-2*-l +		^/+2fe-l	+		Ak-X)\
		,	/-.(A-l) c №-l)		,	<*—0 ,
		+	L	\Pi—2^ l +		Pi+2k-i +	qi )■

Выберем теперь вектор qP таким, чтобы выполнялось соотно­ шение

	^ = 2		р ?» + «й 2 .1 + о			(18)
Тогда	предыдущее уравнение после умножения на					П р И .
мет вид
	-1)с(А-1) _ П(*-Ч
	С 1	■Jf.	— Р,-аА-1 + Pi+^-l + Qi			(19)
			*
где			=р.(М-Pi(h~ l).
Таким образом, вычисление векторов Fp				можно	заменить	нахож­
дением	векторов p f \	qf’	из системы уравнений (17) — (19). Сначала,
обращая матрицу C(k' l), находим вектор				затем	вычисляем	рр —

— Р?~" + st~1] и затем по формуле (18) вычисляем qp. Правую часть

	Ff~l) уравнения (7) надо заменить согласно (17) выражением
		1L	-- ^	_№-1) ! _(*—и
				^4	“Г ЧС
	Тогда придем к уравнению						20
	ь	г,	— 7,-	+ УL_ 2u-i +		y iV2k -u
							( )
	где tf — ус— р(к 1).	Из	этого	уравнения,		обращая матрицу	С(А11,
	находим /f-0 и затем	вычисляем		yi =	pp'1)~ t f ~ 1]■
							423

4. Формулировка и обсуждение алгоритма. Сформулируем бо­ лее детально алгоритм метода редукции.

Вычисления ведутся в цикле по индексу k. Сначала осуществля­

ется прямой ход, т. е. для	k = \, 2,	т—1 решаются уравнения
£<A-i)s<A-l) .	(ft-l) ч	Ik-D	,№-i)	(21)
	Pi-2*-1 + Pi+2k~l
и находятся векторы
РТ =	pf~l\ +	s r i),
J k )	<y-(k) ,	Ik-1) , Ik-1)

где i= 2\ 2-2\ 3-2\				2т—2к. Вычисления				ведутся, начиная с
k=l, причем при k= 1 задаются начальные значения
	„ ( 0 ) =	О,	До)	■■Ft,	* = 1 , 2 ....... N — \.
Решение	систем (21) сводится, как					это	было		показано в п. 2,
к решению более простых систем уравнений
	Ck-i,i^l,i — Vl-i,it				1= 1,2.......2й ,				(22)
где		»'= 2\ 2 -2\			. , 2т—2\
			_	_(*—1) I	„(*-1)	I	„(*-1)
		,i —		Pi-2k-i i -	рi+2k-i +		<7<	,
		V -		j k - D
				■>[
Системы	(22)	решаются при			фиксированном				I для каждого
i = 2\ 2-2\	. . . , 2т—2\		Поскольку		матрица		Ск1ш1 не зависит от i,

вычисления целесообразно организовать так, чтобы матрица Ск- i,t

обращалась один раз.

Подсчитаем число действий, необходимых для решения всех си­ стем вида (22). Предположим, что для решения системы (22) с фиксированными k, I, i гпебуется q арифметических действий. Тог­ да при фиксированных k, I для решения систем (22) с i = 2\ 2-2\ .. .

. . . ,	2^_2к		арифметических дей-
	2™—2к требуется----------q = (2т~к—1)q
	2k
ствий. При фиксированном k и для		1= 1, 2,	.. ., 2s-1, i= 2 \ 2-2*,
. . . ,	2m—2\ требуется 2к~1(2т~к—\)q={2m~'—2h~l)q действий. На­
конец, для всех k = 1, 2, . . . , т—1 необходимо выполнить
	т- 1	+ (т - 2) 2т~1) q
	(2- 1_ 2*-1) = (1
	k=i

арифметических действий. Самое существенное здесь то, что при больших N число действий является величиной О (qN log2 Лг).

После того как все векторы р)4', <7;е) найдены, осуществляется обратный ход метода редукции, т. е. начиная с k = m решаются

424

	у р а в н ен и я			№-i)	I	_i_	fj .
	Ык-Vf'k-1) _								(23)
	Ь	f i	—	Qi	-+- У (_21г-1 i		t/i+ ik-i
	и вычисляются искомые векторы
			, , _n(*-o I			’
			£/£ — P i		T ‘i
	где fe =m, m—1, .... 1, t'= 2*-‘, 3-2*-1, . . . ,					М -2*-', M = 2m.
	Система (23) при фиксированных i,					k решается, как и ранее,
	путем последовательного решения систем уравнений
	C	k — i ' i W i ' i	— W	i - i i ,	I — 1, 2....... 2			,	(24)
	I= 24- 1, 3-2*-1, 5-2к~\					2т—2к~\
	где wllU= q!{ 0 + y^k-i +		yi+2k-u			4	г)-	Решение	системы

(23) также требует О (qN log2 N) действий.

Рассмотрим применение метода редукции к решению разност­ ного уравнения Пуассона (4), (5) из § 5. Предположим, что сетка содержит N1= 2"1 точек по направлению хх и N2 точек — по х2. Со­

гласно	(9) из § 5, это разностное уравнение можно записать в век­
торном	виде	(1), (2), где N = Nl и С= 2Е2— h\A2— трехдиагональ­
ная матрица		порядка N2—1. Поэтому системы вида (22), (24) ре­

шаются методом прогонки, что требует q= 0(N z) действий. Таким -образом, решение разностного уравнения Пуассона осуществляется методом редукции за число действий 0(N 2Nl \og2Ni). На квадрат­ ной сетке, когда Nt= N2 = N, число действий является величиной О {Nz \og2N), т. е. имеет тот же порядок, что и в методе быстрого дискретного преобразования Фурье. В отличие от последнего, ме­ тод редукции не требует знания собственных функций, что позво­ ляет применять его и в более общих случаях, например в случае краевых условий третьего рода.

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

(1) с постоянной матрицей С. Например, разностные задачи для

уравнения
£ (ki (х, 0) ^	^ (h (х,	(М У)

можно решать методом редукции только в том случае, если коэф­ фициенты ku k2не зависят от х.

СПИСОК ЛИТЕРАТУРЫ

1.	Б а б е н к о	К- И. Основы численного			анализа.— М.:	Наука,	1986.
2.	Б а х в а л о в		Н. С. Численные	методы.— М.: Наука,		1975.
3.	Б а х в а л о в		Н. С., Ж и д к о в	Н. П.,	К о б е л ь к о в	Г. М.	Численные мето­
4.	ды.— М.: Наука, 1987.
	Б е р е з и н	И. С., Ж и д к о в Н. П. Методы вычислений — Ч. I,— М.: Наука,
	1966. То же.— Ч. 2.— Физматгиз, 1962.

5.Б о б к о в В. В., Г о р о д е ц к и й Л. М. Избранные численные методы решения на ЭВМ инженерных и научных задач.— Минск: Изд-во «Университетское», 1985.

6.В о е в о д и н В. В. Вычислительные основы линейной алгебры.— М.: Наука, 1977.

7.В о е в о д и н В. В. Математические модели и методы в параллельных процес­ сах.— М.: Наука, 1986.

8.

В о е в о д и н

В. В., К у з н е ц о в Ю. А. Матрицы и вычисления.— М.: Наука,

1984.

9.

В о л к о в Е. А. Численные методы.— М.: Наука, 1987.

10. Г о д у н о в

С. К. Решение

систем

линейных уравнений.— Новосибирск: Нау­

11.

ка, 1980.

С. К-, Р я б е н ь к и й

В. С. Разностные схемы, введение в тео­

Г о д у н о в

12.

рию.— М.: Наука,

1977.

Э.

Г. Линейная алгебра.— М.: Наука, 1984.

И л ь и н

В.

А.,

П о з н я к

13. И л ь и н В.

П.,

К у з н е ц о в

Ю. И. Трехдиагональные

матрицы и их прило­

14.

жения.— М.:

Наука, 1985.

К а л и т к и н

Н. Н. Численные методы.— М.: Наука, 1978.

15.

К а р п о в

В. Я. Алгоритмический

язык фортран

(фортран — Дубна).— М.:

Наука, 1976.

16.

К р ы л о в

В. И.,

Б о б к о в

В. В.,

М о н а с т ы р и ый

П. И. Вычислительные

методы.— Т. I.— М.: Наука,

1976. То же.— Т. II.— М.:

Наука, 1977.

17.

К р ы л о в

В. И.,

Б о б к о в

В.

В.,

М о н а с т ы р н ы й

П. И. Начала теории

вычислительных методов. Интерполирование и интегрирование.— Минск: На­

ука и техника, 1983.

18.

К р ы л о в

В. И.,

Б о б к о в

В.

В.,

М о н а с т ы р н ы й

П. И. Начала теории

вычислительных

методов.

Дифференциальные

уравнения.— Минск: Наука и

техника, 1982.

19.

Л я ш к о

И. И.,

М а к а р о в

В. Л., С к о р о б о г а т ь к о А. А. Методы вы­

числений.— Киев: Вища школа, 1977.

20. М а к а р о в

В. Л., X л о б ы с т о в

В. В. Сплайн-аппроксимация функций.—

М.: Высшая школа, 1983.

21.

М а р ч у к

Г. И., Методы вычислительной математики.— 3-е изд.— М.: Наука,

1989.

22.

М а р ч у к

Г. И.,

А г о ш к о в В. И. Введение

в проекционно-сеточные мето­

ды.— М.: Наука,

1981.

23.

М а р ч у к Г. И.,

Ш а н д у р о в

В. В. Повышение

точности решений разност­

ных схем.— М.: Наука, 1979.

24.

Н а т а н с о н

И. П. Конструктивная теория функции.— М: Гостехиздат, 1949.

426

25.	О с т р о в ск и й А.		М. Решение			уравнений и систем			уравнений,— М.: ИЛ,
26.	1963.	Ю. В.,		У с т и н о в		С. М., Ч е р н о р у ц к и й И. Г. Численные
	Р а к и т с к и й
27.	методы решения жестких систем.— М.: Наука, 1979.
	Р и х т м а й е р Р., М о р т о н К. Разностные методы решения краевых задач.—
28.	М.: Мир, 1972.	В. С.,		Ф и л и п п о в			А. Ф. Об устойчивости разностных урав­
	Р я б е н ь к и й
29.	нений,— М.: Гостехиздат, 1956.						Г. И. Программирование на языке форт­
	С а л т ы к о в А. И.,		М а к а р е н к о
30.	ран..— М.: Наука, 1976.				в теорию разностных схем.— М.: Наука, 1971.
	С а м а р с к и й	А. А. Введение
31.	С а м а р с к и й	А. А. Введение			в		численные методы.— 2-е изд.— М.: Наука,
	1987.
32.	С а м а р с к и й А. А. Теория разностных схем.— 2-е изд.— М.: Наука, 1983.
■33. С а м а р с к и й		А. А., А н д р е е в				В. Б. Разностные методы для эллиптических
34.	уравнений.— М.: Наука, 1976.				А.		В. Устойчивость		разностных схем.— М.:
	С а м а р с к и й	А.	А.,	Г у л и н
35.	Наука, 1973.	А. А.,		Н и к о л а е в			Е. С. Методы	решения сеточных уравне­
	С а м а р с к и й
36.	ний,— М.: Наука, 1978.				Ю. П. Разностные			методы решения задач га­
	С а м а р с к и й	А. А.,		П о п о в
	зовой динамики.— 2-е изд.— М.: Наука, 1980.

37.Современные численные методы решения обыкновенных дифференциальных уравнений.— М.: Мир, 1979.

38.Т и хо н о в А. Н., А р с е н и н В. Я. Методы решения некорректных задач.—

3-е изд.— М.: Наука, 1986.

39.	Т и х о н о в А. Н., В а с и л ь е в а	А. Б., С в е ш н и к о в А. Г. Дифференциаль­
	ные уравнения.— 2-е изд.— М.: Наука, 1985.
40.	Т и х о н о в А. Н., К о с т о м а р о в Д. П. Вводные лекции по прикладной ма­
	тематике.— М.: Наука, 1984.
41.	Т и х о н о в А. Н., С а м а р с к и й	А. А. Уравнения математической физики.—
	5-е изд.— М.: Наука, 1977.

42.Т р е н о г и н В. А. Функциональный анализ.— М.: Наука, 1980.

43.Т у р ч а к Л. И. Основы численных методов.— М.: Наука, 1987.

44.	У и л к и н с о н Дж . X. Алгебраическая проблема собственных значений.—
	М.: Наука, 1970.
45.	Ф а д д е е в Д. К- Лекции по алгебре.— М.: Наука,	1984.
46.	Ф о р с а й т Дж., М а л ь к о л ь м М., М о у л е р	К. Машинные методы мате­
	матических вычислений.—М.: Мир, 1980.

П Р Е Д М Е Т Н Ы Й У К А З А Т Е Л Ь

Алгоритм быстрого дискретного преоб­ разования Фурье 336

Аппроксимация дифференциального оператора разностным 266

—первого порядка 35

—суммарная 376

Ведущий элемент 53 Вычислительный эксперимент 11

Граница сетки 293 Граничная точка сетки 297

Дискретизация II1

Жесткая система 249

Задача о наилучшем приближении 157

Интегро-интерполяционный метод 262 Интерполирование 127 Интерполяционный многочлен 127

------ Лагранжа 129

------ Ньютона 130

------ обобщенный 151, 156

------ Эрмита 136 Итерационный метод 48

------ верхней релаксации 85

-------двухшаговый явный 208

-------Зейделя 83

---------- нелинейный 212

------ касательных 193 ■------ минимальных невязок 1116

428

Итерационный метод минимальных поправок 116

-------многошаговый 84

------ неявггый 85, 2116

------ Ньютона 193, 210

---------- модифицированный 193

---------- с параметром 202, 2Г1

------ одношаговый 84

------ парабол 85, 494

------ переменных направлений 404

— — Пикара 209

------ попеременно-треугольный 394;

------ релаксации 209

------ стационарный 85, ‘208

------ Стеффенсена 199

------ явный 85, 208

------ Якоби 82

---------- нелинейный 212

Каноническая форма одношагового итерационного метода 84

------ разностного уравнения 293

------ разностной схемы двуслойной 349

-------------- трехслойной 363 Квадратурная формула 1161

------ Гаусса 180

-------интерполяционного типа 173

------ Ньютона — Котеса 178

------ парабол 165

------ прямоугольников 162, 163

------ составная 179

------ трапеций 164

------ Эрмита 185 Корректность операторных уравнений

342

—разностной схемы 290

—численного метода 15

Мантисса числа 116 Матрица верхняя треугольная 51

— нижняя треугольная 51

Матрица перехода 91

—плохо обусловленная 76 Машинный нуль 17

—эпсилон 49

Метод Адамса 231

—баланса 262

—бисекции 191

—гармоник 275

—Гаусса 51

-------с выбором главного элемента 61

—интегро-интерполяционный 262

—матричной прогонки 4111

—последовательных приближений 48

—прогонки 45

—простой итерации 85

—разностный 217

—Ричардсона 85

—Ромберга 172

—Рунге 168

—Рунге — Кутта 217

—Эйлера 245

неявный 249

—Эйткена ускорения сходимости 198

—экстраполяции 167, 172

Модель математическая 11 Невязка 43, 1116, 215, 231 Норма матрицы 75

— энергетическая 317

Область устойчивости 253 Округление 18

Оператор второй разностной производ­ ной 311

—левой разностной производной 348

—монотонный 304

—перехода разностной схемы 35а

—положительный 315

—правой разностной производной 348

Погрешность абсолютная 76

— аппроксимации 35, 43, 231

------ на решении 44, 215, 268, 275, 289

—вычислительная 14

—дискретизации 13

—интерполирования 132

—итерационного метода 87

—метода 215

—неустранимая 113

—округления 13, 14

—относительная ,18, 76

—разностной схемы 274, 289

—экстраполирования 133 Позиционная система счисления 16

Порядок аппроксимации 44, 216, 289

— точности 44

------ разностного метода 215, 268, 290

Порядок числа 16 Принцип максимума 296

Пространство сеточных функций 287

Разделенная разность 129 Разностная краевая задача 37

— схема 13, 37, 217, 262, 287

------ абсолютно устойчивая 276

------ асимптотически устойчивая 328

------ двуслойная 349

------ консервативная 115

------ локально-одномерная 377

------ монотонная 304

------ неустойчивая 276

------ повышенного порядка аппроксима­ ции 278

-------продольно-поперечная 372

------ с весами 277, 321

------ трехслойная 283, 362

--условно устойчивая 276

—— чисто неявная 276

------ шестпточечная симметричная 277

------ явная 274

—формула Грина 263 Разностный метод 34

------ абсолютно устойчивый 249

------ многошаговый 230

------ условно устойчивый 249

------ чисто не явный 255

------ .4-устойчивый 254

------ / (а.) -устойчивый 255

—оператор Лапласа 261 Разряд числа 16

Сетка 15, 34, 286

—на отрезке 134

—равномерная 34, 215

—разрядная 17

—связная 295

Сеточная функция 34, 215, 286 Слой 273

Скорость сходимости итерационного метода 96

Сплайн 141 Сходимость птерполяцпонного процес­

са 135

—квадратичная 1193

—при т—>-0 215

—разностной схемы 286, 290

Теорема сравнения 298

Узел внутрепнпн 273

Узел граничный 273

—интерполирования 127

—кратный 136

—сетки 34, 273

Устойчивость коэффициентная 74

— разностной схемы 290, 342, 351

-----------ио начальным данным 240, 352

----------- по правой части 352

Формула суммирования по частям 39, 269

Функция мажорантная 299

Характеристическое уравнение 26, 234

Число жесткости 250

—обусловленности 76

—с плавающей запятой 16

—с фиксированной запятой 16

Шаблон разностного оператора 261 Шаг сетки 34, 286