СПЛАЙН-ФУНКЦИИ
Сам термин "сплайн" происходит от английского spline. Именно так называется гибкая полоска стали, при помощи которой чертежники проводили через заданные точки плавные кривые. В былые времена подобный способ построения плав- нык обводов различных тел, таких, как, например, корпус корабля, кузов автомобиля, а потом фюзеляж или крыло самолета, был довольно широко распространен в практике машиностроения.
В результате форма тела задавалась при помощи набора очень точно изготовленных сечений — плазов. Появление компьютеров позволило перейти от этого, плазово-шаб- лонного, метода к более эффективному способу задания поверхности обтекаемого тела. В основе этого подхода к описанию поверхностей лежит использование относительно несложных формул сплайн-функций, позволяющих восстанавливать облик изделия с необходимой точностью. Рассмотрим сплайны, в построении которых используются кубические (для одномерных сплайнов — сплайновых кривых) и бикубические (для двумерных сплайнов сплайновых поверхностей) многочлены. В компьютерной графике подобные сплайны применяются наиболее часто.
Достаточно типичной является следующая задача: по заданному массиву точек на плоскости (2D) или в пространстве (3D) построить кривую, проходящую либо через все эти точки (задача интерполяции), либо вблизи от этих точек (задача сглаживания).
Совершенно естественно возникают вопросы: в каком классе кривых искать решение поставленной задачи? как искать?
А. Случай одной переменной. Обратимся для определенности к задаче интерполяции и начнем рассмотрение с обсуждения правил выбора класса кривык. Ясно, что допустимый класс кривык должен быть таким, чтобы решение задачи было единственным (это обстоятельство сильно помогает в преодолении многих трудностей поиска). Кроме того, желательно, чтобы построенная кривая изменялась плавно.
Пусть на плоскости задан набор точек (х/,уг), i = 0,1,...,т, таких, что xq lt; х\ lt;...
lt;хті lt; хт(рис. 4.32). КУо)
fomfYm)
ш
*
х
о
Рис. 4.32. Набор точек на плоскости
Благодаря тому, что точки заданного набора занумерованы в порядке возрастания их абсцисс, можно искать кривую в классе графиков функции, а основные моменты сглаживания этого дискретного набора описывать, ограничившись многочленами.
Как известно из курса математического анализа, существует интерполяционный многочлен Лагранжа:
![]()
где figt;m(x) = || .=0(x-JCy),
график которого проходит через все заданные точки (хг-, yi), i = 0,1,.. .,rn.
Это обстоятельство и простота описания (заметим, что многочлен однозначно определяется набором своих коэффициентов; в данном случае их число совпадает с количеством точек в заданном наборе) являются несомненными достоинствами построенного интерполяционного многочлена (разумеется, есть и другие).
Однако полезно остановиться и на некоторых недостатках предложенного подхода.
- Степень многочлена Лагранжа на единицу меньше числа заданных точек. Поэтому чем больше точек задано, тем выше степень такого многочлена. И хотя график интерполяционного члена Лагранжа всегда будет проходить через все точки массива, его уклонение (от ожидаемого) может оказаться довольно значительным.
- Изменение одной точки (ситуация, довольно часто встречающаяся на практике) требует полного пересчета коэффициентов интерполяционного многочлена и к тому же может существенно повлиять на вид задаваемой им кривой.
Приближенную кривую можно построить и совсем просто: если последовательно соединить точки заданного набора прямолинейными отрезками, то в результате получится ломаная (рис. 4.33).
![Рис.<div class=]()
4.33. Приближенная ломаная" /> Рис. 4.33. Приближенная ломаная
О
х
При такой, кусочно-линейной, интерполяции требуется найти всего 2т чисел (каждый прямолинейный отрезок определяется ровно двумя коэффициентами), но, к сожалению, построенная таким образом аппроксимирующая кусочно-линейная функция не обладает нужной гладкостью: уже первая производная этой функции терпит разрывы в узлах интерполяции.
Рассмотрев эти две крайние ситуации, попробуем найти класс функций, которые сохранили бы перечисленные выше достоинства обоих подходов и были бы в известной степени свободны от их недостатков.
Для этого будем использовать многочлены (как и в случае 1) и строить их последовательно, звено за звеном (как и в случае 2). В результате получится так называемый полиномиальный мно- гозвенник. При подобном подходе важно правильно выбрать степени привлекаемых многочленов, а для плавного изменения результирующей кривой необходимо еще тщательно подобрать коэффициенты многочленов (из условия гладкого сопряжения соседних звеньев). То, что получится в результате описанных условий, называют сплайн-функциями или просто сплайнами.
Для того чтобы понять, какое отношение имеют сплайн-функции к чертежным сплайнам, возьмем гибкую стальную линейку, поставим ее на ребро и, закрепив один из концов в заданной точке, поместим ее между опорами, которые располагаются в плоскости ОХУ в точках (х;-, у,), i = 0,1 ,..., т, где хо lt; xilt;...lt;xm_i lt;хт (рис. 4.34).
![Рис. 4.34. Приближение сплайном]()
Рис. 4.34. Приближение сплайном
Интересно отметить, что функция у - S(x). описывающая профиль линейки, обладает следующими свойствами:
- с довольно большой точностью часть графика этой функции, заключенную между любыми двумя соседними опорами, можно считать многочленом третьей степени;
- на всем промежутке [хо,хт] функция у = S(x) дважды непрерывно дифференцируемая.
Построенная функция S(x) относится к так называемым интерполяционным кубическим сплайнам.
Перейдем, однако, к точным формулировкам.
Интерполяционным кубическим сплайном называется функция S(x), обладающая следующими свойствами:
- график функции проходит через каждую точку массива, S(xi) =yi, - 0,1
- на каждом из отрезков [х/, x/+i], i - 0,l,...,rn-l, функция является многочленом третьей степени:
3) на всем отрезке задания [хо, хт] функция Д(хг) имеет непрерывную вторую производную.
На каждом из отрезков [т,-, Jt,+i] сплайн S(x) определяется четырьмя коэффициентами, поэтому для полного построения на всем отрезке задания необходимо найти 4т чисел.
Условие 3 будет выполнено, если потребовать непрерывности сплайнов во всех внутренних узлах х/, i = 0,l,...,rn-l (это дает т~\ условий на коэффициенты), а также его первой (m-і условий) и второй (еще т- \ условий) производных в этих узлах. Вместе с условием 1 получаем равенство
Недостающие два условия для полного определения коэффициентов можно получить, задав, например, значения первых производных на концах отрезка [то, хт] (граничные условия):
Существуют граничные условия и других типов.
Б. Случай двух переменных. Более сложная задача построения по заданному набору точек в трехмерном пространстве интерполяционной функции двух переменных решается похожим образом. Определим прежде всего интерполяционный бикубический сплайн.
Пусть на плоскости задан набор из (т + 1)(и + 1) точек (рис. 4.35)
(Xi, yji, і = 0,1 т; j = 0,
где -to lt; -V, lt; ...lt; хт-\ lt;Хт, ТО lt; Лlt; - -• lt;Ул-1 lt;Уп-
![Рис. 4.35. Набор (т + 1)(и + 1) точек на плоскости]()
Рис. 4.35. Набор (т + 1)(и + 1) точек на плоскости
Добавим к каждой паре (х/, yj) третью координату zy (х/, у у, гф. Тем самым получаем массив (х/ yj, гф, i = 0,1,..., га;/= 0,1,..., п.
Прежде чем строить поверхность, проходящую через все точки заданного массива, определим функцию, графиком которой будет эта поверхность.
Интерполяционным бикубическим сплайном называется функция двух переменных S (х, у), обладающая следующими свойствами:
- график функции проходит через каждую точку заданного массива: S(x,,y,) = Zj, i = 0,1,..., т-J = 0,1,..., и;
- на каждом частичном прямоугольнике [х/, Xj+1] x |у,-, y/+i],
i = 0,1,..., m-\;j= 0,1,..., и-1, функция представляет собой многочлен третьей степени по каждой из переменных:
- на всем прямоугольнике задания [хо, хт] х [уо, Уп] функция S(x, у) имеет по каждой переменной непрерывную вторую производную.
Для того чтобы построить по заданному массиву {(х,-, yj, гф} интерполяционный бикубический сплайн, достаточно определить все \6тпкоэффициентов. Как и в одномерном случае, отыскание коэффициентов сплайн-функции сводится к построению решения системы линейных уравнений, связывающих искомые коэффициенты afk.
Последняя возникает из условий 1 и 3, после добавления к ним недостающих соотношений путем задания значений произвольной искомой функции в граничных узлах прямоугольника [хо, хт] х [уоgt; Уп] (или ин^іх соображений).
Достоинства предложенного способа несомненны: для решения линейных систем, возникающих в ходе построения сплайн- функций, существует много эффективных методов, к тому же эти системы достаточно просты; графики построенных сплайн-функций проходят через все заданные точки, полностью сохраняя первоначально заданную информацию.
Вместе с тем изменение лишь одной точки (случай на практике довольно типичный) при описанном подходе заставляет пересчитывать заново, как правило, все коэффициенты.
Однако во многих задачах исходный набор точек задается приближенно, и, значит, требование неукоснительного прохождения графика искомой функции через каждую точку этого набора оказывается излишним. В этом случае используются методы сглаживания, при которых можно отказаться от требования строго однозначного проектирования искомой кривой на координатную ось, а поверхности — на координатную плоскость.
