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

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

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

Учитывая набор из n + 1 точек данных , в которых нет двух одинаковых, говорят , что полиномиальная функция интерполирует данные, если для каждой . ${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$ ${\displaystyle x_{j}}$ ${\displaystyle p(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}}$ ${\displaystyle p(x_{j})=y_{j}}$ ${\displaystyle j\in \{0,1,\dotsc ,n\}}$

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

Приложения

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

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

В численном анализе полиномиальная интерполяция необходима для выполнения субквадратного умножения и возведения в квадрат, например умножения Карацубы и умножения Тума – Кука , где интерполяция через точки на полиноме произведения дает конкретный требуемый продукт. Например, учитывая a = f ( x ) = a ₀ x ⁰ + a ₁ x ¹ + ··· и b = g ( x ) = b ₀ x ⁰ + b ₁ x ¹ + ···, произведение ab равно конкретное значение W ( x ) = f ( x ) g ( x ). Можно легко найти точки вдоль W ( x ) при малых значениях x , и интерполяция на основе этих точек даст члены W ( x ) и конкретное произведение ab . Как сформулировано в умножении Карацубы, этот метод существенно быстрее, чем квадратичное умножение, даже для входных данных скромного размера, особенно на параллельном оборудовании.

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

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

Для любых двумерных точек данных , где нет двух одинаковых, существует уникальный полином не более степени, который интерполирует эти точки, т.е. ^[2] ${\displaystyle n+1}$ ${\displaystyle (x_{0},y_{0}),\dotsc ,(x_{n},y_{n})\in \mathbb {R} ^{2}}$ ${\displaystyle x_{j}}$ ${\displaystyle p(x)}$ ${\displaystyle n}$ ${\displaystyle p(x_{0})=y_{0},\ldots ,p(x_{n})=y_{n}}$

Эквивалентно, для фиксированного выбора узлов интерполяции полиномиальная интерполяция определяет линейную биекцию между ( n +1)-кортежами значений действительных чисел и векторным пространством действительных полиномов степени не более n : ${\displaystyle x_{j}}$ ${\displaystyle L_{n}}$ ${\displaystyle (y_{0},\ldots ,y_{n})\in \mathbb {R} ^{n+1}}$ ${\displaystyle P(n)}$

$${\displaystyle L_{n}:\mathbb {R} ^{n+1}{\stackrel {\sim }{\longrightarrow }}\,P(n).}$$

Это разновидность теоремы о неразрешимости . Теорема также справедлива для любого бесконечного поля вместо действительных чисел , например рациональных или комплексных чисел. ${\displaystyle \mathbb {R} }$

Первое доказательство

Рассмотрим базисные функции Лагранжа , определяемые следующим образом: ${\displaystyle L_{1}(x),\ldots ,L_{n}(x)}$

$${\displaystyle L_{j}(x)=\prod _{i\neq j}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {(x-x_{1})\cdots (x-x_{j-1})(x-x_{j+1})\cdots (x-x_{n})}{(x_{j}-x_{1})\cdots (x_{j}-x_{j-1})(x_{j}-x_{j+1})\cdots (x_{j}-x_{n})}}.}$$

Обратите внимание, что это полином степени , и у нас есть для каждого , в то время как . Отсюда следует, что линейная комбинация: ${\displaystyle L_{j}(x)}$ ${\displaystyle n}$ ${\displaystyle L_{j}(x_{k})=0}$ ${\displaystyle j\neq k}$ ${\displaystyle L_{k}(x_{k})=1}$

$${\displaystyle p(x)=\sum _{j=0}^{n}y_{j}L_{j}(x)}$$

${\displaystyle p(x_{k})=\sum _{j}y_{j}\,L_{j}(x_{k})=y_{k}}$ ${\displaystyle p(x)}$ ${\displaystyle n}$

Для доказательства единственности предположим, что существует другой интерполяционный полином степени не выше , так что для всех . Тогда – многочлен степени не выше , имеющий различные нули ( ). Но ненулевой полином не более степени может иметь не более нулей, ^[a] так же должен быть нулевой многочлен, т.е. ^[3] ${\displaystyle q(x)}$ ${\displaystyle n}$ ${\displaystyle p(x_{k})=q(x_{k})}$ ${\displaystyle k=0,\dotsc ,n}$ ${\displaystyle p(x)-q(x)}$ ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle x_{k}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle p(x)-q(x)}$ ${\displaystyle p(x)=q(x)}$

Второе доказательство

Запишите интерполяционный полином в виде

Подставив это в уравнения интерполяции , получим систему линейных уравнений в коэффициентах , которая в матрично-векторной форме читается как следующее умножение : ${\displaystyle p(x_{j})=y_{j}}$ ${\displaystyle a_{j}}$

$${\displaystyle {\begin{bmatrix}x_{0}^{n}&x_{0}^{n-1}&x_{0}^{n-2}&\ldots &x_{0}&1\\x_{1}^{n}&x_{1}^{n-1}&x_{1}^{n-2}&\ldots &x_{1}&1\\\vdots &\vdots &\vdots &&\vdots &\vdots \\x_{n}^{n}&x_{n}^{n-1}&x_{n}^{n-2}&\ldots &x_{n}&1\end{bmatrix}}{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{0}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}.}$$

