part2 / vm

Интерполяционный многочлен в форме Ньютона. Пусть узлы x0, x1,…, xn

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

ln x f x0 x x0 f x0 ; x1 x x0 x x1 f x0 ; x1 ; x2		(4.11)
x x0 x x1 x xn 1 f x0 ; x1 ; ; xn

является интерполяционным, т.е.

		ln x j	f x j ,				j 0,1, , n. (4.12)
Покажем, что равенства (4.12)			выполняются для n=1:
ln x0 f x0									f x1 f x0
l		x f	x			x x					f x .
	n			0			0
		1				1					1

x1 x0

Для n>1 доказательство проводится по индукции.

Многочлен (4.11) называется интерполяционным многочленом в форме

Ньютона. Он тождественно совпадает с интерполяционным многочленом в форме Лагранжа, т.е.

ln(x)≡Ln(x).

Случай равноотстоящих узлов. Пусть xk=x0+kh, h>0, k=0, 1, …, n; f(xk)=yk.

Тогда, учитывая соотношение (4.10) для конечной и разделенной разности и

вводя безразмерную переменную					t	x x0			, перепишем многочлен (4.11) в виде
							h
ln x ln x0	th y0	t	y0	t	t 1		2 y0		t t 1 t n 1	n y0	. (4.13)
			1!				2!			n!

Этот многочлен называется интерполяционным многочленом Ньютона интерполирования «вперед». Здесь начальное значение t=0 расположено в крайнем слева узле x0. Многочлен (4.13) используется при вычислениях в начале таблиц и для экстраполяции значений f (x) в точках, лежащих левее x0

(при t<0).

Интерполяционный многочлен с узлами x–n, x–(n–1),…, x–1, x0, где x–k=x0–kh,

имеет вид

ln x ln x0 th y0	t	y 1	t t 1	2 y 2	t t 1 t n 1	n y n . (4.14)
		1!		2!		n!

61

[a,b],

x f x Ln x K n x ,

и называется интерполяционным многочленом Ньютона для интерполяции

«назад». Для этого многочлена начало отсчета t=0 расположено в крайнем правом узле x0. Он используется при интерполяции в конце таблицы (t<0) и для экстраполяции правее точки x0 (t>0). Чаще всего интерполяционные формулы

(4.13) и (4.14) для равномерной сетки узлов применяют при t [ 1,1].

Отметим, что для одной и той же системы интерполяционных узлов формулы (4.11), (4.13), (4.14) описывают один и тот же интерполяционный многочлен, ранее записанный в форме Лагранжа.

Оценка погрешности интерполяции. Погрешность приближения функции интерполяционным многочленом Лагранжа (4.8) описывается разностью

f(x)–Ln(x).

Оценим погрешность интерполяции в точке x*. Будем предполагать, что f C[na,b1] . Рассмотрим вспомогательную функцию

(4.15)

где ωn(x)=(x–x0)…(x–xn); K – постоянная. Очевидно, что φ(xk)=0, k=0, 1, …, n. Выберем K так, чтобы φ(x*)=0, x*≠ xk, k=0,1,…,n. Имеем

K	f x* L			n	x*		.
		n	x*

Тогда функция φ(x) обращается в нуль по крайней мере в (n+2) точках интервала [a,b]: x*, x0, x1, …, xn. Согласно теореме Ролля [1] φ'(x) имеет не менее (n+1) нулей на [a,b], φ'' (x) – не менее n нулей и т.д. Для функции φ(n+1)(x)

существует по крайней мере одна точка в которой φ(n+1)(ξ)=0.

Дифференцируя равенство (4.15) (n+1) раз, получаем

(n 1) x f (n 1) x K n 1 !.

Полагая x=ξ, имеем	K	f (n 1)	.	Из (4.15)				следует, что погрешность
		n 1 !
приближения в точке x* можно представить в виде
	f x L x				f (n 1)			x .
							n
		n			n 1 !

62

Отсюда получаем выражение для оценки погрешности приближения в точке x*

f x L

x

max

f (n 1) x

x

n

n 1 !

n

[a,b]

и оценки погрешности интерполяции на интервале

max

f x L

x

max

f (n 1) x

max

x

. (4.16)

n

n 1 !

n

[a,b]

[a,b]

[a,b]

Поскольку многочлены Лагранжа и Ньютона отличаются только формой записи, оценка погрешности (4.16) верна для всех формул.

