book1989

данном начальном значении z0. Ясно, что решение задачи Коши для разностного уравнения (13) существует и единственно.

Коэффициенты qh правые части <р,- и искомое решение zs урав­ нения (13) можно рассматривать как функции целочисленного ар­ гумента /', т. е. q,= q{j), Ф; = ф ( / ) , 2 , = 2 ( / ) .

Нам потребуется прежде всего записать решение уравнения (13) в явном виде. Подставляя в (13) вместо zs-i выражение

Zj_1=qs- i2j_2+(pj-i,

получим

zi= 4iQj - iz i-2 + + i-

Теперь можно подставить сюда выражение для zH2, затем —для з и т. д. В результате получим формулу, в которой z, выражается

через Zj-h <pj_1+1, <pj-i+2, . . . , cpj. Эта формула имеет вид

I

г,- = QjtZj-t - f ^	Q/.М Ф*. 1 =		1, 2, . . ., / — 1, /,
*=/-/+1						(14)
где
		1= 0,
	1,			<		(15)
	QiQi-1 • • • Qi-iн>
Строго доказать формулу (14) можно				индукцией по числу /		при
каждом фиксированном I.		Нам	потребуется		формула (14)	при
l=j, т. е.
2/ — Qifiо "К 2		Qi.f-k^k,		/ = 1,2, . . .,п,		(16)
где согласно (15)	*=i
	1,	А = /,
Ql.i-k =						(17)
	QiQi-i ■• ■9ь+1,
В частности, если	(13) является уравнением с постоянными ко­
эффициентами, т. е. qj=q для всех /, то из (16) получим
2/ = Q'z0 + 2		1	/ = 1,2,		. . ., п.	(18)

Явную формулу (16) можно использовать для получения раз­ личных оценок решения z} через начальные данные z„, заданные

коэффициенты qs и правые части ср,.	выполнены неравенства
Л е м м а 1. Если для некоторого q ^O
/ =1, 2, . . . , «,		(19)
то для решения уравнения (13) справедливы оценки
| z / K ‘7/ l*ol + 2 9М |Ф*1. / =	1,2, ... ,п.	(20)
k = \
		21

Д о к а з а т е л ь с т в о . Из (17)	и (19) получаем, что
\Q ij-h\< q,~h,	£=0,1
Отсюда п из (16) следуют оценки (20).
З а м е ч а н и е . Оценки (20) неулучшаемы в том смысле,		что	для	уравнения
(13) с постоянными коэффициентами и	положительными го,	<>/„	k = \ ,	2,	J,

неравенства (20) выполняются согласно (18) со знаком равенства.

5. Оценки погрешностей округления. Приведем примеры оценок погрешностей округления, возникающих в результате выполнения вычислительных алгоритмов. Нас будет интересовать в основном зависимость результирующей погрешности от числа арифметиче­ ских действий п и от величины е=2"', определяемой разрядностью ЭВМ.

П р и м е р 1. Вычисление произведения

П

2п = П У!

1=1

п вещественных чисел проводится по формуле
Ъ=У&-и /= 1,2,. .. , л, z„=l.	(21)

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

чения	получено приближенное		значение Zj_,. Тогда согласно
(7) вместо yjZj-i получим величину
	^	i ) У	( 1 Т" 6 j ) ,

где |е,-|^е= 2~ ‘. Таким образом, вместо г, получаем

Zj= (1	-Т е;-)«/А --|,
т. е. приближенное значение zj	удовлетворяет рекуррентному соот­
ношению	2,	г0=1,	(22)
21 = у&-1, /=1,

где У] = Уз{1+е3). Результирующая погрешность равна

ПП

2п —~п = П У! — Я 0 + е/) уи