Интерполянт соответствует решению приведенного выше матричного уравнения . Матрица X слева представляет собой матрицу Вандермонда , определитель которой, как известно, не равен нулю, поскольку все узлы различны. Это гарантирует, что матрица обратима и уравнение имеет единственное решение ; то есть существует и уникален. ${\displaystyle p(x)}$ ${\displaystyle A=(a_{n},\ldots ,a_{0})}$ ${\displaystyle X\cdot A=Y}$ ${\displaystyle \textstyle \det(X)=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}),}$ ${\displaystyle x_{j}}$ ${\displaystyle A=X^{-1}\cdot Y}$ ${\displaystyle p(x)}$

Следствие

Если является многочленом степени не более , то интерполяционным многочленом в различных точках является он сам. ${\displaystyle f(x)}$ ${\displaystyle n}$ ${\displaystyle f(x)}$ ${\displaystyle n+1}$ ${\displaystyle f(x)}$

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

Красные точки обозначают точки данных ( x _k , y _k ) , а синяя кривая показывает полином интерполяции.

Интерполяция Лагранжа

Мы можем сразу записать полином через полиномы Лагранжа как:

$${\displaystyle {\begin{aligned}p(x)&={\frac {(x-x_{1})(x-x_{2})\cdots (x-x_{n})}{(x_{0}-x_{1})(x_{0}-x_{2})\cdots (x_{0}-x_{n})}}y_{0}\\[4pt]&+{\frac {(x-x_{0})(x-x_{2})\cdots (x-x_{n})}{(x_{1}-x_{0})(x_{1}-x_{2})\cdots (x_{1}-x_{n})}}y_{1}\\[4pt]&+\cdots \\[4pt]&+{\frac {(x-x_{0})(x-x_{1})\cdots (x-x_{n-1})}{(x_{n}-x_{0})(x_{n}-x_{1})\cdots (x_{n}-x_{n-1})}}y_{n}\\[7pt]&=\sum _{i=0}^{n}{\Biggl (}\prod _{\stackrel {\!0\,\leq \,j\,\leq \,n}{j\,\neq \,i}}{\frac {x-x_{j}}{x_{i}-x_{j}}}{\Biggr )}y_{i}=\sum _{i=0}^{n}{\frac {p(x)}{p'(x_{i})(x-x_{i})}}\,y_{i}\end{aligned}}}$$

формулой Сильвестраковариантами Фробениуса

Интерполяция Ньютона

Теорема

Для полинома степени меньше или равной 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}).}$

Полиномиальные коэффициенты

Чтобы найти , нам нужно решить нижнюю треугольную матрицу , образованную преобразованием приведенного выше уравнения в матричную форму: ${\displaystyle a_{i}}$ ${\textstyle p_{n}(x_{i})=f(x_{i})=y_{i}}$

${\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}^{n-1}(x_{n}-x_{j})\end{bmatrix}}{\begin{bmatrix}a_{0}\\\\\vdots \\\\a_{n}\end{bmatrix}}={\begin{bmatrix}y_{0}\\\\\vdots \\\\y_{n}\end{bmatrix}}}$

Коэффициенты выводятся как

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

где

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

это обозначение разделенных разностей . Таким образом, полиномы Ньютона используются для получения формулы полиномиальной интерполяции n точек. ^[3]

Форвардная формула Ньютона

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

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

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

Поскольку связь между разделенными разностями и прямыми разностями определяется как: ^[4]

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

формула прямой интерполяции Ньютона ${\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 x_{j}}$

$${\displaystyle f(x_{j}+sh)=f(x_{j})+{\frac {s}{1!}}\Delta f(x_{j})+{\frac {s(s-1)}{2!}}\Delta ^{2}f(x_{j})+{\frac {s(s-1)(s-2)}{3!}}\Delta ^{3}f(x_{j})+{\frac {s(s-1)(s-2)(s-3)}{4!}}\Delta ^{4}f(x_{j})+\cdots }$$

Обратная формула Ньютона

Если узлы переупорядочить как , полином Ньютона станет ${\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}}}$

^{Поскольку связь между} разделенными различиями и обратными различиями определяется как ^:

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

формула обратной интерполяции Ньютона ${\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}{(-1)}^{i}{-s \choose i}\nabla ^{(i)}f(x_{j}).}$$

${\displaystyle x_{j}}$

$${\displaystyle f(x_{j}+sh)=f(x_{j})+{\frac {s}{1!}}\nabla f(x_{j})+{\frac {s(s+1)}{2!}}\nabla ^{2}f(x_{j})+{\frac {s(s+1)(s+2)}{3!}}\nabla ^{3}f(x_{j})+{\frac {s(s+1)(s+2)(s+3)}{4!}}\nabla ^{4}f(x_{j})+\cdots }$$

Ромбическая диаграмма

Ромбическая диаграмма — это диаграмма, которая используется для описания различных формул интерполяции, которые можно построить для заданного набора данных. Линия, начинающаяся с левого края и проходящая через диаграмму вправо, может использоваться для представления формулы интерполяции, если соблюдаются следующие правила: ^[5]

