Кубический сплайн

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

История

Термин «сплайн» (от англ. spline — гибкая линейка) происходит из корабельной и авиационной промышленности, где для построения плавных кривых по заданным точкам использовали гибкую металлическую или деревянную рейку, закреплённую в опорных точках. Математическая теория сплайнов начала активно развиваться в середине XX века. В 1946 году американский математик Исаак Шёнберг опубликовал работу, в которой впервые ввёл математическое определение сплайна и обосновал его свойства. В 1960-х годах, с развитием вычислительной техники, кубические сплайны стали широко применяться в численном анализе, компьютерной графике и обработке сигналов.

Определение и математическая формулировка

Пусть на отрезке [a, b] задана сетка узлов:

a = x₀ < x₁ < x₂ < ... < xₙ = b

и значения функции f(x) в этих узлах: y₀, y₁, y₂, ..., yₙ.

Кубическим сплайном S(x) называется функция, удовлетворяющая следующим условиям:

1. Кусочная полиномиальность: На каждом подынтервале [xᵢ₋₁, xᵢ] (i = 1, 2, ..., n) функция S(x) является многочленом третьей степени Sᵢ(x) = aᵢ + bᵢ(x - xᵢ₋₁) + cᵢ(x - xᵢ₋₁)² + dᵢ(x - xᵢ₋₁)³.
2. Интерполяция: S(xᵢ) = yᵢ для всех i = 0, 1, ..., n.
3. Непрерывность: S(x) непрерывна на всём отрезке [a, b].
4. Гладкость: Первая производная S'(x) и вторая производная S''(x) непрерывны на всём отрезке [a, b].

Для однозначного определения сплайна (нахождения 4n коэффициентов aᵢ, bᵢ, cᵢ, dᵢ) необходимо задать два дополнительных граничных условия на концах отрезка. Наиболее распространённые типы граничных условий:

• Естественный сплайн (natural spline): S''(a) = 0 и S''(b) = 0. Это условие обеспечивает нулевую кривизну на концах.
• Защемлённый сплайн (clamped spline): S'(a) = f'(a) и S'(b) = f'(b). Требует знания производных интерполируемой функции на концах.
• Периодический сплайн (periodic spline): S'(a) = S'(b) и S''(a) = S''(b). Используется для интерполяции периодических функций.
• Условие отсутствия узла (not-a-knot spline): Третья производная S'''(x) непрерывна в точках x₁ и xₙ₋₁. Это условие приводит к тому, что первые два и последние два подынтервала описываются одним многочленом.

Алгоритм построения

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

1. Вычисляются шаги hᵢ = xᵢ - xᵢ₋₁ для i = 1, ..., n.
2. Составляется система уравнений для вторых производных mᵢ = S''(xᵢ) (i = 0, ..., n).
3. Для внутренних узлов (i = 1, ..., n-1) уравнение имеет вид:

hᵢ mᵢ₋₁ + 2(hᵢ + hᵢ₊₁) mᵢ + hᵢ₊₁ mᵢ₊₁ = 6 * ( (yᵢ₊₁ - yᵢ) / hᵢ₊₁ - (yᵢ - yᵢ₋₁) / hᵢ )

1. Добавляются граничные условия. Для естественного сплайна: m₀ = 0, mₙ = 0.
2. Решается полученная трёхдиагональная система, находятся все mᵢ.
3. Коэффициенты каждого кубического многочлена Sᵢ(x) на подынтервале [xᵢ₋₁, xᵢ] вычисляются по формулам:

aᵢ = yᵢ₋₁ bᵢ = (yᵢ - yᵢ₋₁) / hᵢ - hᵢ (2mᵢ₋₁ + mᵢ) / 6 cᵢ = mᵢ₋₁ / 2 dᵢ = (mᵢ - mᵢ₋₁) / (6 * hᵢ)

Свойства

• Минимизация кривизны: Среди всех функций, дважды непрерывно дифференцируемых на [a, b] и интерполирующих заданные значения, именно кубический сплайн с естественными граничными условиями минимизирует функционал ∫(S''(x))²dx. Это свойство означает, что сплайн является «максимально гладкой» интерполяционной кривой.
• Сходимость: При увеличении числа узлов разбиения (h → 0) кубический сплайн сходится к интерполируемой функции f(x) вместе со своими производными, если f(x) достаточно гладкая (например, f ∈ C⁴[a, b]).
• Локальность: Изменение значения в одном узле влияет на коэффициенты сплайна только на нескольких соседних подынтервалах, что делает его устойчивым к локальным возмущениям данных.
• Отсутствие осцилляций: В отличие от интерполяции полиномами высокой степени (например, интерполяционного многочлена Лагранжа), кубические сплайны не подвержены эффекту Рунге — сильным осцилляциям на краях отрезка при большом числе узлов.

Применение

Кубические сплайны находят широкое применение в различных областях науки и техники:

• Численный анализ: Интерполяция табличных функций, численное дифференцирование и интегрирование.
• Компьютерная графика: Построение гладких кривых (например, в шрифтах TrueType, в системах автоматизированного проектирования (САПР) для создания обводов деталей).
• Обработка сигналов: Сглаживание и ресемплинг данных (например, в аудио- и видеообработке, при изменении частоты дискретизации).
• Статистика и анализ данных: Построение непараметрических регрессионных моделей (сглаживающие сплайны).
• Робототехника: Планирование траекторий движения роботов, обеспечивающее плавное изменение скорости и ускорения.
• Геоинформационные системы (ГИС): Построение цифровых моделей рельефа и интерполяция пространственных данных.

Разновидности и обобщения

• B-сплайн (Basis spline): Кубический сплайн, представленный как линейная комбинация базисных функций (B-сплайнов) с компактным носителем. Обладает лучшей локальностью и численной устойчивостью.
• Сглаживающий сплайн (smoothing spline): Строится не по точным значениям, а по зашумлённым данным. Минимизирует взвешенную сумму квадратов невязок и штрафа за кривизну. Параметр сглаживания определяет баланс между точностью и гладкостью.
• Параметрический кубический сплайн: Используется для представления кривых на плоскости или в пространстве, когда каждая координата (x(t), y(t)) является отдельным кубическим сплайном от параметра t.
• Эрмитов кубический сплайн: На каждом подынтервале задаются не только значения функции, но и значения её производной в узлах. Позволяет контролировать форму кривой.

Критика

Основным недостатком кубических сплайнов является их чувствительность к выбросам в данных. Один резко выбивающийся узел может вызвать значительные искажения формы кривой на нескольких соседних интервалах. Кроме того, для построения сплайна требуется решение системы линейных уравнений, что при очень большом числе узлов (сотни тысяч и миллионы) может быть вычислительно затратным, хотя трёхдиагональная структура системы позволяет применять эффективные алгоритмы. В некоторых приложениях, где требуется более высокая гладкость (например, непрерывность третьей производной), используются сплайны более высоких степеней (например, квинтические сплайны пятой степени).

Источники

1. Шёнберг И. Дж. Contributions to the problem of approximation of equidistant data by analytic functions. — Quarterly of Applied Mathematics, 1946.
2. де Бор К. Практическое руководство по сплайнам. — М.: Радио и связь, 1985. — 304 с.
3. Завьялов Ю. С., Квасов Б. И., Мирошниченко В. Л. Методы сплайн-функций. — М.: Наука, 1980. — 352 с.
4. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. — М.: Мир, 1980. — 280 с.
5. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Бином, 2008. — 636 с.