Главная > Математика > Геометрическое моделирование
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.8. В-сплайны

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

Покажем, что теоретически можно построить на отрезке кусочнополиномиальную функцию, удовлетворяющую поставленным условиям. Для этого разобьем отрезок оси параметра t на произвольных участков. Точки разбиения обозначим через и построим на каждом отрезке полиномы степени , гладко стыкуя их между собой по производным от до порядка включительно. Вид искомой функции показан на рис. 2.8.1.

Каждый полином имеет коэффициентов, всего полиномов . Для их определения можно составить уравнений в точках стыковки полиномов уравнений на каждом из краев. Всего мы получим уравнений для коэффициентов. Недостающее уравнение может нормировать величину прогиба кусочно-полиномиальной линии, например, путем нормирования площади под ней, что дает возможность удовлетворить требованию (2.7.6).

Рис. 2.8.1. Составной полиномиальный сплайн

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

Рассмотренные теоретически возможные кусочно-полиномиальные функции, а также базисные функции Бернштейна, являются частными случаями -сплайнов. Основу теории -сплайнов заложили Фергюсон, Шёнберг, Уитни и Карри. Гордон и Розенфельд установили связь между кривыми Безье и -сплайнами и показали, что -сплайны являются мощным обобщением функций Бернштейна. Теория -сплайнов базируется на разделенных разностях.

Разделенные разности.

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

(2.8.1)

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

Следуя данному алгоритму, вычисляются разделенные разности более высоких порядков. Например, если известны разделенные разности порядка, то разделенная разность порядка определяется как отношение

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

Если в разделенной разности первого порядка значения узлов совпадают, то она равна пределу отношения (2.8.1), т.е. производной функции в данной точке

(2.8.4)

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

в знаменателе правой части является следствием того, что в знаменателе разделенной разности стоит длина нескольких участков . Узлы, значения которых совпадают, называются кратными узлами. Так, если говорят, что эти узлы имеют кратность к.

Разделенная разность порядка следующим образом выражается через значения функции в узлах:

где — производная функции вычисленная при . Индексы i и k в обозначении функции говорят об индексе начального узла и о количестве узлов. Равенство (2.8.6) докажем методом индукции. Для разделенной разности первого порядка формула (2.8.6) совпадает с (2.8.1), т.е. для равенство (2.8.6) справедливо. Предположим, что равенство (2.8.6) справедливо для разделенных разностей порядка и убедимся, что из этого предположения следует его верность для разделенных разностей порядка. Для этого вычтем равенства

и

аналогичные (2.8.6), для разделенных разностей на порядок ниже, у которых соответствующие слагаемые приведены к общему знаменателю. В результате получим равенство

из которого после деления на на основании (2.8.3) следует (2.8.6). Из равенства (2.8.6) видно, что разделенная разность не зависит от порядка, в котором следуют узлы в списке аргументов.

Разделенные разности полиномов.

Если является полиномом степени параметра t и нам известны значения полинома в точках , то разделенная разность первого порядка

является полиномом степени.

В самом деле, функция имеет корень и, следовательно, согласно теореме Безу делится без остатка на . Разделенная разность второго порядка

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

(2.8.7)

а разделенная разность порядка полинома степени m равна нулю:

(2.8.8)

Пусть теперь является интерполяционным полиномом функции совпадающим с ней в узлах Разделенные разности, построенные по узлам для функций будут равны. Из определения разделенной разности для функции построенной на последовательности

и равенств разделенных разностей следуют равенства:

Так как то подставляя последовательно эти равенства каждое последующее в предыдущее, начиная с последнего, получим интерполяционную формулу Ньютона (2.4.17) для скалярной функции

(2.8.10)

Таким образом, коэффициенты в полиноме Ньютона являются соответствующими разделенными разностями интерполируемой функции. Если интерполяцию (2.8.10) выполнить на совокупности совпадающих узлов то в соответствии с (2.8.5) разделенные разности пропорциональны производным соответствующего порядка интерполируемой функции, и мы получим усеченный ряд Тейлора.

