Интерполяция
1. Введение и определение
Интерполяция — это процесс построения функции \(P(x)\), которая совпадает с известными значениями некоторой другой функции \(f(x)\) в заданном наборе точек (узлов) \(x_0, x_1, \dots, x_n\):
Ключевая идея: имеем дискретный набор пар \((x_i,y_i)\) — хотим восстановить (приблизить) поведение \(f(x)\) между этими точками. Интерполяция даёт точную проходку через все узлы.
Почему важно подробно понимать:
- Интерполяция — не просто «соединить точки»; это выбор структурной модели (многочлен, кусочки многочленов, рациональная функция, тригонометрический ряд и т.д.) с разными свойствами (гладкость, локальность, поведение на границах).
- Различные методы имеют разную численную устойчивость и пригодность для задач с шумом/без шума.
- Не все методы одинаково хороши для экстраполяции (прогноз за пределами узлов).
2. Интерполяция, аппроксимация и экстраполяция
Интерполяция
- Формально: \(P(x_i)=y_i\) для всех узлов.
- Когда применять: когда значения в узлах считаются репрезентативными и достаточно точными (например, табличные функции, моделирование, физические теории с точными вычислениями в точках).
- Плюсы: точная проходка через узлы(точно описывает известные данные).
- Минусы: при наличии шума в данных интерполянт воспроизведёт шум; возможны осцилляции при использовании глобальных полиномов высокой степени.
Аппроксимация (пример — метод наименьших квадратов)
- Формально: на практике ищем \(Q(x)\), минимизирующую \(\sum_i (y_i - Q(x_i))^2\) (или другую метрику). \(Q(x)\) не обязана проходить через узлы.
- Когда применять: данные содержат шум, измерительные ошибки, или задача — получить простую модель (регрессию).
- Плюсы: устойчивее к шуму, даёт «сглаженное» представление.
- Минусы: теряется точная проходка через узлы; возможно смещение реальные точки.
Экстраполяция
- Формально: использование интерполянта/аппроксиманта для оценки \(f(x)\) вне интервала \([x_0,x_n]\).
- Особенности: риск ошибок часто значительно выше, особенно для полиномиальной экстраполяции высокой степени.
- Когда допустима: если модель известна теоретически за пределами данных (асимптотика, физический закон), или при очень близкой экстраполяции (не дальше по масштабу, чем шаги между узлами).
Куда применять интерполяцию, а куда аппроксимацию?
- Если данные точные, эксперимент повторяем, и задача — восстановить (воссоздать) конкретную функцию → интерполяция.
- Если данные грязные/шумные или требуется обобщённая модель → аппроксимация (регрессия, сглаживание).
3. Что нужно знать перед интерполяцией
- Качество данных: есть ли шум? Есть ли выбросы?
- Если данные шумные — подумать о предварительной фильтрации или аппроксимации.
- Разметка узлов: равномерные ли узлы? Или произвольные?
- Равномерные узлы удобны, но приводят к феномену Рунге для полиномов.
- Гладкость искомой функции: известны ли производные? Это упрощает выбор Эрмита/сплайна.
- Диапазон интереса: интерполяция внутри диапазона vs экстраполяция.
- Цель: визуализация, интегрирование, дифференцирование численно, поиск экстремумов? Это влияет на выбор метода.
4. Линейная интерполяция
Формула (между соседними узлами \(x_i\) и \(x_{i+1}\)):
Разбор формулы:
- \(y_i\) — базовое значение на левом узле;
- \(\frac{y_{i+1}-y_i}{x_{i+1}-x_i}\) — наклон ( slope ) прямой через узлы;
- \((x-x_i)\) — смещение относительно левого узла.
Пошаговое использование:
- Найти \(i\) такое, что \(x\in[x_i,x_{i+1}]\) (если \(x\) равен узлу — вернуть \(y_i\)).
- Подставить \(x\) в формулу и получить \(P_1(x)\).
Пример (численно):
Узлы: \((x_0,y_0)=(1,2)\), \((x_1,y_1)=(4,8)\). Для \(x=2\):
Свойства:
- \(C^0\) непрерывность (значение непрерывно), но \(P_1'(x)\) разрывна в узлах;
- сложность \(O(1)\) для одного значения; память — только узлы.
Когда применять:
- быстрый и надёжный метод для грубой оценки;
- при необходимости выполнения большого числа измерений в реальном времени;
- когда гладкость не нужна (например, при отрисовке ломаной в визуализации).
Оценка ошибки: для гладкой \(f\) на \([x_i,x_{i+1}]\) с максимальной второй производной \(M=\max |f''|\):
5. Полиномиальная интерполяция
Утверждение существования и единственности:
Если \(x_0,\dots,x_n\) — попарно разные узлы, то существует единственный полином \(P_n(x)\) степени \(\le n\) такой, что \(P_n(x_i)=y_i\) для всех \(i\).
Доказательство (кратко, идея):
- Рассмотреть разность \(f(x)-P_n(x)\), показать, что если два полинома совпадают в \(n+1\) точках, то их разность имеет не более \(n\) корней, следовательно тождественно ноль — единственность.
Как находят \(P_n\):
- Решением системы линейных уравнений на коэффициенты \(a_k\) (Вандермонд).
- По формулам (Лагранж или Ньютона) — аналитические представления.
Важность:
полином глобален — изменение одного \(y_i\) влияет на весь полином. Это даёт как плюсы (гладкость, аналитическая форма), так и минусы (колебания, плохая локализация).
6. Полином Лагранжа
Формула:
Почему работает:
- \(L_i(x_j)=\delta_{ij}\) (Кронекер) — потому что когда \(x=x_j\), каждый множитель \((x_j-x_j)=0\) в \(L_i\) за исключением случая \(i=j\), где все множители в знаменателе/числителе корректно обращаются в 1.
- Следовательно \(P_n(x_j)=\sum_i y_i \delta_{ij}=y_j\).
Пояснение знаменателя:
- знаменатель \(d_i=\prod_{j\ne i}(x_i-x_j)\) — это нормировочный множитель, постоянный для данного \(i\), предотвращающий деление на 0 и масштабируя \(L_i\).
Численный пример (полный расчёт):
Точки: \((x_0,y_0)=(0,1)\), \((x_1,y_1)=(1,3)\), \((x_2,y_2)=(2,2)\).
- \(L_0(x)=\dfrac{(x-1)(x-2)}{(0-1)(0-2)}=\dfrac{(x-1)(x-2)}{2}\).
- \(L_1(x)=\dfrac{(x-0)(x-2)}{(1-0)(1-2)}=\dfrac{x(x-2)}{-1}=-x(x-2)\).
- \(L_2(x)=\dfrac{(x-0)(x-1)}{(2-0)(2-1)}=\dfrac{x(x-1)}{2}\).
Теперь
Развёрнутый вид (можно упростить):
Упрощение даст явный квадратичный полином; при подстановке \(x=1.5\) можно вычислить значение.
Плюсы/минусы:
- Плюс: прямая формула, ясна теоретически.
- Минус: при больших \(n\) вычисления неустойчивы и дорогостоящи (много произведений), и ненадёжны для равномерной сетки (феномен Рунге).
7. Полином Ньютона
Форма Ньютона:
где \(a_k = f[x_0,\dots,x_k]\) — разделённая разность порядка \(k\).
Разделённые разности — определение:
- \(f[x_i] = f(x_i)\),
- \(f[x_i,x_{i+1}] = \dfrac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}\),
- и рекурсивно
Почему удобно:
- Табличная структура: можно заполнять треугольную таблицу (как разности), экономя вычисления.
- Добавление нового узла \(x_{n+1}\) требует только вычисления новой диагонали разностей — старые коэффициенты остаются неизменными.
- Численно стабильнее, чем решение системы Вандермонда.
Пример (полный):
Данные: \((0,1),(1,3),(2,2)\).
Таблица разделённых разностей:
- \(f[0]=1\), \(f[1]=3\), \(f[2]=2\).
- \(f[0,1]=(3-1)/(1-0)=2\).
- \(f[1,2]=(2-3)/(2-1)=-1\).
- \(f[0,1,2]=(-1-2)/(2-0)=-3/2\).
Следовательно:
- \(a_0=1\), \(a_1=2\), \(a_2=-3/2\),
и
Проверка в узлах \(x=0,1,2\) даст соответствующие \(y\).
8. Барицентрическая форма Лагранжа
Формула (второй вид — часто используемый):
Разбор:
- Веса \(w_i\) зависят только от расположения узлов — вычисляются один раз.
- Для каждого нового \(x\) рассчитывается дробь сумм; если \(x\) совпадает с \(x_k\), то \(P_n(x)=y_k\) (реализация: проверка совпадения прежде чем вычислять дробь).
- Барицентрическая форма конфликтует с численным взрывом при \(x\) близких к \(x_i\), но это контролируемо: если \(x\) близок к \(x_i\), возвращаем \(y_i\).
Преимущество:
- Очень быстро и устойчиво вычислять множество значений \(P_n(x)\) при фиксированных узлах (или когда добавление узла редкое).
- На практике — предпочтительная форма для интерполяции Лагранжа.
9. Ошибка интерполяции
Формула остатка (Лагранж):
Если \(f\in C^{n+1}\) на промежутке содержащем узлы и точку \(x\), то существует \(\xi\) в этом промежутке, такое что
Разбор компонентов:
- \(f^{(n+1)}(\xi)\) — \((n+1)\)-я производная функции; если она мала, то даже с большим продуктом ошибка будет небольшой.
- \((n+1)!\) — факториал быстро растёт, уменьшает вклад производной (в некоторых оценках).
- \(\prod (x-x_i)\) — ключевой геометрический фактор. Если \(x\) близок к узлам, произведение мало; для равномерных узлов на концах интервала произведение может стать большим → феномен Рунге.
Применение формулы:
- Оценка локальной ошибки: зная оценку на \((n+1)\)-ю производную, можно дать верхнюю границу.
- Для практики часто оценивают максимум: если \(|f^{(n+1)}(t)|\le M\) на интервале, то
Заключение:
остаток подчёркивает слабые стороны глобальных полиномов для больших \(n\) и объясняет, почему сплайны часто лучше на практике.
10. Чебышёвские узлы и феномен Рунге
Феномен Рунге
- При интерполяции на равномерных узлах функции с быстрыми изменениями на концах интервала (например, \(f(x)=\frac{1}{1+25x^2}\) на \([-1,1]\)), при увеличении \(n\) полиномы начинают сильно колебаться у границ, и погрешность растёт.
- Это — не баг алгоритма, а свойство глобальных полиномов на равномерных узлах.
Чебышёвские узлы — рецепция:
Чтобы минимизировать максимум \(|\prod(x-x_i)|\) на \([-1,1]\), выбирают узлы
Почему это помогает:
- Чебышёвские узлы кластеризуются ближе к концам интервала (плотность увеличивается у краёв), что уменьшает амплитуду осцилляций.
- Для многих функций замена равномерных узлов на Чебышёвские даёт более равномерную точность по всему интервалу и предотвращает Рунге-эффект.
Примечание: при реальных данных узлы заданы, и нельзя их выбирать — тогда решением будет переход от глобального полинома к сплайнам.
11. Эрмитова интерполяция, рациональная и тригонометрическая
Эрмитова интерполяция
- Сценарий: помимо \(y_i=f(x_i)\) известны производные \(y_i'=f'(x_i)\) (и, возможно, более высокие производные).
- Цель: построить полином \(H(x)\) такой, что \(H^{(k)}(x_i)=f^{(k)}(x_i)\) для заданных порядков \(k\).
- Пример простейшей Эрмиты: при двух узлах \((x_0,y_0,y'_0)\) и \((x_1,y_1,y'_1)\) строится полином степени не выше 3 (кубический) удовлетворяющий четырём условиям.
Рациональная интерполяция
- Форма: \(R(x)=\dfrac{p(x)}{q(x)}\), где \(\deg p = m\), \(\deg q = k\).
- Преимущества: может моделировать асимптотическое поведение, полюса; часто компактнее и даёт лучшее приближение для функций с особенностями.
- Недостатки: условия интерполяции приводят к нелинейной системе (если одновременно задавать степени и коэффициенты \(q\)), возможны проблемы с полюсами на интервале.
Тригонометрическая интерполяция
- Сценарий: данные равномерно расположены на \([0,2\pi)\); функция периодична.
- Форма: конечный ряд Фурье
- Преимущество: естественно моделирует периодические сигналы; стабильна при использовании быстрого преобразования Фурье (FFT) для вычисления коэффициентов.
12. Сплайны
Что такое сплайн
Сплайн — это «кусочно-полиномиальная» функция: каждый интервал \([x_i,x_{i+1}]\) покрыт собственным многочленом (обычно невысокой степени), и все куски «сшиты» так, чтобы обеспечить определённую степень гладкости в узлах (совпадение значений и некоторых производных).
Почему сплайны
- Локальность: изменение в одном узле влияет только на несколько соседних кусочков (в отличие от глобального полинома).
- Гладкость: можно обеспечить непрерывность первых и вторых производных.
- Устойчивость: минимальны осцилляции, особенно при большом количестве узлов.
Классификация сплайнов:
- Линейный сплайн (степень 1) — \(C^0\) (значение непрерывно).
- Квадратичный сплайн (степень 2) — обычно \(C^1\).
- Кубический сплайн (степень 3) — наиболее распространённый: обеспечивает \(C^2\) (непрерывность вторых производных).
- B-сплайны (basis splines) — базис для сплайнов с компактной опорой; удобны для вычислений и CAD.
- Сглаживающие (smoothing) splines — комбинируют интерполяцию и регуляризацию (минимизируют компромисс между точной проходкой через точки и гладкостью).
Формально (кубический сплайн):
На каждом отрезке \([x_i,x_{i+1}]\):
Условия:
- \(S_i(x_i) = y_i\), \(S_i(x_{i+1}) = y_{i+1}\) (проход через точки),
- \(S_i'(x_{i+1}) = S_{i+1}'(x_{i+1})\) (первая производная непрерывна),
- \(S_i''(x_{i+1}) = S_{i+1}''(x_{i+1})\) (вторая производная непрерывна),
-
- граничные условия (\(S''(x_0)=S''(x_n)=0\) для натурального сплайна или заданы \(S'(x_0),S'(x_n)\) для clamped).
Детали реализации (алгоритм):
- Вычислить \(h_i = x_{i+1}-x_i\).
- Составить систему для вторых производных \(M_i = S''(x_i)\):
для \(i=1,\dots,n-1\). Граничные условия устанавливают \(M_0\) и \(M_n\).
- Решить трёхдиагональную систему (алгоритм Томаса — \(O(n)\)).
- Затем на отрезке \([x_i,x_{i+1}]\):
Это явная формула для каждого кусочка в терминах \(M_i,y_i,h_i\).
Пример:
Узлы: \((0,0),(1,1),(2,0)\).
- \(h_0=h_1=1\).
- Правая часть в формуле (для \(i=1\)):
- Система (только для \(M_1\) при натуральных \(M_0=M_2=0\)):
- Далее подставляем \(M_0=0\), \(M_1=-3\), \(M_2=0\) в формулы для \(S_0(x)\) на \([0,1]\) и \(S_1(x)\) на \([1,2]\).
(Это демонстрация алгоритма; полные выражения \(S_i\) получаются по общей формуле.)
Сглаживающие сплайны:
Если данные шумные, вводят параметр сглаживания \(\lambda\) и ищут \(S\) минимизирующий
При \(\lambda=0\) получаем интерполяцию, при большой \(\lambda\) — приблизительно линейную (или более простую) функцию. Это компромисс между проходом через точки и гладкостью.
13. Многомерная интерполяция
Сценарии:
- \(f:\mathbb{R}^2\to\mathbb{R}\) (поверхности), \(f:\mathbb{R}^d\to\mathbb{R}\).
- Узлы могут быть регулярной сеткой (uniform grid) или рассеянными точками.
Методы для регулярной сетки:
-
Tensor-product interpolation (product of 1D bases).
Если у вас по каждой координате есть 1D-интерполянты \(P_x(x)\) и \(P_y(y)\), можно строить\[ P(x,y) = \sum_{i}\sum_{j} c_{ij} \phi_i(x)\psi_j(y). \]Пример: билинейная (линейная по \(x\) и \(y\)) и бикубическая (кубическая по \(x\) и \(y\)).
- Bilinear interpolation (на квадрате):
Для точки \((x,y)\) внутри прямоугольника вершин \((x_0,y_0),(x_1,y_0),(x_0,y_1),(x_1,y_1)\):- Сначала линейно интерполировать по \(x\) на фиксированных \(y\),
- Затем по \(y\) на полученных значениях.
Формула (стандартная) даёт гладкость \(C^0\).
- Bicubic interpolation — использует 16 соседних точек и обеспечивает непрерывность первых производных; широко применяется в ресемплинге изображений.
Методы для рассеянных узлов:
-
Radial Basis Functions (RBF):
\[ S(x) = \sum_{i=1}^N \lambda_i \,\phi(\|x-x_i\|), \]где \(\phi(r)\) — радиальная базисная функция (Gaussian \(\phi(r)=e^{-(\epsilon r)^2}\), multiquadric, thin-plate spline и т.д.). Коэффициенты \(\lambda_i\) решаются через систему линейных уравнений \(S(x_j)=y_j\).
- Подходит для произвольных точек в \(\mathbb{R}^d\).
- Часто требует решения полного (NxN) линейного уравнения — дорого \(O(N^3)\), но гибко.
- TIN / Delaunay triangulation и натуральный сосед (natural neighbor):
- Для двумерных данных используют триангуляцию Делоне. Интерполяция внутри треугольника (линейная) или более сложная (серфы) — локальный и быстрый метод.
- Kriging (геостатистика):
- Стохастический метод, учитывает ковариацию и даёт оценку погрешности. Используется в геонауках и при пространственном моделировании.
Пример билинейной интерполяции (численно):
Вершины квадрата \((0,0):f_{00}=1\), \((1,0):f_{10}=2\), \((0,1):f_{01}=3\), \((1,1):f_{11}=4\), хотим \(f(0.3,0.6)\):
- Сначала лин. интерп. по \(x\) при \(y=0\): \(f_x(0.3,0)=1 + (2-1)*0.3 = 1.3\).
- По \(x\) при \(y=1\): \(f_x(0.3,1)=3 + (4-3)*0.3 = 3.3\).
- Затем лин. по \(y\) между 1.3 и 3.3: \(f(0.3,0.6) = 1.3 + (3.3-1.3)*0.6 = 1.3 + 2*0.6 = 2.5\).
14. Численные аспекты
Вандермонд и обусловленность
- Решение системы \(V a = y\) для коэффициентов полинома (матрица Вандермонда \(V_{ij}=x_i^{j}\)) может быть крайне плохо обусловлено при больших \(n\) или при близких узлах. Это означает, что малые ошибки в \(y\) или округления приведут к большим ошибкам в \(a\).
Что делать на практике:
- Использовать формы Ньютона или барицентрической Лагранж-формы.
- Для больших \(n\) — переходить к сплайнам или локальным методам.
- При RBF — внимательно выбирать параметр формы (например, ширину гаусса) и применять регуляризацию для устойчивости.
Сложности по времени/памяти:
- Глобальный полином (коэффициенты через Вандермонд): решение \(O(n^3)\) наивно, численно плохо.
- Таблица разделённых разностей (Ньютон): \(O(n^2)\) предвычисление, \(O(n)\) оценка.
- Барицентрическая форма: \(O(n)\) на одну оценку, \(O(n^2)\) для многих \(x\) (если веса не переиспользуются).
- Кубический сплайн: трёхдиагональная система \(O(n)\) решение, оценка также \(O(\log n)\) или \(O(1)\) при поиске интервала + \(O(1)\) вычисление на интервале.
- RBF: решение полной системы \(O(N^3)\), при больших N — методы ускорения (fast multipole, локальные методики).
Оценка ошибок округлений
- При вычислении построений с множественными произведениями (Лагранж) аккуратно использовать численно устойчивые алгоритмы: барицентрическая форма, формула Ньютона, применение условной нормировки.
15. Практическая методология: как выбирать метод (чеклист)
- Оценить качество данных:
- чистые теоретические значения → глобальные полиномы допустимы;
- шумные данные → аппроксимация или сглаживающие сплайны.
- Оценить число узлов:
- мало (n ≤ 8–10) → полиномы (с осторожностью);
- много → кубические сплайны.
- Нужна ли гладкость \(C^1,C^2\)?
- да → сплайн (кубический);
- нет → линейный/поли-н.
- Есть ли производные в узлах?
- да → Эрмит/сплайны с условиями;
- нет → стандартные методы.
- Регулярность узлов:
- равномерные и периодические → тригонометрическая/Фурье;
- нерегулярные → RBF или Delaunay методы.
- Экстраполяция важна?
- да → лучше выбрать модель с обоснованной асимптотикой (рациональная модель, аппроксимация с регуляризацией).
- Числовые ограничения:
- ограниченная память/скорость → сплайны (O(n) подготовка, O(1) оценка).
16. Пошаговые примеры
Пример 1. Полином Лагранжа
Даны: \((0,1),(1,3),(2,2)\).
- Вычисляем \(L_0(x)\):
- \(L_1(x)=\frac{(x-0)(x-2)}{(1-0)(1-2)}=-x(x-2)\).
- \(L_2(x)=\frac{x(x-1)}{2}\).
- Складываем:
- Упрощаем (по алгебре) и проверяем \(P_2(0)=1\), \(P_2(1)=3\), \(P_2(2)=2\).
Пример 2. Ньютон
Те же узлы:
- \(a_0=1\),
- \(a_1=2\),
-
\(a_2=-3/2\),
и\[ P_2(x)=1 + 2(x-0) -\tfrac32(x-0)(x-1). \]
Подставляем \(x=1.5\):
Пример 3. Кубический сплайн
Узлы \((0,0),(1,1),(2,0)\). Натуральный сплайн (\(M_0=M_2=0\)).
- \(h_0=h_1=1\).
- Уравнение для \(M_1\):
подставляем \(M_0=M_2=0 \Rightarrow \frac{2}{3}M_1=-2\Rightarrow M_1=-3\).
- Тогда по формуле куска \(S_0(x)\) на \([0,1]\):
Подставим \(M_0=0,M_1=-3,y_0=0,y_1=1\) и упростим — получим явный \(S_0(x)\).
- Аналогично \(S_1(x)\) на \([1,2]\).
17. Типичные ошибки и как их избегать
- Интерполировать шум напрямую → используйте сглаживание/аппроксимацию.
- Использовать глобальный полином высокой степени при большом \(n\) → переходите к сплайнам.
- Игнорировать численные ошибки Вандермонда → применять Ньютона/барицентрическую форму.
- Экстраполировать далеко за пределы узлов через высокую степень полинома → это риск; используйте модель с физическим смыслом или рациональную модель.
- Неправильно выбирать узлы → при проектировании узлов (если возможно) используйте Чебышёвские узлы.
18. Сводка формул
- Интерполянт: \(P_n(x_i)=y_i\).
- Линейная: \(P_1(x)=y_i+\dfrac{y_{i+1}-y_i}{x_{i+1}-x_i}(x-x_i)\).
- Лагранж: \(P_n(x)=\sum_{i=0}^n y_i \prod_{j\ne i}\dfrac{x-x_j}{x_i-x_j}\).
- Ньютон: \(P_n(x)=\sum_{k=0}^n f[x_0,\dots,x_k]\prod_{j=0}^{k-1}(x-x_j)\).
- Барицентрическая: \(P_n(x)=\dfrac{\sum_{i=0}^n \frac{w_i}{x-x_i}y_i}{\sum_{i=0}^n \frac{w_i}{x-x_i}}\).
- Остаток: \(R_n(x)=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n (x-x_i)\).
- Чебышёв: \(x_k=\cos\left(\frac{2k+1}{2(n+1)}\pi\right)\).
- Кубический сплайн (система для \(M\)): \(\dfrac{h_{i-1}}{6}M_{i-1} + \dfrac{h_{i-1}+h_i}{3}M_i + \dfrac{h_i}{6}M_{i+1} = \dfrac{y_{i+1}-y_i}{h_i} - \dfrac{y_i-y_{i-1}}{h_{i-1}}\).
19. Заключение и рекомендации
- Интерполяция — мощный инструмент, но требует хорошего понимания входных данных и последствий выбора метода.
- Для практики чаще всего кубические сплайны дают лучшее сочетание гладкости и устойчивости.
- Для коротких наборов данных и при необходимости аналитической формы — Ньютон/Лагранж приемлемы.
- Всегда проверяй адекватность метода: визуализируй, оцени остатки, проверяй поведение на краях и при экстраполяции.