2. Интерполяция по Ньютону

Дана табличная функция:

i
0
1
2
..	..	..
n

Точки с координатами называются узловыми точками или узлами.

Количество узлов в табличной функции равно N=n+1.

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

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

где n – степень многочлена,

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

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

Пусть в узлах

известны значения функции . Предположим, что среди точек , , нет совпадающих. Разделенными разностями первого порядка называются отношения

, ,.

Будем рассматривать разделенные разности, составленные по соседним узлам, т. е. выражения

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

,

,

Таким образом, разделённая разность -го порядка на участке может быть определена через разделённые разности -го порядка по рекуррентной формуле:

где , , - степень многочлена.

Максимальное значение равно . Тогда и разделенная разность n-го порядка на участке равна

т.е. равна разности разделенных разностей -го порядка, разделенной на длину участка .

Разделенные разности

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

При вычислении разделенных разностей принято записывать их в виде таблицы

■

Разделенная разность -го порядка следующим образом выражается через значения функции в узлах:

. (1)

Эту формулу можно доказать методом индукции. Нам потребуется частный случай формулы (1):

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

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

Заметим, что решение задачи интерполяции по Ньютону имеет некоторые преимущества по сравнению с решением задачи интерполяции по Лагранжу. Каждое слагаемое интерполяционного многочлена Лагранжа зависит от всех значений табличной функции y i , i=0,1,…n. Поэтому при изменении количества узловых точек N и степени многочлена n (n=N-1) интерполяционный многочлен Лагранжа требуется строить заново. В многочлене Ньютона при изменении количества узловых точек N и степени многочлена n требуется только добавить или отбросить соответствующее число стандартных слагаемых в формуле Ньютона (2). Это удобно на практике и ускоряет процесс вычислений.

Программирование функции формулы Ньютона

Для построения многочлена Ньютона по формуле (1) организуем циклический вычислительный процесс по . При этом на каждом шаге поиска находим разделенные разности k-го порядка. Будем помещать разделенные разности на каждом шаге в массив Y.

Тогда рекуррентная формула (3) будет иметь вид:

В формуле Ньютона (2) используются разделенные разности -го порядка, подсчитанные только для участков т.е. разделенные разности -го порядка для . Обозначим эти разделенные разности k-го порядка как . А разделенные разности, подсчитанные для , используются для расчетов разделенных разностей более высоких порядков.

Используя (4), свернем формулу (2). В результате получим

(5)

– значение табличной функции (1) для .

– разделенная разность -го порядка для участка .

Лекция 4

1. Конечные разности
2. Первая интерполяционная формула
Ньютона
3. Вторая интерполяционная формула
Ньютона
4. Погрешности интерполяции

Конечные разности 1–го порядка

Если интерполируемая функция y = f(x) задана в
равноотстоящих узлах, так что xi = x0 + i∙h, где h – шаг таблицы, а
i = 0, 1, … n, то для интерполяции могут применяться формулы
Ньютона, использующие конечные разности.
Конечной разностью первого порядка называется разность yi
= yi+1 - yi, где
yi+1= f(xi+h) и yi = f(xi). Для функции, заданной
таблично в (n+1) узлах, i = 0, 1, 2, …, n, конечные разности
первого порядка могут быть вычислены в точках 0, 1, 2,…, n - 1:
y 0 y1 y 0 ,
y1 y 2 y1,
.......................
yn 1 yn yn 1.

Конечные разности высших порядков

Используя конечные разности первого порядка, можно
получить конечные разности второго порядка 2yi = yi+1 - yi:
2 y 0 y1 y 0 ;
2 y1 y 2 y1;
..........................
2 y n 2 y n 1 y n 2 .
Конечные разности k-го порядка в узле с номером i могут
быть вычислены через разности (k-1)–го порядка:
k yi k 1yi 1 k 1yi
Любые конечные разности можно вычислить через значения
функции в узлах интерполяции, например:
2 y 0 y1 y 0 (y 2 y1) (y1 y 0) y 2 2y1 y 0 .

Таблица конечных разностей

