В математике, сплайн - это специальная функция , определенная кусочно на полиномы. В задачах интерполяции, сплайн-интерполяция часто предпочтительнее полиномиальной интерполяции, потому что она дает аналогичные результаты даже при использовании полиномов низкой степени, избегая при этом явления Рунге. для более высоких степеней.
В подполях информатика компьютерного проектирования и компьютерной графики термин сплайн чаще относится к кусочному полиному (параметрический) кривая. Сплайны - популярные кривые в этих подполях из-за простоты их построения, простоты и точности оценки, а также их способности аппроксимировать сложные формы с помощью подбора кривой и интерактивного проектирования кривых.
Термин «сплайн» происходит от гибких шлицевых устройств, используемых судостроителями и чертежниками для рисования плавных форм.
Термин «сплайн» используется для обозначения широкого класса функций, которые используются в приложениях, требующих интерполяция и / или сглаживание данных. Данные могут быть одномерными или многомерными. Сплайновые функции для интерполяции обычно определяются как минимизаторы подходящих мер шероховатости (например, интегрального квадрата кривизны) с учетом ограничений интерполяции. Сглаживающие сплайны можно рассматривать как обобщения интерполяционных сплайнов, в которых функции определяются для минимизации взвешенной комбинации среднего квадрата ошибки аппроксимации по наблюдаемым данным и меры шероховатости. Для ряда содержательных определений меры шероховатости сплайн-функции оказываются конечномерными по своей природе, что является основной причиной их полезности в вычислениях и представлении. В оставшейся части этого раздела мы полностью сосредоточимся на одномерных полиномиальных сплайнах и используем термин «сплайн» в этом ограниченном смысле.
Начнем с ограничения нашего обсуждения одномерным полиномиальным случаем. В этом случае сплайн - это кусочно полиномиальная функция. Эта функция, назовите ее S, принимает значения из интервала [a, b] и отображает их в , набор действительных чисел,.
Мы хотим, чтобы S был определен кусочно. Для этого пусть интервал [a, b] покрыт k упорядоченных подинтервалов с попарно непересекающимися внутренностями ,
На каждой из этих k «частей» [a, b] мы хотим определить многочлен, назовем его P i..
На i-м подынтервале [a, b] S определяется как P i,.
Данные k + 1 балл t i называются узлами . Вектор называется вектор узла для сплайна. Если узлы равномерно распределены в интервале [a, b], мы говорим, что сплайн однородный, в противном случае мы говорим, что он неравномерный .
Если полиномиальные части P i каждый имеет степень не выше n, тогда говорят, что сплайн имеет степень(или порядка n + 1).
Если в окрестности t i, то Говорят, что сплайн имеет гладкость (по крайней мере) в t i. То есть в t i две части P i-1 и P i имеют общие значения производной от производной порядка 0 (значение функции) вверх через производную порядка r i (другими словами, два соседних полиномиальных участка соединяются с потерей гладкости не более чем на n - r i).
Вектор так, чтобы сплайн имел гладкость в t i для называется вектором гладкости для сплайна.
Дан вектор узла , степень n и вектор гладкости для , можно рассматривать множество всех сплайнов степени с вектором узлов и вектором гладкости . Оснащенный операцией сложения двух функций (точечное сложение) и взятия действительных кратных функций, этот набор становится реальным векторным пространством. Это сплайновое пространство обычно обозначается .
В математическое исследование полиномиальных сплайнов, на вопрос о том, что происходит, когда два узла, скажем t i и t i + 1, перемещаются вместе, дает простой ответ. Полиномиальный кусок P i (t) исчезает, а куски P i − 1 (t) и P i + 1 (t) соединяются с суммой потерь непрерывности для t i и t i + 1. То есть
Это приводит к более общему пониманию вектора узла. Потеря непрерывности в любой точке может рассматриваться как результат нескольких узлов, расположенных в этой точке, а тип сплайна может быть полностью охарактеризован его степенью n и его расширенным вектором узлов
где t i повторяется j i раз для .
A параметрическая кривая на интервале [a, b]
является сплайн-кривая, если и X, и Y являются сплайн-функциями одинаковой степени с одинаковыми расширенными векторами узлов на этом интервале.
Предположим, что интервал [a, b] равен [0,3], а подынтервалы - [0,1], [1,2] и [2,3]. Предположим, что полиномиальные части должны иметь степень 2, а части на [0,1] и [1,2] должны соединяться по значению и первой производной (при t = 1), а части на [1,2] и [ 2,3] включаются просто по значению (при t = 2). Это определило бы тип сплайна S (t), для которого
будет членом этого типа, а также
будет членом этого типа. (Примечание: хотя полиномиальная часть 2t не является квадратичной, результат по-прежнему называется квадратичным сплайном. Это демонстрирует, что степень сплайна - это максимальная степень его полиномиальных частей.) Расширенный вектор узлов для этого типа сплайна будет иметь вид (0, 1, 2, 2, 3).
Самый простой сплайн имеет степень 0. Его также называют ступенчатой функцией. Следующий по простоте сплайн имеет степень 1. Он также называется линейным сплайном . Замкнутый линейный сплайн (т. Е. Первый узел и последний одинаковые) на плоскости - это просто многоугольник.
Обычный сплайн - это естественный кубический сплайн степени 3 с непрерывностью C.Слово "естественный" означает, что вторые производные полиномов сплайна устанавливаются равными нулю в конечных точках интервала интерполяции
Это заставляет сплайн быть прямой линией за пределами интервала, не нарушая его гладкости.
Кубические сплайны имеют вид .. Заданный набор координат мы хотим найти множество из шлицы для
Они должны удовлетворять:
Определим один кубический сплайн а sa 5-кортеж где и соответствуют коэффициентам в форме, показанной ранее, и равно
Алгоритм вычисления естественных кубических сплайнов: . Ввод: набор координат , с . Вывод: установить сплайны, состоящие из n кортежей.
Может возникнуть вопрос, что означает более n нескольких узлов в векторе узлов иметь, поскольку это привело бы к непрерывности типа
Классический тип сплайна степени n, используемый в численном анализе, имеет непрерывность
что означает, что каждые два соседних полиномиальных фрагмента пересекаются по своему значению и первым n - 1 производным на каждом узле. Математический сплайн, который наиболее точно моделирует плоский сплайн , является кубическим (n = 3), дважды непрерывно дифференцируемым (C), естественным сплайном, который представляет собой сплайн этого классического типа с дополнительными условиями, наложенными на конечных точках a и б.
Другой тип сплайна, который часто используется в графике, например, в программах для рисования, таких как Adobe Illustrator из Adobe Systems, имеет кубические части, но имеет непрерывность только не более
Этот тип сплайна также используется в PostScript, а также в определении некоторых компьютерные типографские шрифты.
Многие системы автоматизированного проектирования, разработанные для высококачественной графики и анимации, используют расширенные узловые векторы, например Maya из Alias . В системах автоматизированного проектирования часто используется расширенная концепция сплайна, известная как Неоднородный рациональный B-сплайн (NURBS).
Если доступны выборочные данные из функции или физического объекта, интерполяция сплайна - это подход к созданию сплайна, который аппроксимирует эти данные.
Общее выражение для i-го интерполирующего кубического сплайна C в точке x с естественным условием можно найти по формуле
где
Для заданного n интервал [a, b] и данный расширенный вектор узлов на этом интервале, сплайны степени n образуют векторное пространство. Вкратце это означает, что добавление любых двух сплайнов заданного типа дает сплайн данного типа, а умножение сплайна данного типа на любую константу дает сплайн данного типа. Размер пространства, содержащего все сплайны определенного типа, можно отсчитать из расширенного вектора узлов:
Размер равен сумме степени плюс кратности
Если на тип сплайна накладываются дополнительные линейные условия, то полученный сплайн будет лежать в подпространство. Например, пространство всех естественных кубических сплайнов является подпространством пространства всех кубических C-сплайнов.
Литература по шлицам изобилует названиями специальных типов шлицев. Эти имена были связаны с:
Часто для типа сплайна, удовлетворяющего двум или более основным пунктам, указанным выше, выбиралось специальное имя. Например, сплайн Эрмита - это сплайн, который выражается с помощью полиномов Эрмита для представления каждой из отдельных частей полинома. Чаще всего они используются при n = 3; то есть, как кубические шлицы Эрмита. В этой степени они могут быть дополнительно выбраны только непрерывными по касательной (C); откуда следует, что все внутренние узлы двойные. Было изобретено несколько способов подгонки таких сплайнов к заданным точкам данных; то есть превратить их в интерполирующие сплайны и сделать это путем оценки вероятных значений касательной в местах пересечения каждых двух частей полинома (что дает нам кардинальные сплайны, сплайны Катмулла-Рома и шлицы Кочанека-Бартелса, в зависимости от используемого метода).
Для каждого из представлений должны быть найдены некоторые средства оценки, чтобы значения сплайна могли быть получены по запросу. Для тех представлений, которые выражают каждый отдельный полиномиальный кусок P i (t) в терминах некоторого базиса для многочленов степени n, это концептуально просто:
Однако этапы оценки и суммирования часто хитроумно комбинируются. Например, многочлены Бернштейна являются основой для многочленов, которые можно эффективно вычислять в линейных комбинациях с помощью специальных рекуррентных соотношений. В этом заключается суть алгоритма Де Кастельжау, который используется в кривых Безье и сплайнах Безье.
. Для представления, которое определяет сплайн как линейную комбинацию базисных сплайнов, однако необходимо нечто более сложное. Алгоритм де Бура - эффективный метод оценки B-сплайнов.
До использования компьютеров численные расчеты выполнялись вручную. Хотя использовались кусочно-определенные функции, такие как знаковая функция или ступенчатая функция, в целом предпочтение было отдано многочленам, поскольку с ними было проще работать. С появлением компьютеров шлицы приобрели значение. Сначала они использовались как замена многочленам при интерполяции, а затем как инструмент для построения гладких и гибких форм в компьютерной графике.
Принято считать, что первая математическая ссылка на сплайны - это статья 1946 года Шенберга, которая, вероятно, является первым местом, где слово «сплайн» используется в связи с гладкими, кусочными полиномиальная аппроксимация. Однако эти идеи уходят корнями в авиастроение и судостроение. В предисловии к (Bartels et al., 1987) Робин Форрест описывает «подъем », технику, использовавшуюся в британской авиационной промышленности во время Второй мировой войны создавать шаблоны для самолетов, пропуская тонкие деревянные планки (называемые «шлицы ») через точки, проложенные на полу большого дизайнерского чердака, - метод, заимствованный из дизайна корпуса кораблей. В течение многих лет практика проектирования кораблей использовала модели для проектирования в малом. Затем успешный дизайн был нанесен на миллиметровую бумагу, а ключевые точки графика были перенесены на миллиметровую бумагу большего размера в полный размер. Тонкие деревянные планки обеспечили интерполяцию ключевых точек в плавные кривые. Полоски будут удерживаться на месте в дискретных точках (названных Форрестом «утками»; Шенберг использовал «собаки» или «крысы»), а между этими точками они принимают формы с минимальной энергией деформации. По словам Форреста, одним из возможных стимулов для математической модели этого процесса была потенциальная потеря критически важных компонентов конструкции для всего самолета в случае попадания в чердак вражеской бомбы. Это привело к «коническому подъему», при котором конические секции использовались для моделирования положения кривой между утками. Конические подъемы были заменены на то, что мы назвали бы шлицами в начале 1960-х на основе работы Boeing и (несколько позже) British Aircraft Corporation.
Слово «шлиц» изначально было восточноанглийское диалектное слово.
Использование шлицев для моделирования автомобильных кузовов, кажется, имеет несколько независимых начал. Кредит заявлен от имени де Кастельжау по адресу Citroën, Пьер Безье по адресу Renault и Биркгоф, Гарабедян и де Бур в General Motors (см. Birkhoff and de Boor, 1965), все для работ, имевших место в самом начале 1960-х или в конце 1950-х годов. По крайней мере, одна из статей де Кастельжау была опубликована, но не широко, в 1959 году. Работа Де Бура в General Motors привела к тому, что в начале 1960-х годов был опубликован ряд статей, в том числе некоторые из фундаментальных работ по B-шлицы.
Работа также велась в компании Pratt Whitney Aircraft, где были задействованы два автора (Ahlberg et al., 1967) - первой книги, посвященной шлицевым соединениям, и Модель бассейна Дэвида Тейлора, автор Федор Тейлхеймер. Работа в General Motors подробно описана в (Birkhoff, 1990) и (Young, 1997). Дэвис (1997) резюмирует некоторые из этих материалов.
Теория
Функция Excel
Онлайн-утилиты
Computer Code