239287

						Продолжение табл. 1.4
Степень		Многочлен Чебышева
n = 2	T2	(x) = x2 −	1
			2
n = 3	T3	(x) = x3 −	3 x
			4
n = 4	T4	(x) = x4 − x2 +		1
				8
n = 5	T5	(x) = x5 −	5 x3	+		5
					16
			4

	Рассмотрим поведение многочлена Чебышева T n ( x ) на отрезке [−1; 1].
	Положим			в формуле	(1.34) x = cos θ ,		0 ≤θ ≤ π		(функция
	x = cos θ взаимно однозначно отображает отрезок [0;π ]на отрезок [−1; 1]).
	Получим			1n {(cosθ +	cos2 θ −1)n + (cosθ −			cos2 θ −1)n }=
	Tn (cosθ) =
		1		2		1		~
			{cos nθ +i sin nθ + cos nθ −i sin nθ}=
	=							cos nθ =Tn	(θ)
		2n				2n	−1
	или

1

~

Tn (x)

x=cosθ =

cos nθ =Tn (θ) , 0 ≤ θ ≤ π.

2n−1

Итак, значения многочлена~Tn (x)

(−1 ≤ x ≤1) при x = cos θ

падают со значениями функции Tn (θ) на отрезке [0;π ].

Отсюда получаем, что

~

1

max

T n ( x )

= max

T n (θ )

=

.

n − 1

− 1 ≤ x ≤ 1

0 ≤ θ ≤ π

T2(x) , n ≥ 1

Предложение 1.3. Корни многочлена Чебышева

ственные, различные и принадлежат интервалу (−1; 1).

n

(1.35)

сов-

(1.36)

веще-

Вопрос о корнях многочлена							T (x) сводится к отысканию корней
~							n
функции Tn (θ) на отрезке [0;π].
~		1
Функция Tn	(θ ) =			cos nθ			обращается в нуль в точках
			2 n −1
	θk =	(2k −1) π				, k = 0, ± 1, ± 2,…
			n		2

21

Отрезку

[0;π]

принадлежат точки

θk

только при k = 1, 2, … , n .

Следовательно,

все n

корней многочлена Tn (x) принадлежат интервалу

(−1; 1) и в силу (1.35) находятся по формуле

xk = cos θk = cos

(2k −1)

π

,

k =1, 2, …, n.

(1.37)

Предложение 1.3 доказано.

n

2

~

равномерно распределены на от-

Замечание 1.12. Нули функции Tn (θ)

резке [0;π], расстояние между нулями равно

π

. Корни многочлена Чебыше-

2n

вавсилунелинейностифункции cos θ сгущаютсякконцамотрезка [−1; 1].

Предложение 1.4. Многочлен Чебышева

Tn (x) , n ≥1 на отрезке

[−1; 1] имеет экстремумы

Tn (xm )

=

(−1)m

,

x

=cos

mπ

,

m =0,1, 2,…n.

(1.38)

2n−1

m

~ ′

n

− n

Действительно,

производная

Tn

(θ ) =

sin nθ обращается на

2n −1

отрезке [0;π] в нуль в точках θ

mπ

=

,

m

m = 0, 1, 2, … n. Точки θm

нахо-

n

~

(θ) и, следовательно, являются точками

дятся между нулями функции Tn

экстремума. Отсюда получаем, что многочлен Чебышева T n ( x )

имеет

экстремумы при xm =cos

mπ

,

m =0,1, 2,…n.

n

Предложение 1.4 доказано.

Важное замечание 1.6. Многочлены Чебышева Tn (x) , n ≥ 0 на от-

резке [−1; 1] определяются формулой

Tn ( x) =

1

cos (n arccos x ).

(1.39)

n−1

2

Формула (1.39) получается из (1.34) с помощью обратной замены

θ = arccos x при −1 ≤ x ≤1.

С помощью (1.39) легко вычисляются значения многочлена Чебышева на отрезке [−1; 1].

Замечание 1.13. Из формулы (1.39) немедленно получаем следующее. 1. Все многочлены T2k (x) являются четными функциями, а T2k+1 (x) –

нечетными.

2. Для n = 1, 2, … имеет место рекуррентная формула

22

T

(x) = x T

(x) −

Tn−1 (x)

.

n+1

n

4

3. Многочлены

φ0 =1

2 , φn =Tn (x) , n ≥ 1 образуют на отрезке