Величину |ωn(x)|, входящую в оценку погрешности (4.16), можно минимизировать за счет выбора узлов интерполяции. Эта задача решается с помощью многочленов Чебышева: в качестве узлов интерполяции на интервале

[a,b] выбираются корни многочлена Чебышева степени (n+1) [2], т.е. узлы

x			a b		b a	cos 2k 1 ,	k 0,1, , n.
	k
		2		2		2 n 1

При таком выборе узлов интерполяции оценка (4.16) принимает вид

max

f x L

x

max

f (n 1) x

b a n 1

.

n

n 1 !

22n 1

[a,b]

[a,b]

О сходимости интерполяционного процесса. На практике часто возникает вопрос: можно ли, выбрав достаточное количество узлов интерполяции,

приблизить интерполируемую функцию с заданной степенью точности? Ответ,

вообще говоря, отрицателен.

Рассмотрим на интервале [a,b] последовательность систем узлов интерполяции

x0(0) , x0(1) , x1(1) , , x0(n) , x1(n) , , xnn , (4.17)

Сопоставим последовательности (4.17) последовательность интерполяционных многочленов функции f(x)

L0(x), L1(x),…, Ln(x)

такую, что многочлен Li(x) соответствует системе узлов x0(i) , x1(i) , , xi i .

Интерполяционный процесс для функции f(x) называется сходящимся, если

63

Ln x f x 0.

n

Процесс сходится равномерно, если

		x f x		0.
max	Ln
[a,b]				n

Сходимость и расходимость интерполяционного процесса зависит как от выбора последовательности систем узлов (4.17), так и от гладкости функции f(x). Например, для функции f(x)=|x|, рассматриваемой на интервале [–1,1],

процесс интерполяции не сходится. На рис.4. 1 представлен график многочлена

L9(x) при x [0,1] , построенного на интервале [–1,1] по равноотстоящим узлам.

Интерполяция сплайнами. С увеличением числа узлов интерполяции и,

соответственно, вычисленных в них значениях функции f(x) естественно желание использовать дополнительную информацию о поведении приближаемой функции и получить более качественное приближение. Если число узлов превышает 5 – 7, то решение поставленной задачи посредством интерполяционных многочленов, как правило, не приводит к успеху. Это объясняется как сильным накоплением ошибок при вычислении интерполяционных многочленов высоких степеней, так и отсутствием сходимости интерполяционного процесса в целом. В этом случае целесообразно применять кусочно–многочленную интерполяцию, используя

64

многочлены невысоких степеней (первой, второй, третьей). Наиболее часто применяют интерполяцию сплайнами.

Пусть на интервале [a,b] задана непрерывная функция f(x). Рассмотрим набор узлов a<x0<x1<…<xN=b и обозначим f(xi)=fi, i=0, 1, …, N. Сплайном Sn,ν(x) порядка n дефекта ν, соответствующим данной функции f(x) и узлам x0, x1, …, xN, называется функция, удовлетворяющая следующим условиям:

а) на произвольном подынтервале [xi–1,xi], i=1,…, N, функция Sn,ν(x)

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

б) функция Sn,ν(x) имеет m непрерывных производных на [a,b] (ν=n–m);

в) Sn,ν(xi)= f(xi), i=0,1,…,N.

Последнее условие является условием интерполирования и определяет название сплайна: интерполяционный сплайн (рис. 4.2). Примером простейшего сплайна является ломанная. Степень такого сплайна равна единице, дефект также равен единице. Наиболее широко применяются сплайны третьей степени, имеющие на интервале [a,b] одну или две непрерывные производные (дефекта 2 или 1, соответственно). Сплайн дефекта 1 называют кубическим.

Рассмотрим процедуру построения интерполяционного кубического сплайна, удовлетворяющего условиям а) – в), и докажем его существование и единственность.

На каждом из отрезков [xi–1,xi], i=1,…, N будем искать сплайн S3,1(x)=Si(x) в виде многочлена третьей степени

65

Si(x)=ai+bi(x–xi–1)+ci(x–xi–1)2+di(x–xi–1)3 (4.18)

Где ai, bi, ci, di – коэффициенты, подлежащие определению (i=1, …, N).

Построим систему алгебраических уравнений для вычисления искомых

коэффициентов. Из выражения (4.18) для i–го звена сплайна получаем

a

i

