book1989

Пусть p(jt) == 1, а= —1, b—1. При п= 1 получаем т= 1 и систе­

ма (2) принимает вид	1
1
Ci — ^ dx = 2,	CiXi = j х dx = О,
-1	-1

т. е. приходим к известной формуле прямоугольников

j /(*)<**-2/(0), -I

которая точна для любого многочлена первой степени. При п = 2, т = 3 система (2) записывается в виде

	^1 + ^2= 2,		^2^2	= О»
	“Ь ^2^2 :== ~ ~ I		C i X i	С $ Х 2 =	0 .
Отсюда находим		о
	1		1		1
		Xi --		Хп--
Сг --- Со -- 1 у			г~—~у		--у
1	2	1	УЗ		УЗ

т. е. получаем квадратурную формулу

|№)<ч=/(-Йг)+/(?т)'

“1

которая точна для любого алгебраического многочлена третьей степени.

2. Основная теорема. Возвращаясь к рассмотрению квадратур­ ных формул (!) общего вида, введем многочлен

и (х) = (х—х^ (х—х2) ... (х—хп) .	(3)
Будем предполагать, что р(х) >0.	любого
Т е о р е м а 1. Квадратурная формула (1) точна для

многочлена степени т = 2п—1 тогда и только тогда, когда выполне­

ны два условия:				любому многочле­
1)	многочлен ш(х) ортогонален с весом р(х)
ну q(x) степени меньше п, т. е.
			ь
		J р(х) ш (х) q(x) dx — 0;			(4)
		а
2)	формула (1)	является квадратурной формулой интерполяци­
онного типа, т. е.
	ь
	c * = f p ( * ) - -----М.(Х), . . dx, 6 = 1 , 2 ........ п.				(5)
	J	(X	— Xk ) со' ( x k )
	а
Д о к а з а т е л ь с т в о .			Н е о б х о д и м о с т ь .	Пусть	формула

(1) точна для любого многочлена степени т = 2п—1. Это значит,

181

что она точна и для многочлена a>(x)q(x), имеющего степень не выше 2н—1, т. е.

Ь	п
^ р (х) со (х) q (х) dx =	2 cAco (х*) q (хк) =	0.
a	fe=i
Требование (5) выполняется	в силу теоремы	1 из § 2 (если ква­

дратурная формула (1) точна для любого многочлена степени п—1, то она является формулой интерполяционного типа).

Д о с т а т о ч н о с т ь . Пусть f( x ) — любой многочлен степени 2п—I. Согласно теореме о делении многочленов, его можно пред­ ставить в виде

		f(x) =со (x)q{x)+r(x),
где q(x)	и г(х) — многочлены, имеющие степень не выше п—1. При
этом
b	b	ь	ь
р (х) / (х) dx = ^ р (х) со (х) q (х) dx -j- ^ р (х) г (х) dx = j Р (х) r (х) dx.
а	а	а	а
Последнее равенство справедливо в силу			предположения (4).
Далее,	поскольку г(х) — многочлен степени не выше п—1 и фор­

мула (1) является формулой интерполяционного типа, она точна для г(х), т. е.

Ь п п п

