Довольно распространенным методом интерполирования является метод Ньютона. Интерполяционный полином для этого метода имеет вид:

P n (x) = a 0 + a 1 (x-x 0) + a 2 (x-x 0)(x-x 1) + ... + a n (x-x 0)(x-x 1)...(x-x n-1).

Задача состоит в отыскании коэффициентов a i полинома P n (x). Коэффициенты находят из уравнения:

P n (x i) = y i , i = 0, 1, ..., n,

позволяющего записать систему:

a 0 + a 1 (x 1 - x 0) = y 1 ;

a 0 + a 1 (x 2 - x 0) + a 2 (x 2 - x 0)(x 2 - x 1) = y 2 ;

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

a 0 +... + a n (x n - x 0)(x n - x 1) ... (x n - x n-1) = y n ;

Используем метод конечных разностей. Если узлы x i заданы через равные промежутки h, т.е.

x i+1 - x i = h,

то в общем случае x i = x 0 + i×h, где i = 1, 2, ..., n. Последнее выражение позволяет привести решаемое уравнение к виду

y 1 = a 0 + a 1 ×h;

y 2 = a 0 + a 1 (2h) + a 2 (2h)h;

- - - - - - - - - - - - - - - - - - -

y i = a 0 + a 1 ×i×h + a 2 ×i×h[(i-1)h] + ... + a i ×i!×h i ,

откуда для коэффициентов получаем

где Dу 0 – первая конечная разность.

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

где D 2 у 0 - вторая конечная разность, представляющая собой разность разностей. Коэффициент а i можно представить в виде:

Поставляя найденные значения коэффициентов а i в значения для P n (x), получим интерполяционный полином Ньютона:

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

Полученная формула известна как первая интерполяционная формула Ньютона, или формула Ньютона для интерполирования "вперед". Ее выгодно использовать для интерполирования функции y = f(x) в окрестности начального значения х – х 0 , где q мало по абсолютной величине.

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

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

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

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

Если интерполирование осуществляется с одинаковым шагом, то формула для остаточного члена видоизменяется. В частности, при интерполировании "вперед" и "назад" по формуле Ньютона выражение для R(x) несколько отличаются друг от друга.

Анализируя полученную формулу, видно, что погрешность R(x) представляет собой, с точностью до постоянной произведение двух множителей, из которых один, f (n+1) (x), где x лежит внутри , зависит от свойств функции f(x) и не поддается регулированию, а величина другого,

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

При неудачном расположении этих узлов верхняя граница модуля |R(x)| может быть весьма большой. Поэтому возникает задача о наиболее рациональном выборе узлов интерполирования x i (при заданном числе узлов n) с тем, чтобы полином П n+1 (х) имел наименьшее значение.

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) для .

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

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

Интерполяционные формулы используются также при вычислении интегралов, при написании разностных аппроксимаций для дифференциальных уравнений, на основе интегральных тождеств.
Часто требуется восстановить функцию f(x) на отрезке a ≤ x ≤ b , если известны её значения в некотором конечном числе точек этого отрезка.

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

В таблице 1 приведены данные временной сложности алгоритмов.

Таблица 1

Входные данные:
x — координата, в которой необходимо вычислить.
n – Количество узлов.
Step – шаг интерполяции
Множество MasX – Значения x .
Множество MasY – Значения f(x) .

Выходные данные:
res – значение полинома в точке x .

Алгоритмическая модель метода Ньютона:
Множество mas мощностью |n + 2, n + 1|; Для всех i от 0..2: Для всех j от 0..n+1: Если i = 0: masi,j = MasXj; иначе Если i = 1: masi,j = MasYj; m = n; Для всех i от 2..n+2: Для всех j от 0..m: masi,j = mas(i-1),(j+1) – mas(i–1),j; m = m-1; Множество dy0 мощностью |n + 1|; Для всех i от 0..n+1: dy0i = mas(i + 1),0; res = dy00; Множество xn мощностью |n|; xn0 = x - mas0,0; Для всех i от 1..n: ans = xni - 1 * (x - mas0, i); xni = ans; ans = 0; m1 = n + 1; fact = 1; Для всех i от 1..m1: fact = fact * i; res = res + (dy0i * xni - 1) / (fact * stepi);

На рисунке 1 изображена схема интерполяции метода Ньютона.


Рисунок 1 — интерполяция метода Ньютона

// x - координата, в которой необходимо вычислить значение полинома Ньютона; n - количество узлов; MasX - массив x; MasY - массив значений x; step - шаг public double Newton(double x, int n, double MasX, double MasY, double step) { double[,] mas = new double; for (int i = 0; i < 2; i++) { for (int j = 0; j < n + 1; j++) { if (i == 0) mas = MasX[j]; else if (i == 1) mas = MasY[j]; } } int m = n; for (int i = 2; i < n + 2; i++) { for (int j = 0; j < m; j++) { mas = mas - mas; } m--; } double dy0 = new double; for (int i = 0; i < n + 1; i++) { dy0[i] = mas; } double res = dy0; double xn = new double[n]; xn = x - mas; for (int i = 1; i < n; i++) { double ans = xn * (x - mas); xn[i] = ans; ans = 0; } int m1 = n + 1; int fact = 1; for (int i = 1; i < m1; i++) { fact = fact * i; res = res + (dy0[i] * xn) / (fact * Math.Pow(step, i)); } return res; }

Составим таблицу значений для f(x) = x^3.

Найдем полимер в точке 2.1: f(2.1) = 2.1^3=9,261

С помощью программной функции мы получили такой же результат (Рисунок 2).


Рисунок 2 — применение функции

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

Мы построили математическое описание методов, после чего приступили к разработке схемы программы.

Разработали программу реализующую интерполяцию метода Ньютона, на языке C# в Visual Studio 2012.

Протестировали программу, все тесты на основе заданных нами данных были успешно пройдены.

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

Лекция 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)–й степени.
Если задана допустимая погрешность
интерполяции ε, то надо последовательно
добавлять новые узлы и, соответственно,
новые слагаемые, увеличивая степень
интерполяционного многочлена до тех пор,
пока очередное слагаемое не станет меньше ε.