Ромбическая диаграмма: геометрическое представление полиномиальных интерполяций.

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

Коэффициенты выражаются по формуле:

$${\displaystyle C(u+k,n)={\frac {(u+k)(u+k-1)\cdots (u+k-n+1)}{n!}}}$$

Доказательство эквивалентности

Если путь идет из в , он может соединяться через три промежуточных шага: (a) через , (b) через или (c) через . Доказательство эквивалентности этих трех двухшаговых путей должно доказать, что все (n-шаговые) пути могут быть преобразованы с одинаковым началом и концом, и все они представляют собой одну и ту же формулу. ${\displaystyle \Delta ^{n-1}y_{s}}$ ${\displaystyle \Delta ^{n+1}y_{s-1}}$ ${\displaystyle \Delta ^{n}y_{s-1}}$ ${\textstyle C(u-s,n)}$ ${\displaystyle \Delta ^{n}y_{s}}$

Путь (а):

${\displaystyle C(u-s,n)\Delta ^{n}y_{s-1}+C(u-s+1,n+1)\Delta ^{n+1}y_{s-1}}$

Путь (б):

${\displaystyle C(u-s,n)\Delta ^{n}y_{s}+C(u-s,n+1)\Delta ^{n+1}y_{s-1}}$

Путь (с):

${\displaystyle C(u-s,n){\frac {\Delta ^{n}y_{s-1}+\Delta ^{n}y_{s}}{2}}\quad +{\frac {C(u-s+1,n+1)+C(u-s,n+1)}{2}}\Delta ^{n+1}y_{s-1}}$

Вычитая вклады от путей a и b:

${\displaystyle {\begin{aligned}{\text{Path a - Path b}}=&C(u-s,n)(\Delta ^{n}y_{s-1}-\Delta ^{n}y_{s})+(C(u-s+1,n+1)-C(u-s,n-1))\Delta ^{n+1}y_{s-1}\\=&-C(u-s,n)\Delta ^{n+1}y_{s-1}+C(u-s,n){\frac {(u-s+1)-(u-s-n)}{n+1}}\Delta ^{n+1}y_{s-1}\\=&C(u-s,n)(-\Delta ^{n+1}y_{s-1}+\Delta ^{n+1}y_{s-1})=0\\\end{aligned}}}$

Таким образом, вклад пути (а) или пути (б) одинаков. Поскольку путь (c) является средним значением путей (a) и (b), он также вносит в полином идентичную функцию. Таким образом, доказывается эквивалентность путей с одинаковыми начальной и конечной точками. Чтобы проверить, можно ли сместить пути на разные значения в крайнем левом углу, достаточно сделать всего два шага пути: (а) до сквозного или (б) фактор между и , до сквозного или (в) начиная с . ${\displaystyle y_{s+1}}$ ${\displaystyle y_{s}}$ ${\displaystyle \Delta y_{s}}$ ${\displaystyle y_{s+1}}$ ${\displaystyle y_{s}}$ ${\displaystyle y_{s}}$ ${\displaystyle \Delta y_{s}}$ ${\displaystyle y_{s}}$

Путь (а)

${\displaystyle y_{s+1}+C(u-s-1,1)\Delta y_{s}-C(u-s,1)\Delta y_{s}}$

Путь (б)

${\displaystyle {\frac {y_{s+1}+y_{s}}{2}}+{\frac {C(u-s-1,1)+C(u-s,1)}{2}}\Delta y_{s}-C(u-s,1)\Delta y_{s}}$

Путь (с)

${\displaystyle y_{s}}$

Поскольку подстановка в приведенные выше уравнения показывает, что все приведенные выше члены сводятся к и, следовательно, эквивалентны. Следовательно, эти пути можно трансформировать, чтобы они начинались с крайнего левого угла и заканчивались в общей точке. ^[5] ${\displaystyle \Delta y_{s}=y_{s+1}-y_{s}}$ ${\displaystyle y_{s}}$

Формула Ньютона

Если взять трансверсальный наклон с отрицательным наклоном от до, получим формулу интерполяции всех последовательно расположенных точек, эквивалентную формуле прямой интерполяции Ньютона: ${\displaystyle y_{0}}$ ${\displaystyle \Delta ^{n}y_{0}}$ ${\displaystyle n+1}$

${\displaystyle {\begin{aligned}y(s)&=y_{0}+C(s,1)\Delta y_{0}+C(s,2)\Delta ^{2}y_{0}+C(s,3)\Delta ^{3}y_{0}+\cdots \\&=y_{0}+s\Delta y_{0}+{\frac {s(s-1)}{2}}\Delta ^{2}y_{0}+{\frac {s(s-1)(s-2)}{3!}}\Delta ^{3}y_{0}+{\frac {s(s-1)(s-2)(s-3)}{4!}}\Delta ^{4}y_{0}+\cdots \end{aligned}}}$

тогда как, принимая трансверсальный положительный наклон от до , дает формулу интерполяции всех последовательно расположенных точек, эквивалентную формуле обратной интерполяции Ньютона: ${\displaystyle y_{n}}$ ${\displaystyle \nabla ^{n}y_{n}=\Delta ^{n}y_{0}}$ ${\displaystyle n+1}$