x
y
Δy
Δ2y
Δ3y
x0
y0 Δy0 = y1 – y0 Δ2y0 = Δy1 – Δy0 Δ3y0 = Δ2y1 – Δ2y0
x1 = x0 + h
y1 Δy1 = y2 – y1 Δ2y1 = Δy2 – Δy1
x2 = x0 + 2h
y2 Δy2 = y3 – y2
x3 = x0 + 3h
y3

По величине конечных разностей можно
сделать
вывод
о
степени
интерполяционного
многочлена,
описывающего
таблично
заданную
функцию.
Если
для
таблицы
с
равноотстоящими
узлами
конечные
разности k-го порядка постоянны или
соизмеримы с заданной погрешностью, то
функцию можно представить многочленом
k-й степени.

Конечные разности и степень многочлена

Рассмотрим, например, таблицу конечных разностей для
многочлена y = x2 – 3x + 2.
0
y
-0.16
2y
0.08
3y
0
1.2
-0.16
-0.08
0.08
0
1.4
-0.24
0
0.08
1.6
-0.24
0.08
1.8
-0.16
x
y
1.0
Конечные разности третьего порядка равны нулю, а все
конечные разности второго порядка одинаковы и равны 0.08. Это
говорит о том, что функцию, заданную таблично, можно
представить многочленом 2–й степени (ожидаемый результат,
учитывая способ получения таблицы).

Пусть функция y = f(x) задана в n+1 равноотстоящих узлах xi , i = 0, 1,
2,…n с шагом h. Требуется найти интерполяционный многочлен Pn(x)
степени n, удовлетворяющий условию:
Pn(xi) = yi, i =0, 1, 2, …,n .
Будем искать интерполяционный многочлен в виде:
Pn(x) = a0 + a1(x-x0) + a2(x-x0)(x-x1) + … + an(x-x0)(x-x1)…(x-xn-1),
где аi, i = 0, 1, 2,…n – неизвестные коэффициенты, не зависящие от узлов
интерполяции. Найдем эти коэффициенты из условий интерполяции.
Пусть х = x0, тогда Pn(x0) = y0 = a0. Следовательно, a0 = y0.
Пусть х = x1, тогда Pn(x1) = y1 = a0 + a1(x1 - x0) = y0 + a1(x1 - x0), откуда
a1
y1 y0 y0
.
x1 x0
h
Теперь пусть х = х2 , тогда:
Pn (x 2) y 2 a0 a1(x 2 -x 0) a2 (x 2 -x 0)(x 2 -x1) y 0
y 0
2h a2 2h2.
h
Выразив из этого выражения a2, получим:
y 2 2 y0 y0 y 2 2(y1 y0) y0 y 2 2y1 y 0 2 y 0
a2
.
2h2
2h2
2h2
2h2

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

Продолжая подстановки, можно получить выражение для любого
коэффициента с номером i:
i y 0
ai
,
i! hi
i 0,1,...,n.
Подставив найденные значения коэффициентов в исходное выражение,
получим первую интерполяционную формулу Ньютона:
y0
2 y0
n y 0
Pn (x) y0
(x x0)
(x x 0)(x x1) ...
(x x 0)...(x x n 1).
1!h
2!h2
n!hn
Из формулы видно, что в ней используется верхняя строка таблицы
конечных разностей (слайд 4). Особенностью формулы является также
последовательное увеличение степени многочлена по мере добавления
очередных слагаемых. Это позволяет уточнять получаемый результат без
пересчета уже учтенных слагаемых.

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

Первая интерполяционная формула Ньютона может быть записана в
более компактном и удобном для программной реализации виде.
Обозначив
q
x x0
,
h
x x 0 qh
и проведя несложные преобразования вида:
x x1 x x 0 h
q 1;
h
h
x xn
x x2
q n 1,
q 2;.....;
h
h
получим первую интерполяционную формулу Ньютона, выраженную
относительно неизвестной q:
n y 0
2 y0
q(q 1)...(q n 1).
q(q 1) ...
Pn (x) Pn (x0 hq) y0 y0q
n!
2!