/=1	/=1
поэтому относительная погрешность есть
A Z I n = , _ - f [ ( i +		e.).
2;i	1=1
Для оценки относительной	погрешности заметим, что
I 1+ ei| ^ 1+ Щ	/=1,2,	е=2- ',

поэтому с точностью до величин второго порядка малости относи­ тельно е можно считать, что

-::ф пг = п2~‘.

(23)

22

При выводе оценки (23) предполагалось, что е=2- ', т. е. при перемножении не возникает чисел, меньших машинного нуля или больших машинной бесконечности. Однако может оказаться, что на каком-то этапе вычислений в качестве промежуточного резуль­ тата будет получен либо машинный нуль М0, либо машинная бес­ конечность М„. Поскольку оба указанных случая приводят к не­ верному окончательному результату, необходимо видоизменить вы­ числительный алгоритм. Оказывается, что здесь существенным яв­ ляется порядок действий.

Пусть, например, Л10= 2~р и М„=2Р при некотором р > 0. Пред­

положим,	что надо перемножить	пять чисел	(/,=2р/2,	у1=2рП,
у3= 23р/\ yi=2~p/1, у5=2~3р/,\ Каждое		из этих чисел и их		произве­
дение 2р/4	принадлежат допустимому диапазону		чисел	(М0,М Х).

Однако произведение у1у2Уз=231,/2>.М„, поэтому при указанном по­ рядке действий дальнейшее выполнение алгоритма становится не­ возможным. Если проводить вычисление в порядке уъу^УзУзУи то получим у5У4= 2 ~5р/4<М 0, следовательно, fl(t/5y4)=0 и все произ­ ведение окажется равным нулю, т. е. получим неверный результат.

В данном примере к верному	результату приводит вычисление
произведения в порядке
УьУгУ^кУг.
В случае произвольного числа п сомножителей можно предложить следую­
щий алгоритм вычисления произведения	(см. [6]). Предположим, что
Ы < Ы <	... <|«/п|,
причем |i/[|^ 1 , |j / n |^ l . Будем сначала проводить умножение в порядке

УШпУп-\. . . до тех пор, пока впервые не получим число, большее единицы. За­

тем полученное частичное произведение будем последовательно умножать на Уъ Уз и т. д. до тех пор, пока новое частичное произведение не станет меньше

единицы. Процесс повторяется до тех пор, пока все оставшиеся сомножители будут либо только большими единицы по модулю, либо только меньшими. Далее умножение проводится в произвольном порядке.

П р и м е р 2. Рассмотрим процесс вычисления суммы
гп= у1+У2+ . ■■+ Уп.	(24)

Для простоты изложения предположим, что все yi положительны и больше машинного нуля. Тогда в процессе вычислений не может появиться нулевого результата. Алгоритм вычисления суммы (24) состоит в решении разностного уравнения (10) при начальном зна­ чении z0= 0.

Получим уравнение, которому удовлетворяет приближенное оешение z}. Предположим, что вместо точного значения z,-_, в ре­ зультате накопления погрешностей округления получено прибли­ женное значение z,_,. Тогда согласно (7) вместо z} получим число

Z =fl (Zj-i + tjj) = (1+6j) {Zj-i + y,) ,

где | е,| г^2-‘.

Таким образом, приближенное значение 2,- удовлетворяет раз­

ностному уравнению
Zj^qjZj-i + yu /= 1, 2........«,	z0 = 0,	(25)
		23

где Qj—1 —| ej, ]ji= (1 + £j) уу Можно считать, что уравнение (25) по­ лучено из исходного уравнения (10) путем внесения возмущений в коэффициенты и в правые части, причем для каждого j возму­ щение пропорционально г, и не превосходит 2~‘.

Оценим теперь результирующую погрешность zn—zn. Для этого выпишем в явном виде решения уравнений (10) и (25), предпола­ гая, что г0=20=0. Согласно (16), (18) имеем

ПЛ

: : 2 Ук1

2 0.п.,п—кУк,

k=i k=i

где yk=qhyk. Поэтому для погрешности получим следующее выра­ жение:

п
гп— =	(26)
к=1
где
Епк — qkQn,n-k 1— Чп — U k = n,	Л=1, 2, .. .,п — 1.
УпЧп-1 ■■■Як rtfk 1,
	(27)

Коэффициент Enh в формуле (26) указывает, какую долю по­ грешности вносит k-e слагаемое суммы (24) в общую погрешность. Покажем, что чем меньше номер £, тем большая погрешность вно­ сится за счет ук. Для этого оценим приближенно величины Епк.

Так как q ^ l + Ej и |е;| < е= 2~ ‘, то \qn\ =^1+е, \qnq„-i. . . qk+iqk\ < ^ (1 + е)п_м‘1. Отбрасывая величины второго порядка малости от­ носительно е, можно считать, что

| qnqn-t ■. ■qk\ =^1+ (n-k+ 1)е,

и тогда

\Enh\^ ( n - k + l) e ,

k= \, 2,. .. , п.

(28)

Из формулы (26) легко получить оценку относительной погреш­ ности \zn—zn\!\zn\. Заметим сначала, что для положительных Уи.-.,Уп последовательность zh определенная согласно (10), не­ отрицательная и монотонно возрастающая, т. е.

£ = 1,2

Поэтому для yk=zk—zk-i справедливо неравенство

|2*| + |гА_,| < 2 |z „ |,

£=1, 2, ..., п.

Отсюда и из (26) получим оценку

| гл -'<! | ^ 2 \zn| ^ | Е ^

k = i

Учитывая приближенное неравенство (28), приходим к следующей

24

оценке относительной погрешности:

sgC гп (п +1),

е = 2 \

Следовательно, относительная погрешность, возникающая при суммировании п положительных чисел, оценивается примерно как п22 ', где I —число разрядов, отводимое для записи мантиссы. На­ пример, при 2- ‘ = 10-12, л=103 получаем, что результирующая от­ носительная погрешность не превзойдет 10_б.

§3. Разностные уравнения второго порядка

1.Задача Коши и краевые задачи для разностных уравнений.

Вп. 4 § 2 рассматривалась задача Коши для разностного уравне­ ния первого порядка. Обратимся теперь к линейным разностным

уравнениям второго порядка

ял/j-i—C4/i+Mi+i = —/ь

(О

где a,, b., си fj —заданные коэффициенты и правая часть и у; —ис­ комое решение. Индекс / в уравнении (1) пробегает некоторое до­ пустимое множество / целых чисел. Например,

/ = { 0 , 1 , 2 , . . . } ,	/ = {1, 2,. . . , А/— 1},	/ = { 0 , ±1, ±2, . . .},
где Л’> 1 —заданное	целое число. Всюду	в дальнейшем будем

предполагать, что Ь,Ф0, а$Ф0 для всех допустимых /. Коэффициенты, правую часть и решение уравнения (1) следует

рассматривать как функции целочисленного аргумента / е / , т. е.

i/i=y(i), fi=f(j) и т. д.

Уравнение (1) имеет бесконечное множество решений. Каждое отдельное решение называется частным решением уравнения (1). Общим решением уравнения (1) называется такое двухпарамет­ рическое семейство решений, которое содержит любое частное ре­ шение. В пп. 3, 4 будет показано, каким образом строится общее решение уравнения (1).

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

Задача Коши состоит в отыскании решения уи / =0, 1, 2, . . . , уравнения (1), удовлетворяющего при /=0, 1 заданным начальным условиям

	Уо= Р-1>	У1= Ц2-		(2)
Если ЬФ0 для всех допустимых /, то уравнение (1)				можно раз­
решить относительно z/j+1, т. е. записать в виде
Уi+i=	т~У/-1	~т~ Vi	т~ •	О)
	Ь,	bf	ь,

Отсюда следует, что задача Коши имеет единственное решение.

25