${\displaystyle {\begin{aligned}y(u)&=y_{k}+C(u-k,1)\Delta y_{k-1}+C(u-k+1,2)\Delta ^{2}y_{k-2}+C(u-k+2,3)\Delta ^{3}y_{k-3}+\cdots \\&=y_{k}+(u-k)\Delta y_{k-1}+{\frac {(u-k+1)(u-k)}{2}}\Delta ^{2}y_{k-2}+{\frac {(u-k+2)(u-k+1)(u-k)}{3!}}\Delta ^{3}y_{k-3}+\cdots \\y(k+s)&=y_{k}+(s)\nabla y_{k}+{\frac {(s+1)s}{2}}\nabla ^{2}y_{k}+{\frac {(s+2)(s+1)s}{3!}}\nabla ^{3}y_{k}+{\frac {(s+3)(s+2)(s+1)s}{4!}}\nabla ^{4}y_{k}+\cdots \\\end{aligned}}}$

где – число, соответствующее введенному в интерполяции Ньютона. ${\displaystyle s=u-k}$

Формула Гаусса

Проведя зигзагообразную линию вправо, начиная с отрицательного наклона, мы получаем формулу форварда Гаусса: ${\displaystyle y_{0}}$

${\displaystyle y(u)=y_{0}+u\Delta y_{0}+{\frac {u(u-1)}{2}}\Delta ^{2}y_{-1}+{\frac {(u+1)u\left(u-1\right)}{3!}}\Delta ^{3}y_{-1}+{\frac {(u+1)u\left(u-1\right)(u-2)}{4!}}\Delta ^{4}y_{-2}+\cdots }$

тогда как, начиная с положительного наклона, мы получаем обратную формулу Гаусса: ${\displaystyle y_{0}}$

${\displaystyle y(u)=y_{0}+u\Delta y_{-1}+{\frac {(u+1)u}{2}}\Delta ^{2}y_{-1}+{\frac {(u+1)u\left(u-1\right)}{3!}}\Delta ^{3}y_{-2}+{\frac {(u+2)(u+1)u\left(u-1\right)}{4!}}\Delta ^{4}y_{-2}+\cdots }$

Формула Стирлинга

Пройдя горизонтальный путь вправо, начиная с , мы получаем формулу Стирлинга: ${\displaystyle y_{0}}$

${\displaystyle {\begin{aligned}y(u)&=y_{0}+u{\frac {\Delta y_{0}+\Delta y_{-1}}{2}}+{\frac {C(u+1,2)+C(u,2)}{2}}\Delta ^{2}y_{-1}+C(u+1,3){\frac {\Delta ^{3}y_{-2}+\Delta ^{3}y_{-1}}{2}}+\cdots \\&=y_{0}+u{\frac {\Delta y_{0}+\Delta y_{-1}}{2}}+{\frac {u^{2}}{2}}\Delta ^{2}y_{-1}+{\frac {u(u^{2}-1)}{3!}}{\frac {\Delta ^{3}y_{-2}+\Delta ^{3}y_{-1}}{2}}+{\frac {u^{2}(u^{2}-1)}{4!}}\Delta ^{4}y_{-2}+\cdots \end{aligned}}}$

Формула Стирлинга представляет собой среднее арифметическое прямой и обратной формул Гаусса.

Формула Бесселя

Пройдя горизонтальный путь вправо, начиная с множителя между и , мы получаем формулу Стирлинга: ${\displaystyle y_{0}}$ ${\displaystyle y_{1}}$

${\displaystyle {\begin{aligned}y(u)&=1{\frac {y_{0}+y_{1}}{2}}+{\frac {C(u,1)+C(u-1,1)}{2}}\Delta y_{0}+C(u,2){\frac {\Delta ^{2}y_{-1}+\Delta ^{2}y_{0}}{2}}+\cdots \\&={\frac {y_{0}+y_{1}}{2}}+\left(u-{\frac {1}{2}}\right)\Delta y_{0}+{\frac {u(u-1)}{2}}{\frac {\Delta ^{2}y_{-1}+\Delta ^{2}y_{0}}{2}}+{\frac {\left(u-{\frac {1}{2}}\right)u\left(u-1\right)}{3!}}\Delta ^{3}y_{0}+{\frac {(u+1)u(u-1)(u-2)}{4!}}{\frac {\Delta ^{4}y_{-1}+\Delta ^{4}y_{-2}}{2}}+\cdots \\\end{aligned}}}$

Алгоритмы Вандермонда

Матрица Вандермонда во втором доказательстве выше может иметь большое число обусловленности ^[6] , что приводит к большим ошибкам при вычислении коэффициентов a _i , если система уравнений решается методом исключения Гаусса .

^{Поэтому несколько авторов предложили алгоритмы ,} которые используют структуру матрицы Вандермонда для вычисления численно устойчивых решений за O( n2 ) операций вместо O( n3 ) ^, требуемых методом исключения Гаусса. ^{[7] [8] [9]} Эти методы основаны на построении сначала интерполяции Ньютона полинома, а затем на преобразовании его в мономиальную форму .

Алгоритмы, не относящиеся к Вандермонду