Вычислим с помощью (2.8.10) разделенную разность порядка для совпадающих узлов и одного отличного от остальных разделенные разности более низкого порядка в соответствии с (2.8.5) будут пропорциональны производным соответствующего порядка функции Искомая разделенная разность определяется формулой

где — производная порядка в точке (производной нулевого порядка мы называем значение функции).

Свойства разделенных разностей.

Известно, что по заданной совокупности значений функции в узлах , можно построить единственный полином степени , совпадающий в узлах U с заданной функцией. Из интерполяционной формулы Ньютона (2.8.9) видим, что разделенная разность порядка на заданной последовательности узлов равна коэффициенту при наивысшей степени аргумента полинома степени , значения которого в заданных узлах согласуются с функцией Это свойство может быть принято в качестве определения разделенной разности.

Свойство 1. Если , то

для любого дополнительного узла .

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

(2.8.13)

где есть последовательность узлов записанных в произвольном порядке. Разделенная разность выражается через значения функции в узлах с помощью формулы (2.8.6). Если некоторые узлы являются кратными, то разделенная разность выражается через значения функции в простых узлах и ее производные в кратных узлах.

Свойство 3. Если то

(2.8.14)

Это равенство следует из единственности интерполяционного полинома.

Свойство 4. Если то

(2.8.15)

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

Свойство 5. Если для функции построен полином степени на последовательности узлов то

(2.8.16)

Это равенство получим, рассматривая t как дополнительный узел в последовательности узлов и рассматривая равенство как необходимое условие в дополнительном узле для полинома степени .

Усеченная степенная функция.

Рассмотрим усеченную степенную функцию со смещенным началом, которую обозначим через

(2.8.17)

Эта функция равна 0 при равна в противном случае. Функция — кусочно-монотонная, непрерывная при при она имеет скачок в точке равный единице. Функция имеет непрерывные производные до порядка включительно. Производная порядка имеет разрыв в точке равный Функция (2.8.17) примечательна тем, что ее производные являются аналогичными функциями, только на порядок ниже. Нам понадобятся как производные по , так и производные по

Графики функций приведены на рис. 2.8.2. Чем выше порядок функции тем она более гладкая в точке

Рассмотрим, свойства вычисленных по значениям функции в узлах разделенных разностей порядка Разделенная разность вычисляется при фиксированном параметре t, но является функцией параметра t.

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

Предположим, что последовательность узлов является возрастающей, т. е. для всех . Тогда по указанным выше причинам разделенная разность и ее производные по t при и равны нулю.

Рис. 2.8.2. Усеченная степенная функция со смещенным началом

Разделенная разность как функция параметра t является непрерывной функцией, отличной от нуля только на интервале . В соответствии с (2.8.6) она выражается через значения усеченной степенной функции в узлах

где — производная функции вычисленная при . Производные разделенной разности до порядка

также являются непрерывными функциями параметра .

Таким образом, разделенная разность как функция параметра t удовлетворяет всем требованиям кроме требования (2.7.6), предъявленным к базисным функциям в формуле (2.7.5), и имеет вид, приведенный на рис. 2.8.1.

Набор функций является претендентом на роль базисных функций в формуле (2.7.5). Для удовлетворения требованию (2.7.6) функции можно нормировать, умножив их на некоторый коэффициент.

В-сплайн (фундаментальный сплайн).

В литературе используется несколько различных определений и обозначений -сплайна. Вводятся определения ненормированного -сплайна и нормированного -сплайна. В общем случае эти определения звучат так. Ненормированный В-сплайн для неубывающей последовательности узлов есть разделенная разность порядка усеченной степенной функции со смещенным началом Нормированный В-сплайн для неубывающей последовательности узлов есть разделенная разность порядка усеченной степенной функции со смещенным началом умноженная на разность значений последнего и первого узла. Ненормированный и нормированный -сплайны связаны между собой только коэффициентом и с точностью до множителя их определения одинаковы. Далее, если не будет указано конкретно, термин -сплайн» мы будем использовать для обоих указанных сплайнов.

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

Определение 1. Нормированный -сплайн порядка для неубывающей последовательности узлов есть разделенная разность порядка усеченной степенной функции умноженная на

