Сплайн-интерполяция

Для более широкого освещения этой темы см. Сплайн (математика) .

В математической области анализа численного сплайн-интерполяция — это форма интерполяции , где интерполянтом является особый тип кусочного полинома, называемый сплайном . То есть вместо того, чтобы подгонять один полином высокой степени ко всем значениям одновременно, сплайн-интерполяция подгоняет полиномы низкой степени к небольшим подмножествам значений, например, подгоняя девять кубических полиномов между каждой из пар по десять точек. , вместо того, чтобы подгонять под них один полином девятой степени. Сплайн-интерполяция часто предпочтительнее полиномиальной интерполяции , поскольку ошибку интерполяции можно сделать небольшой даже при использовании для сплайна полиномов низкой степени. Сплайн-интерполяция также позволяет избежать проблемы феномена Рунге , при котором между точками могут возникать колебания при интерполяции с использованием полиномов высокой степени.

Введение

Интерполяция кубическими сплайнами между восемью точками. Нарисованные от руки технические чертежи для судостроения являются историческим примером сплайн-интерполяции; рисунки были построены с использованием гибких линеек, которые изгибались по заранее определенным точкам.

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

Мы хотим смоделировать подобные типы кривых, используя набор математических уравнений. Предположим, у нас есть последовательность $n+1$ узлы, $(x_{0},y_{0})$ через $(x_{n},y_{n})$. Будет кубический многочлен $q_{i}(x)=y$ между каждой последующей парой узлов $(x_{i-1},y_{i-1})$ и $(x_{i},y_{i})$ подключение к ним обоим, где $i=1,2,\dots ,n$. Так что будет $n$ полиномы, причем первый полином начинается с $(x_{0},y_{0})$, и последний многочлен, заканчивающийся на $(x_{n},y_{n})$.

Кривизна любой кривой $y=y(x)$ определяется как

$\kappa ={\frac {y''}{(1+y'^{2})^{3/2}}},$

где $y'$ и $y''$ являются первой и второй производными $y(x)$ относительно $x$.Чтобы сплайн принял форму, минимизирующую изгиб (при условии прохождения через все узлы), определим как $y'$ и $y''$ быть непрерывным всюду, в том числе и в узлах. Каждый последующий полином должен иметь равные значения (которые равны значению y соответствующей точки данных), производные и вторые производные в их соединяющих узлах, то есть, что

${\begin{cases}q_{i}(x_{i})=q_{i+1}(x_{i})=y_{i}\\q'_{i}(x_{i})=q'_{i+1}(x_{i})\\q''_{i}(x_{i})=q''_{i+1}(x_{i})\end{cases}}\qquad 1\leq i\leq n-1.$

Этого можно достичь только в том случае, если используются полиномы степени 3 (кубические полиномы) или выше. Классический подход заключается в использовании полиномов ровно 3-й степени — кубических сплайнов .

В дополнение к трем условиям, указанным выше, « натуральный кубический сплайн » имеет условие, при котором $q''_{1}(x_{0})=q''_{n}(x_{n})=0$.

В дополнение к трем основным условиям, указанным выше, « зажатый кубический сплайн » имеет условия, при которых $q'_{1}(x_{0})=f'(x_{0})$ и $q'_{n}(x_{n})=f'(x_{n})$ где $f'(x)$ является производной интерполированной функции.

В дополнение к трем основным условиям, указанным выше, « сплайн без узлов » имеет условия, при которых $q'''_{1}(x_{1})=q'''_{2}(x_{1})$ и $q'''_{n-1}(x_{n-1})=q'''_{n}(x_{n-1})$.

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

Мы хотим найти каждый многочлен $q_{i}(x)$ учитывая баллы $(x_{0},y_{0})$ через $(x_{n},y_{n})$. Для этого рассмотрим только один участок кривой, $q(x)$, который будет интерполировать из $(x_{1},y_{1})$ к $(x_{2},y_{2})$. Эта часть будет иметь наклоны $k_{1}$ и $k_{2}$ в его конечных точках. Или, точнее,

$q(x_{1})=y_{1},$

$q(x_{2})=y_{2},$

$q'(x_{1})=k_{1},$

$q'(x_{2})=k_{2}.$

Полное уравнение $q(x)$ можно записать в симметричной форме

$q(x)={\big (}1-t(x){\big )}\,y_{1}+t(x)\,y_{2}+t(x){\big (}1-t(x){\big )}{\Big (}{\big (}1-t(x){\big )}\,a+t(x)\,b{\Big )},$ ( 1 )

где

$t(x)={\frac {x-x_{1}}{x_{2}-x_{1}}},$ ( 2 )

$a=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1}),$ ( 3 )

$b=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1}).$ ( 4 )

