Сплайны, финитные функции
Реферат:
«Сплайны. Финитные
функции. Основные понятия, назначение. В сплайны Шенберга»
Введение
Функции,
подобные тем, что сейчас называют сплайнами были известны математикам давно,
начиная как минимум с Эйлера, но их интенсивное изучение началось, фактически, только
в середине XX века. В 1946 году Исаак Шёнберг впервые употребил этот термин в
качестве обозначения класса полиномиальных сплайнов. До 1960 годов сплайны были
в основном инструментом теоретических исследований, они часто появлялись в
качестве решений различных экстремальных и вариационных задач, особенно в
теории приближений.
После 1960
года с развитием вычислительной техники началось использование сплайнов в
компьютерной графике и моделировании, что продолжается по сей день.
1. Сплайны
Под сплайном
(от англ. spline – планка, рейка) обычно понимают кусочно-заданную функцию,
совпадающую с функциями более простой природы на каждом элементе разбиения
своей области определения.
Классический
сплайн одной переменной строится так: область определения разбивается на
конечное число отрезков, на каждом из которых сплайн совпадает с некоторым
алгебраическим полиномом. Максимальная степень из использованных полиномов
называется степенью сплайна. Разность между степенью сплайна и получившейся
гладкостью называется дефектом сплайна. Например, непрерывная ломаная есть
сплайн степени 1 и дефекта 1.
Сплайны имеют
многочисленные применения как в математической теории, так и в разнообразных
вычислительных приложениях. В частности, сплайны двух переменных интенсивно используются
для задания поверхностей в различных системах компьютерного моделирования.
1.1 Кривые
Безье
Кривые
Безье́ или Кривые Бернштейна-Безье были разработаны в 60-х годах XX века
независимо друг от друга Пьером Безье и Полем де Кастельжо.
Впервые кривые
были представлены широкой публике в 1962 году французским инженером Пьером
Безье, который, разработав их независимо от де Кастельжо, использовал их для
компьютерного проектирования автомобильных кузовов. Кривые были названы именем
Безье, а именем де Кастельжо назван разработанный им рекурсивный способ
определения кривых (алгоритм де Кастельжо).
Впоследствии
это открытие стало одним из важнейших инструментов систем автоматизированного
проектирования и программ компьютерной графики.
Определение
Кривая Безье –
параметрическая кривая, задаваемая выражением:
(1.1)
где 
– функция компонент
векторов опорных вершин, а 
– базисные функции кривой Безье, называемые
также полиномами Бернштейна.
(1.2)
, (1.3)
где n – степень
полинома, i – порядковый номер опорной вершины
1.2 Виды
кривых Безье:
1. Линейные
кривые
При n = 1
кривая представляет собой отрезок прямой линии, опорные точки P0 и P1
определяют его начало и конец. Кривая задаётся уравнением:
(1.4)
2.
Квадратичные кривые
Квадратичная
кривая Безье (n = 2) задаётся 3-мя опорными точками: P0, P1 и P2:
(1.5)
Квадратичные
кривые Безье в составе сплайнов используются для описания формы символов в
шрифтах TrueType и в SWF файлах.
3. Кубические
кривые
В
параметрической форме кубическая кривая Безье (n = 3) описывается следующим
уравнением:
(1.6)
Четыре
опорные точки P0, P1, P2 и P3, заданные в 2-х или 3-мерном пространстве определяют
форму кривой.
Линия берёт
начало из точки P0 направляясь к P1 и заканчивается в точке P3 подходя к ней со
стороны P2. То есть кривая не проходит через точки P1 и P2, они используются
для указания её направления. Длина отрезка между P0 и P1 определяет, как скоро
кривая повернёт к P3.
Рисунок 1 Кубическая
кривая Безье
В матричной
форме кубическая кривая Безье записывается следующим образом:
, (1.7)
где 
называется базисной
матрицей Безье:
(1.8)
В современных
графических системах, таких как PostScript, Metafont и GIMP для представления
криволинейных форм используются сплайны Безье, составленные из кубических
кривых.
1.3 Построение
кривых Безье
1. Линейные
кривые
Параметр t в
функции, описывающей линейный случай кривой Безье, определяет где именно на
расстоянии от P0 до P1 находится B(t). Например, при t = 0,25 значение функции
B(t) соответствует четверти расстояния между точками P0 и P1. Параметр t
изменяется от 0 до 1, а B(t) описывает отрезок прямой между точками P0 и P1.
Рисунок 2 Построение
линейной кривой Безье
2.
Квадратичные кривые
Для
построения квадратичных кривых Безье требуется выделение двух промежуточных
точек Q0 и Q1 из условия чтобы параметр t изменялся от 0 до 1:
Точка Q0
изменяется от P0 до P1 и описывает линейную кривую Безье.
Точка Q1
изменяется от P1 до P2 и также описывает линейную кривую Безье.
Точка B
изменяется от Q0 до Q1 и описывает квадратичную кривую Безье.
Рисунок 3 Построение
квадратичной кривой Безье
3. Кривые
высших степеней
Для
построения кривых высших порядков соответственно требуется и больше
промежуточных точек. Для кубической кривой это промежуточные точки Q0, Q1 и Q2,
описывающие линейные кривые, а также точки R0 и R1, которые описывают
квадратичные кривые: более простое уравнение p0q0/p0q1=q1p1/p1p2=bq0/q1q0
Рисунок 4 Построение
кубической кривой Безье
Для кривых
четвёртой степени это будут точки Q0, Q1, Q2 и Q3, описывающие линейные кривые,
R0, R1 и R2, которые описывают квадратичные кривые, а также точки S0 и S1,
описывающие кубические кривые Безье:
Рисунок 5 Построение
кривой Безье 4-ой степени
1.4 Применение
в компьютерной графике
Благодаря
простоте задания и манипуляции, кривые Безье нашли широкое применение в
компьютерной графике для моделирования гладких линий. Кривая целиком лежит в
выпуклой оболочке своих опорных точек. Это свойство кривых Безье с одной
стороны значительно облегчает задачу нахождения точек пересечения кривых (если
не пересекаются выпуклые оболочки опорных точек, то не пересекаются и сами
кривые), а с другой стороны позволяет осуществлять интуитивно понятное
управление параметрами кривой в графическом интерфейсе с помощью её опорных
точек. Кроме того аффинные преобразования кривой (перенос, масштабирование,
вращение и др.) также могут быть осуществлены путём применения соответствующих
трансформаций к опорным точкам.
Наибольшее
значение имеют кривые Безье второй и третьей степеней (квадратичные и
кубические). Кривые высших степеней при обработке требуют большего объёма
вычислений и для практических целей используются реже. Для построения сложных
по форме линий отдельные кривые Безье могут быть последовательно соединены друг
с другом в сплайн Безье. Для того, чтобы обеспечить гладкость линии в месте
соединения двух кривых, три смежные опорные точки обеих кривых должны лежать на
одной прямой.
1.5 Преобразование
квадратичных кривых Безье в кубические
Квадратичная
кривая Безье с координатами 
преобразовывается в кубическую кривую Безье с
координатами:
2.
Финитные функции
Финитной
называется функция 
, определенная для всех 
, но отличная от нуля лишь на некоторой
конечной области 
, называемой конечным
носителем:
(2.1)
Для 
, определенных на , построение базиса 
из финитных функций осуществляется
следующим образом. Сначала область , в которой решается
задача, некоторым регулярным образом покрывается конечным числом 
перекрывающихся подобластей 
, например как на рис. 6.1:
(2.2)
Подобласти получили название конечные элементы.
Затем на
каждом как на конечном носителе строим
базисную финитную функцию 
. Все функции таким образом
выбранного базиса линейно независимы в силу условий (2.1), (2.2).
Отметим
преимущества такого выбора базиса:
а) ввиду
того, что выбираются значительно меньшими и при этом скалярные произведения
(2.3)
равны нулю
для функций с непересекающимися носителями, матрица проекционного уравнения
будет сильно разрежена. Более того, если условие 
выполняется
только для смежных носителей, то матрица получается ленточной, т.е. аналогична
той, к которой приводят сеточные методы;
б)
возможность выбора специфических приграничных конечных элементов и связанных с
ними финитных функций, учитывающих особенности границы, позволяет эффективно
решать краевые задачи на достаточно произвольной области .
Основная
трудность аппроксимации финитными функциями состоит в сопряжении финитных
функций на границах Wk таким образом, чтобы функция 
в целом была непрерывна вместе со
своими производными достаточно высокого порядка.
При таком
выборе базиса естественно поставить вопросы о его полноте, выборе вида функций и аппроксимационных свойствах разложения
искомого решения
. (2.4)
На все эти
вопросы частично дает ответ теория Стренга-Фикса.
Изложим
основные идеи этой теории для функций одной переменной с регулярными конечными
элементами.
Область 
покрываем равномерной сеткой
, [p] – целая часть p.
Конечные
элементы выберем как отрезки длиной 
с центром в точке 
: 
.
Если 
, смежные элементы не пересекаются и их
длина равна 
: если 
, то
длина пересечения равна , длина равна 
; при
– длина пересечения , длина равна
. Заметим, что такое покрытие полностью
удовлетворяет условиям (2.2). Все базисные финитные функции с носителями выберем одинаковой формы как сдвиги
одной «стандартной» финитной функции 
:
; 
(2.5)
Если «стандартная»
функция нормирована к единице, то ее сдвиги записываются в виде
(2.6)
Теорема
Стренга-Фикса (один из вариантов)
Допустим, что
. В этом случае для 
существует преобразование Фурье:
прямое 
обратное 
Допустим, что
для преобразования Фурье стандартной финитной функции выполнено
условие
и 
при
(2.7)
(т.е. в 
точках 
имеет
нули 
й кратности).
Тогда
существуют такие 
, что при 
.
Это значит,
что если, например, подобрать 
, у которой условия
теоремы выполняются для 
, то аппроксимация
самой функции имеет порядок 
, аппроксимация ее первой производной
, второй – 
.
Наличие такой
центральной теоремы, а также еще ряда доказанных Стренгом-Фиксом теорем, в
частности о существовании функций, удовлетворяющих условиям (2.7), дает
алгоритм для построения базисных финитных функций, обладающих необходимыми
аппроксимационными свойствами.
3. B-сплайны
Шёнберга
В вычислительной
математике B-сплайном называют сплайн-функцию, имеющую наименьший носитель для
заданной степени, порядка гладкости и разбиения области определения.
Фундаментальная теорема устанавливает, что любая сплайн-функция для заданной
степени, гладкости и области определения может быть представлена как линейная
комбинация B-сплайнов той же степени и гладкости на той же области определения.
[1] Термин B-сплайн был введён И. Шёнбергом и является сокращением от
словосочетания «базисный сплайн». [2] B-сплайны могут быть вычислены с помощью
алгоритма де Бора, обладающего устойчивостью.
В системах
автоматизированного проектирования и компьютерной графике термин B-сплайн часто
описывает сплайн-кривую, которая задана сплайн-функциями, выраженными линейными
комбинациями B-сплайнов.
Когда узлы
равноудалены друг от друга, говорят, что B-сплайн является однородным, в
противном случае его называют неоднородным.
Когда
количество узлов совпадает со степенью сплайна, B-сплайн вырождается в кривую
Безье. Форма базисной функции определяется расположением узлов. Масштабирование
или параллельный перенос базисного вектора не влияет на базисную функцию.
Сплайн
содержится в выпуклой оболочке его опорных точек.
Базисный
сплайн степени n: 
.
не обращается
в нуль только на промежутке [ti, ti+n+1], то есть:
. (3.1)
Другими
словами, изменение одной опорной точки влияет только на локальное поведение
кривой, а не на глобальное, как в случае кривых Безье.
Базисная
функция может быть получена из полинома Бернштейна
В-сплайн и некоторые наиболее часто используемые
базисы
Теорема
Стренга-Фикса указывает на то, что если стандартную финитную функцию выбрать исходя из условия (2.7), то ряд
(2.4), построенный на основе ее сдвигов, будет обладать хорошими
аппроксимационными свойствами.
Шенберг
предложил один интересный класс функций, удовлетворяющих условию (2.7). Функцию
называют В-сплайном (Шенберга) степени 
, если ее преобразование Фурье имеет вид
. (3.2)
Как видим,
функция (6.8) удовлетворяет всем условиям (6.7).
Базис из
ступенек
Довольно
просто показать, что при 
(3.3)
В этом случае
базис представляет собой набор сдвигов (2.5) стандартной ступеньки 
(3.3), а функция представляет собой разрывную ступенчатую
функцию (
). Аппроксимация по норме 
имеет порядок 
.
Такой базис может быть выбран в качестве второго базиса 
при
использовании метода Галеркина-Петрова.
Базис из
крышек
Рассмотрим
В-сплайн степени 
: 
.
Из этого соотношения следует, что 
получается как свертка
функций 
= 
После
несложных преобразований получаем:
(3.4)
Функция представляет собой аппроксимацию
непрерывной ломаной линией, имеющей разрывные производные. Аппроксимация по
норме имеет второй порядок, по норме 
– первый. Эта аппроксимация
используется наиболее часто при решении дифференциальных уравнений второго
порядка проекционным методом. Она приводит к наиболее простым формулам для интегралов
и максимально разреженной матрице при ее вычислении.
Кроме того, у
этого базиса, ввиду того, что p=1, есть одна особенность – для аппроксимируемой функции значения коэффициентов 
совпадают со значениями функции в узлах
сетки 
, что позволяет быстро находить начальные
приближения для .
В-сплайн
степени представляет собой
кусочно-полиноминальный кубический сплайн, который получается сверткой:
.
(3.5)
Размер
носителя при увеличился до четырех (). Заметим, что для обеспечения
непрерывности второй производной в точках 
выполняется
условие 
. Как уже отмечалось, аппроксимация по
норме имеет четвертый порядок, по норме – третий.
Литература
1. Роджерс Д., Адамс
Дж. Математические основы машинной графики. – М.: Мир, 2001.
2. Корнейчук, Н.П.,
Бабенко, В.Ф., Лигун, А.А. Экстремальные свойства полиномов и сплайнов /
отв. ред. А.И. Степанец; ред. С.Д. Кошис, О.Д. Мельник, АН
Украины, Ин-т математики.–К.: Наукова думка, 1992.–304 с.
3. Роджерс Д., Адамс
Дж. Математические основы машинной графики. – М.: Мир, 2001.
4. Лившиц Евгений
Давидович. Непрерывные E-выборки для приближения полиномиальными и
рациональными сплайнами: Дис. … канд. физ.-мат. наук: 01.01.01 Москва, 2005 90 с.
5. Алберг Дж., Нильсон Э.,
Уолш Дж. – Теория сплайнов и ее приложения
6. Винниченко Л.Ф. Экспоненциальные
гистосплайны: предпосылки введения // Publishing house Education and
Science s.r.o., конференция «Европейская наука XXI века», 2009
7. Корнейчук, Н.П.,
Бабенко, В.Ф., Лигун, А.А. Экстремальные свойства полиномов и сплайнов /
отв. ред. А.И. Степанец; ред. С.Д. Кошис, О.Д. Мельник, АН
Украины, Ин-т математики. – К.: Наукова думка, 1992.–304 с.