10. Первая интерполяционная формула Ньютона

Конечные разности высших порядков, используемые в формуле
Ньютона, имеют обычно большую погрешность, связанную с ошибками
округления при вычитании близких значений. Поэтому соответствующие
слагаемые формулы имеют также большую погрешность. Чтобы уменьшить
их вклад в сумму, то есть в конечный результат, надо, чтобы выполнялось
условие |q| < 1. Это обеспечивается, если точка интерполяции x находится
между двумя первыми узлами таблицы: x0 < x < x1. По этой причине
интерполяцию с использованием первой формулы Ньютона называют
интерполяцией в начале таблицы или интерполяцией вперед.

интерполяции первая интерполяционная формула Ньютона принимает
следующий вид:
P1(x) y0 y0q.
P2 (x) y 0 y 0 q 2 y 0
q(q 1)
.
2

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

что и в примере на слайде 6. Требуется найти приближенное
значение функции в точке x = 1.1 путем квадратичной
интерполяции по первой формуле Ньютона.
x
1.0
1.2
1.4
1.6
1.8
y
0
-0.16
-0.24
-0.24
-0.16
y
-0.16
-0.08
0
0.08
2y 3y
0.08 0
0.08 0
0.08
Шаг таблицы h = 0.2
q = (x – x0)/h = 0.5
q(q 1)
2
0.5(0.5 1)
0 (0.16) 0.5 0.08
0.09
2
P2 (x) y 0 Δy 0 q Δ 2 y 0
Результат совпадает с
значением многочлена
y = x2 – 3x + 2, из которого
получена таблица

12. Схема алгоритма вычислений по первой интерполяционной формуле Ньютона

13. Вторая интерполяционная формула Ньютона

Вторая формула Ньютона обладает аналогичными свойствами
относительно правой части таблицы. Для ее построения используют
многочлен вида:
Pn(x) = a0 + a1(x-xn) + a2(x-xn)(x-xn-1) + … + an(x-xn)(x-xn-1)…(x-x1),
где аi, i = 0, 1, 2, … n – коэффициенты, не зависящие от узлов интерполяции.
Для определения коэффициентов аi будем в это выражение поочередно
подставлять узлы интерполяции. При х = xn Pn(xn) = yn, следовательно,
a0 = yn.
При х = xn-1 имеем Pn(xn-1) = yn-1 = a0 + a1(xn-1-xn) = yn + a1(xn-1-xn),
откуда
a1
yn 1 yn yn yn 1 yn 1
.
xn 1 xn xn xn 1
h

14. Вторая интерполяционная формула Ньютона

Продолжая подстановки, получим выражения для всех коэффициентов
многочлена и вторую интерполяционную формулу Ньютона:
n y 0
yn 1
2 yn 2
Pn (x) yn
(x xn)
(x xn)(x xn 1)
(x xn)...(x x1).
2
n
1!h
2!h
n!h
Из формулы видно, что в ней используется нижняя диагональ таблицы
конечных разностей (слайд 4). Как и в первой формуле Ньютона, добавление
очередных слагаемых ведет к последовательное увеличению степени
многочлена, что позволяет уточнять получаемый результат без пересчета уже
учтенных слагаемых.
Введя обозначение: q
x xn
,
h
x xn hq
и, проделав несложные преобразования, получим вторую интерполяционную
формулу Ньютона, выраженную относительно переменной подстановки q:
n y 0
2 yn 2
Pn (x) yn yn 1q
q(q 1) ...
q(q 1)...(q n 1).
2!
n!

15. Вторая интерполяционная формула Ньютона

Из тех же соображений, что и в случае первой формулы Ньютона, для
уменьшения вычислительной погрешности надо, чтобы выполнялось условие
|q| < 1. Это обеспечивается, если точка интерполяции x находится между
двумя последними узлами таблицы: xn-1 < x < xn. По этой причине
интерполяцию с использованием второй формулы Ньютона называют
интерполяцией е конце таблицы или интерполяцией назад.
Для частных случаев линейной (n=1) и квадратичной (n=2)
интерполяции вторая интерполяционная формула Ньютона принимает
следующий вид:
P1 (x) y n y n 1q
2 y n 2
P2 (x) y n y n 1 q
q(q 1)
2!

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

