Полином Ньютона

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

Определение

Учитывая набор из k + 1 точек данных

$(x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{k},y_{k})$

где нет двух x _j одинаковых , интерполяционный полином Ньютона представляет собой линейную комбинацию Ньютона базисных полиномов

$N(x):=\sum _{j=0}^{k}a_{j}n_{j}(x)$

с базисными полиномами Ньютона, определяемыми как

$n_{j}(x):=\prod _{i=0}^{j-1}(x-x_{i})$

для j > 0 и $n_{0}(x)\equiv 1$.

Коэффициенты определяются как

$a_{j}:=[y_{0},\ldots ,y_{j}]$

где

$[y_{0},\ldots ,y_{j}]$

это обозначение разделенных разностей .

Таким образом, полином Ньютона можно записать как

$N(x)=[y_{0}]+[y_{0},y_{1}](x-x_{0})+\cdots +[y_{0},\ldots ,y_{k}](x-x_{0})(x-x_{1})\cdots (x-x_{k-1}).$

Формула прямой

Полином Ньютона можно выразить в упрощенной форме, если $x_{0},x_{1},\dots ,x_{k}$ расположены последовательно с одинаковым интервалом.

Если $x_{0},x_{1},\dots ,x_{k}$ расположены последовательно и на равном расстоянии от ${x}_{i}={x}_{0}+ih$ для i = 0, 1, ..., k и некоторой переменной x выражается как ${x}={x}_{0}+sh$, то разница $x-x_{i}$ можно записать как $(s-i)h$. Таким образом, полином Ньютона становится

${\begin{aligned}N(x)&=[y_{0}]+[y_{0},y_{1}]sh+\cdots +[y_{0},\ldots ,y_{k}]s(s-1)\cdots (s-k+1){h}^{k}\\&=\sum _{i=0}^{k}s(s-1)\cdots (s-i+1){h}^{i}[y_{0},\ldots ,y_{i}]\\&=\sum _{i=0}^{k}{s \choose i}i!{h}^{i}[y_{0},\ldots ,y_{i}].\end{aligned}}$

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

Формула обратного

Если узлы переупорядочены как ${x}_{k},{x}_{k-1},\dots ,{x}_{0}$, полином Ньютона становится

$N(x)=[y_{k}]+[{y}_{k},{y}_{k-1}](x-{x}_{k})+\cdots +[{y}_{k},\ldots ,{y}_{0}](x-{x}_{k})(x-{x}_{k-1})\cdots (x-{x}_{1}).$

Если ${x}_{k},\;{x}_{k-1},\;\dots ,\;{x}_{0}$ расположены на равном расстоянии от ${x}_{i}={x}_{k}-(k-i)h$ для i = 0, 1, ..., k и ${x}={x}_{k}+sh$, затем,

${\begin{aligned}N(x)&=[{y}_{k}]+[{y}_{k},{y}_{k-1}]sh+\cdots +[{y}_{k},\ldots ,{y}_{0}]s(s+1)\cdots (s+k-1){h}^{k}\\&=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots ,{y}_{k-i}].\end{aligned}}$

Это называется формулой обратного деления разности Ньютона .

Значение

Дополнительная информация: Конечные разности § Ряд Ньютона.

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

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

Основная статья: Полиномиальная интерполяция

Для полинома $p_{n}$ степени меньше или равной n, которая интерполирует $f$ в узлах $x_{i}$ где $i=0,1,2,3,\cdots ,n$. Позволять $p_{n+1}$ — многочлен степени меньше или равной n+1, который интерполирует $f$ в узлах $x_{i}$ где $i=0,1,2,3,\cdots ,n,n+1$. Затем $p_{n+1}$ дается:

$$p_{n+1}(x)=p_{n}(x)+a_{n+1}w_{n}(x)$$

где ${\textstyle w_{n}(x):=\prod _{i=0}^{n}(x-x_{i})}$ и ${\textstyle a_{n+1}:={f(x_{n+1})-p_{n}(x_{n+1}) \over w_{n}(x_{n+1})}}$.

Доказательство:

Это можно показать для случая, когда $i=0,1,2,3,\cdots ,n$:

$$p_{n+1}(x_{i})=p_{n}(x_{i})+a_{n+1}\prod _{j=0}^{n}(x_{i}-x_{j})=p_{n}(x_{i})$$

и когда $i=n+1$:

