Вычислительная математика лекции

чередоваться). Теорема накладывает на точки чебышевского

альтернанса два требования:

1) В точках xi погрешность |f(xi)-Qn(xi)|=

max| f (x) Qn (x)|.

[a,b]

2)Для всех i=0,1,…,n+1 погрешность f(xi) - Qn(xi) меняет знак при переходе от точки xi к следующей точке xi+1. Следовательно, внутри диапазона функция погрешности имеет n+1 нулей.

Следующий пример подтверждает справедливость последней теоремы. Рассмотрим частную задачу наилучшего равномерного приближения функции f(x) = xn+1 многочленом n-ого порядка Qn(x) на отрезке [-1.1] . Заметим, что погрешность Rn+1 =xn+1 –Qn(x) есть многочлен n+1-ой степени. Задачу можно переформулировать так: среди всех многочленов степени n+1 с фиксированным старшим коэффициентом, равным 1, найти многочлен Rn+1(х) такой, для которого величина max|Rn+1(x)|, x [-1,1] была минимальной. Таким многочленом является нормированный многочлен Чебышева

Tn+1(x)/2n, а	решением поставленной задачи многочлен Qn(x) = xn+1
- Tn+1(x)/2n.	С другой стороны, легко доказать, что Rn+1(х)

удовлетворяет условиям теоремы Чебышева. Действительно, Tn+1(xm) = (-1)m, где xm = cos(mπ)/(n+1). Здесь xm – точки максимумов многочлена Чебышева, m = 0,1,…,n+1. Максимум модуля погрешности max|Rn+1(x)| на отрезке [-1,1] достигнут в n+2 точках и равен 1/2n. При этом знаки погрешности чередуются при переходе к каждой следующей точке. Таким образом, Qn(x) удовлетворяет условиям теоремы Чебышева.

Дополнительные замечания.

В большинстве случаев задача о наилучшем равномерном

приближении является очень трудной. Для ряда частных случаев

разработаны специальные численные методы, реализованные в

типовых программах.

41

Часто достаточно ограничится нахождением многочлена,

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

7.ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ

Постановка задачи. Пусть заданы значения функции в узлах

fi f (xi ) ,	где xi x0 ih,	i 0,1,2,	, h-постоянный шаг
изменения	аргумента. Будем	полагать	f (x) Cn	. Требуется
			[a,b]
определить	f (x0 ) .

Решение задачи. Используем соотношение

f (x0 x) f (x0 )

f (x0 ) lim

. Для приближенного

решения

x

x 0

можно положить

f0 f (x0 )

f1

f0

.

Для

оценки погрешности

h

рассмотрим

степенное

разложение

f (x

h) f (x ) h f (x )

h2

f ( )

,

из

которого

получим

0

0

0

2

соотношения

f0

f1 f0

r

,

(1)

h

где r

h

f ( ),

[x , x

h]

−

погрешность

(1).

2

0

0

Соотношение (1) имеет первый порядок точности, определяемый степенью h в остаточном члене r.

Формула (1) не единственна. Используя разложения

	f1 f0				h f0 (x0 )		h2			f0	h3			f ( ) ,
							2				6
	f		f		h f (x )			h2		f		h3		f (		) ,
		1		0
					0	0	2			0	6

можно получить

42

f	f	f	1		h2
	1					f (3) ( ) .	(2)
0		2h			6

Формула (2) имеет второй порядок точности. Складывая приведенные выше степенные разложения, получим формулу для вычисления производной второго порядка

		f	1	2 f	0	f			h2		( ); [		,
f (2)						1				f (4)					]..
				h2
0								12

(3)

Для нахождения производных любого порядка можно строить формулы любого порядка точности. Основной прием заключается в замене функции, заданной в (n+1)-ом узлах интерполяционным многочленом pn(x) и принятии

	f (m) (x) p(m) (x) .				(4)
	n
Пример. Пусть задана табличная функция
	x0		x1		x2
	f0		f1		f2

Требуется найти оценку производной функции в узле x0,

полагая что узлы таблицы расположены с постоянным шагом h.

Интерполяционный полином для заданной таблицы

	p2 (x)	f0	(x x1)(x x2 )				f1	(x x0 )(x x2 )				f		(x x0 )(x x1)
			(x x )(x x )					(x x )(x x )					2 (x x )(x x )
		0		1	0	2	1		0	1	2		2		0	2	1
,	и				погрешность							интерполирования