^ р(х) г (х) dx — 2 с*г (**) =		2 Ск ^ ^	“ (**) Я(Л'0) = 2 Cfj
a	k= \	k=i	k= i
Таким образом,	Ь	п
			Ckf (хк),
	^р (х) f (х) dx = 2

ak=i

т.е. формула (1) точна для любого многочлена степени 2п—1. Тео рема 1 доказана.

Отметим, что использование теоремы 1 существенно упрощает

построение формул Гаусса.

Условие (4) эквивалентно требованиям
ь	(6)
j р (х) со (х) xadx = 0, а = 0, 1, . . . , п — 1,

а

которые представляют собой систему п уравнений относительно п неизвестных хи хг, ... , х„. Таким образом, для построения формул Гаусса достаточно найти узлы х,, х2, . . . , х„ из соотношений орто­ гональности (6) и затем вычислить коэффициенты ск согласно (5).

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

182

3. Существование и единственность квадратурных формул наи­ высшей алгебраической степени точности. Представим искомый многочлен (3) в виде

(О(х) =Я0+ Й1Х+. . .+ йп-1-JC”' 1+ х™.			(7)
Тогда условия ортогональности	(6) примут вид
ь
р (х) (я0 + ахх + ... + Qrt-iX”-1+ Xя) xadx = 0 ,			(8)
а	1........ п—1.
а = 0,
Условия (8) представляют собой систему линейных алгебраиче­
ских уравнений относительно коэффициентов а0) я,, . . . ,			я„-,. По­
кажем, что соответствующая однородная система уравнений
ь		ап-1хп~1) ха dx = 0,
$ РМ (а„ + х +	... +		(9)
а		п—1,
a = 0,	1, .. .,

имеет единственное решение а0= а, = .. ,= ап_1= 0. Для этого умно­ жим уравнение (9) на яа и просуммируем по всем сс. Тогда получим

rt-1	b				П- 1	Л — 1		xkxfX dx = 0,
2	U	Р (*) akxkS		j	2	2	a^
					Р w
а=о	а	&=0			а,—ок=о
т. е.		ь
			Л - 1	2
					dx = 0.			(10)
		р(*)	2 а‘х‘
Если хотя бы один из коэффициентов						я,,	1 = 0,	1.........п—1, от­
личен от нуля, то функция

@н

может обратиться в нуль на [я, Ь] лишь в конечном числе точек. Отсюда и из условия р(х)>0 следует, что равенство (10) возможно лишь в случае

Яц= —... —яп—i= 0.

Тем самым неоднородная система (8) имеет единственное решение. Следовательно, существует единственный многочлен со(х) степени п со старшим коэффициентом 1, ортогональный с весом р(х)>0

лю бом у многочлену степени п— 1.

Т е о р е м а 2. Если со(х) — многочлен степени п, ортогональный на [я, b] с весом р(х)>0 любому многочлену степени меньше п, то все его корни различны и расположены на [а, Ь].

Д о к а з а т е л ь с т в о . Предположим, что многочлен со(х) имеет гп^О различных корней нечетной кратности на [я, Ь]. Очевидно,

183

что т ^ п . Теорема 2 будет доказана, если покажем, что т = п. Обо­ значая эти корни через | ь | 2, . . . , | т, представим ю(х) в виде

	и (х) = (х — У “‘ (х — У “2... (х — £m)“mг (х),
где аи а2, . • •, ой — нечетные числа и функция г(х)			не меняет знак
на [а, Ь]. Вычислим интеграл
I =	ь	... (х — lm) dx =
	^ р (х) со (х) (х — у
	а
	=	J p ( * ) ( j eУ- “‘+1 • • • (X- U	“m+1 (X)Г dx. (11)
		о
Поскольку cti+1, . . . ,		ат+ 1 четные числа и г(х)	знакопостоянна
на	La, b], интеграл (11) отличен от нуля. С другой стороны, если
т<п, то
	q(x) = (*—£,) (х—Ы • • - (х—1т)

— многочлен степени меньше п и по условию теоремы имеем 1 = 0. Следовательно, т = п, что и доказывает теорему 2.

Из теорем 1 и 2 следует, что для любого п существует, притом единственная, квадратурная формула, точная для любого много­ члена степени 2п—1.

4. Свойства квадратурных формул Гаусса. Нетрудно показать, что 2п—1 — наивысшая точность формулы Гаусса, т. е. что сущест­ вует многочлен степени 2п, для которого эта формула не является точной. Действительно, для многочлена (3) имеем

ь

^ р (х) со2 (х) dx > 0,

а

НО

2 CfeOJ2 (хк) = 0. k=1

Докажем теперь, что при любом п коэффициенты ск формул Га­ усса положительны. Рассмотрим многочлены

!	ш (х)	Л
ф‘‘ М = (	(X —Х,.)«в' (*,) ) ’	1 = 1 , 2

имеющие степень 2п—2 и обладающие свойством

ф.(*ь) = бй.

Так как для этих многочленов формула Гаусса точна, справед­ ливы равенства

ь	П
^ р (х) <рI (х) dx =	'2s скЩ {Xk) = Cl,
a	fe=l

откуда и следует, что с\>0, с = 1, 2, . . . , п.

184

В п. 4 § 2 отмечалось, что свойство положительности коэффици­ ентов чрезвычайно важно для устойчивости вычислений и позволя­ ет использовать формулы с большим числом узлов п. На практике применяются формулы Гаусса с числом узлов до 100.

Для погрешности формул Гаусса справедливо представление

h

	!>»(/) - ~ ~	f Р М «2 (*) Г ’ (?) dx,	(12)
	(4я)!	J
	где £е=(а, Ъ).	а
		(см. [16, т. 1, с. 248]), отметим лишь,
	Не приводя доказательства

что оно основано на использовании интерполяционного многочле­ на Эрмита Н (х) с двукратными узлами

H(xh)= f(xk), H'(xk)=f'(xh), £ =1 , 2 ........я.

5. Частный случай формул Гаусса. Формулами Эрмита называ­ ются формулы Гаусса для вычисления интеграла

—1I	f (х) dx	(13)

т. е. когда а= —6= —1, р{х) = (1—хг)~иг.

Чтобы определить узлы соответствующей квадратурной форму­

лы, надо, согласно теореме 1, найти многочлен (3), для	которого
Г--(х) q- ^ ]dx = 0	(14)
для любого многочлена у(х) степени меньше п. Можно показать
(см. [2, с. 117]), что таковым является многочлен Чебышева
(х) = Тп(х) = ~^-Cos(narccosx).	(15)

Поэтому узлами квадратурной формулы Эрмита являются корни этого многочлена

	(2k — 1) я		,			(16)
	X k - COS :	п	k — 1, 2, ... , п.
	2
	Соответствующие коэффициенты вычисляются по формулам					(5)
	Ck		Тп (х) dx			(17)
	V 1 — * 2 T n ( x k ) (x — Xk )
	и оказываются равными
	ck=nln,	k= 1, 2,			. . . , n.
	Таким образом, формулы Эрмита имеют вид
	/ (х) dx		-	2	/(**)•	(18)
	У Т ^ Т 1
			п	Й=1

где хк— корни многочлена Чебышева, определенные согласно (16).

185

§4. Численное дифференцирование

I.Некорректность операции численного дифференцирования.

Задача численного дифференцирования состоит в приближенном вычислении производных функции и(х) по заданным в конечном

числе точек значениям этой функции. Простейшие примеры фор­ мул численного дифференцирования рассматривались в п. 1 § 4 ч. I. Напомним эти примеры. Пусть на [а, Ь] введена сетка

<0h = {xi= a+ ih, г = 0, 1, ... , N, hN = b—а}

и определены значения и{ = и(х{) функции и(х) в точках сетки. В качестве приближенного значения и'(х{) можно взять, например, любое из следующих разностных отношений:

	2h
Возникающая в результате такой замены погрешность характе­
ризуется разложениями
u~Xfi = «' (Xi) — Y Ы" (d1'),	(i)

		ихЛ = и'(Х1) + | « "		( d 2)),		(2)
		и,x,i = u ’(Xi) + ^ou '" ( tf\				(3)
где £г;), /=	1,2, 3,— точки из интервала				я(+1).	отношением
Вторую	производную в точке х{ можно				заменить
при этом	UXX,L=-	j ( U^	их.) =		Л3
					о (V).
	и-х . = и" (Xl) +			(*) +		(4)

Четвертая производная uiv (Xi) с точностью до величины О(/г2) аппроксимируется разностным отношением

U X X X K , i	h 2 ( U X X , i + l	^ U x x , i	U x x . i - 1 )
			= — («i+2 — 4U i + i + 6Ui — 4«i_! -}- H1- 2).
			ft4

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

186

сетки h к нулю. Поэтому операцию вычисления разностных отноше­ ний называют некорректной. Поясним причину некорректности на примере вычисления разностного отношения u - [==(ui—ы4_,)//1.

Разностное отношение и - 1 хорошо приближает и'{х{) только в

том случае, когда шаг h достаточно мал. Требование малости вели­ чины И, находящейся в знаменателе разностного отношения, как раз и является причиной некорректности операции численного диф­ ференцирования. Действительно, пусть вместо точного значения uit и<-1 вычислены приближенные значения й; = щ+бь ui-, = ai_,+ 6i- 1. Тогда вместо и-, будет вычислена величина u - i + (б;—бi-,)/A. Сле­

довательно, погрешность в вычислении первой разностной произ­ водной окажется равной б -£= (б;—бt-i)/h.

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

ностями округления	(хотя их реальная природа может быть иной).
Пусть известна	граница б погрешностей б,-, 6,-1, т. е.	|б;|=£1 б,
| б,-! | г?;б. Тогда	I бг.; I < 26//i,	(5)

причем эта оценка достигается при 6i= —61_1= б. Из оценки (5) видно, что вследствие малости h погрешность, возникающая при вычислении первой разностной производной, значительно превосхо­ дит погрешность вычисления самой функции и(х). Если б не за­ висит от h, то погрешность 6- с неограниченно возрастает при Л-И).

Сказанное не означает, что нельзя пользоваться формулами чис­ ленного дифференцирования. Чтобы не происходило существенного понижения точности, надо следить за тем, чтобы погрешность округ­ ления имела тот же порядок, что и погрешность аппроксимации. Например, из (1) следует, что погрешность аппроксимации при замене и'(х) отношением и -с не превосходит величины 0,5/гЛ42,

где М2= max |и "(х)|. Естественно потребовать, чтобы и по-

грешность округления б-, была бы сравнима с погрешностью аппроксимации, например

26/A<Af2A/2,

(6)

где М2 не зависит от h. Это означает, что погрешность б при вычис­ лении значений функции «(лД должна быть величиной 0 (й2). С другой стороны, неравенство (6) показывает, что если величина б задана и мы не можем ее менять, то вычисления надо проводить не с произвольно малым шагом h, а с шагом, удовлетворяющим

условию AlSsfto, где /г0= 2Уб/М2.

При вычислении производных более высокого порядка, когда в знаменатель разностного отношения входит hh, k~> 1, влияние неточ­ ности в задании и(х{) сказывается еще сильнее. Например, при вычислении разностного отношения и~ххх £ погрешность округления

является величиной 0 (6/i-4), где б — граница погрешности округ­ ления функции и(х). В этом случае для того чтобы погрешность округления 8%хх i была сравнима с погрешностью аппроксимации,

187

надо потребовать, чтобы h ^ h 0, где h0= О(б1/:), либо проводить вы­ числение и(х{) с погрешностью б= 0(he). Например, если 6^10~12, то шаг h надо брать примерно равным 0,01. При этом погрешность аппроксимации и погрешность округления будут примерно равны­

ми 10~\ Вычисление производной и'(х) по заданной функции и(х) так­

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

ниченной функции и(х) производная и'(х)	может быть сколь угод­
но большой. Например, для u(x)=sincox	имеем шах |ы (х )|^ 1		и
шах | и' (х) | = | со |->-оо при <й->-оо.	х^[а,Ь]
*е[а,ц		задачи	и
Строгие определения корректности математической
способы решения некорректных задач изложены в книге		[38].

2. Применение интерполирования. Многие формулы численного дифференцирования можно получить как следствие интерполяцион­ ных формул. Для этого достаточно заменить функцию и(х) ее ин­ терполяционным многочленом Ln(x) и вычислить производные мно­

гочлена Ln(x), используя его явное	представление. В отличие от
п. 1 рассмотрим неравномерную сетку
шЛ= {а= х0< х ,< х 2< . . ,<xN = b}
и обозначим через А.;= Х;—Х ;_,, i= 1,	2, . . . , N, шаги этой сетки.

В качестве примера получим формулы численного дифференциро­ вания, основанные на использовании многочлена Лагранжа L2i(x),

построенного для функции и(х)					по трем точкам х,-,, х,-, xi+1. Много­
член L2i(x)	имеет вид
L2,i (х) =
(X — хс) (х — х£+1)				(X — Xi_x) (х — xi+1)			(*—*м ) ( x - x t)
= ----------------------------------- Ui—1				—	1	--- ----Ui “Т"-------------------------- lli+ 1»
hi	+	hi+l)			hchl+l		hi+1 (ht +		hi+1)	(7)
Отсюда получим
Ll.i (*) ==:
(2x	x^ •	X[+1)		(2x	xi+i)	" ,	{^x	xi—i	xd	Ui+1•
= ----------------- Hi-л-------------------------						Hi “p ■ '		---------
hi {hi +		hi+1)			h,At-+1		hi+1 (hi Ai+1)
Это выражение можно принять за приближенное значение и'(х)
в любой точке х е [х ;_ь xi+1]. Его удобнее записать в виде
U.t (х) — —			(X —	Xt-y,)-	+ (x1-+1/l — х) —					( )
					hi+\			h,		8

где hi=0,5{hi + hi+l) , xi-vJ = x1—0,5ht. В частности, при х = х, получим

hj	u i +1 u i	. hj+1 u;	lli-L \
hi	hc+ 1	hc	At	(9)
				J ’

и если сетка равномерна, hi+i = ht= h, то приходим к центральной разностной производной, L2ii (х$ = и°..

188

При использовании интерполяционного многочлена первой сте­ пени точно таким же образом можно получить односторонние раз­ ностные производные и- £ и ихл.

Далее, вычисляя вторую производную многочлена L2i(x), полу­ чим приближенное выражение для и"{х) при xe[x;_i, xi+i]:

	и"(х) Lt.i (*) = —	( 10>
		h,-
	%

На равномерной сетке это выражение совпадает со второй разност­ ной производной и-х г Ясно, что для приближенного вычисления

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

Порядок погрешности аппроксимации зависит как от порядка интерполяционного многочлена, так и от расположения узлов ин­ терполирования. Получим выражение для погрешности аппроксима­ ции, возникающей при замене и'(х) выражением Ь'2Л(х). Будем считать, что хе[х,_,, jci+1] и что величины hh hiJri имеют один и тот же порядок малости при измельчении сетки. По формуле Тейлора в предположении ограниченности ulv (х) получим

Ui+k = и (х) + (xi+k — х) и' (х) +

+ ■(Xi+k ~ Х)2 и" (х) +	(Xi+k~ x)i и"' (X) + о (h4)r
2	б

где k = 0, ±1, h = max{hu hi+l}. Отсюда приходим к следующим раз­ ложениям разностных отношений:

—■ “1~1 = W {х) — (х — Х;_у2) и" (х) +

		+	( —	— + 4 )и'"(* )-+ 0		<п >
—~г— - = и' W + (■*»■+'/, — х) и" W +
hUl
		+		+ % ) и " ' w + 0		2>
Подставляя (11) и (12) в выражение для разностной производной
(8)	и приводя подобные члены, получим
^-2,1 (Х) --
=	( х - х у	(hi+i — hi) (*— хд			и"' (х) + О(/г3),
	и' (х) - [		3
	2

(Х{-1, Xij,i)..

Отсюда видно, что разностное выражение (8) аппроксимирует и'(х) со вторым порядком. Несколько хуже обстоит дело с выраже­ нием (10), аппроксимирующим вторую производную. Из (4) видно,

189

что на равномерной сетке в точке х = х{ имеет место аппроксимация О {К1). Покажем, что на неравномерной сетке {h{^ h t+l) погреш­ ность аппроксимации будет иметь только первый порядок. Подстав­

ляя разложения (11), (12) в выражение	(10) для L2ti (х), получим
L'z.i (х) = и" (х) + ^хс — х + 1+1	kl j и" (х) + О (h2).

Здесь даже на равномерной сетке второй порядок аппроксима­ ции имеет место лишь в точке х = хи а относительно других точек (например, точек х = и x = xi+i) выполняется аппроксимация только первого порядка.

Г Л А В А 5

РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ И СИСТЕМ УРАВНЕНИЙ

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

1. Введение. Пусть задана функция f(x)	действительного пере­
менного. Требуется найти корни уравнения
f ( x) = 0	(1)

или, что то же самое, нули функции f(x).

Уже на примере алгебраического многочлена известно, что нули f(x) могут быть как действительными, так и комплексными. Поэто­ му более точная постановка задачи состоит в нахождении корней уравнения (1), расположенных в заданной области комплексной плоскости. Можно рассматривать также задачу нахождения дейст­ вительных корней, расположенных на заданном отрезке. Иногда, пренебрегая точностью формулировок, будем говорить, что требу­ ется решить уравнение (1).

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

Не существует каких-то общих регулярных приемов решения задачи о расположении корней произвольной функции f(x). Наи­ более полно изучен вопрос о расположении корней алгебраических

многочленов	(2)
f(x)=a0+ aix+a2x2+ ... + amxm.

Например известно, что если для многочлена (2) с действительными коэффицентами выполнены неравенства

((c) >0, f'(c) > 0.......f(m>(c)>0,

190