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

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

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

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

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

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

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

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

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

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

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

На единичном интервале , если задана начальная точка в и конечная точка в с начальной касательной в точке и конечной касательной в точке , многочлен можно определить как , где t ∈ [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},}$$

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

Интерполяция в произвольном интервале выполняется путем отображения последнего в посредством аффинной (степень-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}}$

Столбец "Expanded" показывает представление, используемое в определении выше. Столбец "Factorized" сразу показывает, что и равны нулю на границах. Вы можете далее заключить, что и имеют нуль кратности 2 в точке 0, а и имеют такой же нуль в точке 1, поэтому они имеют наклон 0 на этих границах. Столбец "Bernstein" показывает разложение базисных функций Эрмита в полиномы Бернштейна порядка 3: ${\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}}$

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

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

Набор данных для можно интерполировать, применяя вышеописанную процедуру к каждому интервалу, где касательные выбираются разумным образом, что означает, что касательные для интервалов, имеющих общие конечные точки, равны. Интерполированная кривая тогда состоит из кусочно-кубических сплайнов Эрмита и глобально непрерывно дифференцируема в . ${\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] На каждом конце кривой требуются две дополнительные точки. Равномерная реализация Кэтмелла–Рома может создавать петли и самопересечения. Хордовая и центростремительная реализации Кэтмелла–Рома ^[8] решают эту проблему, но используют немного другой расчет. ^[9] В компьютерной графике сплайны Кэтмелла–Рома часто используются для получения плавного интерполированного движения между ключевыми кадрами . Например, большинство анимаций траектории камеры, сгенерированных из дискретных ключевых кадров, обрабатываются с помощью сплайнов Кэтмелла–Рома. Они популярны в основном из-за того, что их относительно легко вычислять, гарантируя, что каждая позиция ключевого кадра будет точно достигнута, а также гарантируя, что касательные сгенерированной кривой непрерывны на нескольких сегментах.

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

Сплайн Коханека–Бартельса представляет собой дальнейшее обобщение того, как выбирать касательные по заданным точкам данных , и , с тремя возможными параметрами: натяжением, смещением и параметром непрерывности. ${\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). Advanced Engineering Mathematics (9-е изд.). Wiley. стр. 816. ISBN 9780471488859.
2. Стивен Ричардс (2020). «Эрмитово-сплайновая модель смертности после выхода на пенсию». Scandinavian Actuarial Journal . Taylor and Francis: 110–127. doi : 10.1080/03461238.2019.1642239.
3. Sixian Tang, Jackie Li и Leonie Tickle (2022). «Подход сплайна Эрмита для моделирования смертности населения». Annals of Actuarial Science . Cambridge University Press: 1–42. doi : 10.1017/S1748499522000173.
4. Петцольд, Чарльз (2009). «Канонические сплайны в WPF и Silverlight».
5. "Кардинальные сплайны". Microsoft Developer Network . Получено 2018-05-27 .
6. Кубическая интерполяция не является уникальной: эта модель, использующая сплайн Катмулла-Рома и базисные полиномы Лагранжа, проходит через все четыре точки. Примечание: если черная точка находится слева от желтой точки, то желтое горизонтальное расстояние отрицательно; если черная точка находится справа от зеленой точки, то зеленое горизонтальное расстояние отрицательно.
7. Кэтмелл, Эдвин ; Ром, Рафаэль (1974), «Класс локальных интерполяционных сплайнов», в Barnhill, RE; Riesenfeld, RF (ред.), Computer Aided Geometric Design , Нью-Йорк: Academic Press, стр. 317–326
8. Н. Дин, М. С. Флоатер и К. Хорманн. Четырехточечное подразделение кривой на основе итерированных хордовых и центростремительных параметризаций. Computer Aided Geometric Design, 26(3):279–286, 2009.
9. PJ Barry и RN Goldman. Рекурсивный алгоритм оценки для класса сплайнов Catmull-Rom. SIGGRAPH Computer Graphics, 22(4):199–204, 1988.
10. Две иерархии сплайн-интерполяций. Практические алгоритмы для многомерных сплайнов высшего порядка.

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

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