Как построить интерполяционный многочлен ньютона

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Многочлен в форме Ньютона, который строится на основании шести значений, представляет собой полином 5 степени. Результат построения полинома в форме Ньютона показан в графическом виде.

С помощью найденного полинома можно определить значение функции в любой точке заданного интервала. Определение промежуточных значений величины по имеющемуся дискретному набору известных значений называется «интерполяцией». В соответствии с условиями задачи полином в форме Ньютона в точке x =9,5 принимает следующее значение: L (9,5)= – 4,121. Из графика видно, что полученное значение не совпадает c о значением функции f ( x ) на величину абсолютной погрешности интерполяционной формулы Ньютона.

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

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

Источник

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

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

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

Как пользоваться

Теория и формулы, как обычно, описаны под калькулятором.

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

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

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

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

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

Источник

Инструменты сайта

Основное

Навигация

Информация

Действия

Содержание

Интерполяция

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

Происхождение слова «интерполяция» ☞ ЗДЕСЬ.

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

Полиномиальная интерполяция

Все множество интерполяционных полиномов, принимающих значения по таблице, можно представить в виде

Решение ☞ ЗДЕСЬ.

Пусть имеется интерполяционная таблица

Пример. Интерполяционный полином для таблицы

Следовательно, применение вычислительных методов решения систем линейных уравнений — типа метода Гаусса — к системе с матрицей Вандермонда столкнется с необходимостью строгого контроля округлений. ♦

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

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

Пример. Построить интерполяционный полином по таблице

Рекурсивное вычисление коэффициентов

В настоящем пункте мы произведем «доводку» метода Лагранжа до коэффициентов интерполяционного полинома

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

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

Теорема. Интерполяционный полином в форме Ньютона записывается в виде:

Применение полиномиальной интерполяции в задаче о разделении секрета

Обратная интерполяция

В одном из предшествующих ☝ пунктов решалcя следующий

Пример. Найти корни интерполяционного полинома, заданного таблицей

Интерполяционный полином Эрмита

Пример. Построить интерполяционный полином по таблице

Построить уравнение «горки»: найти полином из условий

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

Рациональная интерполяция

Первое решение задачи было предложено Коши в 1821 г. [9].

Теорема [Коши]. Обозначим:

Биографические заметки о Коши ☞ ЗДЕСЬ.

Другие примеры на применение теоремы Коши ☞ ЗДЕСЬ

Теорема Коши дает решение задачи в смысле «как правило». Дело в том, что задача рациональной интерполяции (в указанной постановке) не всегда разрешима.

Пример. Для таблицы

Альтернативный подход к решению задачи основывается на следующей теореме, развивающей результат К.Якоби [10,11]; он основан на идее из пункта ☝ о рекурсивном вычислении коэффициентов интерполяционного полинома.

Подробнее о методе Якоби (в том числе и об эффективном способе вычисления ганкелевых полиномов) ☞ ЗДЕСЬ.

Тригонометрическая интерполяция

Доказательство тривиально, если обратить внимание на аналогию с интерполяционным полиномом в форме Лагранжа. ♦

Теорема. Функция

Задача. Найти явные выражения для коэффициентов тригонометрического полинома из последней теоремы.

«Лобовое» решение аналогично решению задачи полиномиальной интерполяции — сведением ее к подходящей системе линейных уравнений.

Пример. Построить интерполяционный полином второго порядка по следующей таблице

Решение ☞ ЗДЕСЬ.

Для случая системы равноотстоящих узлов решение задачи значительно упрощается.

Подробное изложение теории тригонометрической интерполяции (и дискретного преобразования Фурье) ☞ ЗДЕСЬ

Интерполяция суммами экспонент

Материал настоящего пункта — сильная «выжимка» из [2]. Числовой пример — мой.

В отличие от рассмотренных выше задач алгебраической или тригонометрической интерполяции, поставленная задача является, во-первых, принципиально нелинейной относительно параметров, и, во-вторых, не всегда разрешимой.

Пример. Построить экспоненциальную функцию вида

Аппроксимация

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

Аппроксимация в случае недостоверности данных

Предположим теперь, что данные исходной таблицы не являются достоверными: значения обеих переменных подвержены воздействию случайных погрешностей одинакового порядка. Как воспользоваться этими данными для задачи аппроксимации? Мы рассмотрим здесь только две подобные задачи.

Координаты точки, для которой величина

Теорема 2 [3],[4]. Обозначим

