Сплайн-функции одной переменной

Допустим, что мы хотим построить кривую y=y(x), проходящую через последовательность контрольных точек сетки (x₀,y₀), (x_i,y_i), ..., (x_n,y_n) с x₀<x₁<...<x_n. Точки x₀ и x_n называются граничными узлами сетки, а x_{1 …} x_n-1 - внутренними узлами. Функция S(x), заданная на отрезке [x₀,x_n], называется сплайном степени p, если:

1. на каждом интервале [x_i,x_i+1], i=0,1,n-1, эта функция должна быть многочленом заданной степени p>=2, т.е.

2. S(x) непрерывна и имеет p-1 непрерывных производных на всем интервале [x₀,x_n].

Для задания сплайна на каждом интервале требуется определить (p+1) коэффициентов, всего потребуется n(p+1) чисел. Условия непрерывности функции и ее p-1 производных на всех внутренних (n-1) узлах, дают p(n-1) уравнений, оставшиеся (n(p+1)-p(n-1))=n+p уравнений, необходимых для полного задания сплайна определяются пользователем. Например, можно потребовать, чтобы кривая проходила точно через узлы сетки (интерполяционный сплайн), что дает еще (n+1) уравнений. Оставшиеся (p-1) уравнений можно задать в виде младших производных сплайна на граничных узлах отрезка. Если требуется построить сглаживающую кривую (т.е. проходящую не точно через узлы, а где-то поблизости от них), дополнительные уравнения строят исходя из условий близости, которые можно определять по-разному.

Например, требуется построить интерполирующий кубический сплайн, по 4-м узлам.

Нужно получить 3*4=12 коэффициентов (по 4 на каждый из 3-х интервалов), т.е. 12 составить 12 уравнений. Полиномы в интервалах будут иметь вид:

Условия непрерывности сплайна задаются как:

, для i=0,…,n-2

Условия непрерывности первой производной:

, для i=0,…,n-2

Условия непрерывности второй производной:

, для i=0,…,n-2

Условия прохождения сплайна через узлы сетки:

, для i=0,…,n

Оставшиеся 2 условия можно задать, с помощью первых производных в граничных узлах сетки:

, ,

,

Основные недостатки такого подхода:

• изменение одного из узлов сетки влечет за собой вычисление заново всего сплайна;

• при большом кол-ве узлов приходится решать систему линейных уравнений, большой размерности;

• Требуется большой объем памяти для хранения коэффициентов.

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

B-Сплайны

Чтобы избавиться от первого недостатка применяют B-сплайны (базовые или фундаментальных), кроме того, эти сплайны требуют хранения меньшего кол-ва коэффициентов (n+p-1) вместо n(p+1), что значительно снижает требования к памяти. B-сплайн 0-ой степени это ступенчатая функция.

, для более высоких степеней она вычисляется по рекуррентной функции:

Наиболее часто используются кубические B-сплайны, его функция для сетки с постоянными интервалами h:

, где

Сплайн-функция является суммой B-сплайнов с некоторыми коэффициентами.

n+2 коэффициента вычисляются из системы: