B-spline

B-сплайны.

B-сплайн представляет собой сплайн с минимальным носителем для фиксированной степени сплайна и порядка гладкости. Вся прелесть В-сплайнов состоит в том, что любой сплайн заданной степени и гладкости можно записать в виде линейной комбинации соответствующих B-сплайнов. То есть, В-сплайн представляет собой "кирпичик", с помощью которого можно построить сплайн с заданными свойствами. Этим то и объясняется его термин - базисный сплайн (хотя существует иная конструкция других "кирпичиков" - фундаментальные сплайны, но это уже другая история...).
Далее мы рассмотрим В-сплайны минимального дефекта порядка \(r=0,1,2,3\) (самые популярные).
Введем в рассмотрение функцию (замечу что такого рода конструкции очень популярны, это не только В-сплайны, но и входят в конструкции функций Хаара, Уолша и других) \begin{equation}%\label{eq:(1.59)} B_{0,h}(t)=\cases{1\,\,\,\,\, (|t|\lt h/2),\cr\cr 0\,\,\,\,\, (|t| \ge h/2).} \end{equation}

В-сплайн нулевого порядка.
Функцию \(B_{r,h}(t)\) введем с помощью рекуррентных соотношений \begin{equation}%\label{eq:(1.60)} B_{r,h}(t)=\frac{1}{h}\int_{t-h/2}^{t+h/2}{B_{r-1,h}(x)dx} \,\,\,\,\,\,(r=1,2,\ldots). \end{equation} Эту функцию назовем нормализованным B - сплайном по равномерному разбиению или просто В-сплайном.

В-сплайн первого порядка.
Отметим некоторые свойства В-сплайнов необходимые нам в дальнейшем.
Прежде всего отметим, что В-сплайн порядка \(r\) имеет в качестве носителя (замыкание множества, где он отличен от нуля) промежуток \[d_r=\left[-\frac{r+1}{2}h,\frac{r+1}{2}h\right],\] т.е. \(B_{r,h}(t)\ne 0\) внутри отрезка \(d_r\).
Из вида \(B_{0,h}\) следует, что \begin{equation}%\label{eq:(1.61)} \int_{-\infty}^{\infty}{B_{r,h}(t)dt}= \int_{d_r}{B_{r,h}(t)dt}=h. \end{equation} Нами будут использоваться сплайны порядка 2 и 3, т.е. кубические и параболические сплайны, поэтому уделим внимание В-сплайнам именно такого порядка.
Прежде всего отметим (это легко получить непосредственно из определения В-сплайнов), что \[B_{2,h}(t)=\cases{0.125\left(3-2t/h\right)^2\,\,\,\, \left(t \in\left[h/2,3h/2\right]\right),\cr\cr 0.75-0.25\left(2t/h\right)^2\,\,\,\, \left(t \in\left[-h/2,h/2\right]\right),\cr\cr 0.125\left(3+2t/h\right)^2\,\,\,\, \left(t \in\left[-3h/2,-h/2\right]\right),\cr\cr 0\,\,\,\,\,\,\left(|t| \ge 3h/2\right),}\] и график функции \(B_{2,h}(t)\) имеет вид

