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

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. Что нужно знать перед интерполяцией

1. Качество данных: есть ли шум? Есть ли выбросы?
   • Если данные шумные — подумать о предварительной фильтрации или аппроксимации.
2. Разметка узлов: равномерные ли узлы? Или произвольные?
   • Равномерные узлы удобны, но приводят к феномену Рунге для полиномов.
3. Гладкость искомой функции: известны ли производные? Это упрощает выбор Эрмита/сплайна.
4. Диапазон интереса: интерполяция внутри диапазона vs экстраполяция.
5. Цель: визуализация, интегрирование, дифференцирование численно, поиск экстремумов? Это влияет на выбор метода.

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

Формула (между соседними узлами $x_i$ и $x_{i+1}$):

Разбор формулы:

• $y_i$ — базовое значение на левом узле;
• $\frac{y_{i+1}-y_i}{x_{i+1}-x_i}$ — наклон ( slope ) прямой через узлы;
• $(x-x_i)$ — смещение относительно левого узла.

Пошаговое использование:

1. Найти $i$ такое, что $x\in[x_i,x_{i+1}]$ (если $x$ равен узлу — вернуть $y_i$).
2. Подставить $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$:

1. Решением системы линейных уравнений на коэффициенты $a_k$ (Вандермонд).
2. По формулам (Лагранж или Ньютона) — аналитические представления.

Важность:

полином глобален — изменение одного $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)$.

1. $L_0(x)=\dfrac{(x-1)(x-2)}{(0-1)(0-2)}=\dfrac{(x-1)(x-2)}{2}$.
2. $L_1(x)=\dfrac{(x-0)(x-2)}{(1-0)(1-2)}=\dfrac{x(x-2)}{-1}=-x(x-2)$.
3. $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. Линейный сплайн (степень 1) — $C^0$ (значение непрерывно).
2. Квадратичный сплайн (степень 2) — обычно $C^1$.
3. Кубический сплайн (степень 3) — наиболее распространённый: обеспечивает $C^2$ (непрерывность вторых производных).
4. B-сплайны (basis splines) — базис для сплайнов с компактной опорой; удобны для вычислений и CAD.
5. Сглаживающие (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).

Детали реализации (алгоритм):

1. Вычислить $h_i = x_{i+1}-x_i$.
2. Составить систему для вторых производных $M_i = S’‘(x_i)$:

для $i=1,\dots,n-1$. Граничные условия устанавливают $M_0$ и $M_n$.

1. Решить трёхдиагональную систему (алгоритм Томаса — $O(n)$).
2. Затем на отрезке $[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) или рассеянными точками.

Методы для регулярной сетки:

1. Tensor-product interpolation (product of 1D bases).
   Если у вас по каждой координате есть 1D-интерполянты $P_x(x)$ и $P_y(y)$, можно строить

Пример: билинейная (линейная по $x$ и $y$) и бикубическая (кубическая по $x$ и $y$).

1. 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$.
2. Bicubic interpolation — использует 16 соседних точек и обеспечивает непрерывность первых производных; широко применяется в ресемплинге изображений.

Методы для рассеянных узлов:

1. Radial Basis Functions (RBF):

где $\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)$, но гибко.

1. TIN / Delaunay triangulation и натуральный сосед (natural neighbor):
   • Для двумерных данных используют триангуляцию Делоне. Интерполяция внутри треугольника (линейная) или более сложная (серфы) — локальный и быстрый метод.
2. 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 + 20.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. Практическая методология: как выбирать метод (чеклист)

1. Оценить качество данных:
   • чистые теоретические значения → глобальные полиномы допустимы;
   • шумные данные → аппроксимация или сглаживающие сплайны.
2. Оценить число узлов:
   • мало (n ≤ 8–10) → полиномы (с осторожностью);
   • много → кубические сплайны.
3. Нужна ли гладкость $C^1,C^2$?
   • да → сплайн (кубический);
   • нет → линейный/поли-н.
4. Есть ли производные в узлах?
   • да → Эрмит/сплайны с условиями;
   • нет → стандартные методы.
5. Регулярность узлов:
   • равномерные и периодические → тригонометрическая/Фурье;
   • нерегулярные → RBF или Delaunay методы.
6. Экстраполяция важна?
   • да → лучше выбрать модель с обоснованной асимптотикой (рациональная модель, аппроксимация с регуляризацией).
7. Числовые ограничения:
   • ограниченная память/скорость → сплайны (O(n) подготовка, O(1) оценка).

16. Пошаговые примеры

Пример 1. Полином Лагранжа

Даны: $(0,1),(1,3),(2,2)$.

1. Вычисляем $L_0(x)$:

1. $L_1(x)=\frac{(x-0)(x-2)}{(1-0)(1-2)}=-x(x-2)$.
2. $L_2(x)=\frac{x(x-1)}{2}$.
3. Складываем:

1. Упрощаем (по алгебре) и проверяем $P_2(0)=1$, $P_2(1)=3$, $P_2(2)=2$.

Пример 2. Ньютон

Те же узлы:

• $a_0=1$,
• $a_1=2$,
• $a_2=-3/2$,
  и

Подставляем $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. Типичные ошибки и как их избегать

1. Интерполировать шум напрямую → используйте сглаживание/аппроксимацию.
2. Использовать глобальный полином высокой степени при большом $n$ → переходите к сплайнам.
3. Игнорировать численные ошибки Вандермонда → применять Ньютона/барицентрическую форму.
4. Экстраполировать далеко за пределы узлов через высокую степень полинома → это риск; используйте модель с физическим смыслом или рациональную модель.
5. Неправильно выбирать узлы → при проектировании узлов (если возможно) используйте Чебышёвские узлы.

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. Заключение и рекомендации

• Интерполяция — мощный инструмент, но требует хорошего понимания входных данных и последствий выбора метода.
• Для практики чаще всего кубические сплайны дают лучшее сочетание гладкости и устойчивости.
• Для коротких наборов данных и при необходимости аналитической формы — Ньютон/Лагранж приемлемы.
• Всегда проверяй адекватность метода: визуализируй, оцени остатки, проверяй поведение на краях и при экстраполяции.