Сплайн (от англ. spline, – гибкое лекало, гибкая плазовая рейка – полоса металла, используемая для черчения кривых линий) – функция, область определения которой разбита на конечное число отрезков, на каждом из которых сплайн совпадает с некоторым алгебраическим многочленом. Максимальная степень из использованных полиномов называется степенью сплайна. Разность между степенью сплайна и получившейся гладкостью называется дефектом сплайна. Например, непрерывная ломаная есть сплайн степени 1 и дефекта 1. В современном понимании сплайны – это решения многоточечных краевых задач сеточными методами.
Чтобы наглядно продемонстрировать приведенные понятия сплайна, степени сплайна и дефекта сплайна, рассмотрим следующую задачу: имеется совокупность экспериментальных данных, необходимо максимально точность аппроксимировать последовательность данных полиномиальной функцией n-го порядка с достоверностью не менее 95 %. В качестве базового выбираем метод полиномиальной аппроксимации с помощью так называемого сплайна Безье. Данный метод наиболее актуален для реализации в компьютерном алгоритме.
Сплайны (кривые) Безье или Кривые Бернштейна-Безье разработаны в 60-х годах XX века независимо друг от друга Пьером Безье из автомобилестроительной компании «Рено» и Полем де Кастельжо из компании «Ситроен», где применялись для проектирования кузовов автомобилей [1].
Кривая Безье относится к полиномам третьего порядка и уникально определяется четырьмя точками. Обозначим эти точки p0 (начальная), p1, p2 (две управляющие) и p3 (конечная). Обозначенные точки будут иметь координаты: (x0, y0), (x1, y1), (x2, y2) и (x3, y3). Полином третьего порядка, задающий координаты точек в двумерном пространстве, выражается параметрическими уравнениями общего вида:
(1)
Любая кривая Безье уникально определяется этими 8 константами. Их значения зависят от координат четырех точек, задающих кривую. Цель этой задачи – вывести уравнения для расчета восьми констант по заданным координатам четырех точек.
Первое допущение для вывода этих уравнений заключается в том, что кривая Безье начинается в точке с координатами (x0, y0) при t = 0:
(2)
(3)
(4)
(5)
Почему именно 1/3? Дело в том, что длина той части кривой Безье, по касательной к которой проходит прямая, проведенная из точки p0 через p1, направленная в ту же сторону, что и кривая, равна 1/3 от общей длины кривой. Первые производные модифицированных параметрических уравнений можно записать так:
(6)
(7)
(8)
(9)
(10)
(11)
На первом этапе разработки компьютерного алгоритма аппроксимации экспериментальных данных мы будем задавать кривую Безье визуальным способом, перемещая ее узловые точки в декартовой системе координат графической области экрана. Пример графического представления кривой Безье представлен на рисунке 1. Точки P0 и P3 – начальная и конечная точки кривой соответственно, P1 и P2 – управляющие точки (или точки направляющих отрезков).
Рисунок 1 – К построению кривой Безье
В качестве средства разработки выбираем среду программирования Microsoft Visual Basic 6.0. На рисунке 2 представлена форма графического интерфейса, включающая графическое поле для построения кривых, и панель параметров, расположенную в левой части формы.
Рисунок 2 – Графический интерфейс пользователя программы математической аппроксимации кривой Безье
С помощью указателя мыши пользователем задаются положения точек P0, P1, P2 и P3 сплайна Безье. Центр системы координат можно смещать, перемещая указатель мыши в графической области при нажатой правой кнопке мыши.
Далее проведем кривую полиномиальной функции n-го порядка по кривой построенного сплайна Безье. Целью данной процедуры является переход от параметрических уравнений сплайна Безье к аналитической функции вида y=f(x) при аппроксимировании данных. На панели параметров в левой части экрана пользователем выбирается степень n полиномиальной функции. От данного параметра зависит, сколько опорных точек будет выделено на сплайне Безье, через которые проходит полиномиальная кривая, и, следовательно, точность приближения полиномиальной кривой к сплайну, также будет зависеть от выбранной степени полинома.
Принцип построения полиномиальной кривой базируется на вычислении коэффициентов полинома:
(12)
Для вычисления коэффициентов Ci необходимо задать опорные точки на сплайне Безье, координаты которых вычисляются по известным параметрическим уравнениям Безье (10 и 11), и подставить координаты опорных точек (xi, yi) в уравнение (12). В таком случае мы получаем систему линейных уравнений с n неизвестными:
(13)
В представленном алгоритме система линейных уравнений вида (13) решается методом Крамера, подразумевающем преобразование системы уравнений в матрицы 3×3, 4×4, 5×5 и 6×6 для полиномиальной функции 2, 3, 4 и 5-го порядков, соответственно. Программно вычисления производятся с использованием двумерных массивов, в которые записываются столбцы основной и вспомогательных матриц Крамера, после чего производится вычисление их определителей, и находятся коэффициенты полиномиального уравнения.
В программе реализован алгоритм автоматической корректировки коэффициентов уравнения полинома. Сущность алгоритма заключается в цикличной проверке максимального расхождения полиномиальной кривой и кривой Безье в направлении оси Y (рисунок 3). Степень сплайна Безье es равна 3, а степень полиномиальной кривой ep выбирается пользователем (2, 3, 4 или 5). Теоретически, при ep ≥ es расхождение кривых сводится к нулю.
Рисунок 3 – К определению степени достоверности аппроксимации (до пересчета координат опорных точек)
С заданным шагом (по оси абсцисс) вычисляются длины вертикальных отрезков, соединяющих кривую полинома и кривую Безье (закрашенная область на рисунке 3). Длины указанных отрезков записываются в одномерный массив, после чего определяется и фиксируется наибольшая длина отрезка (максимальная величина расхождения кривых Δ). С помощью генератора случайных чисел задаются новые координаты опорных точек на кривой Безье, тем самым происходит их случайное смещение по сплайну, при этом каждая итерация заканчивается пересчетом величины Δ. Если после новой итерации величина Δ уменьшилась по сравнению с предшествующей, то полиномиальная кривая перестраивается. Визуально мы наблюдаем сближение полиномиальной кривой со сплайном Безье (рисунок 4).
Рисунок 4 – К определению степени достоверности аппроксимации (максимальное приближение аппроксимирующей кривой к сплайну Безье)
Разработанный алгоритм является эффективным инструментом для обработки эмпирических данных с использованием сплайнов. К примеру, если речь идет об интегральных кривых распределения, сплайном Безье можно задавать аппроксимирующую функцию, которая будет проходить через экспериментальные точки. При этом, конфигурация сплайна может задаваться не только ручным способом с помощью конечных и управляющих точек, а процедурно, путем проверки расходимости координат экспериментальных точек и точек, выделенных на сплайне с равной абсциссой. В конечном итоге мы получаем полиномиальную функцию n-й степени, которая будет максимально точно описывать последовательность эмпирических данных (например, как на рисунке 5).
Рисунок 5 – Схематичное представление процесса аппроксимации эмпирических данных
В случае аппроксимации интегральных кривых распределения на выходе работы алгоритма мы получаем функцию y(x), дифференцирование которой позволит построить закономерную дифференциальную гистограмму распределения dy(x) (например, как на рисунке 6).
Рисунок 6 – Построение дифференциальной гистограммы распределения по аппроксимирующей полиномиальной кривой
Библиографические ссылки:
[1] – Кривая Безье: Материал из Википедии – свободной энциклопедии: Версия 64994710, сохраненная в 23:11 UTC 22 августа 2014 // Википедия, свободная энциклопедия. – Электрон. дан. – Сан-Франциско: Фонд Викимедиа, 2014.