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

У этого термина существуют и другие значения, см. Интерполяция.

Интерполя́ция (интерполи́рование; от лат. inter–polis — разглаженный, подновлённый, обновлённый; преобразованный) — общее наименование для вычислительно-математических техник восстановления функции по имеющемуся дискретному набору её известных значений. Термин и первый вариант техники впервые употребил Джон Валлис в трактате «Арифметика бесконечных» (1656).

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

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

Определения

Для системы несовпадающих точек ${\displaystyle x_{i}}$ (${\displaystyle i\in \{1,\dots ,N\}}$) из некоторой области ${\displaystyle D}$ и значений функции ${\displaystyle f}$ в этих точках ${\displaystyle y_{i}=f(x_{i})}$ задача интерполяции состоит в поиске такой функции ${\displaystyle F}$ из заданного класса функций, что ${\displaystyle F(x_{i})=y_{i}}$ для каждого

Точки ${\displaystyle x_{i}}$ называют узлами интерполяции, а их совокупность — интерполяционной сеткой. Пары ${\displaystyle (x_{i},y_{i})}$ называют точками данных или базовыми точками. Разность между «соседними» значениями ${\displaystyle \Delta x_{i}=x_{i}-x_{i-1}}$ называют шагом интерполяционной сетки; шаг может быть как переменным, так и постоянным.

Функцию ${\displaystyle F(x)}$ — интерполирующей функцией или интерполянтом.

Способы интерполяции

Простейшим способом интерполяции является интерполяция методом ближайшего соседа. Другой относительно простой способ — кусочно-линейная интерполяция, когда между каждой пары известных значений ${\displaystyle y_{i}}$ и ${\displaystyle y_{i+1}}$ соседних точек данных ${\displaystyle x_{i}}$ и ${\displaystyle x_{i+1}}$ проводится линейная функция:

${\displaystyle F_{i,i+1}(x)=y_{i}{\frac {x_{i+1}-x}{x_{i+1}-x_{i}}}+y_{i+1}{\frac {x-x_{i}}{x_{i+1}-x_{i}}}}$,

в итоге интерполянтом является кусочно-линейная функция — совокупность всех таких отрезков.

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

Лагранжева интерполяция — поиск многочлена ${\displaystyle n}$-й степени проходящего через ${\displaystyle n}$ заданных точек.

Более сложные схемы интерполяции возникают, если для каждой точки кроме значений функции заданы значения производных до некоторой степени — ${\displaystyle y^{(s)_{i}}}$ (где ${\displaystyle s=0,\dots ,k_{i}}$); основная из них — эрмитова интерполяция, когда ищется многочлен степени:

${\displaystyle \sum _{i=1}^{n}(k_{i}-1)-1}$,

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

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