[−1; 1] ортонормированную систему функций с весом 2 (π 1−x2 ):

1

2T

(x)T

(x)

dx =

1

π

1, если

n = m

∫

n

m

2

π

∫cosnθ cosmθ dθ =

0, если

n ≠ m

.

1

π 1− x

−π

−

Теорема 1.3. Многочлен Чебышева Tn (x) , n ≥ 1 среди всех много-

членов степени n с коэффициентом при старшей степени x n ,

равным 1,

имеет на отрезке [−1; 1] наименьшее уклонение от нуля.

Это означает, что для любого многочлена

pn

Ρ( n ) , такого, что

deg pn = n , lim

pn (x)

= 1, имеем

x

n

x→∞

max

p n

( x )

≥ max

T n ( x )

=

1

.

(1.40)

2

n − 1

− 1 ≤ x ≤ 1

− 1 ≤ x ≤ 1

Доказательство. Пусть существует многочлен g n Ρ( n ) , такой, что

max

g n

( x )

< max

T n ( x )

=

1

,

(1.41)

n − 1

2

− 1 ≤ x ≤ 1

− 1 ≤ x ≤ 1

deg gn

= n , lim

gn (x)

=1 .

x

n

x→∞

Тогда разность Tn ( x) − g n ( x) будет многочленом степени не выше n −1, отличным от тождественного нуля. Кроме того, в силу (1.36) и пред-

положения (1.39) эта разность в n +1 точках xm = cos mnπ, m = 0, 1, 2, …n

принимает отличные от нуля значения противоположных знаков:

1

sign (T

n

(x

m

) − g

n

(x

m

))= sign

− g

n

(x

m

)

= sign

n−1

2

m = 0, 1, 2, …n .

Это означает, что многочлен Tn ( x) − g n ( x) степени, шей n, обращается в нуль по крайней мере в n точках (имеет

корней), что невозможно. Теорема 1.3 доказана.

(−1)		m
2	n−1		,

строго мень- n различных

23

Таким образом, для решения задачи об оптимальном выборе узлов интерполяции на отрезке [−1; 1] в качестве узлов интерполяции нужно вы-

брать корни многочлена Чебышева Tn+1 (x) , то есть точки

xk = cos

(2k +1)

π

, k = 0, 1, …, n.

(1.42)

n +1

2

При этом в соответствии с (1.36) оценка погрешности интерполяции

(1.11) примет вид

M n + 1

1

max

rn ( x ;

f )

≤

,

(1.43)

( n + 1)! 2

n

−1 ≤ x ≤1

Mn+1 = max

f (n+1) (x)

,

max

ω ( x )

= max

T n +1 ( x )

=

1

.

n

−1≤x≤1

−1 ≤ x ≤1

−1 ≤ x ≤1

2

Из теоремы 3 следует, что оценку (1.40) улучшить на отрезке [−1; 1] за

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

Рассмотрим случай интерполирования на произвольном отрезке [a; b]. Отрезок [a; b] линейной заменой переменной

x = a + b + b − a t ,

t = 2 x − (a + b)

2

2

b − a

взаимно однозначно отображается на отрезок [−1; 1]

. При этом корням мно-

гочлена Tn+1 (t)

на отрезке

[−1; 1]

соответствуют

корни

многочлена

2 x − (a + b)

Tn+1

на отрезке [a; b]:

b − a

2x

− (a + b)

k

Tn+1

= 0 ,

b − a

1

(2k +1) π

xk =

(a + b) + (b − a) cos

, k

= 0, 1, …, n.

(1.43)

2

n +1 2

Точки (1.43) являются оптимальными узлами для оценки погрешно-

сти интерполяции на произвольном отрезке [a; b].

По узлам (1.43) построим ω( x) :

(b −a)n+1

2x −(a +b)

ω(x) =(x −x0 )(x −x1 )…(x −xn−1 )(x −xn ) =

Tn+1

.

2n+1

b −a

Отсюда получаем оценку погрешности интерполяции на произволь-

ном отрезке [a; b]с узлами (1.42) в виде

rn ( x ; f

≤

M n +1

(b − a ) n +1

max

)

,

( n

+ 1)!

2

2 n +1

a ≤ x ≤ b

24

Mn+1 = max f (n+1) (x) .

a≤x≤b

2. Сходимость интерполяционного процесса

2.1. Интерполяционный процесс

Чтобы построить интерполяционный процесс, нужно задать на [a; b]

