Название: Сплайны, финитные функции
Вид работы: реферат
Рубрика: Математика
Размер файла: 196.68 Kb
Скачать файл: referat.me-215828.docx
Краткое описание работы: Понятие и классификация кривых Безье, их разновидности и методика, основные этапы построения. Порядок и условия применения данных кривых в компьютерной графике. Преобразование квадратичных кривых в кубические. Финитные функции. В-сплайны Шёнберга.
Сплайны, финитные функции
Реферат:
«Сплайны. Финитные функции. Основные понятия, назначение. В сплайны Шенберга»
Введение
Функции, подобные тем, что сейчас называют сплайнами были известны математикам давно, начиная как минимум с Эйлера, но их интенсивное изучение началось, фактически, только в середине 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 and Science s.r.o., конференция «Европейская наука XXI века», 2009
7. Корнейчук, Н.П., Бабенко, В.Ф., Лигун, А.А. Экстремальные свойства полиномов и сплайнов / отв. ред. А.И. Степанец; ред. С.Д. Кошис, О.Д. Мельник, АН Украины, Ин-т математики. – К.: Наукова думка, 1992.–304 с.
Похожие работы
-
Исследование кривых и поверхностей второго порядка
Кафедра высшей математики Курсовая работа по линейной алгебре и аналитической геометрии на тему: Исследование кривых и поверхностей второго порядка
-
Преобразование графиков функции
Тема: « Преобразование графиков функции Цели: 1) Систематизировать приемы построения графиков. 2) Показать их применение при построении: а) графиков сложных функций;
-
Особое решение дифференциальных уравнений первого порядка
Введение Дифференциальным уравнением называется уравнение, связывающее независимые переменные, их функции и производные (или дифференциалы) этой функции.
-
Качественное исследование в целом двумерной квадратичной стационарной системы с двумя частными интегралами в виде кривых третьего и первого порядков
Построение квадратичной двумерной стационарной системы, нахождение состояний равновесия, исследование бесконечно-удаленной части плоскости. Необходимые и достаточные условия существования у системы двух частных интегралов. Построение траектории в круге.
-
Качественное исследование в целом двумерной квадратичной стационарной системы с двумя частными интегралами в виде кривых второго и первого порядков
Порядок и основные этапы построения квадратичных двумерных стационарных систем с заданными интегралами, условия их существования. Методика качественного исследования одной системы первого и второго класса построенных двумерных стационарных систем.
-
Теория случайных процессов
Вычисление спектральной плотности сигнала по выборке его синусоидальных составляющих.
-
Приложения определенного интеграла к решению некоторых задач механики и физики
Моменты и центры масс плоских кривых. Теорема Гульдена. Площадь поверхности, образованной вращением дуги плоской кривой вокруг оси, лежащей в плоскости дуги и ее не пересекающей, равна произведению длины дуги на длину окружности.
-
Базисные сплайны
Определение сплайна степени n дефекта. Простейший пример сплайна - единичная функция Хевисайда. Теорема о линейно независимых функциях и ее доказательство. Базисные сплайны с конечными носителями. Тождество Лемма. Представление многочленов сплайнами.
-
Исследования и теории Габриеля Крамера
Преподавательская работа швейцарского математика Габриэля Крамера, введение в анализ алгебраических кривых. Система произвольного количества линейных уравнений с квадратной матрицей Крамера. Классификация и порядок математических и алгебраических кривых.
-
Выбор и построение интерполирующей функции
Определение значения заданной функции в указанной точке при помощи интерполяционной схемы Эйткина. Проверка правильности данного решения с помощью кубического сплайна. Практическая реализация данного задания на языке Pascal и при помощи таблиц Excel.