Чтобы найти интерполяционный полином p ( x ) в векторном пространстве P ( n ) полиномов степени n , мы можем использовать обычный мономиальный базис для P ( n ) и инвертировать матрицу Вандермонда методом исключения Гаусса, что дает вычислительные затраты O ( n ³ ) операций. Чтобы улучшить этот алгоритм, более удобный базис для P ( n ) может упростить вычисление коэффициентов, которые затем необходимо перевести обратно в термины мономиального базиса .

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

Другой метод предпочтителен, когда целью является вычисление не коэффициентов p ( x ) , а только одного значения p ( a ) в точке x = a, отсутствующей в исходном наборе данных. Форма Лагранжа вычисляет значение p ( a ) со сложностью O( ⁿ² ) . ^[10]

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

Интерполяции как линейные комбинации значений

Учитывая набор точек данных (положение, значение), в которых нет двух одинаковых позиций , интерполирующий полином можно рассматривать как линейную комбинацию значений с использованием коэффициентов, которые являются полиномами в зависимости от . Например, интерполяционный полином в форме Лагранжа представляет собой линейную комбинацию ${\displaystyle (x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{n},y_{n})}$ ${\displaystyle x_{j}}$ ${\displaystyle y(x)}$ ${\displaystyle y_{j}}$ ${\displaystyle x}$ ${\displaystyle x_{j}}$

$${\displaystyle y(x):=\sum _{j=0}^{k}y_{j}c_{j}(x)}$$

${\displaystyle c_{j}(x)}$ ${\displaystyle x_{j}}$

$${\displaystyle c_{j}(x)=L_{j}(x_{0},\ldots ,x_{n};x)=\prod _{0\leq i\leq n \atop i\neq j}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{\frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}\cdots {\frac {(x-x_{n})}{(x_{j}-x_{n})}}.}$$

Поскольку коэффициенты зависят только от позиций , а не от значений , мы можем использовать те же коэффициенты, чтобы найти интерполяционный полином для второго набора точек данных в тех же позициях: ${\displaystyle x_{j}}$ ${\displaystyle y_{j}}$ ${\displaystyle (x_{0},v_{0}),\ldots ,(x_{n},v_{n})}$

$${\displaystyle v(x):=\sum _{j=0}^{k}v_{j}c_{j}(x).}$$

Более того, коэффициенты зависят только от относительных промежутков между позициями. Таким образом, учитывая третий набор данных, точки которого задаются новой переменной ( аффинное преобразование , инвертированное ) : ${\displaystyle c_{j}(x)}$ ${\displaystyle x_{i}-x_{j}}$ ${\displaystyle t=ax+b}$ ${\displaystyle x}$ ${\displaystyle x={\tfrac {t-b}{a}}}$

$${\displaystyle (t_{0},w_{0}),\ldots ,(t_{j},w_{j})\ldots ,(t_{n},w_{n})\qquad {\text{with}}\qquad t_{j}=ax_{j}+b,}$$

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

${\displaystyle {\tilde {c}}_{j}(t):=c_{j}({\tfrac {t-b}{a}})=c_{j}(x),}$

и запишите интерполяционный полином как:

${\textstyle w(t):=\sum _{j=0}^{k}w_{j}{\tilde {c}}_{j}(t).}$

Точки данных часто имеют равноотстоящие друг от друга позиции , которые можно нормализовать с помощью аффинного преобразования в . Например, рассмотрим точки данных ${\displaystyle (x_{j},y_{j})}$ ${\displaystyle x_{j}=j}$

${\displaystyle (0,y_{0}),(1,y_{1}),(2,y_{2})}$.

Интерполяционный полином в форме Лагранжа представляет собой линейную комбинацию

$${\displaystyle {\begin{aligned}y(x):=\sum _{j=0}^{2}y_{j}c_{j}(x)&=y_{0}{\frac {(x-1)(x-2)}{(0-1)(0-2)}}+y_{1}{\frac {(x-0)(x-2)}{(1-0)(1-2)}}+y_{2}{\frac {(x-0)(x-1)}{(2-0)(2-1)}}\\&={\tfrac {1}{2}}y_{0}(x-1)(x-2)-y_{1}(x-0)(x-2)+{\tfrac {1}{2}}y_{2}(x-0)(x-1).\end{aligned}}}$$

Например, и . ${\displaystyle y(3)=y_{3}=y_{0}-3y_{1}+3y_{2}}$ ${\displaystyle y(1.5)=y_{1.5}={\tfrac {1}{8}}(-y_{0}+6y_{1}+3y_{2})}$

Случай равноотстоящих друг от друга точек также можно рассматривать методом конечных разностей . Первое отличие последовательности значений — это последовательность, определяемая . Итерация этой операции дает n- ^ю разностную операцию , определяемую явно следующим образом: ${\displaystyle v=\{v_{j}\}_{j=0}^{\infty }}$ ${\displaystyle \Delta v=u=\{u_{j}\}_{j=0}^{\infty }}$ ${\displaystyle u_{j}=v_{j+1}-v_{j}}$ ${\displaystyle \Delta ^{n}v=u}$

$${\displaystyle u_{j}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}v_{j+k},}$$

треугольника коэффициентов биномиального преобразования