Более общая постановка			задачи Коши состоит в отыскании при				всех ; = 0,
± 1 , ±	2 , . . . решения	уравнения (1),		удовлетворяющего		условиям	{/;в =Цч»
i/j0+i =	|X2 с заданными	/о, pi,	щ. Если	flj¥=0,	О для всех	/, то такая задача
имеет единственное решение.

Краевая задача состоит в отыскании решения уравнения
а ^ _ ,- с ^ + Ь ^ +1= - / я /= 1,2,. . . , ЛГ-1,	(4)
удовлетворяющего дополнительным условиям
У о = И 1У 1+ Р и yx-= *2.y.V-, + P2,	(5)

где Xi, р„ 1=1, 2 —заданные числа. В частности, при х1= х 2=0 по­ лучаем краевые условия первого рода

Уо = У 1 , У х = Цг,

(6)

а при х1= х 2=1 — краевые условия второго рода. Достаточные ус­ ловия существования единственного решения краевой задачи (4), (5), а также алгоритм построения этого решения будут указаны

вп. 7 § 4.

2.Однородное разностное уравнение второго порядка с посто­ янными коэффициентами. Рассмотрим разностное уравнение

аУ)-1-су^Ьуш =0, а¥=О, Ь¥=0,	(7)
с вещественными коэффициентами а, Ь, с, не зависящими от /.
Будем искать частные решения уравнения (7) в виде
yi=y\	(8)
где q — число, подлежащее определению. Подставляя (8) в	(7),
получим квадратное уравнение
bq2—cq + a=Q,	(9)

которое называется характеристическим уравнением, соответст­ вующим разностному уравнению (7).

В зависимости от знака дискриминанта сг—4ab могут предста­ виться три различных случая. Если c2>4ab, то корни

с + Y <?— 4ab	с V сг — АаЬ		(10)
4 i =	Ц г = ~	~2Ъ
2Ь

уравнения (9) вещественны и различны. В этом случае разностное уравнение (7) имеет частные решения

,,(1)	_ J	„(2) _ 1	/.1
У!	— Чи	Уi — Чг-	( ‘ I)

Если c2<4ab, то корни щ и q2 комплексно сопряжены. Функции (11) и в этом случае являются решениями разностного уравнения (7), однако удобнее представить qt в тригонометрической форме: q{ = r (cos ф+ t sin ф), где

V АаЬ — с	cos ф =	с	(12)
г		2 V ai>
2 |/~аЬ ’			'

26

В качестве решений уравнения (7) можно взять функции

У/1’ = r>cos (/ер), y f = r>sin (/ф).

Наконец, если c2=4ab, то уравнение (9) имеет кратный корень q=c/(2b), а разностное уравнение имеет частные решения

уУ = я', У?] = ]<]'■

О 3)

Построим теперь решение задачи Коши

ау;--су;+Ьу^1=0, / = 1 , 2, ... ,		(14)
У<i= P i,	Уi = p 2,	(15)

исходя из найденных частных решений (11). В силу линейности и однородности уравнения (7) любая линейная комбинация

У/ — aiQi +

(16)

также является его решением. Подберем параметры а 4 и а 2 таким образом, чтобы удовлетворялись начальные условия (15):

а . + а 2=Pi,				+ а 2<72= Ц 2.	(17)
Решая систему (17), находим
„ __	Мт<7г — Иг	,	„	__Иг — Pi7i	(18)
ULj--	----------<?2 — 7i		1*2	------------?2 — <71

Подставляя (18) в (16) и собирая коэффициенты при ц,, р2, по­ лучим, что решение задачи Коши (14), (15) в случае сг>4аЬ имеет вид

У / =	<7 I <72 М	г)	.	.	0	(19)
	---------:— :-----------		Pi +	:— — Рг. / — 0 . 1 >2,
	<72 — <71			<72 — <7i

где у,,2 определены согласно (10).

Втаком же виде представляется и решение задачи Коши (14),

(15)в случае c2<i4ab. Заметим, что в этом случае

