книги / Численные методы. Ч. 1

Оценка погрешности методомРунге1*

С целью получения оценки погрешности рассмотрим формулу интегрирования методом трапеций. Для отрезка [xk_,, хк ] введем обозначения:

= 'jffMdx.

Jh .k= -[f(Xk) + f(*k-,)]-

В соответствии с полученным выражением (7.12) можно записать:

v - = J	+f(xk.,)]=Vk - ~	г к и).
или иначе,
	Jk- J , k «C kh3	(7.14)

Теперь уменьшим шаг вдвое и вновь проведем интегрирование на том же отрезке [хк_,, хк];в этом случае общая погрешность

(,,я

Вычитая формулу (7.15) из выражения (7.14), получаем

Jh/U - Jhik*C kh -2Ск^—j =Ск .

Отсюда можно определить коэффициент

“jjjH^h/lk “ Jh.k)

иподсчитать погрешности вычисления интегралов:

~” ^h.k)’

I Рунге Карл Давид Тольме [30.8.1856 - 3.1.1927] - немецкий физик и математик. В 1876 - 1877 годах учился в Мюнхенском, в 1878 - 1880 годах - в Берлинском университетах. Работал в Берлине, Ганновере, Геттингене.

Следовательно, зная величины J^ k , Jh k, можно получать оценки погрешностей, получаемых при вычислении интегралов.

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

Jk ~ J^k * Ckhp,

			р
	^к ^ь/lk
г	2?h?h		I ^
Отсюда, оценки погрешности принимают вид
^к	2*~1	(^Ь/U	Л,к)»
	^h.k *

_1_

К-*Ы2.к™ 2 ^ - 1 '(^ёОк “ ^Ь.к)*

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

производится до тех пор, пока не выполнится условие

|Vk| =|jk _ ^h/Lk| * ^р-1 _ | (^h/2.k ~ \k ) ^ ^ _ a * k = l.n.

Тогда общая погрешность интегрирования
lJ -	I = Z K N		Z h = е •
	k=l	О ” a	k=l

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

Квадратурные формулы интерполяционноготипа

Представим функцию f(x) на всем отрезке [а, Ь] полиномом Лагранжа:

L { х ) = £	( Х ~ Хо ) - - - { Х ~ Xk-lX х ~ Xk » l } - - { X ~ х в )		f(xk).
к=о(Хк Хо)*— *(Х к X k - l K X k Х к*1 )■ *•
		” Х п )

Сопоставляя полученное выражение с формулой (7.2), получим явный вид для функций срк(х):

„ , й

(xk - x w)...(xk - х к ,)(хк - х ы )...(хк -х„)

Теперь весовые коэффициенты формулы (7.3) определяются явным образом:

^	г /	г (х —х0) -..(х —хк -)(х —хк*,)...			(х —х„)		,	, —
С,	= f<Pk	x)dx= fr ^ --	У - А ----- ----------	"О	V	ш>	dx,	к = 0,п. (7.16)

{; (хк - х 0)...(хк - х к.,Ххк -Хы )...(хк -х„)

Для подсчета погрешности квадратурной формулы интерполяционного типа воспользуемся полученной ранее оценкой погрешности интерполяционного полинома:

г(* )-М * ) = -^ ; У м( 4 4б[а,Ь], а)(х) = (х -х ,)(х -х ,)-...(х -х „ ).

Погрешность формулы приближенного интегрирования на отрезке [а, Ь]

Ь

„

b

h f ( n+,) / c )

* = }f(x)dx - g € kf(xk) = j[f(x) - L„(x)]dx = j - J ® ( x ) d x ,

Из последнего соотношения очевидно, что квадратурная формула интерполяционного типа выполняется точно для всех функции, являющихся полиномами степени не выше п. В этом случае в формуле (7.3) имеет место точное равенство.

J f(x)dx =	Ckf(хk).
a	k-1

Справедливо и обратное утверждение.