Полином степени d определяет последовательность значений в положительных целых точках, и разность этой последовательности тождественно равна нулю: ${\displaystyle y(x)}$ ${\displaystyle y_{j}=y(j)}$ ${\displaystyle (d+1)^{\text{th}}}$

${\displaystyle \Delta ^{d+1}y=0}$.

Таким образом, при заданных значениях в равноотстоящих друг от друга точках, где , мы имеем: ${\displaystyle y_{0},\ldots ,y_{n}}$ ${\displaystyle n=d+1}$

$${\displaystyle (-1)^{n}y_{0}+(-1)^{n-1}{\binom {n}{1}}y_{1}+\cdots -{\binom {n}{n-1}}y_{n-1}+y_{n}=0.}$$

${\displaystyle y_{0},y_{1},y_{2},y_{3}}$ ${\displaystyle y(x)}$ ${\displaystyle 0=-y_{0}+3y_{1}-3y_{2}+y_{3}}$ ${\displaystyle y_{3}}$

Ошибка интерполяции: формула остатка Лагранжа

При интерполяции заданной функции f полиномом степени n в узлах x0 _, ..., _xn получаем ошибку ${\displaystyle p_{n}}$

$${\displaystyle f(x)-p_{n}(x)=f[x_{0},\ldots ,x_{n},x]\prod _{i=0}^{n}(x-x_{i})}$$

где ( n +1) ^-я разделенная разность точек данных ${\textstyle f[x_{0},\ldots ,x_{n},x]}$

${\displaystyle (x_{0},f(x_{0})),\ldots ,(x_{n},f(x_{n})),(x,f(x))}$.

Кроме того, существует форма остатка Лагранжа ошибки для функции f , которая n + 1 раз непрерывно дифференцируется на замкнутом интервале , и полином степени не выше n , который интерполирует f в n + 1 различных точках . Для каждого существует такое, что ${\displaystyle I}$ ${\displaystyle p_{n}(x)}$ ${\displaystyle x_{0},\ldots ,x_{n}\in I}$ ${\displaystyle x\in I}$ ${\displaystyle \xi \in I}$

$${\displaystyle f(x)-p_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i}).}$$

Эта граница ошибки предполагает выбор точек интерполяции x _i для минимизации произведения , что достигается с помощью узлов Чебышева . ${\textstyle \left|\prod (x-x_{i})\right|}$

Доказательство остатка Лагранжа

Установите термин ошибки как и определите вспомогательную функцию: ${\textstyle R_{n}(x)=f(x)-p_{n}(x)}$

$${\displaystyle Y(t)=R_{n}(t)-{\frac {R_{n}(x)}{W(x)}}W(t)\qquad {\text{where}}\qquad W(t)=\prod _{i=0}^{n}(t-x_{i}).}$$

$${\displaystyle Y^{(n+1)}(t)=R_{n}^{(n+1)}(t)-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!}$$

Но поскольку – многочлен степени не выше n , мы имеем , и: ${\displaystyle p_{n}(x)}$ ${\textstyle R_{n}^{(n+1)}(t)=f^{(n+1)}(t)}$

$${\displaystyle Y^{(n+1)}(t)=f^{(n+1)}(t)-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!}$$

Теперь, поскольку x _i являются корнями и , мы имеем , что означает, что Y имеет по крайней мере n + 2 корня. По теореме Ролля имеет не менее n + 1 корней и итеративно имеет хотя бы один корень ξ в интервале I . Таким образом: ${\displaystyle R_{n}(t)}$ ${\displaystyle W(t)}$ ${\displaystyle Y(x)=Y(x_{j})=0}$ ${\displaystyle Y^{\prime }(t)}$ ${\displaystyle Y^{(n+1)}(t)}$

$${\displaystyle Y^{(n+1)}(\xi )=f^{(n+1)}(\xi )-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!=0}$$

и:

$${\displaystyle R_{n}(x)=f(x)-p_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i}).}$$

Это соответствует рассуждениям, лежащим в основе остаточного члена Лагранжа в теореме Тейлора ; Фактически, остаток Тейлора представляет собой частный случай ошибки интерполяции, когда все узлы интерполяции x _i идентичны. ^[11] Обратите внимание, что ошибка будет равна нулю при любом i . Таким образом, максимальная ошибка возникнет в какой-то момент интервала между двумя последовательными узлами. ${\displaystyle x=x_{i}}$

Равноотстоящие интервалы

В случае равноотстоящих друг от друга узлов интерполяции где , для и где член произведения в формуле ошибки интерполяции может быть связан как ^[12] ${\displaystyle x_{i}=a+ih}$ ${\displaystyle i=0,1,\ldots ,n,}$ ${\displaystyle h=(b-a)/n,}$

$${\displaystyle \left|\prod _{i=0}^{n}(x-x_{i})\right|=\prod _{i=0}^{n}\left|x-x_{i}\right|\leq {\frac {n!}{4}}h^{n+1}.}$$

Таким образом, граница ошибки может быть задана как

$${\displaystyle \left|R_{n}(x)\right|\leq {\frac {h^{n+1}}{4(n+1)}}\max _{\xi \in [a,b]}\left|f^{(n+1)}(\xi )\right|}$$