Пусть интерполируемая функция f(x) задана той же таблицей,
что и в примере на слайде 11. Требуется найти приближенное
значение функции в точке x = 1.7 путем квадратичной
интерполяции по второй формуле Ньютона.
x
1.0
1.2
1.4
1.6
1.8
y
0
-0.16
-0.24
-0.24
-0.16
y
-0.16
-0.08
0
0.08
2y 3y
0.08 0
0.08 0
0.08
Шаг таблицы h = 0.2
q = (x – xn)/h = -0.5
Результат совпадает с
значением многочлена
y = x2 – 3x + 2, из
которого получена
таблица
q(q 1)
2
0.5(0.5 1)
0.16 0.08 (0.5) 0.08
0.21
2
P2 (x) y n Δy n 1 q Δ 2 y n 2

17. Схема алгоритма вычислений по второй интерполяционной формуле Ньютона

18. Погрешности интерполяции

Интерполирующая функция в точках между
узлами интерполяции заменяет интерполирующую
функцию приближенно:
f(x) = F(x) + R(x), где R(x) – погрешность
интерполяции.
Для оценки погрешности необходимо иметь
необходимо иметь определенную информацию об
интерполируемой функции f(x). Предположим, что
f(x) определена на отрезке , содержащем все
узлы xi, и при x, принадлежащем , имеет все
производные f"(x), f""(x), … f(n+1)(x) до (n+1)–го
порядка включительно.

19. Погрешности интерполяции

Тогда

20. Выбор узлов интерполяции по формуле Лагранжа

При фиксированной степени многочлена:
x*
x0
x1
x2
x3
x4
x5
x
При последовательном увеличении степени
многочлена
x*
x4
x2
x0
x1
x3
x5
x

21. Практическая оценка погрешности интерполяции по формуле Лагранжа

На практике оценка максимального значения производной (n+1)–го
порядка Mn+1 при использовании формулы Лагранжа редко бывает возможна,
и поэтому используют приближенную оценку погрешности
R n (x) f(x) Ln (x) Ln 1 (x) Ln (x) ,
где n число используемых узлов.
Из приведенной формулы следует, что для оценки погрешности
интерполяции многочленом Лагранжа n–й степени необходимо
дополнительно вычислить значение многочлена (n+1)–й степени. Если
допустимая погрешность интерполяции задана, то необходимо, добавляя все
новые узлы, увеличивать степень многочлена до тех пор, пока модуль
разности между двумя последними значениями многочлена |Ln+1(x)-Ln(x)| не
станет меньше заданного значения.

22. Схема алгоритма интерполяции по формуле Лагранжа с заданной точностью

23. Оценка погрешностей интерполяционных формул Ньютона

Для интерполяционных
приобретают следующий вид.
1–я формула Ньютона:
R n (x) h
n 1
формул
Ньютона
оценки
q(q 1) (q n) (n 1)
f
(n 1)!
R n (x) h n 1
q(q 1) (q n)
M n 1
(n 1)!
2–я формула Ньютона:
R n (x) h
n 1
q(q 1) (q n) (n 1)
f
(n 1)!
R n (x) h n 1
q(q 1) (q n)
M n 1
(n 1)!
погрешности

24. Практическая оценка погрешностей интерполяционных формул Ньютона

При использовании интерполяционных формул Ньютона величину
f(n+1)(ξ) можно приближенно оценивать по величинам конечных разностей:
f
(n 1)
n 1
Δ y0
() n 1
h
и в этом случае формулы для оценки погрешности приобретают следующий
вид:
1–я формула Ньютона:
R n (x)
q(q 1) (q n) n 1
Δ y0
(n 1)!
2–я формула Ньютона:
R n (x)
q(q 1) (q n) n 1
Δ y0
(n 1)!

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

