Schisla_1

pk(xi) =

Если все узлы интерполяции xi, i = 1, 2, ..., n различны, то определитель системы (3.1) (определитель Вандермонда) отличен от нуля. Это означает, что существует единственный интерполяционный многочлен g(x) степени n − 1, построенный по узлам xi, i = 1, 2, ..., n. Многочисленные интерполяционные многочлены (формулы), построенные для одного выбранного набора узлов xi, — различные формы записи одного и того же многочлена. Такие формулы удобны, а иногда и необходимы, при построении различных численных методов и алгоритмов, реализующих эти методы. Обычно слово ”полиномиальная“ опускается, и, когда говорят интерполяция, имеют в виду полиномиальную интерполяцию.

3.3Интерполяционный многочлен Лагранжа

Сначала построим фундаментальные многочлены интерполяции (базисные многочлены Лагранжа) pk(x) степени n−1, ассоциированные с множеством узлов xi, i = 1, 2, . . . , n. Многочлены pk(x) удовлетворяют условиям

{ 0, если i ≠ k,

(3.2)

1, если i = k.

Из (3.2) следует, что известны все корни многочлена pk(x), и его можно записать в виде

pk(x) = C(x − x1)...(x − xk−1)(x − xk+1)...(x − xn).

Константа C определяется из условия pk(xk) = 1, для фундаментальных

многочленов получается выражение

(x − x1)...(x − xk−1)(x − xk+1)...(x − xn)

n

x − xi

pk(x) =

=

(xk

x1)...(xk

xk

1)(xk

xk+1)...(xk xn)

=1;i=k

xk

xi

−

−

−

−

−

i

−

∏̸

где k=1, 2, ..., n. С помощью системы многочленов pk(x), k = 1, 2, ..., n

искомый интерполяционный многочлен Ln(x) записывается в виде

n	n		n		−
∑	∑	i	∏̸	x
Ln(x) = f(xk)pk(x) =	f(xk)			xk	− xi		.	(3.3)
k=1	k=1		=1;i=k			xi

21

Для этого многочлена степени n−1 выполняются условия интерполяции

∑n

Ln(xi) = f(xk)pk(xi) = f(xi) i = 1, 2, ..., n.

k=1

Построенный многочлен называется интерполяционным многочленом Лагранжа.

Единственность многочлена Лагранжа.

Единственность многочлена Ln(x) доказывается, как обычно, от противного. Пусть L1n(x) и L2n(x) — два различных интерполяционных многочлена Лагранжа, т.е. выполняются равенства

L1n(xi) = f(xi), L2n(xi) = f(xi) i = 1, 2, ..., n.

Степень многочлен P (x) = L1n(x) −L2n(x) не более n −1, а у него n корней, так как P (xi) = L1n(xi) − L2n(xi) = 0, i = 1, 2, ..., n. Многочлен степени не более n − 1 не может иметь n корней, значит P (x) = L1n(x) − L2n(x) ≡ 0.

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

Пусть f(x) имеет на [a, b] все непрерывные производные до n порядка включительно. Оценим разность f(x) − Ln(x) для значения x [a, b],

отличного от узлов интерполяции.	Рассмотрим функцию r(x) = f(x)		−
	n
	∏k	(x −xk). Константу D выберем
Ln(x) −Dωn(x), где D = const., ωn(x) =
	=1

так, чтобы в точке x [a, b], отличной от узлов интерполяции, функция

r(x)		нуль r(x) = 0. Очевидно,
	обращалась в	e		eD =	f(x) − Ln(x)		.	(3.4)
						eωn(x) e
При таком значении			D	функция		r(x) обращается в нуль на [a, b] в n+1 –
						e

ой точке (n узлов и xe). Согласно теореме Ролля (Если непрерывно дифференцируемая функция на концах отрезка принимает одинаковые значения, то найдется, по крайней мере, одна точка внутри отрезка, в которой её производная равна нулю) получаем цепочку утверждений:

22

r′(x) имеет на [a, b], по крайней мере, n нулей, r′′(x) имеет на [a, b], по крайней мере, n − 1 нуль,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

r(n)(x) имеет на [a, b], по крайней мере, один нуль.

Нуль n - ой производной обозначим ξ(xe). Формула для n - ой производной функции r(x) имеет вид

r(n)(x) = f(n)(x) − D n!

В точке ξ(xe) эта производная обращается в нуль

r(n)(ξ(xe)) = f(n)(ξ(xe)) − D n! = 0,

и для константы D получается выражение

D = f(n)(ξ(xe)). n!

Из этого выражения и (3.4) следует

f(xe) − Ln(xe) = f(n)(ξ(xe))ωn(xe). n!

В силу произвольности xe можно записать

	f(x) − Ln(x) =			f(n)(ξ(x))				(3.5)
							ωn(x).
					n!
Если обозначить	M	max f(n)(x)
		n = a	x b |		|, то из (3.5)) получается оценка