(2.8.21.1)

Определение 2. Нормированный -сплайн порядка для неубывающей последовательности узлов есть разделенная разность порядка усеченной степенной функции умноженная на ):

(2.8.21.2)

Определение 3. Нормированный В-сплайн порядка ) для неубывающей последовательности узлов есть разделенная разность порядка усеченной степенной функции умноженная на

(2.8.21.3)

Определение 4. Нормированный В-сплайн порядка ) для неубывающей последовательности узлов есть разделенная разность порядка усеченной степенной функции умноженная на

(2.8.21.4)

Аналогично звучат определения для соответствующих ненормированных В-сплайнов, которые мы рассмотрим ниже. Для приведенных определений мы ввели различные обозначения В-сплайнов, чтобы не возникла путаница. В первом определении В-сплайн привязан к первому узлу (наследует его индекс) и этот индекс стоит перед индексом порядка В-сплайна. Во втором определении В-сплайн привязан к последнему узлу (наследует его индекс) и этот индекс стоит после индекса порядка В-сплайна. Третье определение аналогично первому, только В-сплайну приписывается порядок, равный степени усеченной функции, который оказывается на единицу меньше порядка разделенной разности. Для обращения внимания на это отличие мы обозначили порядок В-сплайна верхним индексом. Четвертое определение аналогично второму, только В-сплайну приписывается порядок, равный степени усеченной функции, который на единицу меньше порядка разделенной разности. Как и в третьем определении, мы обозначили порядок В-сплайна верхним индексом. В третьем определении В-сплайн привязан к первому узлу, а в четвертом определении В-сплайн привязан к последнему узлу (наследует его индекс). Соответственно, в третьем определении индекс узла привязки стоит перед индексом, обозначающим порядок В-сплайна, а в четвертом определении индекс узла привязки стоит после индекса порядка В-сплайна. Все четыре определения равноправны и приводят к одному и тому же рекуррентному соотношению для В-сплайнов, но форма записи этих рекуррентных соотношений различна.

Дадим пояснения к определениям В-сплайна на примере первого определения. Последовательность узлов должна быть неубывающей, т. е. должно выполняться неравенство для всех . В остальном же значения узлов последовательности не оговариваются и в общем случае могут быть произвольными, в том числе и совпадающими. То, что В-сплайн называется подчеркивает, что разделенная разность построена на последовательности узлов, начинающейся с узла и кончающейся на узле Разделенная разность вычислена по функции при фиксированном значении t, при рассмотрении ее как функции только аргумента z. Значение разделенной разности, естественно, зависит от выбранного параметра , о чем говорит аргумент В-сплайн нормирован коэффициентом на который умножена разделенная разность.

При втором определении В-сплайна последовательность узлов также должна быть неубывающей. То, что В-сплайн называется подчеркивает, что разделенная разность построена на последовательности узлов, начинающейся с узла и кончающейся на узле Разделенная разность вычислена по функции при фиксированном значении t, рассмотренная как функция только аргумента z. Значение разделенной разности зависит от выбранного параметра t, о чем говорит аргумент В-сплайн нормирован коэффициентом на который умножена разделенная разность.

Далее мы будем строить кривые на базе точек в которых индекс узла привязки В-сплайна будет соответствовать (равен) индексу точки . Так как индексация точек обычно начинается с нуля или единицы, то при использовании второго или четвертого определений В-сплайна индексацию узлов последовательности придется начинать с отрицательных значений так, чтобы индекс по порядку узла был равен нулю, тогда индекс первого по порядку узла будет равен .

Гладкость В-сплайнов характеризуется порядком, который в первом и втором определениях равен порядку разделенной разности. В первых двух определениях приходится различать степень полиномов и порядок сплайнов. Порядок сплайна, как и степень полинома, характеризует непрерывность ее производных. Для сплайна порядка m должна существовать и быть отличной от нуля (за исключением отдельных точек) производная порядка, а производная порядка должна быть равна нулю. В первых двух определениях В-сплайны порядка представляют собой кусочно-полиномиальные функции, построенные на полиномах степени поэтому их порядок на единицу больше наивысшей степени полинома. В третьем и четвертом определениях В-сплайны порядка представляют собой кусочно-полиномиальные функции, построенные на полиномах той же степени , поэтому их порядок равен наивысшей степени полинома.

