Кубический сплайн Эрмита

Кубическая функция, используемая для интерполяции

В численном анализе кубический сплайн Эрмита или кубический интерполятор Эрмита представляет собой сплайн , где каждая часть представляет собой полином третьей степени, заданный в форме Эрмита , то есть его значениями и первыми производными в конечных точках соответствующего интервала области значений . ^[1]

Кубические сплайны Эрмита обычно используются для интерполяции числовых данных, заданных при заданных значениях аргументов , для получения непрерывной функции . Данные должны состоять из желаемого значения функции и производной для каждого . (Если указаны только значения, производные необходимо оценить по ним.) Формула Эрмита применяется к каждому интервалу отдельно. Полученный сплайн будет непрерывным и будет иметь непрерывную первую производную. ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ ${\displaystyle x_{k}}$ ${\displaystyle (x_{k},x_{k+1})}$

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

Кубические полиномиальные сплайны широко используются в компьютерной графике и геометрическом моделировании для получения кривых или траекторий движения , проходящих через заданные точки плоскости или трехмерного пространства . В этих приложениях каждая координата плоскости или пространства отдельно интерполируется кубической сплайн-функцией отдельного параметра  t . Кубические полиномиальные сплайны также широко используются в приложениях структурного анализа, таких как теория балок Эйлера – Бернулли . Кубические полиномиальные сплайны также применялись для анализа смертности ^[2] и прогнозирования смертности. ^[3]

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

Кубические сплайны часто называют csplines , особенно в компьютерной графике. Сплайны Эрмита названы в честь Чарльза Эрмита .

Интерполяция на одном интервале

Единичный интервал [0, 1]

Четыре базисные функции Эрмита. Интерполянт в каждом подинтервале представляет собой линейную комбинацию этих четырех функций.

На единичном интервале , учитывая начальную точку в и конечную точку в с начальной касательной в и конечной касательной в , полином может быть определен формулой ${\displaystyle [0,1]}$ ${\displaystyle {\boldsymbol {p}}_{0}}$ ${\displaystyle t=0}$ ${\displaystyle {\boldsymbol {p}}_{1}}$ ${\displaystyle t=1}$ ${\displaystyle {\boldsymbol {m}}_{0}}$ ${\displaystyle t=0}$ ${\displaystyle {\boldsymbol {m}}_{1}}$ ${\displaystyle t=1}$

$${\displaystyle {\boldsymbol {p}}(t)=\left(2t^{3}-3t^{2}+1\right){\boldsymbol {p}}_{0}+\left(t^{3}-2t^{2}+t\right){\boldsymbol {m}}_{0}+\left(-2t^{3}+3t^{2}\right){\boldsymbol {p}}_{1}+\left(t^{3}-t^{2}\right){\boldsymbol {m}}_{1},}$$

t

Интерполяция на произвольном интервале

Интерполяция в произвольном интервале осуществляется путем сопоставления последнего с помощью аффинной (степени-1) замены переменной. Формула ${\displaystyle x}$ ${\displaystyle (x_{k},x_{k+1})}$ ${\displaystyle [0,1]}$

$${\displaystyle {\boldsymbol {p}}(x)=h_{00}(t){\boldsymbol {p}}_{k}+h_{10}(t)(x_{k+1}-x_{k}){\boldsymbol {m}}_{k}+h_{01}(t){\boldsymbol {p}}_{k+1}+h_{11}(t)(x_{k+1}-x_{k}){\boldsymbol {m}}_{k+1},}$$

${\displaystyle t=(x-x_{k})/(x_{k+1}-x_{k})}$ ${\displaystyle h}$ ${\displaystyle x_{k+1}-x_{k}}$

Уникальность

Указанная выше формула обеспечивает уникальный полиномиальный путь третьей степени между двумя точками с заданными касательными.

Доказательство. Пусть – два полинома третьей степени, удовлетворяющие заданным граничным условиям. Определите тогда: ${\displaystyle P,Q}$ ${\displaystyle R=Q-P,}$

${\displaystyle R(0)=Q(0)-P(0)=0,}$

${\displaystyle R(1)=Q(1)-P(1)=0.}$

Поскольку оба и являются полиномами третьей степени, это не более чем полином третьей степени. Так что должно быть в форме ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle R}$

$${\displaystyle R(x)=ax(x-1)(x-r).}$$

