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

Пусть узлы интерполяции распределены на отрезке равномерно
x_i = a + ih, i = 0, 1, … n. Обозначим шаг изменения переменной x через Δ x = h.

Введем сначала понятия конечной разности и обобщенной степени. Эти понятия используются для записи интерполяционной формулы Ньютона.

Первой конечной разностью функции y = f (x) называется выражение

Δ y = f (x + Δ x) – f (x). (4.5)

Конечная разность второго порядка определяется формулой

Δ² y = Δ(Δ y) = Δ[ f (x + Δ x) – f (x)] = f (x + 2Δ x) – 2 f (x + Δ x) + f (x). (4.6)

Используя формулу бинома Ньютона, можно вывести формулу конечной разности n-го порядка

(4.7)

где .

Пример 4.1. Найти конечные разности функции x ² с шагом Δ x = h = 1.

Решение. Δ x ² = (x + h)² – x ² = 2 xh + h ² = 2 x + 1,

Δ² x ² = Δ(2 xh + h ²) = 2(x + h) h + h ² – (2 xh + h ²) = 2 h ² = 2,

Δ³ x ² = Δ(2 h ²) = 0.

Как видим, конечная разность третьего порядка функции x ² равна нулю. Справедливо более общее утверждение:

Конечная разность (n + 1) -го порядка многочлена n-го порядка равна нулю.

Пусть функция f (x) задана своими значениями y_i = f (x_i) в равноотстоящих точках x_i = x ₀ + ih, i = 0, 1, … n.

Таблица конечных разностей функции f (x) записывается в одной из двух форм: горизонтальной или диагональной таблицы разностей. Так как конечная разность использует два значения, столбец Δ y_i содержит n значений, столбец Δ² y_i — на одно значение меньше, и так далее. Если задано n + 1 значений функции, то таблица конечных разностей содержит n столбцов, причем последний столбец содержит только одно значение. Общий вид горизонтальной таблицы конечных разностей приведен в табл. 4.1.

Таблица 4.1

xi	yi	Δyi	Δ^2yi	Δ^3yi	…	Δ ^n- ^1yi	Δ ^n yi
x0	y0	Δy0	Δ^2y0	Δ^3y0	…	Δ ^n ^-1y0	Δ ^n y0
x1	y1	Δy1	Δ^2y1	Δ^3y1	…	Δ ^n ^-1y1
…	…	…	…	…	…
x n – 2	y n – 2	Δy n – 2	Δ^2y n – 2
x n – 1	y n – 1	Δy n – 1
x n	y n

Рассмотрим горизонтальную таблицу конечных разностей на примере.

Пример 4.2. Построить таблицу конечных разностей многочлена
5 x ⁴ + 4 x ², используя его значения в точках x_i = –1 + i∙ 0,5, i = 0, 1, …10.

Решение в программе Excel. Запишем в столбце A 1: A 12 номера i точек, в столбце B 1: B 12 — значения x_i, в столбце C 1: C 12 — значения y_i, и в следующих столбцах — конечные разности Δ y_i, Δ² y_i и т.д. (Табл. 4.2). Как заполняются столбцы A 1: A 12 и B 1: B 12 видно из табл. 4.2, поясним заполнение остальной части таблицы.

Выделим диапазон B 2: B 12 и выполним команду меню «Вставка — Имя — Присвоить — x»;

Запишем в ячейку C 2 формулу =5* x ^4 + 4* x ^2 и протянем маркером заполнения ячейку C 2 до ячейки C 12;

В ячейку D 2 запишем формулу = C 3– C 2, выделим D 2 и протянем до D 11. Затем снова выделим D 2 и маркером заполнения скопируем в ячейки E 2: H 2. Далее выделим и протянем вниз поочередно ячейки: E 2 — до E 10; F 2 — до F 9; G 2 — до G 8; H 2 — до H 7. Мы увидим, что Δ⁴ y_i принимает постоянные значения, а Δ⁵ y_i = 0. Если продолжить таблицу, т.е. вычислить конечные разности старших порядков, в следующих столбцах получим нулевые значения.

Табл. 4.2

	A	B	C	D	E	F	G	H
	i	x	yi	Δyi	Δ^2yi	Δ^3yi	Δ^4yi	Δ^5yi
		-1,000	9,000	-4,392	1,872	-0,672	0,192	0,000
		-0,800	4,608	-2,520	1,200	-0,480	0,192	0,000
		-0,600	2,088	-1,320	0,720	-0,288	0,192	0,000
		-0,400	0,768	-0,600	0,432	-0,096	0,192	0,000
		-0,200	0,168	-0,168	0,336	0,096	0,192	0,000
		0,000	0,000	0,168	0,432	0,288	0,192	0,000
		0,200	0,168	0,600	0,720	0,480	0,192
		0,400	0,768	1,320	1,200	0,672
		0,600	2,088	2,520	1,872
		0,800	4,608	4,392
		1,000	9,000