Но что такое $k_{1}$ и $k_{2}$? Чтобы получить эти критические значения, мы должны учитывать, что

$q'={\frac {dq}{dx}}={\frac {dq}{dt}}{\frac {dt}{dx}}={\frac {dq}{dt}}{\frac {1}{x_{2}-x_{1}}}.$

Отсюда следует, что

$q'={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}+(1-2t){\frac {a(1-t)+bt}{x_{2}-x_{1}}}+t(1-t){\frac {b-a}{x_{2}-x_{1}}},$ ( 5 )

$q''=2{\frac {b-2a+(a-b)3t}{{(x_{2}-x_{1})}^{2}}}.$ ( 6 )

Полагая t = 0 и t = 1 соответственно в уравнениях ( 5 ) и ( 6 ) получаем ), из ( 2 , что действительно первые производные q' ( x ₁ ) = k ₁ и q' ( x ₂ ) = k ₂ , и также вторые производные

$q''(x_{1})=2{\frac {b-2a}{{(x_{2}-x_{1})}^{2}}},$ ( 7 )

$q''(x_{2})=2{\frac {a-2b}{{(x_{2}-x_{1})}^{2}}}.$ ( 8 )

Если теперь ( x _i , y _i ), i = 0, 1, ..., n — это n + 1 точек, и

$q_{i}=(1-t)\,y_{i-1}+t\,y_{i}+t(1-t){\big (}(1-t)\,a_{i}+t\,b_{i}{\big )},$ ( 9 )

где я = 1, 2, ..., n и $t={\tfrac {x-x_{i-1}}{x_{i}-x_{i-1}}}$ — это n полиномов третьей степени, интерполирующие y в интервале x _{i −1} ≤ x ≤ x _i для i = 1, ..., n такие, что q′ _i ( x _i ) = q′ _{i +1} ( x _i ) для i = 1, ..., n − 1, то n полиномов вместе определяют дифференцируемую функцию в интервале x ₀ ≤ x ≤ x _n , и

$a_{i}=k_{i-1}(x_{i}-x_{i-1})-(y_{i}-y_{i-1}),$ ( 10 )

$b_{i}=-k_{i}(x_{i}-x_{i-1})+(y_{i}-y_{i-1})$ ( 11 )

для i = 1,..., n , где

$k_{0}=q_{1}'(x_{0}),$ ( 12 )

$k_{i}=q_{i}'(x_{i})=q_{i+1}'(x_{i}),\qquad i=1,\dots ,n-1,$ ( 13 )

$k_{n}=q_{n}'(x_{n}).$ ( 14 )

Если последовательность k ₀ , k ₁ , ..., k _n такова, что, кроме того, q′′ _i ( x _i ) = q′′ _{i +1} ( x _i ) выполняется для i = 1, ... , n − 1, то результирующая функция будет даже иметь непрерывную вторую производную.

Из ( 7 ), ( 8 ), ( 10 ) и ( 11 ) следует, что это так тогда и только тогда, когда

${\frac {k_{i-1}}{x_{i}-x_{i-1}}}+\left({\frac {1}{x_{i}-x_{i-1}}}+{\frac {1}{x_{i+1}-x_{i}}}\right)2k_{i}+{\frac {k_{i+1}}{x_{i+1}-x_{i}}}=3\left({\frac {y_{i}-y_{i-1}}{{(x_{i}-x_{i-1})}^{2}}}+{\frac {y_{i+1}-y_{i}}{{(x_{i+1}-x_{i})}^{2}}}\right)$ ( 15 )

для i = 1, ..., n − 1. Соотношения ( 15 ) представляют собой n − 1 линейных уравнений для n + 1 значений k ₀ , k ₁ , ..., k _n .

Для упругих линеек, являющихся моделью сплайн-интерполяции, получается, что слева от крайнего левого «узла» и справа от крайнего правого «узла» линейка может свободно перемещаться и поэтому примет форму прямая линия с q′′ = 0 . Поскольку q′′ должно быть непрерывной функцией x , «естественные сплайны» в дополнение к n − 1 линейным уравнениям ( 15 ) должны иметь

$q''_{1}(x_{0})=2{\frac {3(y_{1}-y_{0})-(k_{1}+2k_{0})(x_{1}-x_{0})}{{(x_{1}-x_{0})}^{2}}}=0,$

$q''_{n}(x_{n})=-2{\frac {3(y_{n}-y_{n-1})-(2k_{n}+k_{n-1})(x_{n}-x_{n-1})}{{(x_{n}-x_{n-1})}^{2}}}=0,$

то есть это

${\frac {2}{x_{1}-x_{0}}}k_{0}+{\frac {1}{x_{1}-x_{0}}}k_{1}=3{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}},$ ( 16 )