R ( f , x)		(x x0 )(x x1 )(x x2 )								f (3) ( )		.		Учитывая,			что
2					6
x1 x0 x2			x1 h и x2				x0 2h , можно записать
p (x)					f0	(x2	(x x )x x x )					f1	(x2 (x x )x x x )
2					2h2		1	2		1	2	h2		0	2	0	2
			f2	(x2 (x x )x x x ).
	2h2				0		1	1		2
										43

Используя		равенства	f (x) p2 (x) R2 ( f , x)	и
f (x) p	(x) R	( f , x) , найдем
2	2

			f0 (2x x1			x2 ) 2 f1 (2x x0 x2 ) f2 (2x x0					x1)
p2	(x)							2h2				и
						остаточный член
r(x) R		( f , x)		f (3)	( )		[(x x )(x x ) (x x )(x x )				(x x )(x x )]
	2			6			1	2	0	2		0	1

.

Найдем оценку производной и остаточного члена в узле x0:

f p

(x)

x x0

3 f0 4 f1 f2

,

0

2

2h

r r(x)

x x0

R

( f , x)

f (3) ( )

[2h2 ]

f (3) ( )

h2 .

0

2

6

3

Аналогичным образом можно получить для n=2

(интерполяционный полином pn(x) второй степени при использовании 3 узлов) оценки производных первого порядка в разных узлах:

f				1			( 3 f				4 f f						)		h2				f (3) ( ) ;
										0						2
	0			2h								1								3
f1		1					( f2		f0 )				h2		f (3) ( ) ;
		2h
												6
f			1				( f		4 f			3 f			)			h2			f		(3) ( ) ,
								0						2
	2			2h							1						3
приведенных							соотношениях													символом
значения интервала.

При использовании n=3 (4 узлов):

44

разумеется во всех

ξ обозначались разные

f0

f1

f2

f3

1

6h

1

6h

1

6h

1

6h

( 11 f			18 f		9 f				2 f				)		h3		f (4) ( );
		0						2			3
				1										4
( 2 f		3 f		6 f			f			)		h3		f (4)			( ) ;
	0					2
			1						3		12

( f0 6 f1 3 f2 2 f3 ) h3 f (4) ( ) ;

12

( 2 f		9 f	18 f		11 f	)	h3	f (4) ( ) .
	0			2
		1			3	4

Используя (4), можно найти оценки производных большего порядка ( m=2, n=2):

f0 h12 ( f0 2 f1 f2 ) hf (3) ( ) ;

f1 h12 ( f0 2 f1 f2 ) 12h f (3) ( ) .

Анализируя полученные соотношения можно отметить следующее:

1.С ростом числа узлов n при соответствующей гладкости функции порядок точности формул увеличивается.

2.С ростом порядка производной (с ростом m) порядок точности формул уменьшается.

3.В средних узлах промежутка точность формул выше, чем на краях его.

8.Численное интегрирование.

8.1.Постановка задачи численного интегрирования.

45

b	b
Требуется вычислить F (x)dx f (x) p(x)dx, где p(x) –
a	a

весовая функция (заданная, известная функция), имеющая те же особенности, что и F(x); f(x) – гладкая функция без особенностей.

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

формулы (КФ):

b	n
F (x)dx Ak f (xk ) Rn ( f ),
a	k 1

где n – число узлов КФ.

xk, k 1, n - узлы КФ.

Ak – коэффициенты КФ.

Определение. Говорят, что квадратурная формула с n узлами

имеет степень точности m, если она точна для любого многочлена m – ой степени pm(x)и неточна хотя бы для одного многочлена степени m+1.

Теорема. Для того, чтобы квадратурная формула с n узлами

имела степень точности (n-1), необходимо и достаточно, чтобы она была интерполяционной.

В основе построения КФ лежит замена интегрируемой

функции более простой, её аппроксимирующей. При использовании интерполяционных квадратурных формул (ИКФ) функция f(x)

заменяется интерполяционным полиномом (полиномом (n-1) степени в данном случае)

	n	(x)		n
	f (x) f (xk )			rn ( f , x), (x) (x xi ).
		(x x )	'(x )
	k 1			i 1
		k	k
	Тогда

46

	b		b		n	(x)			b
	F (x)dx p(x)								dx p(x)rn ( f , x)dx
						(x xk ) '(xk )
	a		a		k 1				a
	n		b			(x)
	f (xk ) p(x)							dx	Rn ( f ).
					(x xk )
	k 1		a				'(xk )
		b	(x)
	R ( f )		n!	f (n) ( ); [a,b].
	n