бесконечную матрицу узлов интерполяции

x	0( 0 )
		x1(1 )
x 0(1 )				x
x	( 2 )	x	( 2 )		( 2 )
=	0		1		2			,
	( n )	x	( n )	x	( n )	…	( n )
x	0		1		2		x n
где все элементы xi( k ) [a; b], xi( k )				< xi(+k1) , i, k			= 0 , 1, 2 , …
Набор узлов интерполяции				( n ) = {x 0( n ) ,				x 1( n ) , … , x n( n ) },

принадлежащих n-й строке матрицы , называют сеткой. Таким образом, матрица узлов задает на [a; b]последовательность сеток { ( n ) }.

По каждой сетке ( n ) , n = 0, 1, 2, … можно построить интерполяционный многочлен степени n, интерполирующий заданную функцию f

Pn ( x ; x 0( n ) , x1( n ) ,… , x n( n ) ; f ) = Pn( n ) ( x ; f ).

(2.1)

Последовательность интерполяционных многочленов (2.1) называют интерполяционным процессом. Говоря о сходимости интерполяционного процесса, ищут ответ на вопрос о сходимости последовательности интерпо-

ляционных многочленов {Pn( n ) ( x; f )}к функции f ( x ) при n → ∞.

2.2. Сходимость интерполяционного процесса

Обычно рассматривают следующие виды сходимости функциональной последовательности {Pn( n ) ( x; f )} для фиксированной последовательности сеток { ( n ) }.

1. Поточечная сходимость к f ( x ) на [a; b]:

limPn(n) (x; f ) = f (x) для любого x [a; b];

n→∞

Pn(n) (x; f ) → f (x) на [a; b].

n→∞

25

2. Равномерная сходимость к f ( x ) на [a; b]:
limmax		Pn(n) (x : f ) − f (x)		=0	;
n→∞ a≤x≤b
Pn(n) (x; f ) f (x) на [a; b].
		n→∞
3. Среднеквадратичная сходимостьсвесом ρ(x) >0 к f ( x ) на [a; b]:
limn→∞ ∫b (P(nn) (x : f ) − f (x))2ρ(x) dx = 0;
a
		ср
Pn(n) (x; f ) → f (x) на [a; b].
		n→∞

В дальнейшем нам понадобится важный результат линейного функционального анализа, известный как теорема Банаха – Штейнгауса.

Пусть Β – произвольное банахово пространство. Рассмотрим после-

довательность линейных непрерывных (ограниченных) операторов

Αn : Β → Β.

Теорема 2.1 (Банах – Штейнгаус). Для того чтобы последователь-

ность операторов

{Αn }

поточечно

сходилась

к оператору Α при

n → ∞ , то есть

при n → ∞ для всех

f Β,

Αnf →f

необходимо и достаточно выполнение двух условий:

а) существует Λ > 0 ( Λ = const ) такая, что

Αn

Β→Β ≤ Λ длявсех n .

б)

последовательность Αnf →f

при

n → ∞ для всех

f , где

– плотное множество в банаховом пространстве Β.

Важное замечание 2.1. Для матрицы узлов на [0; 1] построим по-

следовательность интерполяционных многочленов Лагранжа

L n ( x ; x 0( n ) , x1( n ) ,… , x n( n ) ; f ) = L n ( x ; f ).

Введем оператор Ln

: C [0; 1]→ C [0; 1] ( C[0; 1] – пространство

функций, непрерывных на [0; 1],

f

C [0;1]

= max

f (x)

), ставящий в соот-

ветствие

функции

f ( x )

0≤x≤1

ее интерполяционный многочлен

Лагранжа:

f ( x)

Ln ( x; f ).

Положим

n

λn =max∑

lk(n) (x)

,

a≤x≤b k=0

26

где l k( n ) ( x ) =

ω(x)

– многочлены базиса Лагранжа (см. (1.6)).

(x − xk )ω′(xk )

Нетрудно доказать,

что

L n

C [0 ;1 ]→ C [0 ;1 ]

= λ n . С другой стороны,

имеет место неравенство (Бернштейн)

λ > lnn .

(2.2)

n

8 π

L n

Следовательно,

→ ∞ при n → ∞ . Отсюда и из теоремы 2.1

получаем, что последовательность

Ln ( x; f )

не может сходиться равно-

мерно на [0; 1]

для любой функции

f C [0; 1]:

Ln (x; f ) / f (x).

n→∞