S

x

i 1

,

b S ' x

i 1

,

i

i

i

2c

i

S '' x

i 1

, 6d

i

S

''' x

i 1

.

i

i

Учитывая условия интерполирования в), имеем ai=fi–1, i=0, 1, …, N, (4.19)

ai+bi(xi–xi–1)+ci(xi–xi–1)2+di(xi–xi–1)3 =fi. (4.20)

Далее требования непрерывности первой и второй производных сплайна

S3,1(x) приводят к соотношениям

S ' x		S '	x		,
i	i	i 1		i
S '' x		S ''		x	,	i 1,2,.., N 1.
i	i	i 1		i

Подставляя выражение (4.18) для сплайна и обозначая xi–xi–1=hi, получаем

2h c 3h2 d			i	b			b , i 1,2, , N 1, (4.21)
i	i	i			i 1			i
	3hi di ci 1				ci ,			i 1,2, , N 1. (4.22)
Соотношения (4.19)	–	(4.22)				составляют систему 4N–2 алгебраических

уравнений относительно 4N неизвестных ai, bi, ci, di, i=0, 1, …, N. Два недостающих уравнения обычно задаются в виде ограничений на значения сплайна и его производных на концах интервала и называются граничными условиями. Наиболее употребительными являются следующие три условия.

1. Если известны значения f’ в точках x0 и xN, то естественно положить

S '	x	0	f ' ,	S '	x	N	f '
1			0	N			N

Подставляя выражение для сплайна, получаем два уравнения

b		f ' ,
1		0								(4.23)
b	N	2c	N	h	N	3d	N	h2	f ' .
								N	N

Полученный в результате решения системы уравнений (4.19)–(4.23) сплайн называют фундаментальным интерполяционным кубическим сплайном.

2. Если в граничных точках интервала известно значение f'', то можно задать граничные условия вида

66

S '' x

0

f

'' , S ''

x

N

f ''

1

0

N

N

или

2c

f '' ,

1

0

2c

N

6d

N

h

N

f

'' .

N

5. Так называемая интерполяция естественными сплайнами

получается из нулевых граничных условий

f

'' f

''

0,

0

N

т.е.

2c1

0, (4.24)

2cN 6dN hN 0. (4.25)

Такие граничные условия приводят к простейшей системе уравнений для

искомых коэффициентов. Однако следует заметить, что искусственное наложение этих условий на значения сплайна в граничных точках дает погрешность приближения порядка h2 и замедляет сходимость процесса интерполяции сплайнами на концах интервала.

Покажем, что получаемые системы уравнений имеют единственное решение. Выберем для простоты граничные условия (4.24) и (4.25). Из соотношений (4.19) определяются все коэффициенты ai, i=1, … , N. Исключим последовательно из уравнений (4.21), (4.22) и (4.25) переменные di, bi, i=1, …,

N–1 и получим систему N уравнений относительно коэффициентов ci, i=1, … ,

N.

Из (4.22) и (4.25) имеем

d			ci 1 ci			,	i 1, 2, , N 1,
	i
				3hi
d				cN	.
	N
				3hN
Подставляя значения ai		и di в соотношения (4.20), можем выразить

коэффициенты bi:

67

b

fi fi 1

hi

c

2c

,

i 1,2, , N 1,

i 1

i

hi

3

i

b

f N f N 1

2hN cN

.

N

hN

3

Подстановка полученных выражений для di и bi в (4.21) дают искомую систему уравнений:

hi 1ci 1 2 hi 1 hi ci

f

i

f

i 1

f

i 1

f

i 2

hi ci 1

3

hi

hi 1

,

i 2,3, , N 1, (4.26)

c1 0,

(4.27)

2 hN 1

cN

f

N

f

N 1

f

N 1

f

N 2

hN 1cN 1

hN

3

.

(4.28)

hN

hN 1

Соотношения (4.26)–(4.28) определяют трехдиагональную систему N

линейных алгебраических уравнений для N неизвестных. Матрица системы имеет диагональное преобладание, т.е. в каждой строке модуль диагонального элемента превосходит сумму модулей остальных элементов. Из теории матриц известно, что матрица такого вида невырождена, т.е. система (4.26)–(4.28)

имеет единственное решение.

Это доказывает единственность интерполяционного сплайна.

О сходимости процесса интерполяции кубическими сплайнами.

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

f(x) – Sn,ν(x)

зависят от сетки интерполяционных узлов. Для простоты ограничимся рассмотрением случая равномерной сетки xi=x0+ih, h>0, i=0,1,…,N. Обозначим через S1,3(x,N) сплайн для f(x), построенный на этой сетке узлов. Приведем без доказательства следующую теорему [3].

Теорема. Пусть функция f C[4a,b] и в качестве граничных условий выбраны условия 1 или 2. Тогда имеют место оценки

max f k x S3,k1 x, N h4 k max f IV x , (4.29)
[a,b]	[a,b]

где k=0,1,2.

68

Из оценок (4.29) следует, что при h→0 (т.е. при N→∞) соответствующие последовательности сплайнов и их производных S3,k1 x, N сходятся соответственно к функциям f(k)(x), k=0, 1, 2.

4.2 Аппроксимация функций в среднеквадратичной метрике.

При построении среднеквадратичных приближений обычно рассматривают три пространства: пространство En+1 функций, заданных своими табличными значениями на множестве точек x0, x1, …, xn, пространство C[a,b] непрерывных функций, заданных на интервале [a,b] и пространство L2(a,b) интегрируемых с квадратом функций на интервале (a,b), т.е. функций, для которых выполняется неравенство (1.12). Способы введения соответствующих скалярных произведений, норм и метрик описаны в пунктах 1.2, 1.3, 1.5.

Линейно независимые системы	в пространстве	со скалярным
произведением. Пусть F – пространство со скалярным произведением.
Линейная независимость системы элементов f1, f2,…, fn		пространства F

устанавливается при помощи определителя Грама, который имеет вид

f1 , f1 f1 , f 2 f1 , f n

G f1 , f 2 , , f n f 2 , f1 f 2 , f 2 f 2 , f n . (4.30)

f n , f1 f n , f 2 f n , f n

Имеет место следующее утверждение.

Теорема. Система элементов f1, f2,…, fn из пространства F линейно зависима тогда и только тогда, когда определитель Грама этой системы равен нулю.

Доказательство. Необходимость. Пусть система элементов f1, f2,…, fn

линейно зависима. Покажем, что определитель G(f1, f2,…, fn) равен нулю. Из линейной зависимости элементов f1, f2,…, fn следует, что существуют такие числа α1, α2,…, αn, среди которых есть отличные от нуля, что

α1f1+ α2f2+…+ αn fn=0. (4.31)

69

Умножая равенство (4.31) справа последовательно на fk, k=1, 2, …, n,

получаем

α1‹f1, fk›+ α2 ‹f2, fk›+…+ αn ‹fn, fk›=0, k=1, 2, …, n. (4.32)

Рассмотрим соотношение (4.32) как систему линейных уравнений относительно неизвестных αi, i=1, 2, …, n. Учитывая предположение относительно αi, заключаем, что система уравнений (4.32) имеет нетривиальное

(ненулевое) решение. Следовательно, определитель системы (4.32),

являющийся определителем Грама G(f1, f2,…, fn) равен нулю.

Достаточность. Пусть определитель G(f1, f2,…, fn)=0. Покажем, что система элементов f1, f2,…, fn линейно зависима. Рассмотрим систему линейных уравнений

‹f1, fk›β1 + ‹f2, fk›β2 +…+ ‹fn, fk›βn=0, k=1,2,…,n, (4.33)

относительно β1, β2,…, βn. Поскольку определитель этой системы равен нулю,

то она имеет ненулевое решение, т.е. среди чисел βi, i=1, 2, …, n, имеются отличные от нуля. Умножим каждое k – е уравнение системы (4.33) на βk и

сложим полученные соотношения. Имеем

n	n
i fi , k f k		0
i 1	k 1
или
n	n
	k f k , k f k	0.
k 1	k 1

n

В силу аксиом скалярного произведения k f k 0. Учитывая, что среди

k 1

чисел βk, i=1, 2, …, k, имеются ненулевые, приходим к заключению о линейной зависимости системы элементов f1, f2, …, fn.

Ортогональные и ортонормированные системы элементов. Два элемента f

и g пространства со скалярным произведением называются ортогональными,

если их скалярное произведение равно нулю, т.е. ‹f,g›=0. Элемент f называется нормированным, если ||f||=1. Конечную или бесконечную систему элементов называют ортонормированной, если любые два ее элемента ортогональны и

70