Как на практике используются сплайны

Интерполяция сплайнами: теоретические основы

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

Такая задача называется задачей интерполяции и часто возникает на практике.

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

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

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

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

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

Сплайн – функция, которая вместе с несколькими производными непрерывна на всем заданном отрезке [a,b], а на каждом частичном отрезке [, ] в отдельности является некоторым алгебраическим многочленом.

На практике наиболее часто используются кубические сплайны — сплайны третьей степени с непрерывной, по крайней мере, первой производной. При этом величина , называется наклоном сплайна в точке (узле) .

Разобьём отрезок [a,b] на N равных отрезков [, ], где , i=0,1,…,N-1,.

Если в узлах , заданы значения , , которые принимает кубический сплайн, то на частичном отрезке [,] он принимает вид:

. (1)

В самом деле, это легко проверить, рассчитав и в точках ,.

Можно доказать, что если многочлен третьей степени принимает в точках , значения , и имеет в этих точках производные, соответственно, , то он совпадает с многочленом (1).

Таким образом, для того, чтобы задать кубический сплайн на отрезке, необходимо задать значения , i=0,1…,N в N+1 в узле.

Кубический сплайн, принимающий в узлах те же значения , что и некоторая функция, называется интерполяционным и служит для аппроксимации функции f на отрезке [a,b] вместе с несколькими производными.

Существует несколько способов задания наклонов интерполяционного кубического сплайна.

Способ 1 (упрощенный):

, i=1,2,…, N-1, (2)

, (3)

Данные формулы являются формулами численного дифференцирования второго порядка точности относительно шага h=(b-a)/N.

Если у нас имеются значения производной в узлах , то полагаем , i=0,1,…,N.

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

Способ 3 (глобальный):

Пусть — значение в узле справа, его мы найдем из выражения (1), а значение в узле слева – оно находится из соответствующего выражения на частичном отрезке [,], которое получается из (1) заменой i на i-1.

Потребуем непрерывность в узлах:

, i=1,2,…, N-1.

Тогда получим систему линейных алгебраических уравнений относительно наклонов:

(4)

Так как система содержит N+1 неизвестных, необходимо задать два дополнительных условия, называемые краевыми.

Приведем три варианта задания краевых условий:
1) В случае, когда известны задаем

, .

2) Производные , аппроксимируем формулами численного дифференцирования третьего порядка точности:

(6)

3) Иногда бывают известны значения на концах отрезка [a,b], т.е. величины . Тогда требования приводят к краевым условиям

(7)

Система (4) при всех рассмотренных краевых условиях имеет единственное решение, которое можно найти с помощью методов прогонки и итераций.

Таким образом, решая систему (4) при выбранных краевых условиях, находим наклоны i=0,1,…,N, во всех узлах. Затем по формуле (1) задаем сплайн на каждом частичном отрезке [,], i=0,1,…,N-1. Построенный данным глобальным способом сплайн имеет дефект не больше единицы, так как этот сплайн обладает на отрезке [a,b] непрерывной второй производной .

В.П.Боровиков. STATISTICA. Искусство анализа данных на компьютере: для профессионалов (2-е издание), СПб.: Питер, 2003. – 688 с.: ил.

E.A.Волков. Численные методы. Москва, “Наука”, Главная редакция физико-математической литературы, 1987 г.

Источник

Сплайны и их применение

Автор работы: Пользователь скрыл имя, 19 Мая 2012 в 10:32, курсовая работа

Краткое описание

Функции, подобные тем, что сейчас называют сплайнами были известны математикам давно, начиная как минимум с Эйлера, но их интенсивное изучение началось, фактически, только в середине XX века. В 1946 году Исаак Шёнберг впервые употребил этот термин в качестве обозначения класса полиномиальных сплайнов. До 1960 годов сплайны были в основном инструментом теоретических исследований, они часто появлялись в качестве решений различных экстремальных и вариационных задач, особенно в теории приближений.
После 1960 года с развитием вычислительной техники началось использование сплайнов в компьютерной графике и моделировании, что продолжается по сей день.

Содержание

ГЛАВА I. СПЛАЙНЫ…………………………………………………………..4
1.1 Кривые Безье…………………………………………………………4
1.2 Виды кривых Безье…………………………………………………..5
1.3 Построение кривых Безье…………………………………………. 7
1.4 Применение в компьютерной графике……………………………..9
1.5 Преобразование квадратичных кривых Безье в кубические…….10

ГЛАВА II. ФИНИТНЫЕ ФУНКЦИИ………………………………………11
2.1 Теория аппроксимации финитными функциями Стренга-Фикса………………………………………………………………..12