<7г?2 (д[	1 — 7' *)	г / s i n ( ( / — 1) ф)
72	— 71	s i n ср

_	r/_! sin (/ф)
q 2 — <h	s in ф ’

где г и ф определены согласно (12). Поэтому решение задачи Коши можно записать в виде

у, = - ri .sirli.O' —Л ф) Fi +	г/-1 sinj №). и	(20)
sin ф	sin ф

В случае c2=4ab, используя частные решения (13), можно пред­ ставить решение задачи Коши (14), (15) в виде

У ;= -(/-1)Ф р1+ /У “1Р2,

(21)

где q=c/{2b).

27

Аналогичным образом строится решение краевой задачи
Щ-1—суз+Ьуш = 0,	/=	1,	2,	N— 1,	(22)
УО М-1»	УN	2•			(23)
Если с2=£АаЬ, то
yi = -------- 7,-----7,--------^		+		я * - д [	(24)
				Рг>
л-
где quz определены согласно (10).
Если же c2—4ab, то
У/ = f 1— ~ ) ?Vi + ~			Г (АЧ'%,		(25)

где q=cj(2b).

3. Однородное разностное уравнение второго порядка с пере­ менными коэффициентами. Для уравнения с переменными коэф­ фициентами (1) существует теория, аналогичная теории линейных дифференциальных уравнений, а именно: общее решение одно­ родного уравнения

a^j-x—С;1/Д53'1/,-+1 = 0

(26)

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

(1) — в виде суммы частного решения неоднородного уравнения и

общего решения однородного уравнения.		уравнения (26).
Изучим более подробно	свойства разностного
Будем считать сейчас, что	У= {0, ±1, ±2,	т. е. уравнение

(26)определено для всех целых /. Заметим прежде всего, что если

щи и, — два решения уравнения (26), то и любая линейная ком­

бинация «1 tij+a^Vj также является решением. Этот факт следует

из линейности и однородности уравнения (26).			зависимости
Для дальнейшего потребуются понятия линейной
и линейной независимости функций,	заданных	на	множестве 1.
Две функции и, и щ целочисленного	аргумента	/ е /	называются

линейно зависимыми, если существуют постоянные аи к2, одно­ временно не равные нулю и такие, что выполнено равенство

ai«j+a2nj= 0 для всех / е / .

(27)

Если же из условия (27) следует, что а1= аг = 0, то функции и., v}

называются линейно независимыми.

Линейная зависимость решений и}, v} характеризуется значе­ ниями определителей

Щ [ и ,«] =	u/n	vi+1	(28)
являющимися аналогами определителя Вронского.			то ш; = 0
Л е м м а 1. Если функции щ, Vj линейно зависимы,
для всех j<=J.
28

Действительно, согласно (27) для всех / е / выполняются ра­ венства

ujal+vja2 = 0,

Wj+iCCi~bO)+iC£2 —О,

(29)

где

al -f- а\фО. Рассматривая

(29) при каждом

фиксированном'

j как однородную систему линейных

алгебраических уравнений

относительно а ь а 2 и учитывая, что al

а\ ФО, получим, что опре­

делитель Wj этой системы равен нулю.

Для решений однородного уравнения (26) справедливо утверж­

дение, обратное лемме 1.

Л е м м а

2.

Если

uh v, — линейно независимые решения одно­

родного уравнения (26)

и а}ф 0, Ь,ф0

для

всех /,

то определитель

w}\_u, и] не обращается в нуль ни в одной точке j<=J.

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

проведем

от

противного.

Предположим,

что найдется точка /0е / ,

для которой wh\_a, и]=0. Рассмотрим си­

стему уравнений

« / . “ 1 + » / . “ 2 =

О,

(30)

«/о+1 a i +

v io+1a 2 =

0

относительно неизвестных а (,

а 2.

Поскольку

определитель

этой

системы равен

нулю,

существует нетривиальное решение {а!, а 2}.

Образуем с помощью этого решения {at, ос2} функцию

Zj= alu}+a2Vj