Теорема 7.1. Если квадратурная формула Jf(x)dx = ]£ d kf(xk) является точной для
.	к=0
многочленов степени п, то она является квадратурной формулой
интерполяционного типа.
Доказательство. Покажем, что
а.-с.-К[ ■ - ^ 4 - ^ - а - к )		k.G.
{ (xk - x„)... (xk - xk ,)(xk - xk„ )...	(xk - x„)

Пусть функция f(x) является полиномом степени п, тогда ее можно представить

в форме полинома Лагранжа

	1-0
/ч	(х -х „ )...(х -х , .Х х -х и1) ...( х - х п)	.	----
Поскольку все функции Ф,(х), i = 0.n являются		по	построению полиномами
степени п. то в соответствии с условием теоремы
	j<p1(x)dx = X d k<P1(xk) = X d k5 lk =dj,	i = 0,n,

так как согласно правилу построения полинома Лагранжа Ф*(хк) = 6л .

С другой стороны, согласно выражению (7.16)

г	d v	г	(х-х„)	...(х-х, ,)(х-х, .)...		(x-xn)	---
/ч,	х ^ х = М		----- И -а -----		^	---- ^dx = c ,.	i = 0,n,
.		,(Х,-Х„)...		(х,-х,.,Хх|- х ы )...		(х,-х0)
то есть d, = С,,	i = 0,п, что и требовалось доказать.

Квадратурные формулы наивысшей точности. Формулы Гаусса

Зададимся целью построить на заданной сетке П п точную квадратурную формулу вида (7.3) для полинома максимально возможной степени.

Рассмотрим полиномы вида х“, а = 0,ш. Для каждого такого полинома запишем

точную квадратурную формулу интерполяционного типа:

Jxadx = ]TCkx“.				a = 0,m.	(7.17)
.	kMi
В компонентной записи (после интегрирования):
	a = 0, Ь -а = ]ГСк ;
	,	Ь’ - а 1		^
	a = 1 -	—	L	^ Z c kxk;
				k=o
	а = 2.	^	3	= ± с л ;
				k=«
		b4 - Я4		n
	а = 3- V - = I C kx l;
	а = ш,	bm+l - a m+l			m
		m + 1		= Z c kxk
				k=0

Выражения (7.17) можно рассматривать как систему (m+1) нелинейного алгебраического уравнения относительно (2п+2) неизвестных,

С0,С р С2, ..., Сп, х0, хр х2, ..., хп.

Для разрешимости этой системы уравнений потребуем, чтобы число уравнений

было равно числу неизвестных, то есть ш+1=2п+2, откуда следует, что ш=2п+1.

Иными словами, задача заключается в выборе сетки Пп, содержащей (п+1) узлов,

обеспечивающей точность формулы (7.3) для полиномов степени (2п+1).

Пример	7.1.	Пусть	а	=	-I,	b = 1;	рассматривается разностная сетка Ц ,
содержащая	два	узла:	Хо	и	Х|.	Требуется	определить положения этих узлов м

коэффициенты С0, С, для полинома степени ш = 2n + I = 3.

Система уравнений (7.17) для рассматриваемого случая принимает вид

- =С0 +С,; 0 = Сох0+С,х,;

~ = С0хп +С,х,;

0 = C„xJ +C,xJ.

	Из второго уравнения	0 = (2-С ,)х0+С,х|; *0 =			С,*, .
					С ,- 2 ’
	Из последнего уравнения	0 = (2 —С,)	с М
			(С ,-2)3
	Отсюда, при условии, что х, *0, получаем
	C,J = (C ,-2 )J	С, = ± (С ,-2 ),		С, = 2—С ,, С ,=1.
	Соответственно,
	С, = 2-С , = 1;		х0	- ^ i - = -Xr
				С ,- 2	1

Из оставшегося уравнения

- = С„х" + С,х? = 2xf

Отсюда вытекает, что

Jf(x)dx=f(x„) + f(xl) =

I

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

Теорема 7.2. Квадратурная формула (7.3) является точной для любого многочлена

степени m=2n+l тогда и только тогда, когда выполнены условия:
1. Многочлен
0)(х) = (х - х „ )(х - х ,) - ...(х - х п)
ортогонален любому многочлену q(x) степени не выше п, то есть
ь
Ja>(x)q(x)dx = 0.	(7.18)

2. Формула (7.3) является квадратурной формулой интерполяционного типа,

ьрччем коэффициенты Ск. к О.п определяются согласно (7.16).

Доказательство. Докажем необходимость условия теоремы.

Пусть формула (7.3) точна для любого полинома степени ш=2п+1. Это означает, что она точна и для произведения to(x)q(x), имеющего степень не выше 2п+1, то есть

ьп

J<o(x)q(x)dx = £ C k<B(xk)q(xk) = 0.

a k=0

так как ©(xk) = 0 Vxk е£2п по построению функции ш(х).

Формула (7.16) справедлива в силу выполнения условий предыдущей теоремы 7.1. Докажем достаточность условии теоремы. Пусть выполнены требования 1 и 2;

f(x) - многочлен степени (2п+1). Представим f(x) в виде:

f(x) = a(x)q(x)+r(x),

причем q(x) и г(х) имеют степени не выше п.

Конструктивно такое разложение можно получить следующим образом. Для простоты положим п=1 (два узла), тогда ш=3. Пусть

