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

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

История

Идея интерполяции восходит к древним цивилизациям. Вавилонские астрономы использовали линейную интерполяцию для заполнения пробелов в таблицах движения небесных тел. В Древней Греции Архимед применял методы, близкие к интерполяции, для приближённого вычисления числа π. Однако систематическое развитие интерполяция получила в работах математиков XVII—XVIII веков.

Значительный вклад внёс Исаак Ньютон, который в 1670-х годах разработал формулу интерполяции для равноотстоящих узлов (формула Ньютона вперёд и назад). Позднее, в 1795 году, Жозеф Луи Лагранж опубликовал общую формулу интерполяционного многочлена, не требующую равномерного расположения узлов. В XIX веке Карл Фридрих Гаусс и Адриен Мари Лежандр развили методы интерполяции в контексте метода наименьших квадратов и аппроксимации функций. В XX веке с развитием вычислительной техники интерполяция стала ключевым инструментом для обработки цифровых сигналов, компьютерной графики и численного моделирования.

Классификация методов интерполяции

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

По типу функции

• Линейная интерполяция — простейший вид, при котором между двумя соседними точками строится отрезок прямой. Функция кусочно-линейна и непрерывна, но не дифференцируема в узлах.
• Полиномиальная интерполяция — используется многочлен степени n-1 для n точек. Классические формы: интерполяционный многочлен Лагранжа и интерполяционные формулы Ньютона. При большом числе точек может возникать эффект Рунге — сильные осцилляции на краях интервала.
• Сплайн-интерполяция — функция строится из кусков многочленов небольшой степени (чаще всего кубических), которые сшиваются в узлах с условием непрерывности производных. Обеспечивает гладкость и устойчивость к осцилляциям.
• Тригонометрическая интерполяция — используется для периодических функций; основана на рядах Фурье. Часто применяется в обработке сигналов.
• Интерполяция рациональными функциями — интерполянт строится как отношение двух многочленов. Может быть эффективна для функций с особенностями.

По способу построения

• Глобальная интерполяция — одна функция строится по всем узлам сразу (например, полином Лагранжа).
• Кусочная (локальная) интерполяция — функция строится отдельно на каждом интервале между узлами (линейная, сплайновая).

Устройство и характеристики

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

• Узлы интерполяции — точки, в которых известны точные значения функции.
• Интерполянт — функция, проходящая через все узлы.
• Погрешность интерполяции — разность между истинным значением функции и значением интерполянта в данной точке. Зависит от гладкости функции, количества и расположения узлов, а также вида интерполянта.

Для полиномиальной интерполяции погрешность оценивается формулой: \[ |f(x) — P_n(x)| \le \frac{M_{n+1}}{(n+1)!} \cdot \prod_{i=0}^{n} |x — x_i| \] где \(M_{n+1}\) — максимум (n+1)-й производной функции на интервале.

Применение

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

• Численное моделирование — для восстановления функций по табличным данным, построения сеточных функций в методах конечных разностей и конечных элементов.
• Обработка сигналов — изменение частоты дискретизации (ресемплинг), сглаживание данных, восстановление аналогового сигнала из цифрового (теорема Котельникова).
• Компьютерная графика — масштабирование изображений (билинейная, бикубическая интерполяция), построение кривых и поверхностей (сплайны Безье, NURBS).
• Геоинформационные системы (ГИС) — построение цифровых моделей рельефа по данным высотных точек.
• Статистика и анализ данных — заполнение пропусков в данных (импутация), сглаживание временных рядов.
• Астрономия и физика — интерполяция таблиц звёздных величин, спектров, термодинамических свойств веществ.

Примеры

Линейная интерполяция

Пусть даны две точки: (0, 1) и (2, 5). Значение при x=1 вычисляется как: \[ y = 1 + \frac{5-1}{2-0} \cdot (1-0) = 3 \]

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

Для трёх точек (0, 0), (1, 1), (2, 4) интерполяционный многочлен второй степени будет равен \(P(x) = x^2\).

Кубическая сплайн-интерполяция

Используется для построения гладких кривых, проходящих через заданные точки, с непрерывными первой и второй производными. Широко применяется в CAD-системах.

Интересные факты

• Эффект Рунге, названный в честь немецкого математика Карла Рунге, демонстрирует, что при равномерном расположении узлов полиномиальная интерполяция высокой степени может приводить к большим ошибкам на краях интервала. Для борьбы с этим эффектом используют узлы Чебышёва.
• Теорема Котельникова (в западной литературе — теорема Найквиста — Шеннона) утверждает, что любой сигнал с ограниченным спектром может быть точно восстановлен по своим отсчётам с помощью интерполяции sinc-функцией.
• В компьютерной графике бикубическая интерполяция даёт более гладкие изображения при масштабировании, чем билинейная, но требует больших вычислительных затрат.
• Интерполяция сплайнами была впервые систематически описана в 1946 году американским математиком Исааком Шёнбергом, хотя кусочно-полиномиальные функции использовались и ранее, например, в кораблестроении для построения обводов корпуса.

Критика и ограничения

• Интерполяция не является методом аппроксимации: она требует точного совпадения в узлах, что может быть нежелательно при наличии шума в данных. В таких случаях предпочтительнее регрессия или сглаживание.
• Полиномиальная интерполяция высокой степени неустойчива и может давать нефизичные результаты (эффект Рунге).
• Экстраполяция (предсказание значений за пределами известного интервала) с помощью интерполяционных методов, особенно полиномиальных, крайне ненадёжна.

Источники

• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Бином. Лаборатория знаний, 2006.
• Самарский А. А., Гулин А. В. Численные методы. — М.: Наука, 1989.
• Формалев В. Ф., Ревизников Д. Л. Численные методы. — М.: Физматлит, 2004.
• Burden R. L., Faires J. D. Numerical Analysis. — 9th ed. — Brooks/Cole, 2010.
• Шёнберг И. Дж. Contributions to the problem of approximation of equidistant data by analytic functions. — Quart. Appl. Math., 1946.