В противном случае нормы операторов L n были бы по условию а)

теоремы 2.1 ограничены.

Замечание 2.1. С практической точки зрения интересны два случая сходимости интерполяционного процесса на равномерных сетках (сетках с равноотстоящими узлами).

1. Пусть n фиксировано (n = const). В этом случае рассматривается сходимость интерполяционного процесса при h → 0 на последовательно-

сти сеток ( h ) = {x 0 + ih , i = 0 , 1, … , n , h > 0}.

2. Пусть h фиксировано (h = const). В этом случае рассматривается сходимость интерполяционного процесса при n → ∞ на последователь-

ности сеток ( n ) = {a + ih , i = 0 ,1,… , n}.

Случай 1 для f C ( n+1) [a;b] рассмотрен в пункте 1.5 (см. формулы (1.21) и (1.23)). Мы отметили, что погрешность интерполяции есть величина порядка O (h n + 1 ) при h → 0 .

Что касается случая 2, то увеличение числа узлов, то есть степени интерполяционного многочлена n , не всегда целесообразно, поскольку неиз-

вестно, как ведет себя максимум модуля производной M n +1 с ростом ее порядка, и функция f может вообще иметь только ограниченное число

производных.

В общем случае свойство сходимости или расходимости интерполяционного процесса зависит как от выбора на [a; b ] матрицы узлов – последовательности сеток { ( n ) }, так и от гладкости интерполируемой функции f .

Приведем некоторые результаты, иллюстрирующие этот вывод.

27

Теорема 2.2. (Фабер – Бернштейн). Для любой последовательности сеток{ ( n ) } на [a; b] существует непрерывная на [a; b] функция f , для которой соответствующая последовательность интерполяционных

многочленов {P ( n ) ( x; f )}не сходится равномерно при n → ∞ ни к ка-
	n