${\frac {1}{x_{n}-x_{n-1}}}k_{n-1}+{\frac {2}{x_{n}-x_{n-1}}}k_{n}=3{\frac {y_{n}-y_{n-1}}{(x_{n}-x_{n-1})^{2}}}.$ ( 17 )

В итоге ( 15 ) вместе с ( 16 ) и ( 17 ) составляют n + 1 линейные уравнения, однозначно определяющие n + 1 параметров k ₀ , k ₁ , ..., k _n .

Существуют и другие конечные условия: «зажатый сплайн», который определяет наклон на концах сплайна, и популярный «сплайн без узла», который требует, чтобы третья производная также была непрерывной в точках x ₁ и x _{n. −1} балл.Для сплайна «без узла» дополнительные уравнения будут выглядеть следующим образом:

$q'''_{1}(x_{1})=q'''_{2}(x_{1})\Rightarrow {\frac {1}{\Delta x_{1}^{2}}}k_{0}+\left({\frac {1}{\Delta x_{1}^{2}}}-{\frac {1}{\Delta x_{2}^{2}}}\right)k_{1}-{\frac {1}{\Delta x_{2}^{2}}}k_{2}=2\left({\frac {\Delta y_{1}}{\Delta x_{1}^{3}}}-{\frac {\Delta y_{2}}{\Delta x_{2}^{3}}}\right),$

$q'''_{n-1}(x_{n-1})=q'''_{n}(x_{n-1})\Rightarrow {\frac {1}{\Delta x_{n-1}^{2}}}k_{n-2}+\left({\frac {1}{\Delta x_{n-1}^{2}}}-{\frac {1}{\Delta x_{n}^{2}}}\right)k_{n-1}-{\frac {1}{\Delta x_{n}^{2}}}k_{n}=2\left({\frac {\Delta y_{n-1}}{\Delta x_{n-1}^{3}}}-{\frac {\Delta y_{n}}{\Delta x_{n}^{3}}}\right),$

где $\Delta x_{i}=x_{i}-x_{i-1},\ \Delta y_{i}=y_{i}-y_{i-1}$.

Пример

Интерполяция кубическими «естественными» сплайнами между тремя точками

В случае трех точек значения для $k_{0},k_{1},k_{2}$ находятся путем решения системы трехдиагональных линейных уравнений