В-сплайн второго порядка.
Отсюда следует, что \[B'_{2,h}(t)=\frac{1}{2h}\cases{ -\left( 3-2t/h\right)\,\,\,\,\,\, \left( t\in\left[h/2,3h/2\right]\right),\cr\cr -2t/h\,\,\,\,\,\,\,\,\,\,\,\, \left( t\in\left[-h/2,h/2\right]\right),\cr\cr \left(3+2t/h\right)\,\,\,\,\,\, \left( t\in\left[-3h/2,-h/2\right]\right),\cr\cr 0\,\,\,\,\,\,\,\,\,\,\,\,\,\, \left(|t|\ge 3h/2\right),}\] и графически это выглядит так:

График \(B'_{2,h}(t)\).
Кроме того \[B''_{2,h}=\frac{1}{h^2}\cases{ \,\,1\,\,\,\,\,\,\,(t\in [h/2,3h/2]),\cr\cr -2\,\,\,\,(t\in [-h/2,h/2]),\cr\cr \,\,1\,\,\,\,(t\in [-3h/2,-h/2]),\cr\cr \,\,0\,\,\,\,\,\,\,\,\,\,\,\,\,( |t|\ge 3h/2),}\] что графически выглядит так

График \(B''_{2,h}(t)\).
Отметим теперь некоторые соотношения, следующие из определения В-сплайнов (их легко получить и из выписанных явных формул для В-сплайна второго порядка). \begin{equation}\label{eq:(1.62)} B_{2,h}(0)=\frac{3}{4}\,, \end{equation} \begin{equation}%\label{eq:(1.63)} B_{2,h}\left(\pm\frac{h}{2}\right)=\frac{1}{2}\,, \end{equation} \begin{equation}\label{eq:(1.64)} B_{2,h}\left(\pm h\right)=\frac{1}{8}\,, \end{equation} \begin{equation}%\label{eq:(1.65)} B_{2,h}\left(\pm\frac{kh}{2}\right)=0\,\,\,\,\,\,(|k|>2), \end{equation} \begin{equation}\label{eq:(1.66)} \frac{1}{h}\int_{-h/2}^{h/2}{B_{2,h}(t)dt}=\frac{2}{3}\,, \end{equation} \begin{equation}%\label{eq:(1.67)} \frac{1}{h}\int_{-3h/2}^{-h/2}{B_{2,h}(t)dt}=\frac{1}{6}\,, \end{equation} \begin{equation}%\label{eq:(1.68)} \frac{1}{h}\int_{h/2}^{3h/2}{B_{2,h}(t)dt}=\frac{1}{6}\,, \end{equation} \begin{equation}\label{eq:(1.69)} \frac{1}{h}\int_{(k-1/2)h}^{(k+1/2)h}{B_{2,h}(t)dt}=0\,\,\,\,\,\,(|k|>1). \end{equation} Пусть теперь \(r=3\). Тогда \[B_{3,h}(t)=\frac{1}{48}\cases{\left(4-2t/h\right)^3\,\,\,\,\,\,\,(t\in [h,2h]),\cr\cr 3\left(2t/h\right)^3-12\left(2t/h\right)^2+32\,\,\,\,\,(t\in[0,h]),\cr\cr -3\left(2t/h\right)^3-12\left(2t/h\right)^2+32\,\,\,\,\,(t\in[-h,0]),\cr\cr \left(4+2t/h\right)^3\,\,\,\,\,\,\,\,(t\in[-2h,-h]),\cr\cr 0\,\,\,\,\,\,\,\,\,\,\,\,\,(|t|\ge 2h),}\] и график \(B_{3,h}(t)\) имеет вид

Кубический В-сплайн \(B_{3,h}(t)\).
Отсюда следует, что \[B'_{3,h}(t)=\frac{1}{48h}\cases{-6\left(4-2t/h\right)^2 \,\,\,\,\,\,\,(t\in [h,2h]),\cr\cr 18\left(2t/h\right)^2-48\left(2t/h\right)\,\,\,\,\,(t\in[0,h]),\cr\cr -18\left(2t/h\right)^2-48\left(2t/h\right)\,\,\,\,\,(t\in[-h,0]),\cr\cr 6\left(4+2t/h\right)^2\,\,\,\,\,\,\,\,(t\in[-2h,-h]),\cr\cr 0\,\,\,\,\,\,\,\,\,\,\,\,\,(|t|\ge 2h),} \] На графике это будет выглядеть следующим образом:

График \(B'_{3,h}(t)\).
Кроме того, \[B''_{3,h}(t)=\frac{1}{48h^2}\cases{24 \left(4-2t/h\right) \,\,\,\,\,\,\,(t\in [h,2h]),\cr\cr 144t/h-96\,\,\,\,\,(t\in[0,h]),\cr\cr-144t/h-96\,\,\,\,\,(t\in[-h,0]),\cr\cr 24\left(4+2t/h\right)\,\,\,\,\,\,\,\,(t\in[-2h,-h]),\cr\cr 0\,\,\,\,\,\,\,\,\,\,\,\,\,(|t|\ge 2h),}\] что выглядит так:

График \(B''_{3,h}(t)\).
Кроме того \[B'''_{3,h}(t)=\frac{1}{48h^3}\cases{-48\,\,\,\,\,\,\,(t\in [h,2h]),\cr\cr 144\,\,\,\,\,(t\in[0,h]),\cr\cr -144\,\,\,\,\,(t\in[-h,0]),\cr\cr 48\,\,\,\,\,\,\,\,(t\in[-2h,-h]),\cr\cr 0\,\,\,\,\,\,\,\,\,\,\,\,\,(|t|\ge 2h).} \] и графически:

График \(B'''_{3,h}(t)\).
Выпишем некоторые полезные соотношения для кубического В-сплайна \begin{equation}\label{eq:(1.70)} B_{3,h}(0)=\frac{2}{3}\,, \end{equation} \begin{equation}%\label{eq:(1.71)} B_{3,h}\left(\pm\frac{h}{2}\right)=\frac{23}{48}\,, \end{equation} \begin{equation}%\label{eq:(1.72)} B_{3,h}(\pm h)= \frac{1}{6}\,, \end{equation} \begin{equation}\label{eq:(1.73)} B_{3,h}\left(\pm\frac{3h}{2}\right)=\frac{1}{48}\,, \end{equation} \begin{equation}\label{eq:(1.74)} B_{3,h}\left(\pm\frac{kh}{2}\right)=0\,\,\,\,\,(|k|>3)\,, \end{equation} \begin{equation}%\label{eq:(1.75)} \frac{1}{h}\int_{-h/2}^{h/2}{B_{3,h}(t)dt}=\frac{230}{384}\,, \end{equation} \begin{equation}%\label{eq:(1.76)} \frac{1}{h}\int_{(\pm 1-1/2)h}^{(\pm 1+1/2)h}{B_{3,h}(t)dt}= \frac{76}{384}\,, \end{equation} \begin{equation}%\label{eq:(1.77)} \frac{1}{h}\int_{(\pm 2-1/2)h}^{(\pm 2+1/2)h}{B_{3,h}(t)dt}= \frac{1}{384}\,, \end{equation} \begin{equation}\label{eq:(1.78)} \frac{1}{h}\int_{(k-1/2)h}^{(k+1/2)h}{B_{3,h}(t)dt}=0\,\,\,\,\,(|k|>2). \end{equation}

Сплайны по равномерной решетке

Сплайнами называют кусочно - многочленные функции с однородной структурой. Термин этот произошел от английского слова spline - чертежный инструмент, рейка, используемая для проведения гладкой линии через фиксированные точки.
Наиболее распространенный и исторически наиболее ранний пример сплайна - ломаная.
Сплайны обладают рядом замечательных свойств, которые обеспечили им успех в различных приложениях.
Так, в сравнении с классическими аппаратами приближения функций, сплайны обладают лучшими аппроксимативными свойствами. К примеру, в отличие от интерполяционных многочленов, последовательность интерполяционных сплайнов по равномерной сетке всегда сходится к интерполируемой непрерывной функции. С другой стороны, простота компьютерной реализации сплайновых методов, их высокая эффективность, делают использование сплайнов в инженерных расчетах во многих случаях просто незаменимыми. Кроме того, наличие у сплайнов экстремальных свойств, в частности, то, что интерполяционный сплайн принимает форму материальной кривой с минимальной потенциальной энергией, делают естественным использование сплайнов во многих задачах динамики механических систем.
Сплайном минимального дефекта порядка \(r\) по заданному разбиению \(\Delta_h=\{ih\}_{i=-\infty}^{\infty}\) называется \(r-1\) раз непрерывно - дифференцируемая функция \(s_r(t)\), которая на каждом интервале \((ih,(i+1)h)\) \((i=0,\pm 1,\pm 2,\ldots)\) является многочленом степени не выше \(r\).
Отметим, что на множестве сплайнов порядка \(r\) \((r\ge 0)\) существует сплайн тождественно равный нулю и сплайн тождественно равный единице.
Отсюда и из того, что произведение многочлена степени \(r\) на число \(\alpha\) есть многочлен той же степени, если \(\alpha\ne 0\) и тождественный ноль при \(\alpha=0\), а также из того, что сумма многочленов степени \(n \le r\) и \(m \le r\) есть многочлен степени не выше \(r\), получаем, что множество всех сплайнов степени \(r\) по разбиению \(\Delta_h\) есть линейное пространство.
Таким образом, если \(S_r(\Delta_h)\) множество всех сплайнов минимального дефекта по разбиению \(\Delta_h\), и \[ \sigma_{r,i}\in S_r(\Delta_h)\,\,\,\,\, (i=1,2,\ldots,n), \] то линейная комбинация функций \(\sigma_{r,i}\) также будет лежать в множестве \(S_r(\Delta_h)\), т.е. \begin{equation}%\label{eq:(1.79)} \sum_{i=1}^{n}{c_i\sigma_{r,i}}\in S_r(\Delta_h). \end{equation} Приведем несколько примеров сплайнов. Сплайн нулевого порядка есть кусочно - постоянная функция \[s_0(t)=\alpha_i\,\,\,\,\,\,\, t\in (ih,(i+1)h),\,\,\,\,\,\,\, i=0,\pm1,\pm2,\ldots\]

Сплайн нулевого порядка (кусочно-постоянная).
Для определенности будем считать, что в точках разрыва функция принимает среднее значение, т.е. в этих точках значения будут равны \[B_0(t)=\frac{1}{2}(B_0(t+0)+B_0(t-0)).\] Типичными представителями сплайнов нулевого порядка определенных на всей оси является следующий сплайн, его сдвиги и их линейные комбинации: \begin{equation}\label{eq:(1.80)} s_{0,h}(t)=\sum_{i=-\infty}^{\infty}{c_iB_{0,h}(t-(2i+1)h/2)}. \end{equation} Очевидно также, что сплайн первого порядка есть ломаная с узлами в точках \(ih\)

Сплайн первого порядка (ломаная).
Ясно, что множество всех сплайнов первого порядка это множество всех интегралов (первообразных) от всех сплайнов нулевого порядка. Типичным представителем сплайнов 1-го порядка является В-сплайн 1-го порядка, его сдвиги и их линейные комбинации: \begin{equation}\label{eq:(1.81)} s_{1,h}(t)=\sum_{i=-\infty}^{\infty}{c_iB_{1,h}(t-ih)}. \end{equation} Аналогично, множество всех сплайнов второго порядка - это множество всех интегралов от сплайнов первого порядка

Сплайн второго порядка (параболический сплайн).
Типичным представителем сплайнов 2-го порядка будет параболический В-сплайн (функция "шляпка"), его сдвиги и их линейные комбинации: \begin{equation}\label{eq:(1.82)} s_{2,h}(t)=\sum_{i=-\infty}^{\infty}{c_iB_{2,h}(t-(2i+1)h/2)}. \end{equation} И, соответственно, множество кубических сплайнов - это множество всех интегралов от параболических сплайнов, которые можно записать в виде: \begin{equation}\label{eq:(1.83)} s_{3,h}(t)=\sum_{i=-\infty}^{\infty}{c_iB_{3,h}(t-ih)}. \end{equation} Ясно, что для любых чисел \(c_i\) сужение сплайнов (\ref{eq:(1.81)}) - (\ref{eq:(1.83)}) на отрезок \([0,T]\) (где \(T=nh\)) есть сплайн. Кроме того, при любом конкретном \(t\in (ih,(i+1)h)\) в представлении (\ref{eq:(1.80)}) используется лишь одно слагаемое, в (\ref{eq:(1.81)}) - лишь два слагаемых, в (\ref{eq:(1.82)}) - три, а в (\ref{eq:(1.83)}) - четыре слагаемые. Это позволяет для \(t\in [0,T]\) записать сплайны (\ref{eq:(1.81)}) - (\ref{eq:(1.83)}) в виде: \begin{equation}%\label{eq:(1.84)} s_{2,h}(t)=\sum_{i=-1}^{n}{c_iB_{2,h}(t-(2i+1)h/2)}, \end{equation} \begin{equation}%\label{eq:(1.85)} s_{3,h}(t)=\sum_{i=-1}^{n+1}{c_iB_{3,h}(t-ih)}. \end{equation} Записи такого рода будем называть представлениями сплайнов посредством В-сплайнов.
Для \(t\in [ih,(i+1)h]\) \begin{equation}\label{eq:(1.86)} s_2(t)=s_{2,h}(t)=c_{i-1}B_{2,h}(t-(2i-1)h/2)+ c_iB_{2,h}(t-(2i+1)h/2)+c_{i+1}B_{2,h}(t-(2i+3)h/2) \end{equation} и \begin{equation}\label{eq:(1.87)} s_3(t)=s_{3,h}(t)=c_{i-1}B_{3,h}(t-(i-1)h)+c_iB_{3,h}(t-ih)+c_{i+1}B_{3,h}(t-(i+1)h)+c_{i+2}B_{3,h}(t-(i+2)h). \end{equation} Формы записи (\ref{eq:(1.86)}) - (\ref{eq:(1.87)}) не всегда удобны для практики. Покажем, что при \(t\in [ih,(i+1)h]\) можно использовать иную форму записи: \begin{equation}\label{eq:(1.88)} s_2(t)=\frac{1}{8}(c_{i+1}+6c_i+c_{i-1})+\frac{1}{2h}(c_{i+1}-c_{i-1})(t-ih)+\frac{1}{2h^2}(c_{i+1}-2c_i+c_{i-1})(t-ih)^2 \end{equation} и \begin{equation}\label{eq:(1.89)} s_3(t)=\frac{1}{6}(c_{i+1}+4c_i+c_{i-1})+ \frac{1}{2h}(c_{i+1}-c_{i-1})(t-ih)+\frac{1}{2h^2}(c_{i+1}-2c_i+c_{i-1})(t-ih)^2+\frac{\Delta^2(c_{i+1}-c_{i})}{6h^3}(t-ih)^3. \end{equation} Действительно, из соотношения (\ref{eq:(1.86)}) и свойств параболических В-сплайнов (\ref{eq:(1.62)}) - (\ref{eq:(1.64)}) получаем \begin{equation}%\label{eq:(1.90)} s_2(ih)=\frac{1}{8}(c_{i+1}+6c_i+c_{i-1}), \end{equation} \begin{equation}%\label{eq:(1.91)} s'_2(ih)=\frac{1}{2h}(c_{i-1}-c_{i+1}), \end{equation} \begin{equation}%\label{eq:(1.92)} s''_2(ih)=\frac{1}{h^2}(c_{i+1}-2c_i+c_{i-1}). \end{equation} Отсюда и из формулы Тейлора получаем, что параболический многочлен, удовлетворяющий таким условиям, существует, единствен и при \(t\in [ih,(i+1)h]\) имеет вид \[s_2(t)=s_2(ih)+s'_2(ih)(t-ih)+\frac{1}{2!}s''_2(ih)(t-ih)^2,\] т.е. \[s_2(t)=\frac{c_{i+1}+6c_i+c_{i-1}}{6}+\frac{c_{i+1}-c_{i-1}}{2h}(t-ih)+ \frac{c_{i+1}-2c_i+c_{i-1}}{2h^2}(t-ih)^2.\] Таким образом, мы показали, что для \(t\in[ih,(i+1)h]\) сплайн \(s_2(t)\) имеет вид (\ref{eq:(1.88)}).
Аналогично, из (\ref{eq:(1.87)}) и свойств кубических В-сплайнов (\ref{eq:(1.70)}) - (\ref{eq:(1.73)}), получаем значения сплайна и его производных в узлах: \begin{equation}\label{eq:(1.93)} s_3(ih)=\frac{c_{i+1}+4c_i+c_{i-1}}{6}, \end{equation} \begin{equation}%\label{eq:(1.94)} s'_3(ih)=\frac{c_{i+1}-c_{i-1}}{2h}, \end{equation} \begin{equation}%\label{eq:(1.95)} s''_3(ih)=\frac{c_{i+1}-2c_i+c_{i-1}}{h^2}, \end{equation} \begin{equation}%\label{eq:(1.96)} s_3^{(3)}(ih)=\frac{c_{i+2}-3c_{i+1}+3c_i-c_{i-1}}{h^3}=\frac{\Delta^2(c_{i+1}-c_i)}{h^3}. \end{equation} Отсюда и из формулы Тейлора в точке \(ih\) следует, что кубический многочлен, удовлетворяющий таким условиям, существует, единствен и для \(t\in [ih,(i+1)h]\) имеет вид: \begin{equation}\label{eq:(1.97)} s_3(t)=s_3(ih)+s'_3(ih)(t-ih)+\frac{1}{2!}s''_3(ih)(t-ih)^2+ \frac{1}{3!}s'''_3(ih)(t-ih)^3 =\frac{c_{i+1}+4c_i+c_{i-1}}{6}+ \frac{c_{i+1}-c_{i-1}}{2h}(t-ih)+\frac{c_{i+1}-2c_i+c_{i-1}}{2!h^2}(t-ih)^2+\frac{\Delta^2(c_{i+1}- c_i)}{3!h^3}(t-ih)^3 \end{equation} В некоторых случаях более удобным является использование представления сплайна \(s_3(t)\) на промежутке \([ih,(i+1)h]\) через значения в точках \((i+1/2)h\): \begin{equation}%\label{eq:(1.98)} s_3(t)=\frac{c_{i+1}+c_i}{48}+\frac{23}{24}\left(\frac{c_{i+1}+c_i}{2}\right)+ \left[(c_{i+1}-c_i)+\frac{1}{8}\Delta^2(c_{i+1}-c_i)\right]\left(\frac{t}{h}-i- \frac{1}{2}\right) +\frac{1}{2}\left[\frac{c_{i+2}-c_{i+1}}{2}-\frac{c_{i}-c_{i-1}}{2}\right] \left(\frac{t}{h}-i-\frac{1}{2}\right)^2+\frac{1}{6}\Delta^2(c_{i+1}-c_i)\left(\frac{t}{h}-i- \frac{1}{2}\right)^3. \end{equation}

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

Параболические почти интерполяционные сплайны.

В рассмотренных случаях специально оговаривалось, что рассматриваемые данные являются периодическими. Это условие связано с необходимостью использовать значения, выходящие за множество определения данных. Понятно, что условие периодичности накладывает существенные ограничения. Рассмотрим один из подходов, позволяющих это избежать.
Итак, пусть у нас имеются данные \(x_i=x(ih)\) где \(i=0,...,n\).
Определим коэффициенты \(a\), \(b\) и \(c\) из условия минимума суммы квадратов ошибок \[\Phi(a,b,c)=\sum_{i=0}^{4}{(x_i-p(i))^2},\] где \begin{equation}%\label{eq:(1.53)} p(t)=at^2+bt+c \end{equation} и положим \begin{equation}\label{eq:(1.54)} x_{-1}=p(-1),\,\,\,x_{-2}=p(-2). \end{equation} Необходимые и достаточные условия экстремума имеют вид \[\cases{\partial\Phi/\partial a=0;\cr\cr \partial\Phi/\partial b=0;\cr\cr \partial\Phi/\partial c=0}\] или\[\sum_{i=0}^{4}{p(i)i^2}=\sum_{i=0}^{4}{x_i i^2},\] \[\sum_{i=0}^{4}{p(i)i}=\sum_{i=0}^{4}{x_i i},\] \[\sum_{i=0}^{4}{p(i)}=\sum_{i=0}^{4}{x_i}.\] Решая эту систему, и, подставляя найденные значения \(a\), \(b\), \(c\) в (\ref{eq:(1.54)}), получим \begin{equation}\label{eq:(1.55)} x_{-1}=\frac{1}{70}(126x_0-56x_2-42x_3+42x_4), \end{equation} \begin{equation}%\label{eq:(1.56)} x_{-2}=\frac{1}{35}(105x_0-14x_1-63x_2-42x_3+49x_4). \end{equation} Аналогично находим \begin{equation}%\label{eq:(1.57)} x_{n+1}=\frac{1}{70}(126x_n-56x_{n-2}- 42x_{n-3}+42x_{n-4}), \end{equation} \begin{equation}\label{eq:(1.58)} x_{n+2}=\frac{1}{35}(105x_n-14x_{n-1}-63x_{n-2}- 42x_{n-3}+49x_{n-4}). \end{equation}