Однако при этом предполагается, что преобладает , т.е. В некоторых случаях это не так, и ошибка фактически увеличивается при n → ∞ (см. феномен Рунге ). Этот вопрос рассматривается в разделе «Свойства сходимости». ${\displaystyle f^{(n+1)}(\xi )}$ ${\displaystyle h^{n+1}}$ ${\displaystyle f^{(n+1)}(\xi )h^{n+1}\ll 1}$

Константы Лебега

Фиксируем узлы интерполяции x ₀ , ..., x _n и интервал [ a , b ], содержащий все узлы интерполяции. Процесс интерполяции отображает функцию f в полином p . Это определяет отображение X из пространства C ([ a , b ]) всех непрерывных функций на [ a , b ] в себя. Отображение X линейно и является проекцией на подпространство многочленов степени n или меньше. ${\displaystyle P(n)}$

Константа Лебега L определяется как операторная норма X . Имеет место (частный случай леммы Лебега ):

$${\displaystyle \left\|f-X(f)\right\|\leq (L+1)\left\|f-p^{*}\right\|.}$$

Другими словами, интерполяционный полином не более чем в раз ( L  + 1) хуже наилучшего возможного приближения. Это предполагает, что мы ищем набор узлов интерполяции, который делает L маленьким. В частности, для узлов Чебышева имеем :

$${\displaystyle L\leq {\frac {2}{\pi }}\log(n+1)+1.}$$

Мы снова заключаем, что узлы Чебышева являются очень хорошим выбором для полиномиальной интерполяции, поскольку рост n является экспоненциальным для эквидистантных узлов. Однако эти узлы не являются оптимальными.

Свойства сходимости

Естественно задаться вопросом, для каких классов функций и для каких узлов интерполяции последовательность интерполяционных полиномов сходится к интерполируемой функции при n → ∞ ? Сходимость можно понимать по-разному, например, поточечно, равномерно или в некоторой интегральной норме.

Ситуация довольно плохая для эквидистантных узлов, поскольку равномерная сходимость не гарантируется даже для бесконечно дифференцируемых функций. Одним из классических примеров, принадлежащих Карлу Рунге , является функция f ( x ) = 1/(1 + x ² ) на интервале [−5, 5] . Ошибка интерполяции ||  ж - п _п || _∞ неограниченно растет при n → ∞ . Другой пример — функция f ( x ) = | х | на интервале [−1, 1] , для которого интерполяционные полиномы даже не сходятся поточечно, за исключением трех точек x = ±1, 0. ^[13]

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

Теорема  .  Для любой функции f ( x ), непрерывной на интервале [ a , b ], существует таблица узлов, для которой последовательность интерполирующих полиномов сходится к f ( x ) равномерно на [ a , b ]. ${\displaystyle p_{n}(x)}$

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

Понятно, что последовательность полиномов наилучшего приближения сходится к f ( x ) равномерно (в силу аппроксимационной теоремы Вейерштрасса ). Теперь нам осталось только показать, что каждое из них можно получить интерполяцией на определенных узлах. Но это справедливо благодаря особому свойству полиномов наилучшего приближения, известному из теоремы об эквиколебаниях . В частности, мы знаем, что такие многочлены должны пересекать f ( x ) не менее n + 1 раз. Выбирая точки пересечения в качестве узлов интерполяции, получаем интерполяционный полином, совпадающий с полиномом наилучшего приближения. ${\displaystyle p_{n}^{*}(x)}$ ${\displaystyle p_{n}^{*}(x)}$

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

Теорема  .  Для любой таблицы узлов существует непрерывная функция f ( x ) на интервале [ a , b ], для которой последовательность интерполирующих полиномов расходится на [ a , b ]. ^[14]

Доказательство по существу использует оценку нижней оценки константы Лебега, которую мы определили выше как операторную норму X _n (где X _n — оператор проектирования на Π _n ). Теперь ищем таблицу узлов, для которых

$${\displaystyle \lim _{n\to \infty }X_{n}f=f,{\text{ for every }}f\in C([a,b]).}$$

Согласно теореме Банаха–Штайнхауза это возможно только тогда, когда нормы X _n равномерно ограничены, что не может быть правдой, поскольку мы знаем, что

$${\displaystyle \|X_{n}\|\geq {\tfrac {2}{\pi }}\log(n+1)+C.}$$

Например, если в качестве узлов интерполяции выбраны равноудаленные точки, функция из явления Рунге демонстрирует расхождение такой интерполяции. Обратите внимание, что эта функция не только непрерывна, но даже бесконечно дифференцируема на [−1, 1] . Однако для лучших узлов Чебышева такой пример найти гораздо сложнее из-за следующего результата:

Теорема  .  Для каждой абсолютно непрерывной функции на [−1, 1] последовательность интерполяционных многочленов, построенных на узлах Чебышёва, сходится к  f ( x ) равномерно. ^[15]

Связанные понятия

Феномен Рунге показывает, что при высоких значениях n интерполяционный полином может сильно колебаться между точками данных. Эту проблему обычно решают с помощью сплайн-интерполяции . Здесь интерполянтом является не многочлен, а сплайн : цепочка из нескольких многочленов более низкой степени.

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