$$ \begin x & 0.0 & 0.9 & 1.8 & 2.6 & 3.3 & 4.4 & 5.2 & 6.1 & 6.5 & 7.4 \\ \hline y & 5.9 & 5.4 & 4.4 & 4.6 & 3.5 & 3.7 & 2.8 & 2.8 & 2.4 & 1.5 \end $$

Метод наименьших квадратов

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

$$ \begin x & 0.5 & 1 & 1.5 & 2 & 2.5 & 3 \\ \hline y & 0.35 & 0.80 & 1.70 & 1.85 & 3.51 & 1.02 \end $$

Дальнейшее развитие идеологии МНК ☞ ЗДЕСЬ.

Многомерная интерполяция

Сложности: парадокс Крамера

Прямоугольная сетка

Задачи

Источники

[1]. Mycielski J. Polynomials with Preassigned Values at their Branching Points. The American Mathematical Monthly, 77 (8).1970, pp. 853-855

[2]. Henrici P. Applied and Computational Complex Analysis. V. 1. 1974. NY. Wiley

[4]. Hilbert D. Ein Beitrag zur Theorie des Legendreschen Polynoms. Acta Math. Bd.18, 1894, S.155-160

[5]. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М. Мир. 1969

[6]. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений. М.ГИФМЛ. 1958

[7]. Калинина Е.А., Утешев А.Ю. Теория исключения. Учеб. пособие. СПб.: НИИ Химии СПбГУ, 2002. 72 с.

[8]. Утешев А.Ю., Тамасян Г.Ш. К задаче полиномиального интерполирования с кратными узлами. Вестник СПбГУ. Серия 10. 2010. Вып. 3, С. 76-85. Текст (pdf) ☞ ЗДЕСЬ

[9]. Cauchy A.-L. Cours d’Analyse de l’École Royale Polytechnique: Part I: Analyse Algébrique. Paris, France: L’Imprimerie Royale, 1821, pt. 1.

[10]. Jacobi C.G.J. Űber die Darstellung einer Reihe gegebner Werthe durch eine gebrochne rationale Function. J.reine angew. Math. 1846. Bd. 30, S. 127-156

[11]. Утешев А.Ю., Боровой И.И. Решение задачи рациональной интерполяции с использованием ганкелевых полиномов. Вестник СПбГУ. Серия 10. 2016. Вып. 4, С. 31-43. Текст ☞ ЗДЕСЬ (pdf).

[12]. Pearson K. On lines and planes of closest fit to systems of points in space. Phil. Mag. 1901. V.2, pp. 559-572

Источник

Методы функциональной интерполяции

Постановка задачи

В некоторых случаях [math]y_i=f(x_i),

Точки [math]x_0,x_1,\ldots, x_n[/math] называются узлами интерполяции, а искомая функция [math]y=F(x)[/math] — интерполирующей.

Геометрически это означает, что нужно найти кривую, проходящую через заданное множество точек [math](x_i,y_i),

i=\overline<0,n>[/math] (рис. 4.2).

Заметим, что можно провести бесчисленное множество «плавных» кривых, проходящих через заданное множество точек. Поэтому задача интерполяции в общей постановке не имеет единственного решения.

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

Доказательство. Запишем условия интерполяции (4.9) с учетом (4.8) и обозначения [math]y_i= f(x_i)= f_i\colon[/math]

Эта система линейных алгебраических уравнений относительно коэффициентов [math]a_0,a_1, \ldots,a_k[/math] имеет единственное решение, так как определитель матрицы системы

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

коэффициенты которого находятся из системы (4.10) при [math]i=0,

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

4. При большом числе узлов решение системы (4.10) затруднительно. Искомый интерполяционный многочлен можно построить, не решая этой системы. Многочлены могут быть построены так, чтобы в самой структуре формулы многочлена условие интерполяции учитывалось.

5. При решении задачи функциональной интерполяции и в ее приложениях требуется:

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

б) оценить погрешность интерполяции;

в) определить значения функции в точках, не совпадающих с узлами;

г) вычислить значения производных или определенных интегралов с использованием полученных интерполяционных многочленов.

Методика решения задачи интерполяции

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

2. Вычислить значения интерполяционного многочлена в заданных точках [math]x_<\ast j>,

Многочлен Лагранжа

Легко проверить, что (4.14) — многочлен второй степени и также удовлетворяет условиям функциональной интерполяции:

Легко проверить, что [math]P_(x)[/math] удовлетворяют условию

где коэффициенты Лагранжа [math]P_(x)[/math] во внутренних точках отрезка записываются в форме

