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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

${\displaystyle 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}).}$

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

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

${\displaystyle {\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}}}$

Это называется формулой Ньютона для прямого деления разности . ^{[ требуется ссылка ]}

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

${\displaystyle 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}).}$

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

${\displaystyle {\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 . Формула Ньютона — это многочлен Тейлора, основанный на конечных разностях вместо мгновенных скоростей изменения.

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

$${\displaystyle 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})}}$

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

Это можно показать для случая, когда : и когда :${\displaystyle i=0,1,2,3,\cdots ,n}$$${\displaystyle p_{n+1}(x_{i})=p_{n}(x_{i})+a_{n+1}\prod _{j=0}^{n}(x_{i}-x_{j})=p_{n}(x_{i})}$$${\displaystyle i=n+1}$

$${\displaystyle 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})}$$

В силу уникальности интерполированных полиномов степени меньше , требуется интерполяция полинома. Таким образом, функция может быть выражена как:${\displaystyle 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})}$

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

Принимая для некоторой неизвестной функции в формулах разделенных разностей Ньютона, если представление x в предыдущих разделах было принято как , в терминах прямых разностей , формула прямой интерполяции Ньютона выражается как: тогда как для того же самого в терминах обратных разностей формула обратной интерполяции Ньютона выражается как: Это следует из того, что связь между разделенными разностями и прямыми разностями задается как: ^[3] тогда как для обратных разностей она задается как: ^{[ требуется ссылка ]}${\displaystyle y_{i}=f(x_{i})}$${\displaystyle x=x_{j}+sh}$$${\displaystyle f(x)\approx N(x)=N(x_{j}+sh)=\sum _{i=0}^{k}{s \choose i}\Delta ^{(i)}f(x_{j})}$$$${\displaystyle f(x)\approx N(x)=N(x_{j}+sh)=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}\nabla ^{(i)}f(x_{j}).}$$$${\displaystyle [y_{j},y_{j+1},\ldots ,y_{j+n}]={\frac {1}{n!h^{n}}}\Delta ^{(n)}y_{j},}$$$${\displaystyle [{y}_{j},y_{j-1},\ldots ,{y}_{j-n}]={\frac {1}{n!h^{n}}}\nabla ^{(n)}y_{j}.}$$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С помощью формы Ньютона интерполирующего полинома существует компактный и эффективный алгоритм для объединения членов с целью нахождения коэффициентов полинома. ^[5]

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

Доказательство этого — простая индукция: мы вычисляем ${\displaystyle n=1}$$${\displaystyle [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}].}$$

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

$${\displaystyle [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, который для целей индукции и ясности мы также называем Утверждением ( ):${\displaystyle n}$${\displaystyle {\text{Stm}}_{n}}$

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

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

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

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

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

$${\displaystyle {\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}}}$$

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

$${\displaystyle {\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}}}$$

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

Таким образом, мы можем записать последнюю строку в первой цепочке равенств как ` ' и тем самым установить, что Итак, мы установили , и, следовательно, завершили доказательство Факта 2. ${\displaystyle y_{n+1}-P(x_{n+1})}$$${\displaystyle [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}).}$$${\displaystyle {\text{Stm}}_{n+1}}$

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

Предел многочлена Ньютона, если все узлы совпадают, является многочленом Тейлора , поскольку разделенные разности становятся производными.$${\displaystyle {\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 требуется интерполировать по точкам . Запишите${\displaystyle x_{0},\ldots ,x_{n}}$

${\displaystyle {\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 ), используя разделенные разности в точках

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

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

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

Наклон порядка получается следующим образом:${\displaystyle 1}$

• ${\displaystyle 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}$
• ${\displaystyle 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}$
• ${\displaystyle 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}$

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

• ${\displaystyle 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}$
• ${\displaystyle 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}$

Наконец, определим наклон порядка :${\displaystyle 3}$

• ${\displaystyle 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}}}$

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

• ${\displaystyle p_{0}(x)=6}$.
• ${\displaystyle p_{1}(x)=6+3(x-1)}$
• ${\displaystyle p_{2}(x)=6+3(x-1)-5(x-1)(x-2)}$.
• ${\displaystyle 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 году.
• ряд Ньютона
• Схема Невилла
• Полиномиальная интерполяция
• Форма Лагранжа интерполяционного полинома
• Форма Бернштейна интерполяционного полинома
• Интерполяция Эрмита
• Теорема Карлсона
• Таблица рядов Ньютона

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