Дальнейшие выкладки выполним одновременно для первого и второго определений нормированного В-сплайна. Для третьего и четвертого определений все формулы могут быть получены аналогично.

Пусть В-сплайн порядка построен на неубывающей последовательности узлов , где . В-сплайн отличен от нуля на небольшой области, т. е. при и при . Действительно, как только то между точками усеченная функция примет вид и в силу того, что является полиномом степени меньшей , любая разделенная разность порядка, построенная по этому полиному, равна нулю. Как только , то разделенная разность равна нулю в силу того, что между точками . Только на участке функция представляет собой отрезок горизонтальной прямой, сопряженный с отрезком смещенной степенной функции, и поэтому ее разделенная разность отлична от нуля.

Если воспользоваться определением разделенной разности (2.8.4), то В-сплайн можно записать в виде

(2.8.22)

Для любого в силу локальности отличны от нуля только В-сплайнов, а именно, Используя равенство (2.8.22), найдем сумму всех В-сплайнов для

(2.8.23)

В (2.8.23) использовалось то, что как коэффициент при наивысшей степени аргумента полинома которым описывается усеченная степенная функция на открытом интервале При этом на интервале усеченная степенная функция равна нулю, следовательно, Так как участок был выбран произвольно, то аналогичное равенство выполняется для любого другого участка. Таким образом, при любом t для суммы всех В-сплайнов справедливо равенство

(2.8.24)

Именно ради свойства (2.8.24) нормируются разделенные разности в определении нормированного В-сплайна. Функции представляют собой разложение единицы.

Вычисление нормированных В-сплайнов производится через ненормированные В-сплайны, являющиеся обычными разделенными разностями. Обратимся к ненормированным В-сплайнам. Введем четыре различных определения ненормированного В-сплайна. Они соответствуют приведенным выше четырем определениям нормированного В-сплайна.

Определение 1. Ненормированный В-сплайн порядка для последовательности узлов есть разделенная разность порядка усеченной степенной функции

(2.8.25.1)

Определение 2. Ненормированный В-сплайн порядка для последовательности узлов есть разделенная разность порядка усеченной степенной функции

(2.8.25.2)

Определение 3. Ненормированный В-сплайн порядка ) для последовательности узлов есть разделенная разность порядка усеченной степенной функции

(2.8.25.3)

Определение 4. Ненормированный В-сплайн порядка для последовательности узлов ) есть разделенная разность порядка усеченной степенной функции

(2.8.25.4)

Индексные обозначения ненормированного В-сплайна соответствуют индексным обозначениям нормированного В-сплайна. Все определения ненормированного В-сплайна равноценны. Рассмотрим свойства ненормированного В-сплайна.

Ненормированный В-сплайн первого порядка для первых двух определений и ненормированный В-сплайн нулевого порядка для последних двух определений равен разделенной разности первого порядка для функции :

(2.8.26.1)

Формула Кокса-Де Бура. Пусть имеется неубывающая последовательность узлов . Используем формулу Лейбница (2.8.15) для вычисления В-сплайна (2.8.21), представив функцию в виде произведения , где . Тогда при разделенная разность

Подставим в (2.8.27) определение разделенной разности (2.8.3) для

и получим

Перепишем равенство (2.8.28) с использованием определений ненормированного В-сплайна (2.8.25.1)-(2.8.25.4) и получим формулы

(2.8.29.2)

Рекуррентные соотношения (2.8.29.1)-(2.8.29.4) были получены независимо Мэнсфилдом, Коксом и Де Буром и носят имя формул Кокса-Де Бура. Эти соотношения занимают центральное место в теории В-сплайнов. Они побуждают забыть о разделенных разностях и определить В-сплайн или порядка для неубывающей последовательности узлов как функцию, вычисляемую по одному из рекуррентных соотношений (2.8.29.1)-(2.8.29.4) при соответствующем начальном значении (2.8.26.1)-(2.8.26.4). Все рекуррентные формулы равноценны.