погрешности интерполяции			≤ ≤
		|f(x) − Ln(x)| ≤			Mn	|ωn(x)|.		(3.6)
					n!

Обычно вычислить и оценить |f(n)(x)| очень трудно или вообще невозможно, поэтому полученная оценка в очень редких случаях может быть использована при практическом счете. Тем не менее, эта оценка полезна для понимания внутренней природы возникающих ошибок. Например, один вывод можно сделать сразу: увеличивать количество точек, используемых в

23

∑k

f(xi, xi+1, ..., xi+k) =

j=0

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

Другая форма записи интерполяционного многочлена Лагранжа (он единствен), более удобна при изменении количества узлов интерполяции.

3.4Интерполяционный многочлен Ньютона.

Сначала введем понятие разделенной разности.

Определение:

Разделенной разностью нулевого порядка называется значение функции f(xi) в точке xi.

Разделенная разность первого порядка определяется выражением

f(xi, xi+1) = f(xi+1) − f(xi). xi+1 − xi

Разделенная разность второго порядка определяется выражением

f(xi, xi+1, xi+2) = f(xi+1, xi+2) − f(xi, xi+1) xi+2 − xi

. . . . . . . . . . . . . . . .

Разделенная разность k -го порядка выражается через разделенные разности (k-1) -го порядка, следующим образом

f(xi, xi+1, . . . , xi+k) = f(xi+1, xi+2, ..., xi+k) − f(xi, xi+1, ..., xi+k−1).

xi+k − xi

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

f(xi+j)

∏k

(3.7)

(xi+j − xi+l)

l=0;l≠j

Эта формула доказывается методом математической индукции (докажите сами).

24

Выразим f(x) − Ln(x) через разделенные разности

n

n

x − xl

f(x)

−

L

(x) = f(x)

−

f(x

)

=

n

j

xj

−

xl

j=1

l

=1;l=j

∑

∏̸

n

f(x)

n

(xj

f(xj)

(xj

= j=1(x − xj)

n

(x xj)

+ j=1

x)

n

xl) =

∏

j=1

−

∑

−

l=1;l=j

−

̸

∏

∏

= f(x, x1, x2, . . . , xn) ωn(x).

	Таким образом, справедливо соотношение
	f(x) − Ln(x) = f(x, x1, x2, . . . , xn) ωn(x).			(3.8)
	Из (3.5) и (3.8) получается выражение для разделенной разности
	f(x, x1, x2, . . . , xn) =	f(n)(ξ(x))	,	(3.9)
		n!

где ξ(x) некоторое число, находящееся между узлами x, x1, x2, . . . , xn.

Если в этой формуле все узлы x, x1, x2, ..., xn стягивать в одну точку,

например, в x, то f(x, x1, x2, ..., xn) → f(n)(x), т.е. разделенную разность n!

можно понимать как обобщение понятия производной в дискретном (численном) анализе.

Свойства разделенных разностей.

1. Вычисление разделенной разности является линейной операцией. Действительно, из формулы (3.7) следует, что