$$p_{n+1}(x_{n+1})=p_{n}(x_{n+1})+{f(x_{n+1})-p_{n}(x_{n+1}) \over w_{n}(x_{n+1})}w_{n}(x_{n+1})=f(x_{n+1})$$

В силу единственности интерполированных полиномов степени меньше $n+1$, ${\textstyle p_{n+1}(x)=p_{n}(x)+a_{n+1}w_{n}(x)}$ – требуемая полиномиальная интерполяция. Таким образом, функцию можно выразить как:

${\textstyle p_{n}(x)=a_{0}+a_{1}(x-x_{0})+a_{2}(x-x_{0})(x-x_{1})+\cdots +a_{n}(x-x_{0})\cdots (x-x_{n-1})}$

где факторы $a_{i}$ разделены различия . Таким образом, полиномы Ньютона используются для получения формулы полиномиальной интерполяции n точек.

принимая $y_{i}=f(x_{i})$ для некоторой неизвестной функции в формулах разделенных разностей Ньютона, если вместо этого было принято представление x в предыдущих разделах как $x=x_{j}+sh$, с точки зрения прямых разностей , формула прямой интерполяции Ньютона выражается как:

$$f(x)\approx N(x)=N(x_{j}+sh)=\sum _{i=0}^{k}{s \choose i}\Delta ^{(i)}f(x_{j})$$

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

$$f(x)\approx N(x)=N(x_{j}+sh)=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}\nabla ^{(i)}f(x_{j}).$$

Это следует из того, что связь между разделенными разницами и прямыми разницами определяется как:

$$[y_{j},y_{j+1},\ldots ,y_{j+n}]={\frac {1}{n!h^{n}}}\Delta ^{(n)}y_{j},$$

тогда как для обратных разностей он определяется как:

$$[{y}_{j},y_{j-1},\ldots ,{y}_{j-n}]={\frac {1}{n!h^{n}}}\nabla ^{(n)}y_{j}.$$

Добавление новых пунктов

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

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

Гаусс, Стирлинг и Бессель разработали формулы для решения этой проблемы.

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

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

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

Бессель и Стирлинг достигают этого, иногда используя среднее двух разностей, а иногда среднее двух произведений биномов по x , тогда как Ньютон или Гаусс использовали бы только одну разность или произведение. Стирлинг использует среднюю разницу в нечетной степени (разность которой использует четное количество точек данных); Бессель использует среднюю разницу в четных степенях (разница которой использует нечетное количество точек данных).

Сильные и слабые стороны различных формул

Для любого заданного конечного набора точек данных существует только один полином наименьшей возможной степени, который проходит через все из них. Таким образом, уместно говорить о «форме Ньютона», или форме Лагранжа и т. д. интерполяционного полинома. Однако разные методы вычисления этого полинома могут иметь разную вычислительную эффективность. Существует несколько подобных методов, например методы Гаусса, Бесселя и Стирлинга. Их можно получить из значений Ньютона, переименовав значения x точек данных, но на практике они важны.

Бессель против Стирлинга

Выбор между Бесселем и Стирлингом зависит от того, находится ли интерполированная точка ближе к точке данных или ближе к середине между двумя точками данных.

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

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

Методы разделенной

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

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

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

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

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

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

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

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

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

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

Точность

Когда в случае Стирлинга или Бесселя последний использованный член включает среднее из двух разностей, тогда используется на одну точку больше, чем при интерполяции Ньютона или других полиномиальных интерполяциях для той же степени полинома. Таким образом, в этом случае метод Стирлинга или Бесселя не проводит полином N -1 степени через N точек, а вместо этого обменивает эквивалентность с полиномом Ньютона для лучшего центрирования и точности, что дает этим методам иногда потенциально большую точность для заданной степени полинома. , чем другие полиномиальные интерполяции.

Общий случай

Для частного случая x _i = i существует тесно связанный набор полиномов, также называемых полиномами Ньютона, которые представляют собой просто биномиальные коэффициенты для общего аргумента. То есть также имеются полиномы Ньютона $p_{n}(z)$ данный

$p_{n}(z)={z \choose n}={\frac {z(z-1)\cdots (z-n+1)}{n!}}$

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

Основная идея

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

Для k + 1 точек данных мы строим базис Ньютона как

$n_{0}(x):=1,\qquad n_{j}(x):=\prod _{i=0}^{j-1}(x-x_{i})\qquad j=1,\ldots ,k.$

Используя эти полиномы в качестве основы для $\Pi _{k}$ мы должны решить