Обратим внимание на то, что в формулах (2.8.29.1) и (2.8.29.2) В-сплайн порядка для неубывающей последовательности узлов вычисляется через два В-сплайна порядка, определенных на последовательностях m узлов, лежащих внутри заданной последовательности. Один из двух В-сплайнов порядка примыкает к началу вычисляемого В-сплайна, а другой — к концу вычисляемого В-сплайна (рис. 2.8.3).

Рис. 2.8.3. Иллюстрация рекуррентного соотношения Кокса-Де Бура

Каждый из двух В-сплайнов порядка берется с коэффициентом, пропорциональным расстоянию параметра t от крайнего узла заданной последовательности, к которому В-сплайнов порядка примыкает. Сумма этих двух коэффициентов равна единице.

Отвлечемся в формулах (2.8.29.1)-(2.8.29.4) от индексации и рассмотрим их с использованием барицентрических координат. Пусть дана произвольная последовательность узлов хотя бы два из которых имели отличные друг от друга значения. Вспомним, что разделенная разность не зависит от порядка следования узлов в списке аргументов. Из последовательности узлов выберем два произвольных несовпадающих узла

На базе этих двух узлов введем барицентрические координаты

Введем следующие обозначения. Последовательность узлов обозначим через Т. Последовательность m узлов, полученную из Т удалением узла обозначим через . Последовательность m узлов, полученную из Т удалением узла обозначим через Разделенную разность порядка усеченной степенной функции на последовательности узлов Т обозначим через . Разделенную разность порядка усеченной степенной функции на последовательности узлов обозначим через . Разделенную разность порядка усеченной степенной функции на последовательности узлов обозначим через Тогда формулы Кокса-Де Бура (2.8.29.1)-(2.8.29.4) для вычисления ненормированного В-сплайна на последовательности узлов Т можно заменить рекуррентным соотношением

(2.8.30)

Так как в силу свойства 2 разделенная разность является симметричной функцией своих аргументов, то последнее рекуррентное соотношение не зависит от выбора узлов . Рекуррентное соотношение (2.8.30) начинается с последовательности, состоящей из двух узлов

О в остальных случаях.

Последовательность узлов Т в общем случае может быть произвольной. Мы рассматриваем неубывающую последовательность узлов, так как нас интересует не отдельно взятый В-сплайн, а совокупность отличных от нуля В-сплайнов при заданном параметре

Рекуррентные соотношения (2.8.29.1)-(2.8.29.4) показывают, что если , то и и что если то и . Так как в , то можно сделать вывод, что В-сплайны при любых значениях параметра неотрицательные:

Нормированный В-сплайн связан с ненормированным В-сплайном соответствующим соотношением:

(2.8.31.1)

Тогда для нормированного В-сплайна формула Кокса-Де Бура примет вид

(2.8.32.2)

где индексы а и b связаны равенством или . Вычисления начинаются с В-сплайна наименьшего порядка:

(2.8.33.2)

Если формально представить схему вычисления В-сплайна определения 1, то она выглядит следующим образом (порядок В-сплайна возрастает сверху вниз, а номера узлов возрастают слева направо):

Среди В-сплайнов первого порядка (2.8.26.1) только один отличен от нуля при данном параметре t, а для вычисления точки кривой (2.7.5) требуются все В-сплайны, отличные от нуля при данном параметре t. Поэтому для параметра вычисление всех отличных от нуля В-сплайнов m-го порядка удобнее производить по схеме

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

Схема вычисления -сплайна определения 2 выглядит следующим образом (порядок -сплайна возрастает сверху вниз, а номера узлов возрастают слева направо):

Среди -сплайнов первого порядка (2.8.26.2) только один отличен от нуля при данном параметре t. Поэтому для параметра вычисление всех отличных от нуля -сплайнов порядка при данном параметре t удобнее производить по схеме

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

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

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

В дальнейшем мы будем пользоваться первым определением -сплайна (если не оговорено противное), хотя все сказанное будет справедливо и при других определениях -сплайна.

<< Предыдущий параграф Следующий параграф >>
Оглавление