Рассмотрение общего понятия сплайна. Общие понятия и определения кубического сплайна дефекта, его построение и оценка погрешности интерполяции. Определение метода учета величины скачка функции или ее производных при построении кубического сплайна.
Определение: Функция называется сплайном степени n дефекта ? (? - целое число, 0???n 1) с узлами на сетке ?, если А) на каждом отрезке функция является многочленом степени n, то есть для x , i=0, …, N-1 (1) Кубическим сплайном дефекта 1 для функции f(x) называется функция S(x), которая: на каждом отрезке [xi - 1,xi] является многочленом степени не выше третьей; в точках xi выполняется равенство S(xi) = f(xi), т. е. сплайн S(x) интерполирует функцию f в точках xi , i = 0, 1, 2,…, N. Как видно из графика, в случае с функцией sin(x) сплайн ведет себя так же как функция, однако в случае с |sin(x)| появляются расхождения в области точки разрыва производной. //находим c1 и с2 segments[i].c1 = c_function(a1, a2, segments[i].f, segments[i].f1, segments[i].f2, points[i 1].y, points[i 1].y1, points[i 1].y2, segments[i].h);Целью данной работы был анализ методов интерполяции разрывных функций, а также функций, имеющих разрыв производных до второго порядка включительно, с помощью кубических сплайнов дефекта 1. Были рассмотрены следующие варианты: Естественный кубический сплайн; Кроме того, были проанализированы практические реализации вышеуказанных методов, разработанные с помощью языка С# и платформы .NET. Однако, следует учитывать, что для некоторых задач, где требуется высокая точность вычислений представленные реализации следует использовать с осторожностью, в силу возможных ошибок вычисления, связанных с реализацией компилятора и чисел с плавающей запятой. В ходе практического анализа было выведено: для разрывных функций лучше всего применять метод введения скачка, однако в случае с разрывами производных его применение является не очень целесообразным, т.к. при достаточно малом шаге, при выборе узлов сетки, работа метода мало отличается от естественного кубического сплайна.
Введение
сплайн кубический дефект интерполяция
Большинство численных методов решения задач математического анализа так или иначе связано с аппроксимацией функций. Типичной задачей аппроксимации является задача интерполяции: по заданной таблице чисел восстановить функцию с той или иной точностью на заданном отрезке действительной оси. Классический метод решения такой задачи состоит в построении интерполяционного многочлена Лагранжа. Хотя согласно теореме Вейерштрасса всякая непрерывная функция на заданном отрезке может быть как угодно хорошо приближена многочленами, практические возможности применения многочленов Лагранжа ограничены. В ряде случаев происходит быстрое накопление ошибок округления и весьма усложняется вычислительный процесс. Поэтому на практике для того, чтобы достаточно хорошо приблизить функцию, вместо построения интерполяционного многочлена высокой степени используют интерполяцию кусочными многочленами. Примером такого рода является кусочно-линейная интерполяция. В общем случае отрезок разбивается точками на промежутки, и на каждом промежутке строится свой интерполяционный многочлен. Полученные таким образом многочлены дают интерполяцию функции на всем отрезке, которая, вообще говоря, не обеспечивает гладкого перехода от одного звена к другому и может быть даже разрывной. Это допустимо, если не требуется восстанавливать функцию с заданной степенью гладкости. Для гладкого восстановления заданной функции нужно увеличить степень составляющих многочленов, а остающиеся свободными коэффициенты определять из условий гладкого сопряжения многочленов на соседних промежутках. Получающиеся при этом гладкие кусочно-многочленные функции с однородной структурой (составленные из многочленов одной и той же степени) называются сплайн-функциями или просто сплайнами.
Алгоритмы построения сплайнов являются довольно простыми и эффективно реализуются на ЭВМ, причем влияние ошибок округления при вычислениях оказывается незначительным.
Бурное развитие теории сплайн-функций одной переменной как аппарата численного анализа было обусловлено главным образом двумя причинами: 1) хорошей сходимостью сплайнов к аппроксимируемым объектам; 2) простотой в реализации алгоритмов построения сплайнов на ЭВМ.
Опыт применения сплайн-функций как аппарата приближения функций в численном анализе показывает, что во всех известных случаях удавалось добиться ощутимых результатов по сравнению с классическим аппаратом многочленов. В одних задачах переход к сплайнам приводит к повышению точности результатов, в других - к значительному сокращению вычислительных затрат, в третьих - достигаются оба эффекта одновременно. Наконец, с помощью сплайнов удалось решить и такие задачи, которые другим путем решить было бы невозможно. Среди них на первом месте стоит проблема представления и хранения геометрической информации в самых различных областях знания, будь то естественные науки, техника, архитектура, картография. Применение для данных целей сплайнов позволяет хранить геометрическую информацию в числовой форме и с любой точностью. Особенно широкое применение получили сплайны в технике как аппарат для математического моделирования поверхностей деталей и агрегатов сложной формы. Такие математические модели стали необходимыми при создании систем автоматизации проектирования изделий на основе ЭВМ, технологической подготовки их производства, включая разработку программ для оборудования с цифровым программным управлением. Область применения сплайнов непрерывно растет.
Общее понятие сплайна
Пусть на отрезке [a, b] задано разбиение ?; . Для целого k?0 через обозначим множество k раз непрерывно дифференцируемых на [a, b] функций, а через - множество кусочно-непрерывных функций с точками разрыва первого рода.
Определение: Функция называется сплайном степени n дефекта ? (? - целое число, 0???n 1) с узлами на сетке ?, если А) на каждом отрезке функция является многочленом степени n, то есть для x , i=0, …, N-1 (1)
Б) .
Кубический сплайн дефекта 1
Общие понятия и определения
В данной работе будут рассмотрены кубические сплайны дефекта 1, являющиеся дважды непрерывно дифференцируемыми функциями. Хорошие аппроксимативные свойства в сочетании с простотой реализации на ЭВМ сделали их эффективным средством решения самых разнообразных прикладных задач. В дальнейшем в работе будем называть такие сплайны кубическими без указания дефекта.
Пусть некоторая функция f(x) задана на промежутке [a,b], разбитом на отрезки [xi ? 1,xi], a = x0 < x1 < ... < XN = b. Точки разбиения xi назовем узлами сетки разбиения. Кубическим сплайном дефекта 1 для функции f(x) называется функция S(x), которая: на каждом отрезке [xi ? 1,xi] является многочленом степени не выше третьей;
имеет непрерывные первую и вторую производные на всем отрезке [a,b];
в точках xi выполняется равенство S(xi) = f(xi), т. е. сплайн S(x) интерполирует функцию f в точках xi , i = 0, 1, 2,…, N.
Сплайн S(x) на каждом из отрезков [xi ? 1,xi] определяется четырьмя коэффициентами, и поэтому для его построения на всем промежутке [a,b] необходимо определить 4N коэффициентов. Условие 2) эквивалентно требованию непрерывности сплайна и его производных до второго порядка включительно во всех внутренних узлах xi , i = 1, 2,…, N-1, что дает 3(N-1) равенств. Таким образом, вместе с равенствами 3) получается 4N - 2 соотношений. Для однозначного построения сплайна необходимы два дополнительных условия, которые обычно задаются в виде ограничений на значения сплайна и его производных на концах промежутка [a,b] (или вблизи концов) и называются краевыми условиями. Существует несколько различных видов краевых условий, наиболее употребительными из которых являются
Условия типа III носят название периодических. Естественно требовать их выполнения в том случае, когда интерполируемая функция периодическая с периодом
T = ( b-a).
Зачастую используют условие II, дополнительно требуя нулевой кривизны сплайна на концах отрезка, т. е.
S""(a) = S""(b) = 0.
Такой кубический сплайн называется естественным.
Построение
Обозначим: hi = xi ? xi ? 1
На каждом отрезке [xi ? 1,xi] функция S(x) есть полином третьей степени Si(x), коэффициенты которого надо определить. Запишем для удобства Si(x) в виде:
тогда
Условия непрерывности всех производных до второго порядка включительно записываются в виде а условия интерполяции в виде
Отсюда получаем формулы для вычисления коэффициентов сплайна:
Если учесть, что c0 = cn = 0, то вычисление c можно провести с помощью метода прогонки для трехдиагональной матрицы.
Оценка погрешности интерполяции
Пусть S(x) - интерполяционный сплайн, удовлетворяющий условиям 1) - 3). Если f(x) - периодическая, то естественно подчинить S(x) периодическим краевым условиям (тип III). При интерполяции непериодических функций на C[a,b] будем использовать разностный аналог краевых условий типа I: (1)
Обозначим
Теорема 1. Если f(x) C[a,b] и S(x) удовлетворяет краевым условиям (1) или условиям типа III, то (2)
Особенностью полученной оценки является зависимость коэффициента при от отношения максимального и минимального шагов сетки. Сформулируем другую оценку, в которой этот коэффициент зависит от величины
, характеризующей соотношение соседних шагов сетки.
Теорема 2. Если f(x) C[a,b] и S(x) удовлетворяет краевым условиям (1) или условиям типа III, то (5) где n - положительное целое число, , - положительный корень уравнения
(6)
Полученная оценка (5) зависит от целочисленного параметра n. При n=1 уравнение (6) переходит в уравнение
, откуда . С ростом n величина монотонно возрастает, и при из (6) имеем что дает предельное значение
При практическом использовании оценки (5) простым перебором находим такое n, чтобы при выполнении условия дробь в коэффициенте при имела наименьшее значении. Например, при это будет n=1.
Теорема 3. Если f(x) [a,b] и S(x) удовлетворяет краевым условиям (1) или условиям типа III, то
Где
Примеры
Естественный кубический сплайн функции sin(x) с шагом h = 0.2
На графике сплайн полностью совпадает с функцией
Естественный кубический сплайн функции |sin(x)| с шагом h = 0.2
Как видно из графика, в случае с функцией sin(x) сплайн ведет себя так же как функция, однако в случае с |sin(x)| появляются расхождения в области точки разрыва производной.
Функция |sin(x)|, но уже с шагом h=0.025
С уменьшением шага расхождения тоже уменьшаются, но все же остаются.
Код решения на C# class SPLINEBUILDER : Builder
{
SPLINESEGMENT[] segments;
List points;
int n;
///
/// Конструктор SPLINEBUILDER
///
/// Количество узлов сетк
/// Значения в узлах public SPLINEBUILDER(int _n, List _points)
{ return double.NAN; // Если сплайны еще не построены - возвращаем NAN
} int n = segments.Length;
SPLINESEGMENT s;
if (x <= segments[0].x) // Если x меньше точки сетки x[0] - пользуемся первым эл-тов массива
{ s = segments[1];
} else if (x >= segments[n - 1].x) // Если x больше точки сетки x[n - 1] - пользуемся последним эл-том массива
{ s = segments[n - 1];
} else // Иначе x лежит между граничными точками сетки - производим бинарный поиск нужного эл-та массива
{ int i = 0;
int j = n - 1;
while (i 1 < j)
{ int k = i (j - i) / 2;
if (x <= segments[k].x)
{ j = k;
} else
{ i = k;
}
} s = segments[j];
} double dx = x - s.x;
// Вычисляем значение сплайна в заданной точке по схеме Горнера (в принципе, "умный" компилятор применил бы схему Горнера сам, но ведь не все так умны, как кажутся) return s.a (s.b (s.c / 2.0 s.d * dx / 6.0) * dx) * dx;
}
}
Кубические сплайны с дополнительными узлами
Теория и построение
Если по условиям задачи, помимо значений функции, требуется интерполировать и ее производные до некоторого порядка, то для решения подобных задач приходится либо переходить к сплайнам с меньшей гладкостью (с большим дефектом), либо повышать из степень. Однако, существует способ, позволяющий избежать ряда затруднений путем введения узлов сплайна, не являющихся узлами интерполяции. Такие конструкции принято называть сплайнами с дополнительными узлами. Их использование не приводит к увеличению размерности решаемых алгебраических систем, а только к некоторому усложнению элементов матрицы правых частей.
Пусть на отрезке [a,b] требуется интерполировать некоторую функцию f(x) по известным значениям , r = 0,1,2 ,на сетке ?: a= =b. Обычно для решения такой задачи используют сплайны пятой степени с узлами на сетке ?, но можно применить кубические сплайны с дополнительными узлами. Для этого введем на [a,b] еще одну сетку ? = { , где .
Кубический сплайн S(x) дефекта 1 с узлами на сетке , удовлетворяющий условиям для (1) назовем локальным кубическим сплайном с дополнительными узлами.
Условия интерполяции (1) на концах промежутков [ ,дают N линейных систем, по 6 уравнений в каждой, для определения коэффициентов сплайна, решая которые получаем при
(2) с коэффициентами
.
Оценка погрешности локальной интерполяции
Приведем оценку точности приближения функции f(x) сплайном S(x) в зависимости от ее дифференциальных свойств. В данном случае константы в оценках будут зависеть от параметра . В силу сложности получаемых выражений приведены результаты только для фиксированного .
Теорема 1. Если S(x) интерполирует на сетке ? функцию f(x), то имеют место оценки
(1) где при даны в таблице 1
Класс функций
Класс функций
-
-
Придавая параметру различные конкретные значения можно выяснить характер зависимости констант в получающихся оценках от . Естественно было бы выбирать оптимальные значения , при котором константы принимают наименьшие значения, однако в большинстве случаев оптимальные константы в оценках мало отличаются от соответствующих констант при
Примеры
Функция |sin(x)|, h = 0.2
Как видно из графика, несмотря на теоретическое обоснование, график сплайна испытывает серьезные осцилляции при подходе к точке разрыва производной слева, однако надо заметить, что справа осцилляции полностью отсутствуют. К таким результатам привели неточности вычисления чисел с плавающей запятой, потому при использовании этого метода надо учитывать подобные ошибки вычислений.
Та же функция, но с шагом h=0.025
На графике видно, что изменение порядка шага дало значительно лучшие результаты, хотя ошибки вычисления все равно могут присутствовать
Код решения на C# class EXTRASPLINE : Builder
{ public double a1;
public double a2;
EXTRASPLINESEGMENT[] segments;
List points;
int n;
public EXTRASPLINE(int _n, List _points, double _a1, double _a2)
{ n = _n;
a1 = _a1;
a2 = _a2;
points = _points;
segments = new EXTRASPLINESEGMENT[n-1];
for (int i = 0; i < n-1; i)
{ segments[i].x = points[i].x;
segments[i].f = points[i].y;
segments[i].f1 = points[i].y1;
segments[i].f2 = points[i].y2;
//находим h segments[i].h = points[i 1].x - points[i].x;
Метод учета величины скачка функции и/или ее производных при построении кубического сплайна.
Теория и построение
Пусть кубический сплайн, обеспечивающий непрерывность функции и ее производных первого и второго порядков, имеет вид: (1)
В узлах сетки
(2)
Коэффициенты определяются из условия непрерывности первой и второй производных во внутренних узлах и из граничных условий, предполагая нулевую кривизну сплайна на концах отрезка:
Коэффициенты находятся методом прогонки приведенной выше системы, так как матрица системы трехдиагональна:
(5)
При наличии разрывов производных интерполируемой функции выбор узлов помогает управлять свойствами сплайнов.
В частности, если третья производная функции терпит разрыв в некоторых точках отрезка [a,b], то для улучшения качества аппроксимации эти точки следует включить в число узлов интерполяции.
Если разрывна вторая производная , то для того, чтобы избежать осцилляции сплайна вблизи точек разрыва, необходимо принять специальные меры. Обычно узлы интерполяции выбирают так, чтобы точки разрыва второй производной попадали внутрь промежутка , такого, что , где
Если первая производная разрывна, следует разбить отрезок аппроксимации на промежутки, где производная непрерывна, и на каждом из этих промежутков построить сплайн.
Такие процедуры позволяют улучшить сходимость интерполяционной функции, однако они усложняют процедуру интерполяции за счет существенного увеличения числа узлов интерполяции.
Рассмотрим другую возможность учета разрывов как самой функции, таки и ее производных, которая заключается во введении величины скачка в систему уравнений (2-5) для определения коэффициентов кубического сплайна.
При наличии разрывов функции в некоторых точках отрезка [a,b] внесем следующие изменения в построение сплайна. Значение сплайна и/или его производных слева от точки разрыва принимаем равным значению интерполируемой функции в этом узле слева, а величину скачка относим к последующему сплайну. Таким образом, для нахождения коэффициентов в узлах, соответствующих разрывам, вместо (2-5) имеем следующую систему уравнений:
Такой метод учета разрывов позволяет интерполировать функции без увеличения количества узлов и с наименьшей осцилляцией возле разрыва, что значительно упрощает использование сплайнов.
Примеры
Для сравнения взята кусочно-заданная функция, которая при x2,4 y = -x^2
Это естественный кубический сплайн h = 0.2
А это уже сплайн, с учетом скачка, по графикам видно, что осцилляции, хоть и не ушли, но заметно уменьшились.
Та же функция, но с шагом h = 0.025
Естественный кубический сплайн
Сплайн с учетом скачка, с таким шагом осцилляции слева от точки разрыва практически отсутствуют, а справа хоть и остались, но стали заметно меньше.
Код решения на C# class SPLINED : Builder
{
SPLINESEGMENT[] segments;
List points;
int n;
///
/// Конструктор SPLINEBUILDER
///
/// Количество узлов сетк
/// Значения в узлах public SPLINED(int _n, List _points, List _extremums)
{ double D = 0;
n = _n;
points = _points;
foreach (POINTEXTREMUM p in _extremums)
{ int k = n - 1;
for (int i = 0; i < k; i)
{ if (p.p.x > points[i].x && p.p.x < points[i 1].x)
Рассмотрим кубический интерполяционный сплайн для . Пусть и - кубический сплайн с узлами ), интерполирующий в точках , т.е. ; в каждом является алгебраическим многочленом третей степени, удовлетворяющим краевым условиям или и ( . Тогда в окрестности точки a имеет место эффект Гиббса, точнее
Теорема. Для
Следствие. Для имеем при (число узлов)
Обозначим через Q класс функций , кусочно-непрерывных на промежутке , которые имеют на нем конечное число разрывов I рода, . Для любой справедливо
Так как интерполяционный оператор является линейным оператором, то из сходимости интерполяционных кубических и параболических сплайнов при равномерной сетке для любой непрерывной функции получаем: Теорема. Пусть , тогда для параболической и кубической сплайн-интерполяции при равномерной сетке и при нулевых краевых условиях для вторых производных сплайна в концах интервала имеем сходимость интерполяционного сплайна к функции ( - число узлов интерполяции)
В точках разрывов функции имеет место эффект Гиббса величиной скачка для параболического и для кубического сплайнов.
При интерполяции функции со скачками кубическим сплайном класса возникают вблизи точки разрыва осцилляции, амплитуда которых при не затухает, а стремится к константе. Это явление называется эффектом Гиббса.
Для кубического сплайна с дополнительными узлами эффект Гиббса отсутствует точка разрыва в середине интервала.
Осцилляция ослабляется при уменьшении . При имеем эрмитов кубический сплайн, который не имеет осцилляций.
Примеры
Естественный сплайн для параметрической функции, описанной выше, h=0.2
А это сплайн с дополнительными узлами для той же функции.
Из графиков видно, что у сплайна с дополнительными узлами отсутствуют осцилляции в области точки разрыва, однако видны ошибки вызванные вычислениями при подходе слева к точке разрыва.
Вывод
Целью данной работы был анализ методов интерполяции разрывных функций, а также функций, имеющих разрыв производных до второго порядка включительно, с помощью кубических сплайнов дефекта 1.
Были рассмотрены следующие варианты: Естественный кубический сплайн;
Кубический сплайн с дополнительными узлами;
Метод введения величины скачка в построение кубического сплайна.
Для некоторых случаев приведена теоретическая оценка погрешностей интерполяции.
Кроме того, были проанализированы практические реализации вышеуказанных методов, разработанные с помощью языка С# и платформы .NET.
Для каждого метода были разработаны соответствующие алгоритмы, собранные в единый проект. Однако, следует заметить, что каждый разработанный алгоритм является полностью самостоятельным и может быть использован в любой другой программе. Также, для наглядности в проект была включена графическая составляющая, представляющая собой график интерполируемой функции и график соответствующего сплайна. Для графического представления в проекте была использована библиотека ZEDGRAPH.
Реализованные методы применимы для решения задач интерполяции, где требуется высокая скорость вычислительных процессов и/или низкая затратность ресурсов ЭВМ.
Однако, следует учитывать, что для некоторых задач, где требуется высокая точность вычислений представленные реализации следует использовать с осторожностью, в силу возможных ошибок вычисления, связанных с реализацией компилятора и чисел с плавающей запятой. Такими задачами, например, могут быть задачи анализа экономических процессов или каких-либо финансовых вычислений.
В ходе практического анализа было выведено: для разрывных функций лучше всего применять метод введения скачка, однако в случае с разрывами производных его применение является не очень целесообразным, т.к. при достаточно малом шаге, при выборе узлов сетки, работа метода мало отличается от естественного кубического сплайна. Что касается метода с дополнительными узлами, то, несмотря на теоретическое обоснование, его реализация на ЭВМ порождает дополнительные погрешности, которые в некоторых случаях сводят на нет суть метода, а в отдельных заметно ухудшают результаты. Хотя метод с дополнительными узлами можно использовать, если проводить интерполирование не всего интересующего промежутка, а частей, на которых интерполируемая функция непрерывная вплоть до второй производной. Также возможна реализация метода с дополнительными узлами с помощью других стандартов представления чисел с плавающей запятой, которая, возможно, даст лучшие результаты.
Список литературы
1.Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л. Методы сплайн-функций - Москва: Наука 1980
2. Е.С. Полубояринова, Г.З. Шарафутдинов Об интерполяции разрывных функций при помощи сплайнов -Москва: Информационные технологии и программирование, межвузовский сборник статей, выпуск 2(11). 2004
3. Роджерс Д., Адамс Дж. Математические основы машинной графики. -М.: Мир, 2001
4. Е. П. Жидков, А. С. Андреев, В. А. Попов Эффект Гиббса для сплайн-интерполяции и для численного решения интегральных уравнений методом сплайн-коллокации - Дубна: ОИЯИ 1983
Размещено на .ru
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
