Кубический сплайн интерполяция: моменты и прогонка

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

Что такое кубический сплайн

Пусть заданы узлы интерполяции $a = x_0 < x_1 < \dots < x_n = b$ и значения $y_i = f(x_i)$. Кубический сплайн $S(x)$ - это функция, которая на каждом отрезке $[x_i, x_{i+1}]$ совпадает с некоторым кубическим многочленом $S_i(x)$, а в точках стыковки склеена гладко. Формально требуется выполнение четырёх групп условий:

• интерполяция: $S(x_i) = y_i$ во всех узлах;
• непрерывность самой функции в узлах;
• непрерывность первой производной $S'(x)$;
• непрерывность второй производной $S''(x)$.

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

Система на моменты (вторые производные)

Удобнее всего строить сплайн не через коэффициенты напрямую, а через значения вторых производных в узлах $M_i = S''(x_i)$, которые называют моментами. Поскольку $S''$ на каждом отрезке линейна, вторую производную можно записать как линейную интерполяцию между $M_i$ и $M_{i+1}$. Дважды проинтегрировав и подставив значения $y_i$, $y_{i+1}$ на концах отрезка $[x_i, x_{i+1}]$ длины $h_i = x_{i+1} - x_i$, получаем явное выражение для $S_i(x)$ через моменты.

Условие непрерывности первой производной в каждом внутреннем узле $x_i$ даёт связь между тремя соседними моментами:

$h_{i-1} M_{i-1} + 2(h_{i-1} + h_i) M_i + h_i M_{i+1} = 6\left(\frac{y_{i+1} - y_i}{h_i} - \frac{y_i - y_{i-1}}{h_{i-1}}\right).$

Это $n-1$ уравнение на $n+1$ неизвестный момент. Недостающие два уравнения дают краевые условия - о них ниже. Матрица системы трёхдиагональная и диагонально доминирующая, что гарантирует единственность решения и численную устойчивость.

Метод прогонки

Трёхдиагональную систему не нужно решать общим методом Гаусса - для неё есть метод прогонки (алгоритм Томаса), работающий за $O(n)$ операций. Он состоит из двух проходов: прямого, на котором каждую неизвестную выражают через следующую с помощью прогоночных коэффициентов, и обратного, на котором значения восстанавливают с конца. Рекуррентные формулы прямого хода имеют вид

$\alpha_{i+1} = \frac{-c_i}{b_i + a_i \alpha_i}, \qquad \beta_{i+1} = \frac{d_i - a_i \beta_i}{b_i + a_i \alpha_i},$

где $a_i, b_i, c_i$ - поддиагональ, диагональ и наддиагональ, а $d_i$ - правая часть. Обратный ход: $M_i = \alpha_{i+1} M_{i+1} + \beta_{i+1}$. Диагональное преобладание ($|b_i| > |a_i| + |c_i|$), которое автоматически выполняется для кубического сплайна, защищает прогонку от деления на ноль и накопления ошибки.

Краевые условия

Два недостающих уравнения замыкают систему и определяют поведение сплайна на концах отрезка. Выбор зависит от того, что известно о функции:

• Естественный сплайн: $M_0 = M_n = 0$, то есть $S''$ обнуляется на концах. Кривая выпрямляется к краям - это аналог гибкой линейки, отпущенной за пределами крайних точек.
• Закреплённый (clamped): заданы первые производные $S'(x_0)$ и $S'(x_n)$. Даёт наименьшую погрешность, если наклоны на концах известны.
• Not-a-knot: третья производная непрерывна в первом и последнем внутренних узлах. Используется по умолчанию во многих пакетах (в том числе в MATLAB), когда о краях ничего не известно.
• Периодический: значения и производные совпадают на обоих концах - для замкнутых кривых.

Естественные условия проще всего для ручного счёта, поэтому в учебных задачах кубический сплайн чаще всего строят именно как естественный.

Коэффициенты на каждом отрезке

После нахождения моментов многочлен на отрезке $[x_i, x_{i+1}]$ удобно записать в форме разложения по степеням $(x - x_i)$:

$S_i(x) = a_i + b_i (x - x_i) + c_i (x - x_i)^2 + d_i (x - x_i)^3,$

где коэффициенты выражаются через значения и моменты:

$a_i = y_i, \quad c_i = \frac{M_i}{2}, \quad d_i = \frac{M_{i+1} - M_i}{6 h_i}, \quad b_i = \frac{y_{i+1} - y_i}{h_i} - \frac{h_i (2 M_i + M_{i+1})}{6}.$

Подстановка $x = x_i$ даёт $S_i(x_i) = y_i$, а согласование $b_i$ обеспечивает гладкость стыков. Так кубическая сплайн-интерполяция собирает единую дважды дифференцируемую кривую из локальных кубик.

Сравнение с многочленом Лагранжа

Кубический сплайн интерполяция и единый интерполяционный многочлен решают одну задачу - провести кривую через узлы, - но ведут себя противоположно при росте числа точек. Многочлен степени $n$, например в форме интерполяционной формулы Лагранжа, при большом $n$ на равномерной сетке даёт растущие осцилляции у краёв (феномен Рунге). Сплайн же всегда состоит из кубик, поэтому добавление узлов лишь уточняет кривую, не раскачивая её.

Платой за устойчивость является локальность другого рода: сплайн не задаётся одной формулой, его приходится хранить кусочно. Зато погрешность естественного сплайна на гладкой функции убывает как $O(h^4)$ для значений и $O(h^2)$ для второй производной, где $h$ - максимальный шаг сетки. Для большинства прикладных задач это гораздо надёжнее, чем глобальный многочлен.

Есть и принципиальное отличие в чувствительности к данным. Изменение одного значения $y_i$ у многочлена Лагранжа перестраивает кривую на всём отрезке, тогда как у сплайна возмущение быстро затухает с удалением от изменённого узла - система на моменты диагонально доминирующая, и влияние одного узла локализовано. Это делает сплайн предпочтительным при работе с зашумлёнными или часто обновляемыми данными, где не хочется, чтобы одна точка «дёргала» всю кривую.

Где применяется

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

Частые ошибки

• Путаница моментов и коэффициентов: $M_i$ - это $S''(x_i)$, а не $c_i$; коэффициент $c_i = M_i / 2$, забытая двойка ломает весь сплайн.
• Неучтённые краевые условия: без двух дополнительных уравнений система недоопределена - нельзя просто отбросить $M_0$ и $M_n$.
• Неравномерная сетка: при разных $h_i$ нельзя пользоваться упрощёнными формулами для равномерного шага, в систему входят именно $h_{i-1}$ и $h_i$.
• Степень $(x - x_i)$, а не $x$: коэффициенты $b_i, c_i, d_i$ записаны относительно левого конца отрезка; подстановка «голого» $x$ даёт неверное значение.
• Решение Гауссом вместо прогонки: для трёхдиагональной матрицы общий метод избыточен и менее устойчив - используйте алгоритм Томаса.

FAQ

Чем кубический сплайн лучше многочлена Лагранжа? При большом числе узлов он не страдает от феномена Рунге: степень остаётся третьей на каждом отрезке, поэтому кривая не осциллирует у краёв и устойчиво уточняется при добавлении точек.

Что такое моменты в методе сплайнов? Это значения второй производной сплайна в узлах, $M_i = S''(x_i)$. Их находят из трёхдиагональной системы, а затем по ним вычисляют коэффициенты кубики на каждом отрезке.

Какие краевые условия выбрать? Если о концах ничего не известно - естественные ($M_0 = M_n = 0$) для ручного счёта или not-a-knot в пакетах. Если известны наклоны на концах - закреплённые, они дают наименьшую погрешность.

Коротко

Кубическая сплайн-интерполяция строит гладкую кривую через таблицу точек, склеивая её из кубических многочленов $S_i(x) = a_i + b_i(x - x_i) + c_i(x - x_i)^2 + d_i(x - x_i)^3$ с непрерывными $S$, $S'$ и $S''$. Ключ к построению - моменты $M_i = S''(x_i)$, которые находят из трёхдиагональной диагонально доминирующей системы методом прогонки за $O(n)$, после чего по ним выражают коэффициенты каждого отрезка. Два краевых условия (естественные, закреплённые, not-a-knot или периодические) замыкают систему. В отличие от многочлена Лагранжа сплайн не подвержен феномену Рунге и даёт погрешность $O(h^4)$ на гладких функциях.