ГЛАВА III. В-СПЛАЙНЫ ШЁНБЕРГА……………………………………15

Список использованной литературы………………………………………..20

Вложенные файлы: 1 файл

СПЛАЙНЫ.doc

1.3 Построение кривых Безье…………………………………………. 7

1.4 Применение в компьютерной графике……………………………..9

1.5 Преобразование квадратичных кривых Безье в кубические…….10

ГЛАВА II. ФИНИТНЫЕ ФУНКЦИИ………………………………………11

2.1 Теория аппроксимации финитными функциями Стренга-Фикса…………………………………………… …………………..12

ГЛАВА III. В-СПЛАЙНЫ ШЁНБЕРГА……………………………………15

Список использованной литературы………………………………………..20

После 1960 года с развитием вычислительной техники началось использование сплайнов в компьютерной графике и моделировании, что продолжается по сей день.

Под сплайном (от англ. spline – планка, рейка) обычно понимают кусочно-заданную функцию, совпадающую с функциями более простой природы на каждом элементе разбиения своей области определения.

Классический сплайн одной переменной строится так: область определения разбивается на конечное число отрезков, на каждом из которых сплайн совпадает с некоторым алгебраическим полиномом. Максимальная степень из использованных полиномов называется степенью сплайна. Разность между степенью сплайна и получившейся гладкостью называется дефектом сплайна. Например, непрерывная ломаная есть сплайн степени 1 и дефекта 1.

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

Кривые Безье́ или Кривые Бернштейна-Безье были разработаны в 60-х годах XX века независимо друг от друга Пьером Безье и Полем де Кастельжо.

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

Впоследствии это открытие стало одним из важнейших инструментов систем автоматизированного проектирования и программ компьютерной графики.

Кривая Безье – параметрическая кривая, задаваемая выражением:

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

где n – степень полинома, i – порядковый номер опорной вершины

1.2 Виды кривых Безье:

При n = 1 кривая представляет собой отрезок прямой линии, опорные точки P0 и P1 определяют его начало и конец. Кривая задаётся уравнением:

2. Квадратичные кривые

Квадратичная кривая Безье (n = 2) задаётся 3-мя опорными точками: P0, P1 и P2:

Квадратичные кривые Безье в составе сплайнов используются для описания формы символов в шрифтах TrueType и в SWF файлах.

3. Кубические кривые

В параметрической форме кубическая кривая Безье (n = 3) описывается следующим уравнением:

Четыре опорные точки P0, P1, P2 и P3, заданные в 2-х или 3-мерном пространстве определяют форму кривой.

Линия берёт начало из точки P0 направляясь к P1 и заканчивается в точке P3 подходя к ней со стороны P2. То есть кривая не проходит через точки P1 и P2, они используются для указания её направления. Длина отрезка между P0 и P1 определяет, как скоро кривая повернёт к P3.

Рисунок 1 Кубическая кривая Безье

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

где называется базисной матрицей Безье:

В современных графических системах, таких как PostScript, Metafont и GIMP для представления криволинейных форм используются сплайны Безье, составленные из кубических кривых.

1.3 Построение кривых Безье

Параметр 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 Преобразование квадратичных кривых Безье в кубические

Квадратичная кривая Безье с координатами преобразовывается в кубическую кривую Безье с координатами:

ГЛАВА II. ФИНИТНЫЕ ФУНКЦИИ

Подобласти получили название конечные элементы.

Отметим преимущества такого выбора базиса:

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

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

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

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

На все эти вопросы частично дает ответ теория Стренга-Фикса.

2.1 Теория аппроксимации финитными функциями Стренга-Фикса

Изложим основные идеи этой теории для функций одной переменной с регулярными конечными элементами.

Область покрываем равномерной сеткой

Если «стандартная» функция нормирована к единице, то ее сдвиги записываются в виде

Теорема Стренга-Фикса (один из вариантов)

Допустим, что для преобразования Фурье стандартной финитной функции выполнено условие

(т.е. в точках имеет нули й кратности).

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

ГЛАВА III. В-СПЛАЙНЫ ШЁНБЕРГА

В вычислительной математике B-сплайном называют сплайн-функцию, имеющую наименьший носитель для заданной степени, порядка гладкости и разбиения области определения. Фундаментальная теорема устанавливает, что любая сплайн-функция для заданной степени, гладкости и области определения может быть представлена как линейная комбинация B-сплайнов той же степени и гладкости на той же области определения. Термин B-сплайн был введён И. Шёнбергом и является сокращением от словосочетания «базисный сплайн». B-сплайны могут быть вычислены с помощью алгоритма де Бора, обладающего устойчивостью.

Источник