(αf1 + βf2)(x1, x2, . . . , xn) = αf1(x1, x2, . . . , xn) + βf2(x1, x2, . . . , xn),

где α и β - константы.

2.Разделенная разность не меняется при любой перестановке своих аргументов (см. формулу (3.7)).

3.Если функция f(x) является многочленом степени n (f(x) = Pn(x)), то ее разделенная разность n - ого порядка постоянна, а разделенная разность n + 1 - ого порядка обращается в нуль (см. формулу (3.9)).

25

Третье свойство разделенных разностей позволяет выбрать для заданного значения x такую степень (число узлов k) интерполяционного многочлена, чтобы погрешность интерполяции в окрестности точки x была мала. Если разделенные разности, вычисленные для значения x, до l-ого порядка убывают, а затем начинают расти, то число узлов k должно быть не более l. Разделенные разности функции записаны в таблице 1.

x1	f(x1)
		f(x1, x2)
x2	f(x2)		f(x1, x2, x3)
		f(x2, x3)
. . .	. . .	. . .	. . .	. . .
					f(x1, x2, . . . , xn)
. . .	. . .	. . .	. . .	. . .
xn−1	f(xn−1)		f(xn−2, xn−1, xn)
		f(xn−1, xn)
xn	f(xn)

Таблица 1.

Интерполяционная формула Ньютона с разделенными разностями

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

Ln(x) = L1(x) + (L2(x) − L1(x)) + (L3(x) − L2(x)) + ... + (Ln(x) − Ln−1(x))

Каждый из многочленов Lm(x) (m = 1, ..., n) построен по узлам xi, i = 1, ..., m, т.е. выполняются равенства

Lm(xi) = f(xi), i = 1, ..., m.

Выражение Lm(x) − Lm−1(x) является многочленом степени m − 1, все корни которого известны, так как

Lm(xi) − Lm−1(xi) = 0, i = 1, ..., m − 1.

26

Это означает, что

m−1
Lm(x) − Lm−1(x) = Am−1 ∏1	(x − xi) = Am−1ωm−1(x),

где Am−1 — пока неизвестная постоянная. Если положить x = xm, то последняя формула примет вид

Lm(xm) − Lm−1(xm) = Am−1ωm−1(xm).

Из инвариантности разделенных разностей относительно перестановки аргументов и (3.8) следует

Lm(xm) − Lm−1(xm) = f(xm) − Lm−1(xm) = f(xm, x1, x2, ..., xm−1) ωm−1(xm) = = f(x1, x2, ..., xm−1, xm) ωm−1(xm).

Выражение для коэффициента Am−1 = f(x1, x2, ..., xm) получается при сравнении двух последних формул, и тогда

Lm(x) − Lm−1(x) = f(x1, x2, ..., xm) ωm−1(x).

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

Ln(x) = f(x1) + f(x1, x2)(x − x1) + f(x1, x2, x3)(x − x1)(x − x2) + ...+ +f(x1, ..., xn)(x − x1)(x − x2)...(x − xn−1)

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

Коэффициенты интерполяционной формулы Ньютона находятся в таблице 1 вдоль верхней диагонали. Добавление нового узла или удаление последнего узла не требуют пересчета предыдущих коэффициентов.

Формулу Ньютона с разделенными разностями можно понимать как обобщение формулы Тейлора в дискретном анализе: разделенные разности

— обобщение производных, а ωn(x) — обобщение степени бинома. Можно показать, что, если узлы xi (i = 1, ..., n) стягиваются в одну точку, то в пределе формула Ньютона принимает вид формулы Тейлора.

27

3.5Интерполирование с кратными узлами (постановка задачи)

Пусть в каждом узле xi [a, b] (i = 1, 2, . . . , n) известны не только значения некоторой функции f(x), но и значения ее производных f(k)(x),

k = 1, 2, . . . , mi − 1. Говорят, что Qs(x) — интерполяционный многочлен

∑m

Эрмита степени s − 1 (s = mi) с кратными узлами, если для него вы-

i=1

полняются условия

