Реферат:
«Сплайны. Финитныефункции. Основные понятия, назначение. В сплайны Шенберга»
Введение
Функции,подобные тем, что сейчас называют сплайнами были известны математикам давно,начиная как минимум с Эйлера, но их интенсивное изучение началось, фактически,только в середине 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)
На все этивопросы частично дает ответ теория Стренга-Фикса.2.2Теория аппроксимации финитными функциями Стренга-Фикса
Изложимосновные идеи этой теории для функций одной переменной с регулярными конечнымиэлементами.
Область /> покрываем равномернойсеткой
/>, [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 andScience s.r.o., конференция «Европейская наука XXI века», 2009
7. Корнейчук, Н.П.,Бабенко, В.Ф., Лигун, А.А. Экстремальные свойства полиномов и сплайнов /отв. ред. А.И. Степанец; ред. С.Д. Кошис, О.Д. Мельник, АНУкраины, Ин-т математики. – К.: Наукова думка, 1992.–304 с.