Приближение функций с помощью сплайнов

Содержание
Введение.............................................................................................................3
Глава 1. Сущность понятия сплайнов..............................................................4
Глава 2. Интерполяция с помощью кубического сплайна.............................7
Глава 3. Нормализованные базисные сплайны и представление ими многочленов...............................................................................................................10
Глава 4. Кривые Безье.....................................................................................13
Заключение.......................................................................................................17
Список использованных источников.............................................................18

Введение
Аппроксимация функций состоит из оценок, которые заменяют функцию, задаваемую f (x), функцией j (x), в результате чего функция j (x) отклоняется от f (x) в данной области. Функция j (x) в этом случае называется приближенной оценкой. Распространенная проблема с функцией подсчета – проблема интерполяции. Большая часть интерполяции требуется по двум причинам:
. Функция f (x) имеет сложные аналитические объяснения, которые вызывают трудности при использовании (например, f (x) - это специальная функция: гамма-функция, эллиптическая функция и т. Д.).
2. Аналитическое описание функции f (x) неизвестно. В этом случае необходимо иметь сопроводительное аналитическое описание, представляющее f (x) (например, для вычисления значения f (x) в точках арбитража, для оценки интеграла и производной f (x) и т. д.).
Алгоритм построения кубических кривых очень прост и может быть эффективно реализован на компьютере, в то время как влияние ограниченных ошибок в расчетах невелико.
Целью нашей работы является рассмотрение приближения функций с помощью сплайнов.
Задачи, которые мы ставим перед собой:
•Рассмотреть сущность понятия сплайнов;
•Выявить интерполяцию с помощью кубического сплайна;
•Изучить нормализованные базисные сплайны и представление ими многочленов;
•Рассмотреть  кривые Безье.
Глава 1. Сущность понятия сплайнов
Интерполяция – математически расчет того, как найти промежуточное значение количества набора существующих известных значений. Решение задач с научными и инженерными расчетами обычно требует набора значений, полученных экспериментальным путем или путем случайной выборки.
Как правило, на основе этого набора необходимо построить функцию, которая может с высокой точностью получать другие требуемые значения. Эта проблема называется оценкой функции.
Интерполяция – это оценка функции, в которой кривые функции построены так, чтобы соответствовать доступным точкам данных.
Сплайн – это функция, область, которая разделена на ограниченное количество частей, каждый сплайн соответствует нескольким алгебрам полиномов. Максимальная используемая степень полинома называется степенью сплайна. Разница между степенью сплайна и результирующей регулярностью называется дефектом сплайна [1].
Сплайны позволяют эффективно решать экспериментальные задачи по работе с зависимостями между параметрами, имеющими довольно сложную структуру.
Теория сплайн-интерполяции и термин «сплайн» перечислены в статье Исаака Якоба Шенберга 1946 года. Особенно интенсивное развитие произошло в 50-70-е годы. В настоящее время САПР стал традиционно прикладной областью, в которой используются допущения интерполяции.
Однако сплайны – это не только описание нескольких кривых. В реальном мире на неуклюжих слонов нападают быстрые карлики. В механике это деформация гибкой пластины или неподвижного стержня в одной точке; траектория тела, если сила заставляет его изменить больше шагов.
В термодинамике это перенос тепла в стержне, состоящем из разных фрагментов. В химии – расширение слоев на самые разные материалы. В электричестве – распространение электромагнитных полей в непонятных средах. То есть другой сплайн – это придуманная математическая абстракция, но во многих случаях это решение разностного уравнения, описывающего реальный физический процесс.
На рисунке 1 можно наблюдать квадратичный сплайн из шести полиномиальных сегментов. 
Рисунок 1 –  Квадратичный сплайн из шести полиномиальных сегментов
Между точками 0 и 1 проходит прямая линия. Между точками 1 и 2 - парабола со второй производной, равной 4. Между точками 2 и 3 - парабола со второй производной, равной −2. Между точками 3 и 4 проходит прямая линия. Между точками 4 и 5 проходит парабола со второй производной, равной 6. Между точками 5 и 6 проходит прямая линия.
Как отмечалось выше, существует ряд конструкций, называемых сплайнами. Таким образом, необходимо ввести определенные классификации этих видов, чтобы выделить характеристики [2].
Назначение сплайнов. По своему назначению можно выделить три основные группы сплайнов: «интерполяция сплайнов» или «функциональные сплайны» – проходит через заданные точки, «гладкие сплайны» – через заданные точки вычисляется ошибка определения.
«Корреляция сплайнов» – путем сопоставления точек и представления общих зависимостей (тренды, регрессии). Интерполяция и функциональные сплайны работают с проблемами геометрической модели, такими как определение контуров корпусов кораблей и самолетов. Сглаживающие сплайны часто используются для представления зависимости физического эксперимента от известной ошибки измерения. Корреляционные сплайны используются в качестве графиков нелинейной регрессии, простейшими из которых являются описания линейной функции и шага (нулевой диапазон и первая степень).
Кубические шлицы нашли широкое практическое применение (рисунок 2). Основная идея теории кубических канавок сформировалась в результате математических экспериментов по представлению гибких полос из эластичного материала (механических канавок), которые давно используются в тех случаях, когда необходимо провести достаточно гладкую кривую через определенная точка.
Рисунок 2 – Кубические сплайны
Следует отметить, что стержни изготовлены из гибкого материала, закреплены в нескольких точках и в положениях равновесия, что обеспечивает форму, в которой энергия минимальна. Это главное свойство позволяет эффективно использовать сплайны при решении практических задач обработки экспериментальной информации [3].
Глава 2. Интерполяция с помощью кубического сплайна
Сплайн с кубической интерполяцией, связанный с функцией, обозначенной f(x), и данной точкой xi, является функцией S(x), которая удовлетворяет следующим условиям:
1. На каждом сегменте [xi - 1, xi], i = 1, 2, ..., N функция S(x) является полиномом третьей степени,
2. Функция S(x), а также ее первая и вторая производные непрерывны на отрезке [a, b],
3. S(xi) = f(xi), i = 0, 1, ..., N.
На каждом из отрезков [xi - 1, xi], i = 1, 2, ..., N будем искать функцию S(x) = Si(x) в виде полинома третьей степени:
Si(x) = ai + bi(x - xi - 1) + ci(x - xi - 1)2 + di(x -1)3,                          
xi - 1 Ј x Ј xi,                                                          
где ai, bi, ci, di - коэффициенты определены во всех базовых сегментах. Чтобы система алгебраических уравнений имела решение, количество формул в точности совпадает с количеством неизвестных. Поэтому мы должны принять уравнение 4n.
Первые 2n уравнения мы получим из условия, что график функции S(x) должен проходить через заданные точки, т. е.
Si(xi - 1) = yi - 1, Si(xi) = yi.                                              
Эти условия можно записать в виде:
Si(xi - 1) = ai = yi - 1,                                                      
Si(xi) = ai + bihi + cih + dih = yi,                                             
где
hi = xi - xi - 1, i = 1, 2, ..., n.                                                   
Следующие уравнения 2n - 2 являются результатом условия непрерывности первой и второй производных в узлах интерполяции, то есть условия гладкости кривой во всех точках.
S' i + 1(xi) = S' i(xi), i = 1, ..., n - 1,                               
S' ' i + 1(xi) = S' ' i(xi), i = 1, ..., n - 1,                              
S' i (x) = bi + 2 ci (x - xi - 1) + 3 di (x - xi - 1),                    
S' i + 1 (x) = bi + 1 + 2 ci + 1 (x - xi) + 3 di + 1 (x — xi).            
Равным образом в каждой внутренней точке x = xi эти производные значения вычисляются в левом и правом интервалах точек  (с учетом hi = xi - xi - 1):
bi + 1 = bi + 2 hi ci + 3h di, i = 1, ..., n - 1,                       
S' ' i(x) = 2 ci + 6 di (x - xi - 1),
S' ' i + 1(x) = 2 ci + 1 + 6 di + 1 (x - xi),
если x = xi
ci + 1 = ci + 3 hi di, i = 1,2, ..., n - 1.
На данный момент у нас есть 4n неизвестных и 4n - 2 формулы. Следовательно, необходимо найти еще два уравнения.
При свободном присоединении концов изогнутую линию в этой точке можно соединить с нулем. Из состояния нулевой кривой в конце следует, что вторая производная равна нулю в этих точках:
S1' ' (x0) = 0 и Sn' ' (xn) = 0,
ci = 0 и 2 cn + 6 dn hn = 0.
Уравнения составляют систему линейных алгебраических уравнений для определения 4n коэффициентов: ai, bi, ci, di (i = 1, 2, ..., N).
Эту систему можно довести до более практичного вида. Все коэффициенты ai находятся непосредственно из условия.
Тогда получаем:
i = 1, 2, ..., n - 1,
Подставляя, получим:
bi = - (ci + 1 + 2ci) , i = 1,2, ..., n - 1,                              
bn = - (hn cn)
Исключаем из уравнения коэффициенты bi и di. В итоге только для коэффициентов ci получаем следующую систему уравнений:
c1 = 0 и cn + 1 = 0:
hi - 1 ci - 1 + 2 (hi - 1 + hi) ci + hi ci + 1 = 3 ,
i = 2, 3, ..., n.
По найденным коэффициентам сi легко вычислить di ,bi.
Глава 3. Нормализованные базисные сплайны и представление ими многочленов
В практических расчетах удобнее использовать не сами кривые B, а функции, полученные из них умножением на постоянные коэффициенты:                                                                                                                           
Эти функции называются нормализованными B-сплайнами. Нормирующий коэффициент равен среднему арифметическому шагов:                                                                                                                           
Представим первые четыре функции этой последовательности для случая равноудаленных узлов hi = h.
Следует отметить, что степени многочлена Pn (x) являются наибольшим n-м элементом в пространстве сплайнов. В результате они могут быть представлены основаниями этих пространств, особенно основаниями B-сплайнов в пространстве. Для вывода формулы воспользуемся тождеством (8). После того, как мы умножили вторую часть на сумму и просуммировали по индексу i, мы получим:                                                                                                                           
где,                                                                                                                  
Справедливо тождество                                                                                                                        
Рисунок 3 – В-сплайны 
Доказательство. В формуле (10) подставим 
Подставляя в (9),                    находим 
Теперь разложим обе части тождества (11) по степеням t. При этом 
Здесь суть символы элементарных симметрических функций от n аргументов степени а. Это многочлены, состоящие из слагаемых. Они имеют вид 
Подставляя разложения и приравнивая коэффициенты при одинаковых степенях t, находим представления мономов Xa через нормализованные В-сплайны па отрезке [a,b]:                                                                                                                                                                                                          
Полученные формулы (12) решают вопрос о представлении произвольного многочлена п-й степени через нормализованные В-сплайны. 
Глава 4. Кривые Безье
Кривая Безье или кривая Бернштейна-Безье была независимо разработана Пьером Безье и Полем де Кастелло в 1960-х годах.
Кривая была впервые представлена публике в 1962 году французским инженером Пьером Безье, который сам сконструировал ее де Кастелло и использовал для компьютерного проектирования кузова автомобиля. Представляет кривую с именем Безье, а имя де Кастельхо было дано рекурсивному методу, который он разработал для определения кривой (алгоритм де Кастелло).
Более того, это изобретение стало одним из самых важных инструментов для систем АП и программ компьютерной графики.
Кривые Кривые – это параметрические кривые, определяемые выражением:                                                                                                                       
где, Pi– функция компонент векторов опорных вершин, 
bi,n– базисные функции кривой Безье, называемые также полиномами Бернштейна. 
Линейная кривая
При n = 1 кривая представляет собой прямой участок, точки привязки P0 и P1 определяют начало и конец. Кривая задается уравнением:                                                                                                                        
Квадратичные кривые
Квадратичная кривая Безье (n = 2) задаётся 3-мя опорными точками: P0, P1 и P2:                                                                                                                       
Квадратичные кривые Безье в составе сплайнов используются для описания формы символов в шрифтах TrueType и в SWF файлах. 
Кубические кривые
Четыре точки привязки P0, P1, P2 и P3, выраженные в 2- или 3-мерном пространстве, определяют форму кривой (рис. 4).
Маршрут начинается в P0, затем идет в сторону P1 и заканчивается в точке P3 рядом с ним на стороне P2. То есть кривые не пересекают точки P1 и P2, они используются для указания направления. Длина сегмента между точками P0 и P1 определяет, насколько быстро кривая поворачивается к точке P3.
Рисунок 4 – Кубическая кривая Безье 
Параметр t в функции, описывающей линейный случай кривой Безье, определяет, где именно расстояние от P0 до P1 равно B (t). Например, при t = 0,25 значение функции B (t) соответствует расстоянию между точками P0 и P1. Параметр t изменяется от 0 до 1, а B (t) описывает участок линии между точками P0 и P1 (Рисунок 5).
Рисунок 5 – Построение линейной кривой Безье 
Чтобы построить квадратную кривую, необходимо выбрать две промежуточные точки Q0 и Q1 из состояния изменения t, которое следует изменить с 0 на 1:
Точки Q0 находятся в диапазоне от P0 до P1 и описывают линейные кривые.
Точки Q1 находятся в диапазоне от P1 до P2 и также описывают линейные кривые.
Точка B проходит от Q0 до Q1 и описывает перевернутую квадратную кривую (рисунок 6).
Рисунок 6 – Построение квадратичной кривой Безье 
Каждая из более крупных промежуточных точек необходима для построения кривых более высокого порядка. Для кубических кривых это промежуточные точки Q0, Q1 и Q2, которые описывают линейные кривые, а также точки R0 и R1, которые представляют собой квадратную кривую: простейшее уравнение: p0q0 / p0q1 = q1p1 / p1p2 = bq0 / q1q0 (рисунок 7).
Рисунок 7 – Построение кубической кривой Безье 
Из-за простоты определения и обработки кривая Безье широко используется в компьютерной графике в моделях с плавными линиями. Весь поворот проходит на холме с точками от точки привязки [9].
С другой стороны, свойство кривой Безье упрощает поиск точек кривой между углами рисунка, когда они не закрыты, сама кривая не отклоняется), с другой стороны, оно позволяет интенсивно управлять параметрами кривой в графическом интерфейсе пользователя.
Преобразования кривой (перемещение, масштабирование, поворот и т. д.) Также можно выполнить, применив соответствующие преобразования к контрольным точкам.
Наиболее важной является кривая Безье второй и третьей степени (квадратная и кубическая). Кривые более высокого порядка требуют большего количества вычислений и реже используются в практических целях. [7]. 
Чтобы рисовать сложные линии, кривые Безье можно соединить друг с другом на границе Безье. Чтобы линия на пересечении двух кривых оставалась гладкой, три угла на двух кривых должны находиться на одной прямой.
Заключение
Таким образом, мы обнаружили, что интерполяция – математически – это вычисление того, как найти промежуточное значение из числа набора существующих известных значений. Решение задач с научными и инженерными расчетами обычно требует набора значений, полученных экспериментальным путем или путем случайной выборки.
Сплайн – это функция, область, которая разделена на ограниченное количество частей, каждый сплайн соответствует нескольким алгебрам полиномов. Максимальная используемая степень полинома называется степенью сплайна. Разница между степенью сплайна и полученной гладкостью называется дефектом сплайна.
Сплайны позволяют эффективно решать экспериментальные задачи обработки зависимостей между параметрами, имеющими довольно сложную структуру.
Кривая была впервые представлена публике в 1962 году французским инженером Пьером Безье, который сам сконструировал ее де Кастелло и использовал для компьютерного проектирования кузова автомобиля. Представляет кривую с именем Безье, а имя де Кастельхо было дано рекурсивному методу, который он разработал для определения кривой (алгоритм де Кастелло).
Поэтому мы справились с поставленными задачами, а именно:
•Рассмотрена суть концепции сплайна;
•Интерполяция выявлена с помощью кубического сплайна;
•Изучение нормированных базовых сплайнов и их представление полиномами;
•Рассмотрены кривые Безье.
Список использованных источников
1. Голубев Г. К., Крымова Е. А. Сплайны и стационарные гауссовские процессы // Доклады 9-ой Международной конференции «Интеллектуализация обработки информации». 2017. С. 207-211.
2. Голубев Г. К., Крымова Е. A. Splines and stationary Gaussian processes // Информационные технологии и системы - 2017 (ИТиС 2012): сб. трудов конференции. ИППИ РАН, 2017. С. 145-150.
3. Крымова Е. А. Оракульное неравенство для метода экспоненциального взвешивания упорядоченных оценок // Труды 55-й научной конференции МФТИ. МФТИ, 2017. С. 147-149. 
4. Лоран П.-Ж. Аппроксимация и оптимизация. МИР, 2015. С. 49 
5. Матвеев О. В. Интерполирование сплайнами и базисы в пространствах Соболева // Матем. сб. 2016. Т. 189, № 11. С. 75-102.
6. Матвеев О. В. Сплайн-интерполяция функций нескольких переменных и базисы в пространствах Соболева // Труды МИАН. 2016. Т. 198. С. 125-152.
7. Матвеев О. В. Аппроксимативные свойства интерполяционных сплайнов // Докл. АН СССР. 1991. Т. 321, № 1. С. 14-18.
8. Тихомиров В. Некоторые вопросы теории приближений. Москва: Наука, 2016. С. 304. 
9. Шадрин А. Ю. О приближении функций интерполяционными сплайнами, заданными на неравномерных сетках // Матем. сб. 2017. Т. 181, № 9. С. 1236-1255