Qs(xi) = f(xi), Qs′(xi) = f ′(xi), . . . , Q(smi−1)(xi) = f(mi−1)(xi), i = 1, 2, . . . , n.

Кратностью узла xi называется значение mi.

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

Пусть узлы xi (i = 0, 1, . . . , n − 1), в которых заданы значения функции f(xi) = yi, равноотстоящие, т. е. xi+1 − xi = h = const. для любого i = 0, 1, ..., n − 2. В этом случае вместо разделенных разностей вводятся конечные разности.

Конечные разности и их свойства.

Определение:

Конечной разностью первого порядка называется выражение

∆yi = yi+1 − yi.

Конечной разностью второго порядка называется

∆2yi = ∆yi+1 − ∆yi.

Конечной разностью k-ого порядка называется

∆kyi = ∆k−1yi+1 − ∆k−1yi.

Иногда конечная разность k-ого порядка ∆kyi обозначается k+1yi, δkyi+ 12 или yik+ 12 .

28

С помощью метода математической индукции можно установить связь между разделенными и конечными разностями

					∆kyi
	f(xi, xi+1, ..., xi+k) =						.
					k! hk
Из этого равенства и формулы (3.9) получаем
	f(k)(ξ) ∆kyi			f(k)(ξ) =		∆kyi
		=						,
	k!		k!hk			hk

где ξ находится между узлами xi, xi+1, . . . , xi+k.

Конечные разности, также как и разделенные, можно понимать как обобщение понятия производной в дискретном анализе.

Свойства конечных разностей определяются свойствами разделенных разностей:

1. Вычисление конечной разности — линейная операция

∆k(αy + βz)i = α∆kyi + β∆kzi.

2. Если функция f(x) является полиномом n - ой степени, то конечные разности n – ого порядка постоянны, а конечные разности n + 1 – ого порядка равны нулю.

Оценку погрешности интерполяционного многочлена Ln(x), построенного по равноотстоящим узлам xi (i = 0, 1, ..., n − 1), можно записать в виде

					|f(x) − Ln(x)| ≤ |C| Mn hn,
где	M	n	= max f(n)(x)		|,	t =	x − x0	,	C =	t(t − 1)...(t − n + 1)	.
			a x b	|			h			n!
			≤ ≤

Из этой оценки следует, что точность интерполяции в фиксированной точке x можно увеличить, если:

1.уменьшить h — шаг таблицы;

2.увеличить n —число узлов (обычно шаг таблицы h < 1);

3.уменьшить значение константы C.

Может оказаться, что первый из указанных способов невозможен, на-

пример, таблица получена экспериментально, и её шаг нельзя изменить.

29

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

Константа C становится меньше, если выбрать ближайшие узлы к заданной точке x.

Пусть задана таблица значений функции f(xei) для большого числа равноотстоящих узлов xei, i = 0, 1, ..., N (N n). Если интерполяционный многочлен строится для значения x, которое находится между узлами в начале таблицы, то ближайшими к x узлами являются xi = xei, i = 0, 1, ..., n−

1. Для конца таблицы ближайшие к x — узлы xi = xeN−i, i = 0, 1, ..., n − 1 . Если же значение x находится среди узлов в середине таблицы, то в качестве нулевого узла интерполяции x0 (ближайшего к x) выбирается значение xbi, где индекс i равен целой части числа (x − xe0)/h + 0.5. Остальные узлы выбираются из значений x±k = xei±k, очевидно, значение k зависит от n. Удобно ближайший к точке узел интерполяции обозначить x0. Тогда, если x0 > x > x1, то ближайшими к x являются узлы x0, x1, x−1, x2, x−2, ...,

если же x−1 > x > x0, то — x0, x−1, x1, x−2, x2, ....

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

3.7Интерполяционные формулы Ньютона для равноотстоящих узлов

1. Интерполяционная формула Ньютона для начала таблицы

(интерполяция вперед)

В этом случае в качестве узлов выбираются значения x0, x1, ..., xn−1 и

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

30