${\begin{bmatrix}1&&\ldots &&0\\1&x_{1}-x_{0}&&&\\1&x_{2}-x_{0}&(x_{2}-x_{0})(x_{2}-x_{1})&&\vdots \\\vdots &\vdots &&\ddots &\\1&x_{k}-x_{0}&\ldots &\ldots &\prod _{j=0}^{k-1}(x_{k}-x_{j})\end{bmatrix}}{\begin{bmatrix}a_{0}\\\\\vdots \\\\a_{k}\end{bmatrix}}={\begin{bmatrix}y_{0}\\\\\vdots \\\\y_{k}\end{bmatrix}}$

решить задачу полиномиальной интерполяции.

Эту систему уравнений можно решить итерационно, решив

$\sum _{i=0}^{j}a_{i}n_{i}(x_{j})=y_{j}\qquad j=0,\dots ,k.$

Вывод

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

Факт 1. Обращение членов разделенной разности оставляет ее неизменной: $[y_{0},\ldots ,y_{n}]=[y_{n},\ldots ,y_{0}].$

Доказательством этого является простая индукция: для $n=1$ мы вычисляем

$$[y_{0},y_{1}]={\frac {[y_{1}]-[y_{0}]}{x_{1}-x_{0}}}={\frac {[y_{0}]-[y_{1}]}{x_{0}-x_{1}}}=[y_{1},y_{0}].$$

Шаг индукции: предположим, что результат верен для любой разделенной разности, включающей не более $n+1$ условия. Затем, используя гипотезу индукции в следующем втором равенстве, мы видим, что для разделенной разности, включающей $n+2$ условия у нас есть

$$[y_{0},\ldots ,y_{n+1}]={\frac {[y_{1},\ldots ,y_{n+1}]-[y_{0},\ldots ,y_{n}]}{x_{n+1}-x_{0}}}={\frac {[y_{n},\ldots ,y_{0}]-[y_{n+1},\ldots ,y_{1}]}{x_{0}-x_{n+1}}}=[y_{n+1},\ldots ,y_{0}].$$

Сформулируем следующий Факт 2, который в целях индукции и ясности мы также называем Утверждением. $n$( ${\text{Stm}}_{n}$) :

Факт 2. ( ${\text{Stm}}_{n}$) : Если $(x_{0},y_{0}),\ldots ,(x_{n-1},y_{n-1})$ есть какие-нибудь $n$ точки с отчетливыми $x$-координаты и $P=P(x)$ – единственный полином степени (не более) $n-1$ чей график проходит через эти $n$ точек, то имеет место соотношение

$$[y_{0},\ldots ,y_{n}](x_{n}-x_{0})\cdot \ldots \cdot (x_{n}-x_{n-1})=y_{n}-P(x_{n})$$

Доказательство. (Для беглого чтения доказательства будет полезно иметь в виду точное утверждение и его тонкости: $P$ определяется путем прохождения через $(x_{0},y_{0}),...,(x_{n-1},y_{n-1})$ но формула говорит и по обе стороны от дополнительной произвольной точки $(x_{n},y_{n})$ с $x$-координата отличается от другой $x_{i}$.)

Мы снова докажем эти утверждения по индукции.Чтобы показать ${\text{Stm}}_{1},$ позволять $(x_{0},y_{0})$ быть любой одной точкой и пусть $P(x)$ — уникальный многочлен степени 0, проходящий через $(x_{0},y_{0})$. Тогда очевидно $P(x)=y_{0}$ и мы можем написать

$$[y_{0},y_{1}](x_{1}-x_{0})={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x_{1}-x_{0})=y_{1}-y_{0}=y_{1}-P(x_{1})$$

как хотелось.

Доказательство ${\text{Stm}}_{n+1},$ предполагая ${\text{Stm}}_{n}$ уже установлено: Пусть $P(x)$ быть полиномом степени (не более) $n$ проходя через $(x_{0},y_{0}),\ldots ,(x_{n},y_{n}).$