4.1>>\\\hline x-x_0& x_0-x_1& x_0-x_2& \cdots& x_0-x_n& D_0& f_0 \\\hline x_1-x_0& x-x_1& x_1-x_2& \cdots& x_1-x_n& D_1& f_1 \\\hline x_2-x_0& x_2-x_1& x-x_2& \cdots& x_2-x_n& D_2& f_2 \\\hline \vdots& \vdots& \vdots& \ddots& \vdots& \vdots& \vdots \\\hline x_n-x_0& x_n-x_1& x_n-x_2& \cdots& x-x_n& D_n& f_n \\\hline \multicolumn<5><|c|><\begin<>\\[-8pt]<>\end\Pi_(x)= (x-x_0)(x-x_1)(x-x_2)\ldots (x-x_n)>& D_i&f_i \\\hline \end[/math]

Здесь [math]D_i[/math] — произведение элементов i-й строки, [math]\Pi_(x)[/math] — произведение элементов главной диагонали, [math]y_i= f(x_i)= f_i,

1. Если заданная сеточная функция такая, что [math]f_i=1

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

Перейдем к рассмотрению примеров решения задачи интерполяции на основе вышеизложенной методики.

4.2>>\\\hline i& 0& 1& 2&3 \\\hline x_i& 2& 3& 4&5 \\\hline \begin<>\\[-8pt]<>\end f(x_i)= f_i & 7& 5& 8&7 \\\hline \end[/math]

Решение. 1. Построим многочлен Лагранжа. Для этого составим табл. 4.3, соответствующую табл. 4.1.

4.3>>\\\hline x-2&-1&-2&-3&-6\cdot(x-2)&7 \\\hline 1&x-3&-1&-2& 2\cdot(x-3)&5 \\\hline 2& 1& x-4&-1&-2\cdot(x-4)&8 \\\hline 3& 2& 1& x-5& 6\cdot(x-5)&7 \\\hline \multicolumn<4><|c|><\begin<>\\[-8pt]<>\end \Pi_4(x)= (x-2)(x-3)(x-4)(x-5)>& D_i&f_i \\\hline \end[/math]

По формуле (4.18) получаем:

Погрешность интерполяции многочленами Лагранжа

При определении значения [math]f(x),

x\ne x_[/math] для функции [math]y_i=f(x_i)

(i=\overline<0,n>)[/math] с помощью многочлена Лагранжа возникает погрешность или остаточное слагаемое [math]R_n(x)\colon[/math]

Оценка погрешности интерполяции в некоторой произвольной фиксированной точке [math]x_<\ast>\in[a,b][/math] имеет вид, где [math]M_= \max_|f^<(n+1)>(x)|[/math]

Замечание. Для сеточных функций с фиксированными узлами сетки (узлами интерполяции) также можно проводить оценки погрешности по формулам (4.21), (4.22), однако для этого необходимо численно определять [math]M_[/math] с помощью аппарата численного дифференцирования. При этом следует учитывать, что при вычислении производных высокого порядка возникают большие погрешности.

Тогда [math]\omega_1(x_<\ast>)= (85-36)(85-100)=-735;

Тогда [math]\omega_2(x_<\ast>)= (85-16)(85-36)(85-100)=-50715;

Сходимости функционального интерполяционного процесса для непрерывных функций

Будем считать, что интерполяция проводится на последовательности сеток

с возрастающим разбиением [math]k[/math] отрезка [math][a,b]\colon\, k_1=1; k_2=2; \ldots; k_n=n[/math] и т.д.

(n\leqslant 5\div 8)[/math] и задание частичного отрезка согласуют с выбранной степенью многочлена.

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

Линейная и параболическая интерполяция с помощью многочлена Лагранжа

Методика решения задачи линейной интерполяции

3. Вычислить искомое значение [math]f(x_<\ast>)[/math] согласно (4.13):

Методика решения задачи параболической интерполяции

O_2\equiv [x_i, x_][/math] (предполагается, что [math]x_<\ast>[/math] принадлежит внутреннему отрезку [math][x_i,x_][/math] ).

3. Используя значения коэффициентов Лагранжа, вычислить значения [math]L_2^<(1)>(x_<\ast>),\, L_2^<(2)>(x_<\ast>)[/math] по формуле (4.14).

Приведем оценки погрешностей линейной и параболической интерполяции. Вначале предположим, что сетка [math]\Omega_n[/math] равномерная (это имеет значение только для параболической интерполяции). Формулы (4.13), (4.14) и оценки (4.22), записанные для «окон» интерполяции, упрощаются, если ввести в рассмотрение новую переменную — фазу интерполяции и [math]u=\frac\colon[/math]