Задачи интерполяции Эрмита — это задачи, в которых заданы не только значения многочлена p в узлах, но и все производные до заданного порядка. Это оказывается эквивалентным системе одновременных сравнений полиномов и может быть решено с помощью китайской теоремы об остатках для многочленов. Интерполяция Биркгофа — это дальнейшее обобщение, в котором назначаются только производные некоторых порядков, а не обязательно всех порядков от 0 до k .

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

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

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

Смотрите также

• серия Ньютон
• Полиномиальная регрессия

Примечания

1. Это следует из факторной теоремы для полиномиального деления.

Цитаты

1. Тиманн, Джером Дж. (май – июнь 1981 г.). «Полиномиальная интерполяция». Новости ввода/вывода . 1 (5): 16. ISSN  0274-9998 . Проверено 3 ноября 2017 г.
2. Хамферис, Джеффри; Джарвис, Тайлер Дж. (2020). «9.2 – Интерполяция». Основы прикладной математики Том 2: Алгоритмы, приближение, оптимизация . Общество промышленной и прикладной математики. п. 418. ИСБН 978-1-611976-05-2.
3. Эпперсон, Джеймс Ф. (2013). Введение в численные методы и анализ (2-е изд.). Хобокен, Нью-Джерси: Уайли. ISBN 978-1-118-36759-9.
4. Берден, Ричард Л.; Фейрес, Дж. Дуглас (2011). Численный анализ (9-е изд.). п. 129. ИСБН 9780538733519.
5. Хэмминг, Ричард В. (1986). Численные методы для ученых и инженеров (Полная республика 2-го изд. (1973) изд.). Нью-Йорк: Дувр. ISBN 978-0-486-65241-2.
6. Гаучи, Уолтер (1975). «Оценки норм для обратных матриц Вандермонда». Нумерическая математика . 23 (4): 337–347. дои : 10.1007/BF01438260. S2CID  122300795.
7. Хайэм, Нью-Джерси (1988). «Быстрое решение систем типа Вандермонда, включающих ортогональные полиномы». Журнал IMA численного анализа . 8 (4): 473–486. дои : 10.1093/иманум/8.4.473.
8. Бьорк, Å; В. Перейра (1970). «Решение систем уравнений Вандермонда». Математика вычислений . 24 (112). Американское математическое общество: 893–903. дои : 10.2307/2004623. JSTOR  2004623.
9. Кальветти, Д .; Райхель, Л. (1993). «Быстрое обращение матриц типа Вандермонда с использованием ортогональных полиномов». КУСОЧЕК . 33 (3): 473–484. дои : 10.1007/BF01990529. S2CID  119360991.
10. Р.Бевилаква, Д. Бини, М.Каповани и О. Менчи (2003). Appunti ди Calcolo Numerico . Глава 5, с. 89. Servizio Editoriale Universitario Pisa - Azienda Regionale Diritto allo Studio Universitario.
11. «Ошибки полиномиальной интерполяции» (PDF) .
12. «Заметки о полиномиальной интерполяции» (PDF) .
13. Уотсон (1980, стр. 21) приписывает последний пример Бернштейну (1912).
14. Уотсон (1980, стр. 21) приписывает эту теорему Фаберу (1914).
15. Крылов, В.И. (1956). «Сходимость алгебраической интерполирования покорням многочленов Чебышева для абсолютно непрерывных и функций с ограниченным изменением». Доклады Академии наук СССР . Новая серия (на русском языке). 107 : 362–365.МР 18-32.

Рекомендации

• Бернштейн, Сергей Н. (1912). «Sur l'ordre de la meilleure des functions continue par les Polynômes de degré donné» [О порядке наилучшего приближения непрерывных функций полиномами заданной степени]. Память акад. Рой. Бельг. (На французском). 4 : 1–104.
• Фабер, Георг (1914). «Über die interpolatorische Darstellung stetiger Funktionen» [Об интерполяции непрерывных функций]. Немецкая математика. Яр. (на немецком). 23 : 192–210.
• Уотсон, Г. Алистер (1980). Теория приближений и численные методы . Джон Уайли. ISBN 0-471-27706-1.

дальнейшее чтение

• Аткинсон, Кенделл А. (1988). "Глава 3.". Введение в численный анализ (2-е изд.). Джон Уайли и сыновья. ISBN 0-471-50023-2.
• Брутман, Л. (1997). «Функции Лебега для полиномиальной интерполяции — обзор». Анна. Число. Математика . 4 : 111–127.
• Пауэлл, MJD (1981). "Глава 4". Теория и методы приближения . Издательство Кембриджского университета. ISBN 0-521-29514-9.
• Шацман, Мишель (2002). "Глава 4". Численный анализ: математическое введение . Оксфорд: Кларендон Пресс. ISBN 0-19-850279-6.
• Сюли, Эндре ; Майерс, Дэвид (2003). "Глава 6". Введение в численный анализ . Издательство Кембриджского университета. ISBN 0-521-00794-1.

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

• «Процесс интерполяции», Математическая энциклопедия , EMS Press , 2001 [1994]
• ALGLIB имеет реализации на C++/C#.
• GSL имеет код полиномиальной интерполяции на языке C.
• Демонстрация полиномиальной интерполяции.