Сравнивая эти формулы с формулами
Ньютона, можно увидеть, что для оценки
погрешности при интерполяции многочленом
n–й степени надо взять дополнительный узел
и вычислить слагаемое (n+1)–й степени.
Если задана допустимая погрешность
интерполяции ε, то надо последовательно
добавлять новые узлы и, соответственно,
новые слагаемые, увеличивая степень
интерполяционного многочлена до тех пор,
пока очередное слагаемое не станет меньше ε.

Рассмотрим понятие конечных разностей.

Пусть задана функция у=f{x) на отрезке [х 0 , х„], который разбит на п одинаковых отрезков (случай равноотстоящих значений аргумента): Ax=h = const. Для каждого узла х 0 , х, =х 0 + /г, ..., х„ =х () + п h определены значения функции в виде

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

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

Конечные разности второго порядка Аналогично определяются конечные разности высших порядков:

Конечные разности функций удобно располагать в таблицах, которые могут быть диагональными (табл. 5.1) или горизонтальными (табл. 5.2).

Диагональная таблица

Таблица 5.1

Горизонтальная таблица

Таблица 5.2

						а 5 у,
						А 5 Уо
					а 4 у.

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

Пусть для функции у=/(х) заданы значения у, =/(х,) для равностоящих значений независимых переменных:

где h - шаг интерполяции.

Необходимо найти полином Р„{х) степени нс выше п, принимающий в точках (узлах) х, значения:

Интерполирующий полином ищется в виде:

Задача построения многочлена сводится к определению коэффициентов а, из условий:

Полагаем в (5.13) х=х 0 , т. к. второе, третье и другие слагаемые равны 0, то