$${\displaystyle R'(x)=ax(x-1)+ax(x-r)+a(x-1)(x-r).}$$

Мы знаем, кроме того, что

${\displaystyle R'(0)=Q'(0)-P'(0)=0,}$

${\displaystyle R'(1)=Q'(1)-P'(1)=0,}$

Сложив ( 1 ) и ( 2 ) вместе, мы получаем, что и, следовательно, таким образом ${\displaystyle a=0}$ ${\displaystyle R=0,}$ ${\displaystyle P=Q.}$

Представительства

Мы можем записать интерполяционный полином как

$${\displaystyle {\boldsymbol {p}}(t)=h_{00}(t){\boldsymbol {p}}_{0}+h_{10}(t)(x_{k+1}-x_{k}){\boldsymbol {m}}_{0}+h_{01}(t){\boldsymbol {p}}_{1}+h_{11}(t)(x_{k+1}-x_{k}){\boldsymbol {m}}_{1}}$$

${\displaystyle h_{00}}$ ${\displaystyle h_{10}}$ ${\displaystyle h_{01}}$ ${\displaystyle h_{11}}$

В «развернутом» столбце показано представление, использованное в приведенном выше определении. Столбец «факторизованный» сразу показывает это и на границах равны нулю. Далее вы можете заключить, что и имеют ноль кратности 2 в 0, и имеют такой ноль в 1, поэтому на этих границах они имеют наклон 0. В столбце «Бернштейн» показано разложение базисных функций Эрмита на полиномы Бернштейна третьего порядка: ${\displaystyle h_{10}}$ ${\displaystyle h_{11}}$ ${\displaystyle h_{01}}$ ${\displaystyle h_{11}}$ ${\displaystyle h_{00}}$ ${\displaystyle h_{10}}$

$${\displaystyle B_{k}(t)={\binom {3}{k}}\cdot t^{k}\cdot (1-t)^{3-k}.}$$

Используя эту связь, вы можете выразить кубическую интерполяцию Эрмита через кубические кривые Безье относительно четырех значений и выполнить интерполяцию Эрмита с использованием алгоритма де Кастельжо . Он показывает, что в кубическом патче Безье две контрольные точки в середине определяют касательные интерполяционной кривой в соответствующих внешних точках. ${\textstyle {\boldsymbol {p}}_{0},{\boldsymbol {p}}_{0}+{\frac {1}{3}}{\boldsymbol {m}}_{0},{\boldsymbol {p}}_{1}-{\frac {1}{3}}{\boldsymbol {m}}_{1},{\boldsymbol {p}}_{1}}$

Мы также можем записать полином в стандартной форме как

$${\displaystyle {\boldsymbol {p}}(t)=\left(2{\boldsymbol {p}}_{0}+{\boldsymbol {m}}_{0}-2{\boldsymbol {p}}_{1}+{\boldsymbol {m}}_{1}\right)t^{3}+\left(-3{\boldsymbol {p}}_{0}+3{\boldsymbol {p}}_{1}-2{\boldsymbol {m}}_{0}-{\boldsymbol {m}}_{1}\right)t^{2}+{\boldsymbol {m}}_{0}t+{\boldsymbol {p}}_{0}}$$

t

Интерполяция набора данных

Набор данных для можно интерполировать, применив описанную выше процедуру к каждому интервалу, где касательные выбираются разумным образом, что означает, что касательные для интервалов, имеющих общие конечные точки, равны. Интерполированная кривая тогда состоит из кусочно-кубических сплайнов Эрмита и глобально непрерывно дифференцируема по . ${\displaystyle (x_{k},{\boldsymbol {p}}_{k})}$ ${\displaystyle k=1,\ldots ,n}$ ${\displaystyle (x_{1},x_{n})}$

Выбор касательных не уникален, доступно несколько вариантов.

Конечная разница

Пример с касательными в конечной разности

Самый простой выбор — разница в три пункта, не требующая постоянной длины интервала:

${\displaystyle {\boldsymbol {m}}_{k}={\frac {1}{2}}\left({\frac {{\boldsymbol {p}}_{k+1}-{\boldsymbol {p}}_{k}}{x_{k+1}-x_{k}}}+{\frac {{\boldsymbol {p}}_{k}-{\boldsymbol {p}}_{k-1}}{x_{k}-x_{k-1}}}\right)}$

для внутренних точек и односторонняя разница в конечных точках набора данных. ${\displaystyle k=2,\dots ,n-1}$

Кардинальный сплайн

Пример кардинального сплайна в 2D. Линия представляет собой кривую, а квадраты представляют собой контрольные точки . Обратите внимание, что кривая не достигает первой и последней точек; однако эти точки влияют на форму кривой. Используемый параметр натяжения составляет 0,1. ${\displaystyle {\boldsymbol {p}}_{k}}$

Кардинальный сплайн , иногда называемый каноническим сплайном , ^[4] получается ^[5], если

${\displaystyle {\boldsymbol {m}}_{k}=(1-c){\frac {{\boldsymbol {p}}_{k+1}-{\boldsymbol {p}}_{k-1}}{x_{k+1}-x_{k-1}}}}$

используется для вычисления тангенсов. Параметр c — это параметр натяжения , который должен находиться в интервале [0, 1] . В каком-то смысле это можно интерпретировать как «длину» касательной. Выбор c  = 1 дает все нулевые касательные, а выбор c  = 0 дает сплайн Катмулла – Рома в случае равномерной параметризации.

Сплайн Катмулла – Рома

Геометрическая интерпретация кубической интерполяции Катмулла – Рома черной точки с равномерно расположенными абсциссами. ^[6]

Для касательных, выбранных в качестве

${\displaystyle {\boldsymbol {m}}_{k}={\frac {{\boldsymbol {p}}_{k+1}-{\boldsymbol {p}}_{k-1}}{2}}}$

получен сплайн Катмулла–Рома, являющийся частным случаем кардинального сплайна . Это предполагает равномерное расстояние между параметрами.

Кривая названа в честь Эдвина Кэтмелла и Рафаэля Рома . Основное преимущество этого метода заключается в том, что точки исходного набора точек также являются контрольными точками сплайновой кривой. ^[7] На каждом конце кривой требуются две дополнительные точки. Единая реализация Catmull-Rom может создавать циклы и самопересечения. Хордальная и центростремительная реализации Катмулла-Рома ^[8] решают эту проблему, но используют немного другой расчет. ^[9] В компьютерной графике сплайны Катмулла-Рома часто используются для получения плавного интерполированного движения между ключевыми кадрами . Например, большинство анимаций траектории камеры, созданных на основе отдельных ключевых кадров, обрабатываются с помощью сплайнов Catmull-Rom. Они популярны главным образом потому, что их относительно легко вычислить, они гарантируют точное попадание в каждую позицию ключевого кадра, а также гарантируют, что касательные сгенерированной кривой непрерывны на нескольких сегментах.

Сплайн Кочанека – Бартельса

Сплайн Кочанека-Бартельса представляет собой дальнейшее обобщение того , как выбирать касательные с учетом точек данных и с тремя возможными параметрами: натяжением, смещением и параметром непрерывности. ${\displaystyle {\boldsymbol {p}}_{k-1}}$ ${\displaystyle {\boldsymbol {p}}_{k}}$ ${\displaystyle {\boldsymbol {p}}_{k+1}}$

Монотонная кубическая интерполяция

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

Интерполяция на единичном интервале с совпадающими производными в конечных точках

Рассмотрим одну координату точек и как значения, которые функция f ( x ) принимает в целочисленных ординатах x  = n  - 1, n , n  + 1 и n  + 2, ${\displaystyle {\boldsymbol {p}}_{n-1},{\boldsymbol {p}}_{n},{\boldsymbol {p}}_{n+1}}$ ${\displaystyle {\boldsymbol {p}}_{n+2}}$

${\displaystyle p_{n}=f(n)\quad \forall n\in \mathbb {Z} .}$

Кроме того, предположим, что касательные в конечных точках определяются как центрированные разности соседних точек:

$${\displaystyle m_{n}={\frac {f(n+1)-f(n-1)}{2}}={\frac {p_{n+1}-p_{n-1}}{2}}\quad \forall n\in \mathbb {Z} .}$$

Чтобы оценить интерполированное значение f ( x ) для действительного x , сначала разделите x на целую часть n и дробную часть u :

${\displaystyle x=n+u,}$

${\displaystyle n=\lfloor x\rfloor =\operatorname {floor} (x),}$

${\displaystyle u=x-n=x-\lfloor x\rfloor ,}$

${\displaystyle 0\leq u<1,}$

где обозначает функцию пола , которая возвращает наибольшее целое число, не превышающее x . ${\displaystyle \lfloor x\rfloor }$

Тогда сплайн Катмулла–Рома равен ^[10]

$${\displaystyle {\begin{aligned}f(x)=f(n+u)&={\text{CINT}}_{u}(p_{n-1},p_{n},p_{n+1},p_{n+2})\\&={\begin{bmatrix}1&u&u^{2}&u^{3}\end{bmatrix}}{\begin{bmatrix}0&1&0&0\\-{\tfrac {1}{2}}&0&{\tfrac {1}{2}}&0\\1&-{\tfrac {5}{2}}&2&-{\tfrac {1}{2}}\\-{\tfrac {1}{2}}&{\tfrac {3}{2}}&-{\tfrac {3}{2}}&{\tfrac {1}{2}}\end{bmatrix}}{\begin{bmatrix}p_{n-1}\\p_{n}\\p_{n+1}\\p_{n+2}\end{bmatrix}}\\&={\frac {1}{2}}{\begin{bmatrix}-u^{3}+2u^{2}-u\\3u^{3}-5u^{2}+2\\-3u^{3}+4u^{2}+u\\u^{3}-u^{2}\end{bmatrix}}^{\mathrm {T} }{\begin{bmatrix}p_{n-1}\\p_{n}\\p_{n+1}\\p_{n+2}\end{bmatrix}}\\&={\frac {1}{2}}{\begin{bmatrix}u{\big (}(2-u)u-1{\big )}\\u^{2}(3u-5)+2\\u{\big (}(4-3u)u+1{\big )}\\u^{2}(u-1)\end{bmatrix}}^{\mathrm {T} }{\begin{bmatrix}p_{n-1}\\p_{n}\\p_{n+1}\\p_{n+2}\end{bmatrix}}\\&={\tfrac {1}{2}}{\Big (}{\big (}u^{2}(2-u)-u{\big )}p_{n-1}+{\big (}u^{2}(3u-5)+2{\big )}p_{n}+{\big (}u^{2}(4-3u)+u{\big )}p_{n+1}+u^{2}(u-1)p_{n+2}{\Big )}\\&={\tfrac {1}{2}}{\big (}(-u^{3}+2u^{2}-u)p_{n-1}+(3u^{3}-5u^{2}+2)p_{n}+(-3u^{3}+4u^{2}+u)p_{n+1}+(u^{3}-u^{2})p_{n+2}{\big )}\\&={\tfrac {1}{2}}{\big (}(-p_{n-1}+3p_{n}-3p_{n+1}+p_{n+2})u^{3}+(2p_{n-1}-5p_{n}+4p_{n+1}-p_{n+2})u^{2}+(-p_{n-1}+p_{n+1})u+2p_{n}{\big )}\\&={\tfrac {1}{2}}{\Big (}{\big (}(-p_{n-1}+3p_{n}-3p_{n+1}+p_{n+2})u+(2p_{n-1}-5p_{n}+4p_{n+1}-p_{n+2}){\big )}u+(-p_{n-1}+p_{n+1}){\Big )}u+p_{n},\end{aligned}}}$$

транспонирование матрицыметода Горнера ${\displaystyle \mathrm {T} }$

Эта запись актуальна для трикубической интерполяции , где одна оптимизация требует вычисления CINT _u шестнадцать раз с одинаковыми u и разными p .

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

• Бикубическая интерполяция , обобщение на два измерения.
• Трикубическая интерполяция , обобщение на три измерения.
• Интерполяция Эрмита
• Многомерная интерполяция
• Сплайн-интерполяция
• Дискретная сплайн-интерполяция

Рекомендации

1. Эрвин Крейциг (2005). Высшая инженерная математика (9-е изд.). Уайли. п. 816. ИСБН 9780471488859.
2. Стивен Ричардс (2020). «Сплайновая модель Эрмита послепенсионной смертности». Скандинавский актуарный журнал . Тейлор и Фрэнсис: 110–127. дои : 10.1080/03461238.2019.1642239.
3. Сиксиан Тан, Джеки Ли и Леони Тикл (2022). «Сплайновый подход Эрмита для моделирования смертности населения». Анналы актуарной науки . Издательство Кембриджского университета: 1–42. дои : 10.1017/S1748499522000173.
4. Петцольд, Чарльз (2009). «Канонические сплайны в WPF и Silverlight».
5. "Кардинальные сплайны". Сеть разработчиков Microsoft . Проверено 27 мая 2018 г.
6. Кубическая интерполяция не уникальна: эта модель, использующая сплайн Катмулла-Рома и базисные полиномы Лагранжа, проходит через все четыре точки. Примечание. Если черная точка находится слева от желтой точки, расстояние по горизонтали желтого будет отрицательным; если черная точка находится справа от зеленой точки, зеленое расстояние по горизонтали отрицательное.
7. Кэтмалл, Эдвин ; Ром, Рафаэль (1974), «Класс локальных интерполирующих сплайнов», в Барнхилле, РЭ; Ризенфельд, РФ (ред.), Компьютерное геометрическое проектирование , Нью-Йорк: Academic Press, стр. 317–326.
8. Н. Дин, М.С. Флоатер и К. Хорманн. Подразделение кривой по четырем точкам на основе повторяющихся хордальных и центростремительных параметризаций. Компьютерное геометрическое проектирование, 26(3):279–286, 2009.
9. П. Дж. Барри и Р. Н. Голдман. Алгоритм рекурсивного вычисления для класса сплайнов Катмулла-Рома. SIGGRAPH Компьютерная графика, 22 (4): 199–204, 1988.
10. Две иерархии сплайн-интерполяций. Практические алгоритмы для многомерных сплайнов высшего порядка.

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

• Сплайновые кривые, Университет профессора Дональда Х. Хауса Клемсона
• Многомерная интерполяция и аппроксимация Эрмита, профессор Чандраджит Баджадж, Университет Пердью
• Введение в сплайны Катмулла – Рома, MVPs.org
• Интерполяция кардинальных сплайнов и сплайнов Катмулла – Рома
• Методы интерполяции: линейный, косинусный, кубический и эрмитный (с источниками C)
• Общие сплайновые уравнения