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

Математический метод

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

Введение

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

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

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

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

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

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

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

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

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

В дополнение к трем основным условиям, указанным выше, « неузловой сплайн » имеет следующие условия: и . ^[2] ${\displaystyle q'''_{1}(x_{1})=q'''_{2}(x_{1})}$ ${\displaystyle q'''_{n-1}(x_{n-1})=q'''_{n}(x_{n-1})}$

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

Мы хотим найти каждый многочлен, учитывая точки через . Для этого мы рассмотрим только один кусок кривой, , который будет интерполироваться от до . Этот кусок будет иметь наклоны и в своих конечных точках. Или, точнее, ${\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 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}}}.}$

Из этого следует, что

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

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

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

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

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

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

для 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,}$

то есть это

В конечном итоге ( 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}}$

Пример

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

В случае трех точек значения находятся путем решения трехдиагональной системы линейных уравнений ${\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.}$

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

Смотрите также

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

Ссылки

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

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

• Шенберг, Айзек Дж. (1946). «Вклад в проблему аппроксимации равноотстоящих данных аналитическими функциями: Часть A. — О проблеме сглаживания или градуировки. Первый класс аналитических формул аппроксимации». Quarterly of Applied Mathematics . 4 (2): 45–99. doi : 10.1090/qam/15914 .
• Шенберг, Айзек Дж. (1946). «Вклад в проблему аппроксимации равноотстоящих данных аналитическими функциями: Часть B. — О проблеме оскуляторной интерполяции. Второй класс аналитических формул аппроксимации». Quarterly of Applied Mathematics . 4 (2): 112–141. doi : 10.1090/qam/16705 .

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

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