Найдем коэффициент а { .

Приэс=Х1 получим:

Для определения а 2 составим конечную разность второго порядка. При х=х 2 получим:

Аналогично можно найти другие коэффициенты. Общая формула имеет вид:

Подставляя эти выражения в формулу (5.13), получаем:

где х„ у х - узлы интерполяции; х - текущая переменная; h - разность между двумя узлами интерполяции; h - величина постоянная, т. е. узлы интерполяции равно отстоят друг от друга.

Этот многочлен называют интерполяционным полиномом Ньютона для интерполяции в начале таблицы (интерполирование «вперед»), или первым полиномом Ньютона.

Для практического использования этот полином записывают в преобразованном виде, вводя обозначение t=(х - x 0)/h, тогда

Эта формула применима для вычисления значений функции для значений аргументов, близких к началу интервала интерполирования.

Блок-схема алгоритма метода Ньютона для интерполирования «вперед» приведена на рис. 5.3, программа - в приложении.

Пример 5.3. Дана таблица значений теплоемкости вещества в зависимости от температуры C p =f{T) (табл. 5.3).

Таблица 5.3

Воспользуемся формулой (5.16):

Рис. 5.3.

После выполнения преобразований получим интерполяционный многочлен вида:

Полином имеет третью степень и дает возможность вычисления при помощи найденной формулы значения у для неизвестного х.

Пример 5.4. В табл. 5.3.1 приведены значения теплоемкости в зависимости от температуры. Определить значение теплоемкости в точке Г=450 К.

Воспользуемся первой интерполяционной формулой Ньютона. Конечные разности рассчитаны в предыдущем примере (табл. 5.3.2), запишем интерполяционный многочлен при х=450 К:

Таким образом, теплоемкость при температуре 450 К будет

Значение теплоемкости при Г=450 К получили такое же, что и рассчитанное по формуле Лагранжа.

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

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

Коэффициенты а 0 , а ь ..., а„ определяем из условия:

Полагаем в (5.18) х=х„, тогда

Полагаем х =х„_|, тогда следовательно,

Если x = x n - 2 i то

Аналогично можно найти другие коэффициенты многочлена (5.18):

Подставляя эти выражения в формулу (5.18), получим вторую интерполяционную формулу Ньютона, или многочлен Ньютона для интерполирования «назад»:

Введем обозначения:

Произведя замену в (5.19), получим:

Это вторая формула Ньютона для интерполирования «назад».

Пример 5.5. Вычислить теплоемкость (см. табл. 5.3) для температуры Г=550 К.

Воспользуемся второй формулой Ньютона (5.19) и соответствующими конечными разностями (см. табл. 5.4):

Следовательно, значение теплоемкости при температуре 550 К равно

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

Интерполяционный многочлен в форме Ньютона – это математическая функция позволяющая записать полином n -степени, который будет соединять все заданные точки из набора значений, полученных опытным путём или методом случайной выборки с постоянным/переменным временным шагом измерений.

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

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

где n – вещественное число, которое указывает степень полинома;

– переменная, которая представляет собой разделенную разность k-го порядка, которая вычисляется по следующей формуле:

Разделённая разность является симметричной функцией своих аргументов, то есть при любой их перестановке её значение не меняется. Следует отметить, что для разделённой разности k-го порядка справедлива следующая формула:

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

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

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

Следует отметить, что данное выражение может быть переписано в другом виде:

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

Следует отметить, что полином в форме Ньютона может быть представлен в более компактном виде (по схеме Горнера), которая получается путем последовательного вынесения за скобки множителей

2. Интерполяционная формула Ньютона для равноотстоящих значений аргумента

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

Для интерполирования функции в конце рассматриваемого интервала (интерполирование назад и экстраполирование вперед

где конечные разности k

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

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

где конечные разности k -порядка определяются по следующему выражению

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

3. Погрешность интерполяционного полинома в форме Ньютона

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

Абсолютную погрешность интерполяционной формулы Ньютона определяют следующим образом:

Переменная представляет собой верхнюю границу значения модуля (n +1)-й производной функции f(x) на заданном интервале

В случае равноотстоящих узлов абсолютная погрешность интерполяционной формулы Ньютона определяют следующим образом:

Выражение записано с учетом следующей формулы:

Выбор узлов интерполяции

С помощью корректного выбора узлов можно минимизировать значение в оценке погрешности, тем самым повысить точность интерполяции. Данная задача может быть решена с помощью многочлена Чебышева:

В качестве узлов следует взять корни этого многочлена, то есть точки:

4. Методика вычисления полинома в форме Ньютона (прямой способ)

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

1. В качестве исходных данных задается выборка из n -точек, которая включает в себя значения функции и значения аргумента функции.

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

3. Выполняется вычисление полинома n-степени в форме Ньютона по следующей формуле:

Алгоритм вычисления полинома в форме Ньютона представлен на рисунке 1.

При получении интерполяционных формул Ньютона, которые используются для тех же целей, что и формула Лагранжа, сделаем дополнительное предположение, что рассматриваются равноотстоящие значения аргумента. Итак, пусть значения функции у = f (x ) заданы для равноотстоящих значений x 0 , x 1 = x 0 + h, …, x n = x 0 + nh. Этим значениям аргументов будут соответствоватьзначенияфункции: у 0 = f(x 0),у 1 = f(x 1), …, y n = f(x n).

Запишем искомый многочлен в виде

F(x ) = a 0 + a 1 (x - x 0) + a 2 (x - x 0)(x - x 1) + a 3 (x - x 0)(x - x 1)(x - x 2) + …

…+ a n (x - x 0)(x - x 1)…(x - x n -1) (3.9)

Для определения коэффициентов a 0 , a 1 ,..., а n положим в (3.9) х = х 0 . Тогда у 0 = F (x 0)=а 0 . Далее, полагая x=x 1 , получим у 1 = F (x 1) = a 0 + а 1 h , откуда

a 1 =

Продолжая вычисления коэффициентов, положим х = х 2 . Тогда

y 2 = y 0 + 2h + a 2 2hh , y 2 – 2Δy 0 = a 2 2h 2 ;

y 2 – 2y 1 + 2y 0 – y 0 = y 2 – 2y 1 + y 0 = a 2 2h 2 .

Исходя из (3.8), получаем y 2 – 2y 1 + y 0 = Δ 2 y 0.

Точно так же получим

Аналогичные дальнейшие вычисления позволяют записать общую формулу для любого коэффициента а k:

Подставим найденные выражения коэффициентов в формулу (3.9), получим

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

Для практического использования формулу Ньютона (3.10) обычно записывают в преобразованном виде. Для этого введем обозначение

отсюда х = х 0 + ht .

Выразим через t множители, входящие в формулу (3.10):

………………………..

Подставив полученные выражения в формулу (3.10), окончательно получаем

Выражение (3.11) представляет окончательный вид первой интерполяционной формулы Ньютона.

Пример . Приняв шаг h = 0,05,построить на отрезке интерполяционный полином Ньютона для функции y = e x ,заданной табл. 3.3.

Таблица 3.3

Заметим, что в столбцах разностей, следуя обычной практике, мы не отделяем запятой десятичные разряды, которые ясны из столбца значений функций.

Так как разности третьего порядка практически постоянны, то в формуле (3.11) полагаем n = 3. Приняв х 0 = 3,50 и у 0 = 33,115, будем иметь:

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

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

Как и ранее, коэффициенты а 0 , а 1 ,… а n определяются из условия F (x i) = y i . Положим в (3.12) х = х n . Тогда a 0 = y n .

Точно так же, полагая x = x n -1 , получим y n -1 = y n +a 1 (x n -1 - x n) ,

а так как x n -1 – x n = - h , то

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

y n – y n -1 – (y n -1 - y n -2 )= Δy n -1 - Δy n -2 = Δ 2 y n -2 .

Продолжая аналогичные вычисления, получим общую формулу для коэффициентов

После подстановки в (3.12) всех значений коэффициентов эта формула примет вид

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

= t или x = x n + th .

Выразим теперь через t множители в формуле (3.13):

……………………………………………..

Произведя такую замену, окончательно получим:

Пример . По табл. 3.5 значений семизначных логарифмов для чисел от 1000 с шагом 10 найти lg 1044.

Таблица 3.5

x	y	Δy	Δ 2 y	Δ 3 y
	3,0000000 3,0043214 3,0086002 3,0128372 3,0170333 3,0211893		-426 -418 -409 -401

Примем x n = 1050,y n = 3,0211893;Δ y n-1 = 0,0041560;

Δ 2 y n -2 = - 0,0000401;Δ 3 y n -3 = 0,0000008.Тогда для x = 1044 получаем

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

Еслиже x > x 0 и x близко кх п , то удобнее пользоваться второй интерполяционной формулой Ньютона, причем

Таким образом, первая интерполяционная формула Ньютона обычно используется для интерполирования вперед и экстраполирования назад, а вторая интерполяционная формула Ньютона, наоборот, – используется для интерполирования назад и экстраполирования вперед.

Пример . Имея табл. 3.6 значений и разностей,у= sin х : в пределах отх = 15° дох = 55° с шагом h = 5° , найти sin 14° и sin 56° .

Таблица 3.6

x (0 C)	y	Δy	Δ 2 y	Δ 3 y
	0,2588 0,3420 0,4226 0,5000 0,5736 0,6428 0,7071 0,7660 0,8192	832 532	-26 -32 -38 -44 -49 -54 -57	-6 -6 -6 -5 -5 -3

Решение . Для вычисления sin14 0 примем x 0 = 15 0 и x = 14 0 , отсюда t = (14–15)/5 = – 0,2.

Здесь следует выполнить экстраполирование назад, поэтому применим первую интерполяционную формулу Ньютона и подчеркнутые одной чертой конечные разности:

sin14 0 = 0,2588 + (– 0,2)0,0832+ (– 0,0026) +

+ (–0,0006) = 0,242.

Для отыскания sin56 0 примем x n = 55 0 и x = 56 0 , отсюда t = .

Применяя вторую интерполяционную формулу Ньютона (3.14) и, используя дважды подчеркнутые разности, будем иметь:

sin56 0 = 0,8192+ 0,2·0,0532+ (- 0,0057)+ (- 0,0003)= 0,83.