кой непрерывной функции.		] функ-
	Теорема 2.3 (Марцинкевич). Для любой непрерывной на [a; b
ции	f ( f С[a;b]) найдется такая последовательность сеток{ ( n ) }
на	[a; b], для которой последовательность интерполяционных многочле-
нов	{P( n ) (x; f )}будет сходиться равномерно при n → ∞ к функции	f :
	n
	Pn(n) (x; f ) f (x) на [a; b].
	n→∞
	Теорема 2.4. Если f – целая функция ( f является суммой степен-

ного ряда с бесконечным радиусом сходимости), то для любой последовательности сеток{ ( n ) } на [a; b] последовательность интерполяцион-

ных многочленов {P ( n ) ( x; f )} будет сходиться равномерно при n → ∞ к

n

функции f :

Pn(n) (x; f ) f (x)

на [a; b].

n→∞

Пример (Бернштейн). Если f ( x ) =

x

,

−1 ≤ x ≤1, то интерполя-

ционные многочлены

P ( n ) ( x;

f ) , построенные на равномерных сетках

n

( n ) = {−1 + ih , i = 0, 1, …, n, h = 2 n},

не будут сходиться при n →∞ к f ( x) =

x

ни в одной точке, кроме

x = −1, 0, 1:

P(n) (x; f ) →/ f (x) =

x

на

−

−

n

n→∞

[

1; 1]\ { 1, 0, 1}.

Замечание 2.2. Если в предыдущем примере равномерную сетку за-

~

( n )

(сеткой,

построенной по узлам, являю-

менить чебышевской сеткой

щимся корнями многочлена Чебышева Tn+1 (x) ), то интерполяционные

многочлены					P ( n ) ( x; f ) будут сходиться равномерно к					функции
					n
f ( x ) =		x		на [−1; 1]:					на [−1; 1].
					Pn(n) (x; f ) f (x) =		x
					n→∞
Среднеквадратичную сходимость с весом последовательности интер-
поляционных					многочленов {P ( n ) ( x; f )}				легко обеспечить,	выбрав на
					n
[a; b]специальную последовательность сеток{ ( n ) }.

28

	Предложение 2.1. Пусть {ψ n ( x )} – система многочленов, орто-
гональных с весом		ρ(x) > 0	на [a; b]. Пусть xk( n+1) , k = 0, 1, …, n –
корни	многочлена	ψn+1 (x) .	Тогда для последовательности сеток
( n )	= {x0( n +1) , x1( n +1) ,…, xn( n+1) } соответствующая последовательность
интерполяционных многочленов {P ( n ) ( x; f )} с весом ρ(x) будет сред-

n

неквадратично сходиться при n → ∞ к функции f :

ср

Pn(n) (x; f ) → f (x) на [a; b].

n→∞

Важное замечание 2.2. В практических вычислениях интерполяционные многочлены высокой степени ( n > 6 ) обычно не используются. Для интерполяциизаданнойфункции f используюткусочно-полиномиальныефункции.

3.Кусочно-полиномиальная интерполяция

3.1.Локально-интерполяционные формулы

Разделим отрезок [a; b]на N частичных отрезков точками

	a = x ( 0 ) < x (1 ) < … < x N = b .
Выберем на каждом j-м отрезке [x( j−1) ; x( j ) ], j =1, 2, …, N узлы ин-
терполяции x 0[ j ] < x 1[ j ] < … < x n[ jj					]	и построим для функции f ин-
терполяционный многочлен степени не выше n j :
[ j ]	[ j ]	[ j ]	,…	[ j ]		[ j ]	( x; f ) ,
Pn j	( x; x0	, x1		, x n j		; f ) = Pn j
где j – номер частичного отрезка,				n j – степень интерполяционного много-

члена на отрезке [x( j−1) ; x( j ) ].										[a; b] функ-
Совокупность этих многочленов порождает на отрезке
цию P [a ;b ]( x;			f ) , которую мы назовем локальным интерполянтом
N	f	на отрезке [a; b]:
функции
			[a;b]					[j ]	(x; f ) .	(3.1)
			PN	(x; f )			[x( j−1) ;x( j ) ] = Pn j
Таким образом, функция					P [a ;b ]( x; f )				определена на всем отрезке
							N
[a; b] и на каждом частичном отрезке совпадает с интерполяционным мно-
гочленом		[ j ]	( x ; f ) (склеена из					многочленов, интерполирующих
		Pn j
функцию	f	на частичных отрезках). Функция PN[a ; b ]( x ;								f ) не обяза-

29

тельно гладкая (даже непрерывная) в точках склейки x (1 ) , x ( 2 ) , … , x ( N −1 )

интерполяционных многочленов.	Этот способ приближения функции
f ( x ) на отрезке [a; b]называется локальной интерполяцией.
На каждом частичном отрезке [x( j−); x( j) ] погрешность локальной ин-
терполяции для гладкой функции	f можно оценить с помощью формулы
(1.12)

	max		( j )		f (x) − P[j ](x : f )		≤
x	( j−1)	≤x≤x			n j

x [x( j −) ; x( j) ], Mnj +1 =

M n j +1

(n j +1)!

max

x( j−1)≤x≤x( j )

(x( j ) − x( j −1) )n j +1 ,

(3.2)

f (nj +1) (x) .

Наиболее часто в практике используется локальная интерполянта для равноотстоящих узлов. Разделим отрезок [a; b ] на N частичных отрезков равной длины точками

x j = a + jh , j = 0 , 1, … , N , h =	b − a	.	(3.3)
	N

Выберем на каждом j-м отрезке

[x

j−1

; x

j

]

j =1, 2,

, N

узлы интерпо-

,

…

ляции

k

x j , k = x j +

h

,

k =1, 2,…, n.

(3.4)

n

Здесь расстояние между любыми соседними узлами интерполяции

равно (b − a ) (nN ) .

[x j−1 ; x j

]

f

На каждом частичном отрезке

построим для функции

интерполяционный многочлен степени не выше n

Pn[ j ]( x; x j .0 , x j .1 ,… , x j ,n ;

f )

= Pn[ j ]( x;

f ).

(3.5)

Построим на всем отрезке [a;b]локальную интерполянту PN[a;b](x; f )

PN[a ;b ]( x; f )

x [x j −1 ; x j ] = Pn[ j ]( x; f ) , j = 1, 2,…, N .

Локальная

интерполянта

P [a ;b ]( x; f )

склеена

из

многочленов

Pn[ j ]( x ; f ) ,

N

интерполирующих функцию

f

на частичных

отрезках.

Функция PN[a ;b ](x; f ) непрерывна в точках склейки x j ,

j =1, …, N −1

:

P [j ]( x

j

; f ) = P [j +1]

( x

j

; f ) = f ( x

j

).

n

n

Замечание 3.1. Если общая степень n интерполяционных многочле-

нов P [ j ]( x; f ) не зависит от номера

j частичного отрезка

[x

j−1

; x

], то в

n

j

30