С $Q(x)$ являющийся уникальным полиномом степени (не более) $n-1$ проходя через точки $(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$, мы можем написать следующую цепочку равенств, где мы используем в предпоследнее равенство, что Stm $_{n}$ относится к $Q$:

$${\begin{aligned}&[y_{0},\ldots ,y_{n+1}](x_{n+1}-x_{0})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&={\frac {[y_{1},\ldots ,y_{n+1}]-[y_{0},\ldots ,y_{n}]}{x_{n+1}-x_{0}}}(x_{n+1}-x_{0})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=\left([y_{1},\ldots ,y_{n+1}]-[y_{0},\ldots ,y_{n}]\right)(x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=[y_{1},\ldots ,y_{n+1}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})-[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=(y_{n+1}-Q(x_{n+1}))-[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=y_{n+1}-(Q(x_{n+1})+[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})).\end{aligned}}$$

Индукционная гипотеза для $Q$ также применимо ко второму равенству в следующем вычислении, где $(x_{0},y_{0})$ добавляется к точкам, определяющим $Q$ :

$${\begin{aligned}&Q(x_{0})+[y_{0},\ldots ,y_{n}](x_{0}-x_{1})\cdot \ldots \cdot (x_{0}-x_{n})\\&=Q(x_{0})+[y_{n},\ldots ,y_{0}](x_{0}-x_{n})\cdot \ldots \cdot (x_{0}-x_{1})\\&=Q(x_{0})+y_{0}-Q(x_{0})\\&=y_{0}\\&=P(x_{0}).\\\end{aligned}}$$

Теперь посмотрите на $Q(x)+[y_{0},\ldots ,y_{n}](x-x_{1})\cdot \ldots \cdot (x-x_{n}).$ По определению $Q$ этот полином проходит через $(x_{1},y_{1}),...,(x_{n},y_{n})$ и, как мы только что показали, оно также проходит через $(x_{0},y_{0}).$ Таким образом, это единственный полином степени $\leq n$ которая проходит через эти точки. Следовательно, этот полином $P(x);$ то есть: $P(x)=Q(x)+[y_{0},\ldots ,y_{n}](x-x_{1})\cdot \ldots \cdot (x-x_{n}).$

Таким образом, мы можем записать последнюю строку в первой цепочке равенств как ` $y_{n+1}-P(x_{n+1})$' и таким образом установили, что

$$[y_{0},\ldots ,y_{n+1}](x_{n+1}-x_{0})\cdot \ldots \cdot (x_{n+1}-x_{n})=y_{n+1}-P(x_{n+1}).$$

Итак, мы учредил ${\text{Stm}}_{n+1}$, и тем самым завершили доказательство факта 2.

Теперь посмотрим на факт 2: его можно сформулировать так: если $P$ – единственный полином степени не выше $n-1$ график которого проходит через точки $(x_{0},y_{0}),...,(x_{n-1},y_{n-1}),$ затем $P(x)+[y_{0},\ldots ,y_{n}](x-x_{0})\cdot \ldots \cdot (x-x_{n-1})$ – единственный полином степени не выше $n$ прохождение через точки $(x_{0},y_{0}),...,(x_{n-1},y_{n-1}),(x_{n},y_{n}).$ Итак, мы видим, что интерполяция Ньютона действительно позволяет добавлять новые точки интерполяции, не разрушая то, что уже было вычислено.

Полином Тейлора

Предел полинома Ньютона, если все узлы совпадают, является полиномом Тейлора , поскольку разделенные разности становятся производными.

$${\begin{aligned}&\lim _{(x_{0},\dots ,x_{n})\to (z,\dots ,z)}f[x_{0}]+f[x_{0},x_{1}]\cdot (\xi -x_{0})+\dots +f[x_{0},\dots ,x_{n}]\cdot (\xi -x_{0})\cdot \dots \cdot (\xi -x_{n-1})\\&=f(z)+f'(z)\cdot (\xi -z)+\dots +{\frac {f^{(n)}(z)}{n!}}\cdot (\xi -z)^{n}\end{aligned}}$$

Приложение

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

Примеры

Разделенные разности можно записать в виде таблицы. Например, для функции f необходимо интерполировать по точкам $x_{0},\ldots ,x_{n}$. Писать

${\begin{matrix}x_{0}&f(x_{0})&&\\&&{f(x_{1})-f(x_{0}) \over x_{1}-x_{0}}&\\x_{1}&f(x_{1})&&{{f(x_{2})-f(x_{1}) \over x_{2}-x_{1}}-{f(x_{1})-f(x_{0}) \over x_{1}-x_{0}} \over x_{2}-x_{0}}\\&&{f(x_{2})-f(x_{1}) \over x_{2}-x_{1}}&\\x_{2}&f(x_{2})&&\vdots \\&&\vdots &\\\vdots &&&\vdots \\&&\vdots &\\x_{n}&f(x_{n})&&\\\end{matrix}}$

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

Например, предположим, что нам нужно построить интерполяционный полином f ( x ) = tan( x ), используя разделенные разности, в точках

$n$	$x_{n}$	$f(x_{n})$
$0$	$-{\tfrac {3}{2}}$	$-14.1014$
$1$	$-{\tfrac {3}{4}}$	$-0.931596$
$2$	$0$	$0$
$3$	${\tfrac {3}{4}}$	$0.931596$
$4$	${\tfrac {3}{2}}$	$14.1014$

Используя шесть знаков точности, построим таблицу

${\begin{matrix}-{\tfrac {3}{2}}&-14.1014&&&&\\&&17.5597&&&\\-{\tfrac {3}{4}}&-0.931596&&-10.8784&&\\&&1.24213&&4.83484&\\0&0&&0&&0\\&&1.24213&&4.83484&\\{\tfrac {3}{4}}&0.931596&&10.8784&&\\&&17.5597&&&\\{\tfrac {3}{2}}&14.1014&&&&\\\end{matrix}}$

Таким образом, интерполяционный полином равен

${\begin{aligned}&-14.1014+17.5597(x+{\tfrac {3}{2}})-10.8784(x+{\tfrac {3}{2}})(x+{\tfrac {3}{4}})+4.83484(x+{\tfrac {3}{2}})(x+{\tfrac {3}{4}})(x)+0(x+{\tfrac {3}{2}})(x+{\tfrac {3}{4}})(x)(x-{\tfrac {3}{4}})\\={}&-0.00005-1.4775x-0.00001x^{2}+4.83484x^{3}\end{aligned}}$

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

Другой пример:

Последовательность $f_{0}$ такой, что $f_{0}(1)=6,f_{0}(2)=9,f_{0}(3)=2$ и $f_{0}(4)=5$, то есть они $6,9,2,5$ от $x_{0}=1$ к $x_{3}=4$.

Вы получаете наклон порядка $1$ следующим образом:

• $f_{1}(x_{0},x_{1})={\frac {f_{0}(x_{1})-f_{0}(x_{0})}{x_{1}-x_{0}}}={\frac {9-6}{2-1}}=3$
• $f_{1}(x_{1},x_{2})={\frac {f_{0}(x_{2})-f_{0}(x_{1})}{x_{2}-x_{1}}}={\frac {2-9}{3-2}}=-7$
• $f_{1}(x_{2},x_{3})={\frac {f_{0}(x_{3})-f_{0}(x_{2})}{x_{3}-x_{2}}}={\frac {5-2}{4-3}}=3$

Так как у нас склоны в порядке $1$, то можно получить следующий заказ:

• $f_{2}(x_{0},x_{1},x_{2})={\frac {f_{1}(x_{1},x_{2})-f_{1}(x_{0},x_{1})}{x_{2}-x_{0}}}={\frac {-7-3}{3-1}}=-5$
• $f_{2}(x_{1},x_{2},x_{3})={\frac {f_{1}(x_{2},x_{3})-f_{1}(x_{1},x_{2})}{x_{3}-x_{1}}}={\frac {3-(-7)}{4-2}}=5$

Наконец, мы определяем наклон порядка $3$:

• $f_{3}(x_{0},x_{1},x_{2},x_{3})={\frac {f_{2}(x_{1},x_{2},x_{3})-f_{2}(x_{0},x_{1},x_{2})}{x_{3}-x_{0}}}={\frac {5-(-5)}{4-1}}={\frac {10}{3}}$

Зная наклон, мы можем определить последующие полиномы:

• $p_{0}(x)=6$.
• $p_{1}(x)=6+3(x-1)$
• $p_{2}(x)=6+3(x-1)-5(x-1)(x-2)$.
• $p_{3}(x)=6+3(x-1)-5(x-1)(x-2)+{\frac {10}{3}}(x-1)(x-2)(x-3)$

См. также

• De numeris triangularibus et inde de Progressionibus arithmeticis: Magisteria magna , работа Томаса Харриота, описывающая аналогичные методы интерполяции, написанная на 50 лет раньше работы Ньютона, но опубликованная не раньше 2009 года.
• серия Ньютона
• Схема Невилла
• Полиномиальная интерполяция
• Лагранжевая форма интерполяционного полинома
• Форма Бернштейна интерполяционного полинома
• Интерполяция Эрмита
• Теорема Карлсона
• Таблица ньютоновских рядов

Внешние ссылки

• Модуль для полинома Ньютона Джона Х. Мэтьюза