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

Существует несколько основных классов численных методов интерполяции:

• Полиномиальная интерполяция — поиск многочлена степени не выше n, который проходит через n+1 точку. Классические формы: полином Лагранжа и полином Ньютона.
• Кусочная интерполяция — построение простых локальных моделей на каждом промежутке между соседними узлами. Примеры: кусочно-линейная интерполяция, кубические сплайны, кубическая Эрмитова интерполяция.
• Рациональная интерполяция — использование отношения полиномов; позволяет лучше контролировать поведение при разрывах производных или стремлении к бесконечности.
• Специальные устойчивые реализации, например барицентрическая интерполяция и алгоритм Невилла, которые повышают численную устойчивость и удобство вычислений.

Начнем с интуитивного подхода — полином Лагранжа. Идея такова: мы строим базисные функции, каждая из которых равна 1 в своем узле и 0 во всех остальных. Затем складываем их с весами, равными значениям функции. Например, у нас есть три точки: (0; 1), (1; 3), (2; 2). Для каждой точки формируем базис: первая базисная функция равна 1 в x=0 и 0 в x=1 и x=2; для этого в числителе берем (x-1)(x-2), а в знаменателе — значение того же выражения при x=0, чтобы нормировать. Аналогично строим вторую и третью базисные функции. Итоговый многочлен — сумма произведений базисных функций на соответствующие y. Преимущество этого подхода — прозрачная теория и простота формулы; недостатки — дороговизна пересчета при добавлении новой точки и склонность к численной неустойчивости при большом числе узлов и равноотстоящих x. На практике вместо «чистого» Лагранжа часто используют барицентрическую формулу, где предварительно считаются веса, а значение в произвольном x можно получить через устойчивое отношение сумм; это уменьшает эффект накопления ошибок и ускоряет вычисления.

Более практичным в вычислительном смысле является полином Ньютона с разделенными разностями. Этот метод строит интерполяционный многочлен последовательно, добавляя узлы один за другим. Если у нас уже есть интерполяция на первых k точках, то добавление (k+1)-й приводит к простому обновлению коэффициентов. Ключевой инструмент — таблица разделенных разностей: первая колонка — исходные y, вторая — попарные «наклоны» между соседними узлами, следующая — разности «наклонов», и так далее. Например, для точек (0; 1), (1; 3), (2; 2):

1. Первая колонка: 1, 3, 2.
2. Вторая колонка: (3−1)/(1−0)=2 и (2−3)/(2−1)=−1.
3. Третья колонка: (−1−2)/(2−0)=−3/2.

Тогда интерполяционный полином Ньютона запишется в виде: первый коэффициент равен 1 (значение в первом узле), второй — 2 (первая разделенная разность), третий — −3/2 (вторая разделенная разность). Чтобы вычислить значение в x=1.5, последовательно подставляем: начинаем с последнего коэффициента и умножаем на (x−x2), затем прибавляем следующий и умножаем на (x−x1), и так далее (по сути, это вложенная схема, аналог схемы Горнера). Для нашего примера: берем −1.5, умножаем на (1.5−2)=−0.5, получаем 0.75; прибавляем 2, получаем 2.75; умножаем на (1.5−1)=0.5, получаем 1.375; прибавляем 1, итог 2.375. Это и есть интерполированное значение между x=1 и x=2. Преимущества Ньютона: легкое добавление узлов, компактное хранение в виде таблицы разностей, устойчивое вычисление при разумном выборе узлов.

Стоит отдельно упомянуть алгоритм Невилла, который позволяет вычислять значение интерполяционного полинома в конкретной точке x без явного построения полинома. Идея — рекурсивное «смешивание» пар точек: сначала интерполируем на отрезках из двух соседних узлов, потом на отрезках из трех узлов, и так далее, пока не получим значение для всех узлов. Этот метод часто удобен, когда нужно одно значение, а не весь полином, и когда важна численная устойчивость. Он также хорошо работает при неоднородном распределении узлов и не требует перерасчета, если узлы фиксированы, а x меняется — достаточно хранить промежуточную таблицу.

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

Кубические сплайны — стандарт промышленного уровня для плавной интерполяции. На каждом промежутке между соседними узлами строится кубический полином, а на границах интервалов обеспечивается непрерывность функции, первой и второй производной. В зависимости от условий на концах различают «натуральный» сплайн (вторая производная на краях равна нулю), «защемленный» (заданы наклоны на концах), «not-a-knot» (условия на узлах для уменьшения глобального излома). Построение сводится к решению трехдиагональной СЛАУ для вторых производных или известных коэффициентов — это быстро и стабильно. Преимущества сплайнов: локальность (изменение одного узла влияет только на соседние интервалы), гладкость (отсутствие паразитных колебаний), высокая точность при умеренном числе узлов. Например, если у нас данные сенсора с шагом по времени неравномерный, сплайн аккуратно «сошьет» их, сохранив плавность, в то время как высокий глобальный полином может «звонить» на концах.

Иногда важна не только точность по значениям, но и правильный наклон или кривизна. Тогда применяют Эрмитову интерполяцию: помимо значений функции в узлах, учитывают и производные (а можно и вторые производные). Самый практичный вариант — кубическая Эрмитова интерполяция (например, PCHIP), которая обеспечивает монотонность и отсутствие перерегулирования: если исходные данные монотонны, интерполянт тоже не будет образовывать «волны». Это важно, например, для интерполяции кривых спроса, калибровочных зависимостей, профилей высот, где недопустимы искусственные экстремумы.

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

