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

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

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

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

Мы хотим смоделировать подобные типы кривых, используя набор математических уравнений. Предположим, у нас есть последовательность $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})$ . ^[2]

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

Мы хотим найти каждый многочлен $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 1) = k 1$ и $q' (x 2) = k 2$ , и также вторые производные

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 \leq x \leq x i$ для i = 1, ..., n , такие, что $q' i (x i) = q' i +1 (x i)$ для i = 1, ..., n − 1, то n полиномов вместе определяют дифференцируемую функцию в интервале $x 0 \leq x \leq 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 0, k 1, ..., 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 0, k 1, ..., 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 0, k 1, ..., k n$ .

Существуют и другие конечные условия: «зажатый сплайн», который задает наклон на концах сплайна, и популярный «сплайн без узла», который требует, чтобы третья производная также была непрерывной в точках $x 1$ и $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 ).

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

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

^ Холл, Чарльз А.; Мейер, Уэстон В. (1976). «Оптимальные границы ошибок для интерполяции кубическими сплайнами» . Журнал теории приближения . 16 (2): 105–122. дои : 10.1016/0021-9045(76)90040-X .
^ Берден, Ричард; Фейрес, Дуглас (2015). Численный анализ (10-е изд.). Cengage Обучение. стр. 142–157. ISBN 9781305253667 .

Дальнейшее чтение [ править ]

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

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

[1] Холл, Чарльз А.; Мейер, Уэстон В. (1976). «Оптимальные границы ошибок для интерполяции кубическими сплайнами» . Журнал теории приближения . 16 (2): 105–122. дои : 10.1016/0021-9045(76)90040-X .

[2] Берден, Ричард; Фейрес, Дуглас (2015). Численный анализ (10-е изд.). Cengage Обучение. стр. 142–157. ISBN 9781305253667 .

[1]

[2]