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

1. Введение и определение

Интерполяция — это процесс построения функции \(P(x)\), которая совпадает с известными значениями некоторой другой функции \(f(x)\) в заданном наборе точек (узлов) \(x_0, x_1, \dots, x_n\):

\[ P(x_i) = f(x_i) = y_i,\qquad i=0,\dots,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}\)):

\[ P_1(x)=y_i+\frac{y_{i+1}-y_i}{x_{i+1}-x_i}\,(x-x_i). \]

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

  • \(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\):

\[ P_1(2)=2+\frac{8-2}{4-1}(2-1)=2+\frac{6}{3}=4. \]

Свойства:

  • \(C^0\) непрерывность (значение непрерывно), но \(P_1'(x)\) разрывна в узлах;
  • сложность \(O(1)\) для одного значения; память — только узлы.

Когда применять:

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

Оценка ошибки: для гладкой \(f\) на \([x_i,x_{i+1}]\) с максимальной второй производной \(M=\max |f''|\):

\[ |f(x)-P_1(x)| \le \frac{M}{8}(x_{i+1}-x_i)^2 \quad \text{(на отрезке)}. \]

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. Полином Лагранжа

Формула:

\[ P_n(x)=\sum_{i=0}^n y_i L_i(x),\qquad L_i(x)=\prod_{\substack{j=0\\ j\ne i}}^{n}\frac{x-x_j}{x_i-x_j}. \]

Почему работает:

  • \(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}\).

Теперь

\[ P_2(x)=1\cdot L_0(x)+3\cdot L_1(x)+2\cdot L_2(x). \]

Развёрнутый вид (можно упростить):

\[ P_2(x)=\frac{(x-1)(x-2)}{2} - 3x(x-2) + 2\cdot\frac{x(x-1)}{2}. \]

Упрощение даст явный квадратичный полином; при подстановке \(x=1.5\) можно вычислить значение.

Плюсы/минусы:

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

7. Полином Ньютона

Форма Ньютона:

\[ P_n(x) = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) + \dots + a_n\prod_{j=0}^{n-1}(x-x_j), \]

где \(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}\),
  • и рекурсивно
\[ f[x_i,\dots,x_{i+k}] = \frac{f[x_{i+1},\dots,x_{i+k}] - f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-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\),
    и
\[ P_2(x)=1 + 2(x-0) -\tfrac32 (x-0)(x-1). \]

Проверка в узлах \(x=0,1,2\) даст соответствующие \(y\).

8. Барицентрическая форма Лагранжа

Формула (второй вид — часто используемый):

\[ P_n(x)=\frac{\displaystyle\sum_{i=0}^n \frac{w_i}{x-x_i}\,y_i}{\displaystyle\sum_{i=0}^n \frac{w_i}{x-x_i}}, \qquad w_i=\frac{1}{\prod_{j\ne i}(x_i-x_j)}. \]

Разбор:

  • Веса \(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\) в этом промежутке, такое что

\[ R_n(x)=f(x)-P_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i). \]

Разбор компонентов:

  • \(f^{(n+1)}(\xi)\) — \((n+1)\)-я производная функции; если она мала, то даже с большим продуктом ошибка будет небольшой.
  • \((n+1)!\) — факториал быстро растёт, уменьшает вклад производной (в некоторых оценках).
  • \(\prod (x-x_i)\) — ключевой геометрический фактор. Если \(x\) близок к узлам, произведение мало; для равномерных узлов на концах интервала произведение может стать большим → феномен Рунге.

Применение формулы:

  • Оценка локальной ошибки: зная оценку на \((n+1)\)-ю производную, можно дать верхнюю границу.
  • Для практики часто оценивают максимум: если \(|f^{(n+1)}(t)|\le M\) на интервале, то
\[ |R_n(x)| \le \frac{M}{(n+1)!}\left|\prod_{i=0}^n(x-x_i)\right|. \]

Заключение:

остаток подчёркивает слабые стороны глобальных полиномов для больших \(n\) и объясняет, почему сплайны часто лучше на практике.

10. Чебышёвские узлы и феномен Рунге

Феномен Рунге

  • При интерполяции на равномерных узлах функции с быстрыми изменениями на концах интервала (например, \(f(x)=\frac{1}{1+25x^2}\) на \([-1,1]\)), при увеличении \(n\) полиномы начинают сильно колебаться у границ, и погрешность растёт.
  • Это — не баг алгоритма, а свойство глобальных полиномов на равномерных узлах.

Чебышёвские узлы — рецепция:

Чтобы минимизировать максимум \(|\prod(x-x_i)|\) на \([-1,1]\), выбирают узлы

\[ x_k = \cos\left(\frac{2k+1}{2(n+1)}\pi\right),\quad k=0,\dots,n. \]