Несколько слов о погрешности интерполяции и численной устойчивости. Теоретически ошибка полиномиальной интерполяции пропорциональна произведению (x − x0)(x − x1)…(x − xn), умноженному на производную высокой степени исходной функции. Из этого видно, почему равномерная сетка опасна на концах и почему узлы Чебышёва лучше распределяют ошибку. С вычислительной точки зрения формулы, основанные на матрице Вандермонда, плохо обусловлены: небольшая ошибка в данных может привести к большой ошибке в коэффициентах полинома. Поэтому на практике используют формы Ньютона, барицентрическую формулу и сплайны — они устойчивее. Также важна масштабировка переменной x к промежутку длины порядка 1, что уменьшает перепады величин коэффициентов и повышает надежность вычислений.

Часто в данных присутствует шум. В таком случае «жесткая» интерполяция (строго через точки) может быть нежелательной: она воспроизведет шум. Тогда выбирают сглаживающие сплайны или аппроксимацию с регуляризацией, где вводится параметр гладкости: при нулевом параметре получаем точную интерполяцию, при больших — более гладкую кривую с меньшими отклонениями от исходных точек. Полезный прием — кросс-валидация для выбора уровня сглаживания: исключаем точку, интерполируем по остальным, оцениваем ошибку предсказания и подбираем параметр, минимизирующий среднюю ошибку.

Для практической работы полезен следующий алгоритмический чек-лист выбора метода:

1. Если узлов мало (до 8–10), а данные гладкие — подойдут полиномы Ньютона/Лагранжа; для единичных вычислений по всей сетке — барицентрическая форма.
2. Если узлов много или распределение неравномерное — используйте кубические сплайны (натуральные или с заданными наклонами), они устойчивее и локальны.
3. Если важна монотонность и отсутствие пере- и недокачки — выбирайте PCHIP (кубическая Эрмитова кусочная интерполяция).
4. Если есть особенности типа асимптот — рассмотрите рациональные интерполянты.
5. При сильном шуме — применяйте сглаживающие сплайны или аппроксимацию.
6. Для равномерной сетки и быстрого многократного вычисления — используйте формулы Ньютона вперед/назад с конечными разностями.

Разберем пошаговый пример, полезный для обучения. Пусть заданы точки (0; 1), (1; 3), (2; 2), как выше. Построим полином Ньютона и интерполируем в x=1.5. Шаги:

1. Составляем таблицу разделенных разностей:
   • Нулевая колонка (значения): 1, 3, 2.
   • Первая колонка: (3−1)/(1−0)=2; (2−3)/(2−1)=−1.
   • Вторая колонка: (−1−2)/(2−0)=−3/2.
2. Записываем коэффициенты: a0=1, a1=2, a2=−1.5.
3. Вычисляем значение при x=1.5 вложенной схемой:
   • t = a2 = −1.5.
   • t = t*(x−x1) + a1 = (−1.5)*(1.5−1) + 2 = −0.75 + 2 = 1.25.
   • t = t*(x−x0) + a0 = 1.25*(1.5−0) + 1 = 1.875 + 1 = 2.875.

Если на предыдущем абзаце у вас получилось 2.375, проверьте порядок узлов в формуле: вложенная схема чувствительна к порядку x0, x1, x2. В нашем вычислении мы шли от последнего коэффициента, последовательно умножая на (x − соответствующий узел) в обратном порядке. Оба подхода эквивалентны при корректном порядке. Для самопроверки можно сравнить с кусочно-линейной интерполяцией между (1; 3) и (2; 2): там наклон равен −1, значит в x=1.5 получаем 2.5. Видно, что полиномиальная интерполяция дала значение немного ниже из-за учета точки x=0; в трехточечном случае это нормальная ситуация.

Еще одна важная тема — равноотстоящие узлы и конечные разности. Если шаг по x постоянный, удобно использовать формулы Ньютона вперед и назад с таблицей конечных разностей. Это ускоряет вычисления и делает алгоритм близким к «табличному»: значения следующего порядка получают вычитанием соседних значений предыдущего порядка. Для точек, близких к началу сетки, лучше формула «вперед», для точек возле конца — «назад», что уменьшает погрешность округления. Однако при увеличении порядка разности становятся шумными, поэтому не стоит чрезмерно повышать степень полинома.

С точки зрения вычислительной сложности и хранения данных: построение таблицы разделенных разностей или конечных разностей стоит порядка n^2 операций, хранится в виде треугольной таблицы. Оценка в одной точке после предобработки — порядка n операций. Сплайны требуют решения трехдиагональной системы, что занимает линейное время по числу узлов и память порядка n; оценка на каждом интервале — O(1). Для многократных запросов к интерполянту сплайны зачастую выигрывают, особенно при большом n.

Практические советы по реализации:

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

Где это применяется на практике? В инженерии — интерполяция таблиц тепловых и механических свойств материалов; в геоинформационных системах — восстановление рельефа по отметкам высот; в компьютерной графике — Bezier-сплайны и родственные конструкции для гладких траекторий; в цифровой обработке сигналов — перешкальные преобразования и интерполяция между дискретными отсчетами; в экономике и финансах — построение кривых ставок доходности по ограниченному числу ориентиров. Во всех этих случаях важна не только точность, но и контролируемость формы кривой, поэтому сплайны и Эрмитовы методы остаются стандартом.

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