${\begin{bmatrix}a_{11}&a_{12}&0\\a_{21}&a_{22}&a_{23}\\0&a_{32}&a_{33}\\\end{bmatrix}}{\begin{bmatrix}k_{0}\\k_{1}\\k_{2}\\\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\b_{3}\\\end{bmatrix}}$

с

$a_{11}={\frac {2}{x_{1}-x_{0}}},$

$a_{12}={\frac {1}{x_{1}-x_{0}}},$

$a_{21}={\frac {1}{x_{1}-x_{0}}},$

$a_{22}=2\left({\frac {1}{x_{1}-x_{0}}}+{\frac {1}{x_{2}-x_{1}}}\right),$

$a_{23}={\frac {1}{x_{2}-x_{1}}},$

$a_{32}={\frac {1}{x_{2}-x_{1}}},$

$a_{33}={\frac {2}{x_{2}-x_{1}}},$

$b_{1}=3{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}},$

$b_{2}=3\left({\frac {y_{1}-y_{0}}{{(x_{1}-x_{0})}^{2}}}+{\frac {y_{2}-y_{1}}{{(x_{2}-x_{1})}^{2}}}\right),$

$b_{3}=3{\frac {y_{2}-y_{1}}{(x_{2}-x_{1})^{2}}}.$

За три балла

$(-1,0.5),\ (0,0),\ (3,3),$

это понятно

$k_{0}=-0.6875,\ k_{1}=-0.1250,\ k_{2}=1.5625,$

и из ( 10 ) и ( 11 ) то

$a_{1}=k_{0}(x_{1}-x_{0})-(y_{1}-y_{0})=-0.1875,$

$b_{1}=-k_{1}(x_{1}-x_{0})+(y_{1}-y_{0})=-0.3750,$

$a_{2}=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1})=-3.3750,$

$b_{2}=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1})=-1.6875.$

На рисунке сплайн-функция, состоящая из двух кубических многочленов $q_{1}(x)$ и $q_{2}(x)$ заданное ( 9 ).

См. также

• Акима сплайн
• Круговая интерполяция
• Кубический сплайн Эрмита
• Центростремительный сплайн Катмулла – Рома
• Дискретная сплайн-интерполяция
• Монотонная кубическая интерполяция
• Неравномерный рациональный B-сплайн
• Многомерная интерполяция
• Полиномиальная интерполяция
• Сглаживающий сплайн
• Сплайновый вейвлет
• Тонкая пластина шлица
• Полигармонический сплайн

Дальнейшее чтение

• Шенберг, Исаак Дж. (1946). «Вклад в проблему аппроксимации эквидистантных данных аналитическими функциями: Часть A. - К проблеме сглаживания или градуировки. Первый класс формул аналитического приближения» . Ежеквартальный журнал прикладной математики . 4 (2): 45–99. дои : 10.1090/qam/15914 .
• Шенберг, Исаак Дж. (1946). «Вклад в проблему аппроксимации эквидистантных данных аналитическими функциями: Часть B. - К проблеме оскуляторной интерполяции. Второй класс формул аналитического приближения» . Ежеквартальный журнал прикладной математики . 4 (2): 112–141. дои : 10.1090/qam/16705 .

Внешние ссылки

• Инструмент онлайн-расчета и визуализации интерполяции кубическими сплайнами (с исходным кодом JavaScript)
• «Сплайн-интерполяция» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Динамические кубические сплайны с JSXGraph
• Лекции по теории и практике сплайн-интерполяции
• Статья, в которой шаг за шагом объясняется, как выполняется интерполяция кубическими сплайнами, но только для равноудаленных узлов.
• Численные рецепты на языке C, перейдите к главе 3, раздел 3-3.
• Примечание о кубических сплайнах
• Информация о сплайн-интерполяции (включая код на Фортране 77)
• TinySpline: C-библиотека с открытым исходным кодом для сплайнов, реализующая интерполяцию кубическими сплайнами.
• SciPy Spline Interpolation: пакет Python, реализующий интерполяцию.
• Кубическая интерполяция: C#-библиотека с открытым исходным кодом для интерполяции кубическими сплайнами.