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

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

Введение [ править ]

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

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

Мы хотим смоделировать подобные типы кривых, используя набор математических уравнений, с одним многочленом для каждой пары узлов и , где . Итак, будут многочлены и узлы: первый многочлен начинается в , а последний многочлен заканчивается в .${\ Displaystyle у = q_ {я} (х)}$${\ Displaystyle (х_ {я-1}, у_ {я-1})}$${\ Displaystyle (х_ {я}, у_ {я})}$${\ Displaystyle я = 1,2, \ cdots, п}$${\ displaystyle n}$${\ displaystyle n + 1}$${\ displaystyle (x_ {0}, y_ {0})}$${\ displaystyle (x_ {n}, y_ {n})}$

Кривизны любой кривой определяется следующим образом:${\displaystyle y=f(x)}$

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

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

${\displaystyle {\begin{cases}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 - кубических сплайнов .

Алгоритм поиска интерполирующего кубического сплайна [ править ]

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

${\displaystyle q(x_{1})=y_{1}}$

${\displaystyle q(x_{2})=y_{2}}$

${\displaystyle q'(x_{1})=k_{1}}$

${\displaystyle q'(x_{2})=k_{2}}$

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

${\displaystyle 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 )

куда

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

( 2 )

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

( 3 )

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

( 4 )

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

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

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

${\displaystyle 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 )

${\displaystyle 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 _2, а также вторые производные

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

( 7 )

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

( 8 )

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

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

( 9 )

где i = 1, 2, ..., n и - 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 ₀ ≤${\displaystyle t={\tfrac {x-x_{i-1}}{x_{i}-x_{i-1}}}}$x ≤ x _n и

${\displaystyle a_{i}=k_{i-1}(x_{i}-x_{i-1})-(y_{i}-y_{i-1})}$

( 10 )

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

( 11 )

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

${\displaystyle k_{0}=q_{1}'(x_{0})}$

( 12 )

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

( 13 )

${\displaystyle 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 ) следует, что это так тогда и только тогда, когда

${\displaystyle {\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 ) должно иметь

${\displaystyle 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,}$

${\displaystyle 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,}$

т.е. что

${\displaystyle {\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 )

${\displaystyle {\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} балл. Дополнительные уравнения для сплайна «без узла» будут выглядеть так:

${\displaystyle 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)}$

${\displaystyle 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)}$

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

Пример [ править ]

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

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

${\displaystyle {\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}}}$

с

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

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

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

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

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

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

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

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

${\displaystyle 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)}$

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

По трем точкам

${\displaystyle (-1,0.5)\ ,\ (0,0)\ ,\ (3,3)}$,

каждый получает это

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

а из ( 10 ) и ( 11 ) следует, что

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

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

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

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

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

См. Также [ править ]

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

Компьютерный код [ править ]

TinySpline: C-библиотека с открытым исходным кодом для сплайнов, которая реализует интерполяцию кубических сплайнов.

SciPy Spline Interpolation: пакет Python, реализующий интерполяцию

Кубическая интерполяция: библиотека C # с открытым исходным кодом для кубической сплайн-интерполяции

Ссылки [ править ]

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

Внешние ссылки [ править ]

• Инструмент онлайн-расчета и визуализации интерполяции кубических сплайнов (с исходным кодом JavaScript)
• "Сплайн-интерполяция" , Математическая энциклопедия , EMS Press , 2001 [1994]
• Динамические кубические сплайны с JSXGraph
• Лекции по теории и практике сплайн-интерполяции
• Документ, в котором шаг за шагом объясняется, как выполняется интерполяция кубическим сплайном, но только для равноудаленных узлов.
• Цифровые рецепты на языке C, перейдите к главе 3, раздел 3-3
• Замечание о кубических шлицах
• Информация о сплайн-интерполяции (включая код в Fortran 77)