Здесь учтено, что [math]x-x_= x-(x_i+h)= uh-h= h(u-1),

Таким образом, реализуются следующие оценки погрешностей линейной и параболической интерполяции, справедливых для соответствующих «окон»:

4. Для произвольной степени интерполяционного многочлена при [math]h=text,

f(x)\in C_[a,b][/math] погрешность функциональной интерполяции на отрезке [math][x_0,x_n][/math] выражается следующим образом:

5. В широком классе задач математической физики применяются расчетные схемы в основном второго (и иногда третьего и выше) порядка точности. При их реализации, как правило, используются встроенные интерполяционные алгоритмы, основанные на многочленах и сплайн-функциях. Степени интерполяционных многочленов при этом должны выбираться из условия соответствия порядков их аппроксимации порядкам точности схем. Если эти порядки одинаковы, то порядок точности схем сохраняется, хотя константа в оценке погрешности схемы изменяется. Если же порядок встроенных интерполяционных алгоритмов хотя бы на единицу выше порядка точности схемы, то вместе с порядком точности схемы сохраняется и указанная константа. Отсюда следует, что необходимо выбирать такую степень интерполяционного многочлена, которая либо обеспечивает равенство порядка аппроксимации порядку точности схемы, либо на единицу превышает последний. Таким образом, использование параболической интерполяции в качестве встроенных алгоритмов или для восполнения численных решений, полученных по схемам второго порядка, позволяет сохранить требуемую точность расчета, а также не дает избыточный порядок и, следовательно, не усложняет алгоритм. Это замечание носит общий характер и относится к любым аппроксимационным алгоритмам, выполняющим функцию восполнения или интерполирования.

Перейдем к рассмотрению примеров решения задач линейной и параболической интерполяции.

Дана сеточная функция, являющаяся сеточным представлением формульной функции [math]f(x)=x^3[/math] (табл. 4.4). Найти значение [math]f(x_<\ast>)[/math] при [math]x_<\ast>=2[/math] с помощью линейной и параболической интерполяции.

Решение. Применение линейной интерполяции. Воспользуемся методикой.

1. Выбираем «окно» интерполяции [math][x_i,x_]= [1;3]

2. Вычислим коэффициенты Лагранжа: [math]P_<1\,2>= \frac-x_3>= 0,\!5;

3. Определим искомое значение [math]f(2)[/math] по формуле (4.13):

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

1. Выбираем «окна» интерполяции [math]O_1\equiv [x_1;x_3]= [0;3];

Вычисления выполнены правильно, так как [math]\textstyle<\sum\limits_^ <3>P_<2k>^<(1)>=1;

3. Определим значения [math]L_2^<(1)>(x_<\ast>),

Многочлены Ньютона

Разделенные разности вводятся для функции [math]y_i= f(x_i)=f_i,

Выбрав внутри неравномерной или равномерной сетки соответствующие шаблоны интерполяции [math](x_i,x_), (x_i,x_,x_), \ldots, (x_i,x_,\ldots, x_)[/math] введем следующие определения разделенных и конечных разностей:

– разделенная разность первого порядка: [math]f(x_i,x_)= \frac-f_i>-x_i>[/math] ;

– разделенная разность второго порядка: [math]f(x_i,x_,x_)= \frac,x_)-f(x_i,x_)>-x_i>[/math] ;

– разделенная разность k-го порядка: [math]f(x_i,x_,\ldots, x_)= \frac,x_,\ldots, x_)-f(x_i,x_,\ldots, x_)>-x_i>[/math] ;

– конечная разность первого порядка: [math]\Delta f_i= f_-f_i[/math] ;

– конечная разность второго порядка: [math]\Delta^2f_i= \Delta (\Delta f_i)= \Delta f_-\Delta f_i= f_-2f_+f_i[/math] ;

Последовательность получения разделенных и конечных разностей при [math]k=3[/math] для произвольной функции наглядно представляют табл. 4.5 и 4.6.

Связь между разделенными и конечными разностями k-го порядка при [math]h=\text[/math] устанавливается следующим соотношением:

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

Пусть исходная (интерполируемая) сеточная функция [math]y_i=f(x_i),

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

Действительно, [math]N_k(x)[/math] — многочлен k-й степени, что определяется сомножителями последнего слагаемого (разделенные разности, входящие в качестве одного из сомножителей в эти произведения, есть числа). Кроме того, для многочлена [math]N_k(x)[/math] удовлетворяются функциональные условия интерполяции: [math]N_k(x_j)= f_j,