a

Тем самым получили ИКФ

	b		n
	F (x)dx Ak f (xk ) Rn ( f ),
	a		k 1
b	(x)
где Ak p(x)			dx .
	(x xk )
a		'(xk )

.Доказательство необходимости.

Необходимость означает, что ИКФ с n узлами должна быть точной для любого многочлена (n-1) – ой степени. В качестве такового возьмем

	(x)		n	x	xi
f (x)							Любой многочлен (n-1) – ой
						.
	(x x ) '(x )			x	x
	i	i	i 1,i k	k	i

степени можно записать указанным способом. Заметим, что в этом случае f(xk)=0, если k≠i, f(xi)=1. Учитывая вышеизложенное, имеем

	b	b	(x)	n
	p(x) f (x)dx p(x)			dx = Ak f (xk )=Ai .
			(x xi ) '(xi )
	a	a		k 1

Доказательство достаточности.

Пусть f(x) произвольно заданный полином (n-1) – ой степени.

Требуется доказать, что ИКФ точна для этого полинома.

Интерполируем его по n узлам. Интерполирование будет точным в силу теоремы существования и единственности интерполяционного полинома

n	(x)
f (x) f (xk )			.
	(x x )
k 1		'(x )
	k	k
47

Тогда

	b	n	b	(x)	n
	p(x) f (x)dx f (xk ) p(x)				dx f (xk ) Ak .
				(x xk ) '(xk )
	a	k 1	a		k 1

8.2. Квадратурные формулы с равноотстоящими узлами (формулы Ньютона – Котеса).

b

Требуется вычислить f (x)dx , полагаем p(x) = 1.

a

Далее будем использовать обобщенную теорему о среднем.

Теорема. Если u и v непрерывны на [a,b], причем функция v не меняет знака на отрезке [a,b], то существует точка ξ [a,b] такая, что

b	b
uvdx u( ) v(x)dx.
a	a

Пусть n=1 (n – число узлов) a) x1=a.

f

a	b	x

Используя интерполяционный полином нулевой степени

f (x) f (a)	x a	f '(	),	[a,b].
	1!	1	1
	b				(b a)	2
Следовательно, f (x)dx (b a) f (a)							f '( 1 ).
					2
	a

Формула левых прямоугольников: Iл.п. = (b-a)f(a); Погрешность

Rл.п. (b a)2 f '( 1 ). 2

б) Положив x1 = b, аналогичным образом получим формулу правых прямоугольников

48

b	(b a)	2
f (x)dx (b a) f (b)			f (2 ), 2 [a,b].
	2

a	Iп.п.
		Rп.п.

в) Формула центральных прямоугольников

f

(a+b)/2

a b

x

Рассмотрим степенное разложение функции относительно

узла x1= a b : 2

x x

(x x )2

f (x) f (x )

1

f '(x )

1

f ''(

),

[a,b].

3

1

1!

1

2!

3

Интегрируя, получаем

b

a b

(b a)3

f (x)dx (b a) f

f ''(3 ).

a

2

24

Iц.п.

Rц .п.

n=2

Положим x1 = a, x2 = b. Получим формулу трапеций.

f

x

a b

49

b

x b

x a

f (a) f (b)

Iтр

f (a)

f (b)

dx

(b a)

,

a b

a

b a

2

b

(b a)

3

Rтр ( f )

(x a)(x b)

f ''(4 )dx

f ''(4 ).

12

a

2!

n=3.

Положим x1 = a, x2 =(a+b)/2, x3 = b. Получим квадратурную формулу Симпсона или формулу парабол

b	(x x2 )(x x3 )	a b)			(x x1 )(x x3 )
Iсим f (a)		f				f (b)
	(a x2 )(a x3 )				(x2 x1 )(x2 x3 )
a			2

	b a		a b
		f (a) 4 f				f (b) .
	6
				2

(x x1 )(x x2 ) dx

(b x1 )(b x2 )

Оценка погрешности определяется соотношением

Rсимп (b a)5 f (4) ( 5 ). 2880

8.3.Составные квадратурные формулы.

Возможны два пути увеличения точности квадратурных формул.

1) Повышение порядка точности за счет увеличения числа узлов n. Это ведет к существенному усложнению КФ.

2)Разделение отрезка [a,b] на n малых промежутков длиной h=(b-a)/n, на каждом из которых используется ИКФ с малым числом узлов. Такие ИКФ называются большими или составными.

50