(31)

и покажем, что zs = 0 для всех /.

однородного

уравнения

(26),

Поскольку

Uj и

Vj— решения

функция (31) также является его решением,

т. е. удовлетворяет

уравнению

ajZj-1—CjZj+bjZj+l = 0.

(32)

Кроме того, согласно (30) выполнены условия

zk= zh+l = 0.

По предположению коэффициенты а,, Ь, отличны от нуля для

всех /. Следовательно, для уравнения

(32)

можно рассмотреть за­

дачи Коши

г/+1 =

-с/ г/-

~

г/-1>

/ =

/о + 1, /о +

2,

.. .,

2/о =

г/о+1 = 0»

(33)

2/-i =

Ь,

. . .

1>/о

2, . . .,

— г/ —

2/+1>

1= /о>/о

ai

ai

0.

(34)

Z/ . = 2/.H =

Из рекуррентных соотношений (33), (34) получаем, что

2^= 0

для

всех / = 0,

±1, ±2, ... Последнее означает,

что а щ ф а 2ц,= 0

для

всех /,

причем al ф а22Ф0. Следовательно,

функции щ,

v, ли­

нейно зависимы, что противоречит предположению леммы 2.

29

С л е д с т в и е 1.	Определитель (28), составленный для двух
решений уравнения	(26), или тождественно по j равен нулю, или

отличен от нуля для всех /.

Любая система из двух линейно независимых решений уравне­ ния (26) называется фундаментальной системой.

Т е о р е м а 1. Уравнение (26) с а ф 0,					Ь ф 0, / е / , всегда имеет
фундаментальную систему.		Фундаментальную систему образуют,
Д о к а з а т е л ь с т в о .
например, решения щ и о,- следующих задач Коши:
		— C jU jJ r b i U j+i = О,
/ = 0,	± 1, ±2, ...,			и0= О,	и,= 1;
	flj-Wj-!—CjVj+bjVj+i = О,
/ = 0,	±1,	±2, ....		VQ— 1,	vt= 0.
Действительно,
	w n	и а	Hi	Ф О,

v0

исогласно следствию 1 ws[u, v]фО для всех /. Но тогда согласно

лемме 1 функции uh v, линейно независимы.

Т е о р е м а 2. Если uh v, — фундаментальная система решений

уравнения (26), то его общее решение имеет вид
		yj= alUj+a2vj,	(35)
где а, и а-, — произвольные постоянные.			уравнения
Д о к а з а т е л ь с т в о .		Пусть у, — любое решение
(26) и Uj,	Vj — два заданных линейно независимых решения. Надо
показать,	что найдутся	постоянные a t и а2, для которых справед­

ливо (35). Пусть у0 и у1 — значения решения у, в точках / = 0 и j —

= 1 соответственно. Выберем постоянные a t и а2 из условий
щ аф и0а2 = уа, ulal+vla2 = yi-	(36)

Определитель этой системы w0[u, и]Ф0, так как и и v — линей­ но независимые решения. Следовательно, при заданных у0, г/, си­ стема (36) имеет единственное решение {аи а2}- В силу единствен­ ности решения задачи Коши функция (35), построенная с по­ мощью найденных постоянных а, и аг, совпадает с заданным ре­ шением ys.

Сл е д с т в и е . Любые три решения однородного уравнения (26) линейно зависимы.

Пусть uh vu у, — любые решения уравнения (26). Если и, и v, линейно зависимы, то утверждение доказано. Если же и, и v, ли­ нейно независимы, то они образуют фундаментальную систему и согласно теореме 2 решение г/, представляется в виде линейной комбинации Uj и vs.

В качестве упражнения предлагается проверить, что частные решения (11) уравнения (7) с постоянными коэффициентами бу­ дут линейно независимы при цфЩг и линейно зависимы — при qi = q2. В последнем случае линейно независимыми будут решения

30