Почему это помогает:

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

Примечание: при реальных данных узлы заданы, и нельзя их выбирать — тогда решением будет переход от глобального полинома к сплайнам.

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)\); функция периодична.
  • Форма: конечный ряд Фурье
\[ T_n(x)=a_0 + \sum_{k=1}^n(a_k\cos kx + b_k\sin kx). \]
  • Преимущество: естественно моделирует периодические сигналы; стабильна при использовании быстрого преобразования Фурье (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) = a_i + b_i (x-x_i) + c_i (x-x_i)^2 + d_i (x-x_i)^3. \]

Условия:

  • \(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)\):
\[ \frac{h_{i-1}}{6}M_{i-1} + \frac{h_{i-1}+h_i}{3}M_i + \frac{h_i}{6}M_{i+1} = \frac{y_{i+1}-y_i}{h_i} - \frac{y_i-y_{i-1}}{h_{i-1}}, \]

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

  1. Решить трёхдиагональную систему (алгоритм Томаса — \(O(n)\)).
  2. Затем на отрезке \([x_i,x_{i+1}]\):
\[ S_i(x) = \frac{M_{i}}{6}\frac{(x_{i+1}-x)^3}{h_i} + \frac{M_{i+1}}{6}\frac{(x-x_i)^3}{h_i} + \left(\frac{y_i}{h_i} - \frac{M_i h_i}{6}\right)(x_{i+1}-x) + \left(\frac{y_{i+1}}{h_i} - \frac{M_{i+1} h_i}{6}\right)(x - x_i). \]

Это явная формула для каждого кусочка в терминах \(M_i,y_i,h_i\).

Пример:

Узлы: \((0,0),(1,1),(2,0)\).

  • \(h_0=h_1=1\).
  • Правая часть в формуле (для \(i=1\)):
\[ \frac{y_2-y_1}{h_1} - \frac{y_1-y_0}{h_0} = \frac{0-1}{1} - \frac{1-0}{1} = -2. \]
  • Система (только для \(M_1\) при натуральных \(M_0=M_2=0\)):
\[ \frac{1}{6}M_0 + \frac{1+1}{3}M_1 + \frac{1}{6}M_2 = -2 \quad\Rightarrow\quad \frac{2}{3} M_1 = -2 \Rightarrow M_1 = -3. \]
  • Далее подставляем \(M_0=0\), \(M_1=-3\), \(M_2=0\) в формулы для \(S_0(x)\) на \([0,1]\) и \(S_1(x)\) на \([1,2]\).

(Это демонстрация алгоритма; полные выражения \(S_i\) получаются по общей формуле.)

Сглаживающие сплайны:

Если данные шумные, вводят параметр сглаживания \(\lambda\) и ищут \(S\) минимизирующий

\[ \sum_i (y_i - S(x_i))^2 + \lambda \int (S''(x))^2 dx. \]

При \(\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)\), можно строить

    \[ P(x,y) = \sum_{i}\sum_{j} c_{ij} \phi_i(x)\psi_j(y). \]

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

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

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

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

  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)\):
\[ L_0(x)=\frac{(x-1)(x-2)}{(0-1)(0-2)}=\frac{(x-1)(x-2)}{2}. \]
  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. Складываем:
\[ P_2(x)=1\cdot\frac{(x-1)(x-2)}{2} + 3\cdot (-x(x-2)) + 2\cdot\frac{x(x-1)}{2}. \]
  1. Упрощаем (по алгебре) и проверяем \(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\):

\[ P_2(1.5)=1 + 2\cdot1.5 -1.5\cdot(1.5)(0.5) = 1 + 3 - 1.125 = 2.875. \]

Пример 3. Кубический сплайн

Узлы \((0,0),(1,1),(2,0)\). Натуральный сплайн (\(M_0=M_2=0\)).

  • \(h_0=h_1=1\).
  • Уравнение для \(M_1\):
\[ \frac{1}{6}M_0 + \frac{2}{3}M_1 + \frac{1}{6}M_2 = \frac{0-1}{1} - \frac{1-0}{1} = -2, \]

подставляем \(M_0=M_2=0 \Rightarrow \frac{2}{3}M_1=-2\Rightarrow M_1=-3\).

  • Тогда по формуле куска \(S_0(x)\) на \([0,1]\):
\[ S_0(x) = \frac{M_0}{6}\frac{(1-x)^3}{1} + \frac{M_1}{6}\frac{(x-0)^3}{1} + \left(\frac{y_0}{1} - \frac{M_0}{6}\right)(1-x) + \left(\frac{y_1}{1} - \frac{M_1}{6}\right)(x-0). \]

Подставим \(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. Заключение и рекомендации

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