f(x) = а + bx + сх: +dx3

- полином степени ш=3; ш(х) = (х - х 0)(х -х 1).

Пусть

q(x) = а + Рх, г(х) = у + 5х

- функции с коэффициентами а,р ,у ,5 , подлежащими определению. В этом случае

<о(x)q(x) + г(х) = Рх5 + (о -р (х 0 +х,))х! +(рх0х, - а(х„ +х,) + б)х +(ах0х, + у).

Из условия <o(x)q(x) + г(х) = f(x) получаем систему алгебраических уравнений

P=d;

a -P (x 0+xk) = c;

Px0x0-a (x 0+x0) +5 = b; ах0х„+у =

относительно искомых коэффициентов a,p,y,6 .

h

b

b

ь

Jf(x)dx = J©(x)q(x)dx + Jr(x)dx = Jr(x)dx.

a

a

a

a

Поскольку (7.3) является формулой интерполяционного типа, то она точна для полинома г(х). имеющего степень не выше п. Отсюда получаем

| r(x)dx = £ C kr(xk) = Z C k(f(xk)-ffl(xk)q(xk) ) = £ C kf(xk) .

J

k-0

k=0

k=0

В последнем соотношении вновь учтено, что <o(xk) = 0, Vxk бП„.

Из двух последних выражений следует,

Jf(x)dx = £ C kf(xk),

ак=0

то есть формула (7.3) оказывается точной для любого многочлена степени (2п+1), что и требовалось доказать.

Использование в условии ортогональности (7.18) в качестве q(x) системы

полиномов а = ().п позволяет рассматривать это условие как систему

алгебраических уравнений относительно координат узлов разностной сетки хк, к = 0,п, что позволяет упростить построение формул Гаусса:

' ь
Jl	(х - х 0) ... (x-x„)dx = 0:
а
Ь
, Jx	(x-x„)-... (x-x„)dx = 0;	(7.19)

Ь

|х " (х -х„) „. (x-x„)dx = 0.

ъа

Пример 7.2. Пусть, как и в примере 7.1, а = -1, Ь = 1; рассматривается разностная сетка, состоящая из двух узлов: n = 1. Требуется определить положения узлов разностной сетки для полинома степени m = 2n + 1= 3.

= --(x„+x,) = 0,

(1

	Jl-(x-x„Xx-x,)dx =0,
	-I
	I
	fx (x - x 0Xx-x,)dx =0.
Интегрируем первое уравнение:
|	1
Jl • (х - х„Хх - Х1)<& = /(х 1 - х(х0 + Х|) +x0x,)dx =
X X- ,	.

у - у ( Х п + Х ,) + ХХ„Х, = -+2хЛх, =0,

Аналогично интегрируем второе уравнение системы:

J x (x -x 0)(x-x))dx= J(x3 - х 2(х0 +x,) +x x 0x,)dx =

х4 х3 / ч х2

— - y l X o + X . j + y X o X ,

х0=-х,.

Совместно решая полученные уравнения, получаем

- 4

что совпадает с результатом примера 7.1.

Рассмотрим условия существования и единственности системы уравнений (7.19). Представим полином

о(х) = (х-х0)-...(х -х 11)

в виде

(o(x) = a„ +а,х +а2х2 +... + xn+l

Условия ортогональности (7.18)
	jx“ (а0 + а,х + а2х2 + ... + xn+1)dx = 0,	а = 0,п,
b	h
Jxu	(a„+a,x+ a2x2 - ...+anxn)dx = -Jxu	xn+,dx. a = 0,n

можно записать в виде системы линейных алгебраических уравнений относительно

коэффициентов а к, к = (),п.

Рассмотрим соответствующую систему однородных уравнений
Jxa (а,, + а,х + а 2х2 + ... + aIlxn)dx =0. а = 0,п.		(7.20)
Домножим каждое из этих однородных уравнений на соответствующее аа и
просуммируем:
п ^
£ j a (Ix“ (а0 +а,х + а 2х2 +	-fanxn)dx = 0.
а=»„
Ь	п
J(aH+ а,х + а2х2 + ... +anx")^aaxadx = 0,
а
j ' f11=0i X/ x“]	dx=0-

Отсюда очевидно, что последнее равенство возможно лишь при условии

= о .

i/ -0

откуда, в силу линейном независимости функций \ и а =0,п . следует

=-- 0, а = 67п .

Это означает, что однородная система (7.20) имеет только тривиальное решена, то есть определитель системы уравнений отличен от нуля. Таким образом. Полином

о>(х)-(х х,,)-... (х -х„)

определяется единственным обр;