Таким образом, условия интерполяции для многочлена [math]N_2(x)[/math] также выполнены и он может использоваться для параболической интерполяции кусочным способом.

Для произвольного [math]k[/math] справедливость равенств [math]N_k(x_j)=f_i,

2. Интерполяционный многочлен Ньютона (4.29) или (4.32) (так же, как и многочлен Ньютона, выражаемый ниже через конечные разности) записан не через значения функции, как это имеет место для многочлена Лагранжа, а через разделенные разности. Поэтому при изменении степени [math]k[/math] в процессе интерполирования у многочлена Ньютона [math]N_k(x)[/math] требуется только добавить или отбросить соответствующее число слагаемых. Это иногда упрощает алгоритм интерполирования.

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

Сначала рассмотрим решение задачи кусочной интерполяции (применение кусочного способа). Если функция [math]y_i= f(x_i),

где [math]q=\frac[/math] — фаза интерполяции, определенная относительно точки [math]x_i[/math] ; [math]\Delta^jf_i

(j=1,2,\ldots,k)[/math] — конечные разности.

Данный многочлен удобно применять в конце выделенного шаблона или всей таблицы [math]y_i= f(x_i),

Остаточное слагаемое многочлена (4.36) имеет вид

Схема выбора узлов интерполяции при изменении степеней интерполяционных многочленов [math]N_^<(I)>(q),

1. Из формул интерполяционных многочленов [math]N_^<(I)>(q)[/math] и [math]N_^<(II)>(\widehat)[/math] видно, что повышение их степеней в процессе реализации алгоритма не требует пересчета предыдущих слагаемых, входящих в многочлены с меньшими степенями.

4.7>>\\\hline i& 0& 1& 2& 3\\\hline x_i& 2&3& 4& 5\\\hline f(x_i)=f_i& 7&5& 8& 7\\\hline \end[/math]

Построим многочлен Ньютона (4.32), справедливый для произвольного расположения узлов. Для этого составим табл. 4.8, аналогичную табл. 4.5:

По формуле (4.32) для [math]n=3[/math] имеем

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

Запишем также второй интерполяционный многочлен Ньютона (4.36):

По формуле (4.34) имеем

Вычислим значение функции в точке [math]x_<\ast>=2,\!5\colon[/math]

Так как точка [math]x_<\ast>=2,\!5[/math] находится вблизи узла [math]x_i=x_2[/math] и шаблон [math](x_2,x_3,x_4)[/math] имеет неравномерность по шагу, то для выполнения интерполяции выбираем многочлен Ньютона (4.29).

1. Определим разделенные разности [math]f(x_i,x_),

Сравнивая [math]N_2(x)[/math] с соответствующим многочленом Лагранжа L_2(x) (см. пример 4.3), видим, что они совпадают. Это подтверждает единственность решения задачи о построении интерполяционного многочлена.

2. Вычислим значения [math]\Bigl.\Bigr|_>,

Таким образом, найдена фактическая погрешность, которая для квадратичной интерполяции получилась в 4 раза меньше.

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

Для подсчета значения функции в точке [math]x_<\ast 1>=2,\!5[/math] (согласно рис. 4.5,а) выбираем шаблон [math](x_0,x_1,x_2)= (2;3;4)[/math] для параболической интерполяции [math](i=0,

k=2)[/math] и шаблон [math](x_0,x_1)= (2;3)[/math] Для линейной интерполяции [math](i=0,

где [math]q=\frac<1>[/math] (см. табл. 4.9). В результате подстановки получаем

В заданной точке [math]N_1^<(I)>(2,\!5)=6;

Для подсчета значения в точке [math]x_<\ast 2>=4,\!5[/math] выбираем шаблон [math](3;4;5)= (x_1,x_2,x_3)[/math] для параболической интерполяции [math](i=1,

k=2)[/math] и шаблон [math](4;5)=(x_2,x_3)[/math] для линейной интерполяции [math](i=2,

В заданной точке [math]N_1^<(II)>(4,\!5)=7,\!5;

k=2)[/math] и шаблон [math](3;4)=(x_1,x_2)[/math] для линейной интерполяции [math](i=1,

Подсчитать значения в точке [math]x_<\ast3>=3,\!5[/math] (согласно рис. 4.5,б) можно, использовав шаблон [math](2;3;4)= (x_0,x_1,x_2)[/math] для параболической интерполяции [math](i=0,

k=2)[/math] и шаблон [math](3;4)=(x_1,x_2)[/math] для линейной интерполяции [math](i=1,

Источник