Обобщенной степенью n-го порядка числа x называется произведение

x ^{[ n ]} = x (x – h)(x – 2 h)… [ x – (n – 1) h ], (4.8)

где h = const, а для n = 0 полагают x ^[0] = 1.

Найдем конечные разности для обобщенной степени.

Δ x ^{[ n ]} = (x + h)^{[ n ]} – x ^{[ n ]} =

= (x + h) x (x – h)(x – 2 h)… [ x – (n – 2) h ] – x (x – h)(x – 2 h)… [ x – (n – 1) h ] =

= x (x – h)(x – 2 h)… [ x – (n – 2) h ]{ (x + h) – [ x – (n – 1) h ]} = nh x ^{[ n – 1]}.

Мы получили следующую важную формулу

Δ x ^{[ n ]} = nh x ^{[ n – 1]}. (4.9)

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

Δ ^kx ^{[ n ]} = n (n – 1)…[ n – (k – 1)] h^kx ^{[ n – k ]}. (4.10)

Выведем первую интерполяционную формулу Ньютона. Найдем многочлен P_n (x), удовлетворяющий условиям P_n (x_i) = y_i для i = 0, 1, …, n. Будем искать многочлен P_n (x)в следующем виде

P_n (x) = a ₀ + a ₁(x – x ₀) + a ₂(x – x ₀)(x – x ₁) + … a_n (x – x ₀)(x – x ₁)…(x – x_n) =

= a ₀ + a ₁(x – x ₀)^[1] + a ₂(x – x ₀)^[2] + … a_n (x – x ₀)^{[ n ]}.

Из условия P_n (x ₀) = y ₀ следует a ₀ = y ₀.

Найдем первую конечную разность многочлена P_n (x):

Δ P_n (x) = a ₁ h + 2 ha ₂(x – x ₀)^[1] + … na_n (x – x ₀)^{[ n – 1]}.

Отсюда при x = x ₀ получим Δ P_n (x ₀) = a ₁ h = Δ y ₀, т.е. a ₁ = Δ y ₀/ h. Аналогично можно получить общую формулу коэффициентов многочлена Ньютона

. (4.11)

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

. (4.12)

С помощью замены переменной q = (x – x ₀)/ h первую интерполяционную формулу Ньютона можно представить в виде:

. (4.13)

Аналогичными рассуждениями выводится вторая интерполяционная формула Ньютона:

, (4.14)

которая с помощью замены q = (x – x_n)/ h приводится к виду

. (4.15)

Первая интерполяционная формула Ньютона применяется для интерполирования вблизи начала таблицы (около x ₀), а вторая — для интерполирования вблизи конца таблицы (около x_n).

Пример 4.3. Задана таблица значений функции y_i = f (x_i):

i
xi	2,0	2,5	3,0	3,5	4,0
yi			5,5	5,7	5,8

Вычислить значение функции в точке x = 2,3.

Решение в программе Excel. Очевидно, что шаг интерполяции h = 0,5.

Вычислим сначала таблицу разностей, а затем — значение первой интерполяционной формулы Ньютона.

Запишем исходные данные в ячейки A 1: A 3 и B 1: B 2, как показано в табл. 4.3. Присвоим ячейкам B 1, B 2, B 3 имена h, x, q с помощью команды «Вставка — имя — Присвоить».

В ячейку B 3 запишем формулу =(x – $B$6)/ h.

Ячейки A 5: G 5, A 6: A 13, B 6: B 10 и С 6: С 10 заполним как в таблице 4.3. В ячейку D 6 запишем формулу = C 7– C 6. Затем выделим ячейку D 6 и маркером заполнения протянем вниз до ячейки D 9.

Снова выделим D 6 и протянем вправо до G 6.

Аналогично протянем ячейку E 6 до E 8 и ячейку F 6 до F 7. В табл. 4.4 показаны формулы, которые нужно ввести в ячейки диапазона B 12: G 13.

В ячейке G 13 получим результат f (2,3) = 4,6712.

Табл. 4.3

	A	B	C	D	E	F	G
	h=	0,5
	x=	2,3
	q=	0,6
	i	xi	y	Δy	Δ^2y	Δ^3y	Δ^4y
				1,000	-0,500	0,200	0,000
		2,5		0,500	-0,300	0,200
			5,5	0,200	-0,100
		3,5	5,7	0,100
			5,8
	Коэффициенты		0,6	-0,12	0,056	-0,0336	f(x)
	Слагаемые		0,6	0,06	0,0112	2,98E-17	4,6712

Табл. 4.4

	B	C	D	E	F	G
		=q	=C12*(q-1)/2	=D12*(q-2)/3	=E12*(q-3)/4	f(x)
	=B12*C6	=C12*D6	=D12*E6	=E12*F6	=F12*G6	=СУММ(B13:F13)

Составим программу на языке C ++ для вычисления значения таблично заданной функции с помощью первой интерполяционной формулы Ньютона в форме (4.13):

Дата добавления: 2015-07-20