Рассмотрим задачу проведения гладких кривых по заданным граничным точкам, или задачу интерполяции. Поскольку через две точки можно провести сколь угодно много гладких кривых, то для решения этой задачи необходимо ограничить класс функций, которые будут определять искомую кривую. Математическими сплайнами называют функции, используемые для аппроксимации кривых. Важным их свойством является простота вычислений. На практике часто используют сплайны вида полиномов третьей степени. С их помощью довольно удобно проводить кривые, которые интуитивно соответствуют человеческому субъективному понятию гладкости. Термин “сплайн” происходит от английского spline – что означает гибкую полоску стали, которую применяли чертежники для проведения плавных кривых, например, для построения обводов кораблей или самолетов.

Рассмотрим в начале сплайновую функцию для построения графика функции одной переменной. Пусть на плоскости задана последовательность точек , , причем . Определим искомую функцию , причем поставим два условия:

1) Функция должна проходить через все заданные точки: , .

2) Функция должна быть дважды непрерывно дифференцируема, то есть иметь непрерывную вторую производную на всем отрезке .

На каждом из отрезков , будем искать нашу функцию в виде полинома третьей степени:

.

Рис. 40. Сплайновая функция.

Задача построения полинома сводится к нахождению коэффициентов . Поскольку для каждого из отрезков необходимо найти 4 коэффициента , то всего количество искомых коэффициентов будет . Для нахождения всех коэффициентов определим соответствующее количество уравнений. Первые уравнений получаем из условий совпадения значений функции во внутренних узлах , . Следующие уравнений получаем аналогично из условий совпадения значений первых и вторых производных во внутренних узлах. Вместе с первым условием получаем уравнений. Недостающие два уравнения можно получить заданием значений первых производных в концевых точках отрезка . Так могут быть заданы граничные условия.

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

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

.

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

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

Перепишем выражение для в векторном виде:

.

Обозначим вектор строку и вектор столбец коэффициентов , тогда .

Из (*) следует, что , . Для касательных ,

Отсюда получаем векторно-матричное уравнение:

.

Эта система решается относительно нахождением обратной матрицы размером .

.

Здесь - эрмитова матрица, - геометрический вектор Эрмита. Подставим выражение для нахождения : . Аналогично для остальных координат: , .

Выпишем в явном виде формулы для вычисления координат точек сплайна. Так как , то умножая справа на , получаем:

.

Четыре функции в скобках называются функциями сопряжения.

Форму кривой, заданной в форме Эрмита, легко изменять если учитывать, что направление вектора касательной задает начальное направление, а модуль вектора касательной задает степень вытянутости кривой в направлении этого вектора, как показано на рис. 41.

Рис. 41. Параметрический сплайн в форме Эрмита. Вытянутость кривой вправо обеспечивается тем, что .

Рассмотрим форму Безье, которая отличается от формы Эрмита способом задания граничных условий, а именно, вместо векторов и вводятся точки (и соответствующие им радиус векторы) и , как показано на рис.42, такие что выполняются условия: и .

Рис. 42. Параметрический сплайн в форме Безье.

Переход от формы Эрмита к форме Безье осуществляется преобразованием:

, (*)

где - геометрический вектор Безье. Подставляя это в выражение для , получаем

Полезным свойством сплайнов в форме Безье является то что кривая всегда лежит внутри выпуклой оболочки, образованной четырехугольником . Это свойство можно доказать, пользуясь тем, что в выражении (*) коэффициенты принимают значения от 0 до 1 и их сумма равна единице.

Заметим, что матрица вида

- называется матрицей Безье.

Список литературы

1. Ньюмен, Спрулл, Основы интерактивной машинной графики, М. Мир, 1976.

2. Энджел Й. Практическое введение в машинную графику, Радио и Связь, 1984.

3. А. Вэн-Дэм, Дж. Фоли, Основы интерактивной машинной графики, т.1-2, М. Мир, 1985.

4. Е.В. Жикин, А.В.Боресков, Компьютерная графика. Динамика, реалистические ихображения, М., Диалог-МИФИ, 1995, 1997.

5. Л. Аммерал, Машинная графика на языке С, в 4-х томах, изд-во Сол. Систем, 1992.

6. Компьютер обретает разум. Пер. с англ. Под ред. В.Л.Стефанюка, М. Мир, 1990.

7. Роджерс, алгоритмические основы машинной графики. М. Мир, 1989.

8. Грайс, Графические средства персональных компьютеров, М., Мир, 1980.

9. Роджерс, Адамс, Математические основы машинной графики, М. Машиностроение, 1985.

10. Гилой, Интерактивная машинная графика, М., Мир, 1981.

11. Ф. Препарата, М. Шеймос, Вычислительная геометрия: Введение, М. Мир, 1989.

12. А.Фокс, М. Пратт, Вычислительная геометрия, М., Мир, 1982.

13. А.Б.Боресков, Е.В.Шикина, Г.Е.Шикина, Компьютерная графика: первое знакомство, Под ред. Е.В.Шикина, М., Финансы и статистика, 1996.

14. А.В.Фролов, Г.В.Фролов, Графический интерфейс GDI в MS WINDOWS, Москва, Изд-во Диалог-МИФИ, 1994.

15. Майкл Ласло, Вычислительная геометрия и компьютерная графика на С++, Москва, Бином, 1997.

16. Ю.Тихомиров, Программирование трехмерной графики, С.-Пб.: БХВ‑Санкт-Петербург,1999.

17. А.Хонич, Как самому создать трехмерную игру. М.:МИКРОАРТ, 1996.

18. М.Маров, 3D Studio MAX 2.5: справочник – СПб: «Питер», 1999. – 672 с.

19. А.Ла Мот, Д.Ратклифф и др. Секреты программирования игр/ Перев с англ. – СПб: Питер, 1995. – 720 с.

20. Н. Томпсон, Секреты программирования трехмерной графики для Windows 95. Перев с англ. – СПб: Питер, 1997. – 352 с.

* В этом определении при замене, скажем, оси Oz на ось Ox остальные оси заменяются по правилу циклической перестановки, то есть Oy заменится на Oz, а Ox заменится на Oy. Всего циклических перестановок может быть три: (x,y,z)®(y,z,x)®(z,x,y).

* Более строгое определение однородных координат дается в разделе линейной алгебры «Проективные пространства».

Это функция, которая:

Проходит через все заданные точки
,
;

На каждом отрезке между соседними точками является кубической параболой;

Непрерывна вместе со своими первой и второй производными во всех точках.).

интерполяция
локальная			глобальная
линейная	параболическая	кубическая парабола	полином степени (N -1)	кубический сплайн
Рис. 1.5.

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

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

Если функция измеряется или вычисляется приближенно и погрешности существенны, то не имеет смысла проводить интерполяцию и переходят к аппроксимации. В латыни слово ap-proximo означает "почти близкий". При аппроксимации кривая проводится вблизи заданных точек в соответствии с некоторым критерием близости, например, критерием наименьших квадратов или минимаксным критерием. Различия интерполяции и аппроксимации иллюстрирует рис.1.6.

Если имеем непрерывную или дискретную функцию, то обычно используют 5 видов преобразований функций:

Непрерывная в дискретную (дискретизация),

Дискретная в непрерывную (интерполяция),

Дискретная в непрерывную (аппроксимация),

Непрерывная в непрерывную (интерполяция),

Дискретная в дискретную (сглаживание).

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

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

Кубический сплайн - это функция, которая:

Проходит через все заданные точек
,
;

На каждом отрезке между соседними точками является кубическим полиномом;

Непрерывна вместе со своими первой и второй производными во всех точках.

Заметим, что, благодаря третьему условию, кубическая парабола
через две точки проводится однозначно.

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

,

(2.1)

Причем между заданными точками имеем отрезок, так что в этой формуле
.

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

, , ,

(2.2)

где штрих означает дифференцирование по . Следовательно, коэффициенты сплайна характеризуют значения его производных в узлах интерполяции. Третья производная сплайна является разрывной функцией, но в задачах моделирования третьи производные используются очень редко.

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

Постановка задачи: даны точек , . Определить все коэффициенты сплайна , , , т.е. всего
коэффициентов,
, т.к. отрезок.

Рассмотрим два любых соседних отрезка
и
с номерами
и . Точка для них является общей, см. рис. 2.1.

Для правого отрезка кубический сплайн имеет вид (2.1), а для левого, т.е. при

,

(2.3)

.

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

Такие тройки уравнений можно записать для всех внутренних узлов ,
, что даёт
уравнений.

В результате получаем
уравнений. Эти уравнения содержат
неизвестных, т.к. для каждого отрезка между узлами имеем 3 неизвестных. Очевидно, что для однозначного определения коэффициентов нужны ещё два уравнения.

Эти дополнительные два уравнения могут быть произвольными, но обычно полагают, что функция
вблизи её концов является линейной. Тогда, имеем из последнего и первого уравнений (2.4) и уравнения (2.5):

Часто систему уравнений (2.8) записывают для вторых производных в узлах, обозначая их
. Тогда она принимает вид (Бахвалов, Численные методы, М., 2002):

(2.9)

, причем
и формально введено
.

Слово сплайн (английское слово "spline") означает гибкую линейку, используемую для проведения гладких кривых через заданные точки на плоскости. Форма этого универсального лекала на каждом отрезке описывается кубической параболой. Сплайны широко используются в инженерных приложениях, в частности, в компьютерной графике. Итак, на каждом i –м отрезке [x i –1 , x i ], i= 1, 2,…, N, решение будем искать в виде полинома третьей степени:

S i (x )=a i +b i (x–x i )+c i (x –x i ) 2 /2+d i (x–x i ) 3 /6

Неизвестные коэффициенты a i , b i , c i , d i , i= 1, 2,..., N, находим из:

Условий интерполяции: S i (x i )=f i , i= 1, 2,..., N ; S 1 (x 0)=f 0 ,

Непрерывности функции S i (x i– 1 )=S i– 1 (x i –1), i= 2, 3,..., N,

Непрерывности первой и второй производной:

S / i (x i– 1)=S / i– 1 (x i –1), S // i (x i –1)=S // i –1 (x i –1), i= 2, 3,..., N .

Учитывая, что , для определения 4N неизвестных получаем систему 4N –2 уравнений:

a i =f i , i= 1, 2,..., N,

b i h i – c i h i 2 /2 + d i h i 3 /6=f i – f i –1 , i= 1, 2,..., N,

b i – b i–1 = c i h i – d i h i 2 /2, i= 2, 3,..., N,

d i h i = c i – c i– 1 , i= 2, 3,..., N.

где h i =x i – x i– 1. Недостающие два уравнения выводятся из дополнительных условий: S // (a )=S // (b )=0. Можно показать, что при этом . Из системы можно исключить неизвестные b i , d i , получив систему N+ 1 линейных уравнений (СЛАУ) для определения коэффициентов c i :

c 0 = 0, c N = 0,

h i c i –1 + 2(h i +h i +1)c i +h i +1 c i +1 = 6 , i= 1, 2,…, N –1. (1)

После этого вычисляются коэффициенты b i , d i:

, i= 1, 2,..., N. (2)

В случае постоянной сетки h i =h этасистема уравнений упрощается.

Данная CЛАУ имеет трехдиагональную матрицу и решается методом прогонки.

Коэффициенты определяются из формул:

Для вычисления значения S (x ) в произвольной точке отрезка z ∈[a, b ] необходимо решить систему уравнений на коэффициенты c i , i= 1,2,…, N –1, затем найти все коэффициенты b i , d i . Далее, необходимо определить, на какой интервал [x i 0, x i 0–1 ] попадает эта точка, и, зная номер i 0 , вычислить значение сплайна и его производных в точке z

S (z )=a i 0 +b i 0 (z–x i 0)+c i 0 (z–x i 0) 2 /2+d i 0 (z–x i 0) 3 /6

S / (z )=b i 0 +c i 0 (z–x i 0)+d i 0 (z–x i 0) 2 /2, S // (z )=c i 0 +d i 0 (z–x i 0).

Требуется вычислить значения функции в точках 0.25 и 0.8, используя сплайн – интерполяцию.

В нашем случае: h i =1/4, .

Выпишем систему уравнений для определения :

Решая эту систему линейных уравнений, получим: .

Рассмотрим точку 0.25, которая принадлежит первому отрезку, т.е. . Следовательно, получим,

Рассмотрим точку 0.8, которая принадлежит четвертому отрезку, т.е. .

Следовательно,

Глобальная интерполяция

В случае глобальной интерполяции отыскивается единый полином на всем интервале [a, b ], т.е. строится полином, который используется для интерполяции функции f(x) на всем интервале изменения аргумента x. Будем искать интерполирующую функцию в виде полинома (многочлена) m –ой степени P m (x )=a 0 +a 1 x+a 2 x 2 +a 3 x 3 +…+a m x m . Какова должна быть степень многочлена, чтобы удовлетворить всем условиям интерполяции? Допустим, что заданы две точки: (x 0 , f 0) и (x 1 , f 1), т.е. N=1. Через эти точки можно провести единственную прямую, т.е. интерполирующей функцией будет полином первой степени P 1 (x )=a 0 +a 1 x. Через три точки (N=2) можно провести параболу P 2 (x )=a 0 +a 1 x+a 2 x 2 и т.д. Рассуждая таким способом, можно предположить, что искомый полином должен иметь степень N .

Для того, чтобы доказать это, выпишем систему уравнений на коэффициенты. Уравнения системы представляют собой условия интерполяции в при каждом x=x i :

Данная система является линейной относительно искомых коэффициентов a 0 , a 1 , a 2 , …, a N. Известно, что СЛАУ имеет решение, если ее определитель отличен от нуля. Определитель данной системы

носит имя определителя Вандермонда . Из курса математического анализа известно, что он отличен от нуля, если x k ≠ x m (т.е. все узлы интерполяции различные). Таким образом, доказано, что система имеет решение.

Мы показали, что для нахождения коэффициентов
a 0 , a 1 , a 2 , …, a N надо решить СЛАУ, что является сложной задачей. Но есть другой способ построения полинома N –й степени, который не требует решения такой системы.

Полином Лагранжа

Решение ищем в виде , где l i (z ) – базисные полиномы N –й степени, для которых выполняется условие: . Убедимся в том, что если такие полиномы построены, то L N (x) будет удовлетворять условиям интерполяции:

Каким образом построить базисные полиномы ? Определим

, i= 0, 1,..., N.

Легко понять, что

Функция l i (z ) является полиномом N –й степени от z и для нее выполняются условия "базисности":

0, i≠k;, т.е. k=1,…,i-1 или k=i+1,…,N.

Таким образом, нам удалось решить задачу о построении интерполирующего полинома N– й степени, и для этого не нужно решать СЛАУ. Полином Лагранжа можно записать в виде компактной формулы: . Погрешность этой формулы можно оценить, если исходная функция g (x ) имеет производные до N+ 1 порядка:

.

Из этой формулы следует, что погрешность метода зависит от свойств функции g (x ), а также от расположения узлов интерполяции и точки z. Как показывают расчетные эксперименты, полином Лагранжа имеет малую погрешность при небольших значениях N <20 . При бόльших N погрешность начинает расти, что свидетельствует о том, что метод Лагранжа не сходится (т.е. его погрешность не убывает с ростом N ).

Рассмотрим частные случаи. Пусть N=1, т.е. заданы значения функции только в двух точках. Тогда базовые полиномы имеют вид:

, т.е. получаем формулы кусочно–линейной интерполяции.

Пусть N=2. Тогда:

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

Пример: Заданы значений некоторой функции:

x				3.5
f	-1	0.2	0.5	0.8

Требуется найти значение функции при z= 1, используя интерполяционный полином Лгранжа. Для этого случая N =3, т.е. полином Лагранжа имеет третий порядок. Вычислим значения базисных полиномов при z =1:

Подбор эмпирических формул

При интерполировании функций мы использовали условие равенства значений интерполяционного полинома и данной функции в узлах интерполяции. Если же исходные данные получены в результате опытных измерений, то требование точного совпадения не нужно, так как данные не получены точно. В этих случаях можно требовать лишь приближенного выполнения условий интерполяции . Это условие означает, что интерполирующая функция F(x) проходит не точно через заданные точки, а в некоторой их окрестности, так, например, как это показано на рис.

Тогда говорят о подборе эмпирических формул . Построение эмпирической формулы состоит из двух этапов6 подбора вида этой формулы , содержащей неизвестные параметры , и определение наилучших в некотором смысле этих параметров. Вид формулы иногда известен из физических соображений (для упругой среды связь между напряжением и деформацией) или выбираются из геометрических соображений: экспериментальные точки наносятся на график и примерно угадывается общий вид зависимости путем сравнения полученной кривой с графиками извесиных функций. Успех здесь в значительной степени определяется опытом и интуицией исследователя.

Для практики важен случай аппроксимации функции многочленами, т.е. .

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

Метод наименьших квадратов

Пусть для исходных данных x i , f i , i= 1,…,N (нумерацию лучше начинать с единицы), выбран вид эмпирической зависимости: с неизвестными коэффициентами . Запишем сумму квадратов отклонений между вычисленными по эмпирической формуле и заданными опытными данными:

Параметры будем находить из условия минимума функции . В этом состоит метод наименьших квадратов (МНК).

Известно, что в точке минимума все частные производные от по равны нулю:

(1)

Рассмотрим применение МНК для частного случая, широко используемого на практике. В качестве эмпирической функции рассмотрим полином

Формула (1) для определения суммы квадратов отклонений примет вид:

Вычислим производные:

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

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

Автоматизация этого процесса представляла значительный интерес для машинной графики. Форма математического сплайна повторяет контур физического сплайна (рис. 5-4), т.е. гибкой деревянной или пластмассовой линейки, проходящей через определенные точки. Для изменения формы сплайна используются свинцовые грузики. Меняя их количество и расположение, получившуюся кривую стараются сделать более гладкой, красивой и «приятной для глаза».

Если рассматривать физический сплайн как тонкую гибкую рейку, его форма (отклонение ) определяется уравнением Эйлера (5-2) для момента изгиба вдоль рейки:

где - модуль Юнга, зависящий от свойств материала рейки, - момент инерции, определяемый формой кривой, - радиус кривизны.

Для малых отклонений радиус приближенно равен

,

где штрих обозначает производную по - расстоянию вдоль рейки, а - отклонение рейки. Уравнение Эйлера принимает вид

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

и после двойного интегрирования

Таким образом, форма сплайна задается кубическим полиномом.

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

Уравнение одного параметрического сегмента сплайна таково:

, , (5-1)

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

Рис. 5-5 Один сегмент кубического сплайна.

Каждая составляющая имеет вид, похожий на , т.е.

, ,

, ,

, .

Постоянные коэффициенты вычисляются исходя из четырех граничных условий для сегмента сплайна. Запишем уравнение (5-1) в виде

Пусть и - векторы концов сегмента (см. рис. 5-5). Пусть также и , производные по , будут касательными векторами в концах сегмента. Дифференцируя уравнение (5-1), получим

, . (5-3)

Запишем результат

, . (5-4)

Предположим, без потери общности, что , и применим граничные условия

Получим четыре уравнения для неизвестных :

, (5-6b)

, (5-6c)

. (5-6d)

Решения для и имеют вид:

(5-7a)

. (5-7b)

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

Подставив уравнения (5-6) и (5-7) в (5-1), получим уравнение для одного сегмента кубического сплайна:

. (5-8)

Это уравнение для одного сегмента. Чтобы получить кривую целиком, нужно соединить множество сегментов. На рис. 5-6 показаны два соседних сегмента. Если известны векторы , , , касательные векторы , , и значения параметров , , то форма каждого сегмента определяется из уравнения (5-8). Однако маловероятно, что известен касательный вектор в точке соединения. К счастью, его можно вывести из условия непрерывности.

Вспомним, что кусочный сплайн степени имеет непрерывность степени в точках соединения; непрерывность кубического сплайна равна двум. Для этого должна быть непрерывна вторая производная или кривизна линии. Дважды продифференцировав уравнение (5-1), получим

, . (5-9)

Рис. 5-6 Два кусочно кубических сегмента сплайна.

Для первого куска сплайна параметр изменяется в пределах . Подставим в уравнение (5-9):

.

Для второго участка сплайна параметр изменяется в диапазоне . Подставим в уравнение (5-9) значение в начале второго участка

Приравнивая полученные результаты и пользуясь уравнениями (5-6a,b) и (5-7а), получим

.

Левая часть этого уравнения представляет кривизну в конце первого сегмента, а правая - в начале второго. Домножим на и сгруппируем члены:

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

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

Рис. 5-7 Обозначения множества кусочно кубических сегментов сплайна.

Обобщенное уравнение для двух любых соседних сегментов сплайна и в обозначениях рис. 5-7 имеет вид:

(5-11)

для первого сегмента и

(5-12)

для второго, так как для каждого сегмента параметр начинает изменяться с нуля, для первого и для второго - .

Приравнивание вторых производных в точках стыковки для любых соседних сегментов, , дает общий результат, эквивалентный уравнению (5-10),

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

Рекурсивное использование уравнения (5-13) для всех сегментов сплайна порождает уравнений касательных векторов , . В матричной форме:

(5-14)

Матрица неквадратная, так как имеется только уравнений для векторов, и ее нельзя обратить и получить решение для . Если предположить, что известны касательные векторы на концах кривой и , проблема разрешается. Теперь матрица имеет вид

(5-15)

где матрица квадратная и обратимая. Заметим также, что трехдиагональная, что снижает вычислительные затраты на ее обращение. Далее, матрица диагонально доминантная. Отсюда следует, что у нее существует единственное решение:

. (5-16)

Если нам известны , то легко определить коэффициенты для каждого сегмента сплайна. Обобщая уравнения (5-6)-(5-11), получим

,

.

Так как и - это векторные величины, то и тоже векторные; если и имеют , составляющие, значит, и также имеет эти составляющие.

В матричной форме уравнение любого сегмента сплайна таково:

. (5-17)

Пусть требуется задать кубический сплайн, проходящий через точек , с касательными векторами на концах и . Из уравнения (5-16) находим внутренние касательные векторы , . Затем из уравнения (5-17) с известными координатами концов каждого сегмента и касательными векторами определяются , , для каждого сегмента. Окончательное обобщение уравнения (5-1)

, , , (5-18)

используется для расчета сегмента сплайна.

В матричном виде уравнение (5-18) выглядит следующим образом:

, . (5-19)

Подставляя уравнение (5-17) и перегруппируя члены, получим

, , , (5-20)

, (5-21a)

, (5-21b)

, (5-21с)

, (5-21d)

называются весовыми функциями.

Рис. 5-8 Весовые функции кубического сплайна для

Пользуясь этими определениями, запишем уравнение (5-20) в матричном виде

где - матрица весовой функции

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

Из уравнения (5-21) видно, что каждая весовая функция имеет третий порядок. Любая точка на сегменте кубического сплайна это взвешенная сумма конечных точек и касательных векторов. Коэффициенты выступают в роли весовых функций. На рис. 5-8 изображены для . Из рисунка видно, что и , т.е. кривая проходит через вектор-точку . Аналогично и , т.е. кривая также проходит через вектор-точку . Далее отметим симметрию и , и и . Фактически . Наконец, обратим внимание на относительный порядок , , и . Значительная разница величин говорит о том, что в общем случае положение конечных точек имеет большее влияние, чем касательные векторы.

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

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

Один метод вычисления - установить величины параметров равными длинам хорд между соседними точками. При этом качество кривой удовлетворяет требованиям большинства прикладных задач. Другой метод состоит в том, что для нормализации вариации полагается равным единице у каждого сегмента сплайна. Такой выбор упрощает вычисления (см. разд. 5-4). Как видно из приведенных выше уравнений, любой выбор приводит к другим коэффициентам, и, следовательно, получаются различные кривые, проходящие через заданные точки.

Рассмотрим пример.

Пример 5-2 Кубический сплайн Пусть даны четыре вектор-точки на плоскости: , , , (см. рис. 5-9). Найти кусочный кубический сплайн, проходящий через них, используя хордовую аппроксимацию . Касательные векторы в концах: и . Найти промежуточные точки при для каждого сегмента. Сначала найдем Внутренние касательные векторы и вычисляются из уравнения (5-15): . Рис. 5-9 Кусочный кубический сплайн. (а) вычислены с помощью хордовой аппроксимации; (b) нормализованы к 1. Сделав подстановку, получим . С помощью инверсии и умножения вычисляются касательные векторы .
	То кривая выпукла на концах и лежит внутри треугольника из хорды и касательных. При возрастании величины кривая постепенно становится вогнутой и выходит за треугольник. В этом случае при величине вектора у кривой появляется вершина (см. рис. 5-10d). При еще больших величинах появляется петля, как видно из рис. 5-10е. Иногда для улучшения формы кривой величина вектора ограничивается длиной хорды.

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

Рассмотрим наиболее распространенный вариант сплайн-интерполяции - интерполяцию кубическими сплайнами .

Установлено, что упругая недеформируемая линейка проходит между соседними узлами по линии, удовлетворяющей уравнению

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

где a i ,b i ,c i ,d i - коэффициенты сплайна, определяемые из дополнительных условий; i = 1,2,3,....n - номер сплайна.

Всего сплайнов на один меньше, чем точек интерполяции. Интерполяцию сплайнами можно назвать кусочно-полиномиальной.

Коэффициенты сплайнов определяются из следующих условий сшивания соседних сплайнов в узловых точках.

1. Равенство значений сплайнов и функции f(x) в узловых точках - условия Лагранжа:

, . (6.10)

2. Непрерывность первой и второй производных от сплайнов в узлах:

Кроме перечисленных условий, следует добавить условия на концах, т. е. в точках x 0 и x n . В общем случае эти условия зависят от конкретной задачи. Мы воспользуемся условиями свободных концов сплайнов, т.е. вне интервала функция описывается полиномом первой степени - прямой линией:

, . (6.12)

Условия (6.10)-(6.12) позволяют найти коэффициенты a i ,b i ,c i ,d i всех n сплайнов. Их значения выражаются следующими формулами:

, (6.13)

где в первых трех уравнениях i = 1,2,...n , а в третьем i = 2,3,..n ;

h i =x i -x i -1 - i -й шаг аргумента.

Учитывая индексацию для с i , добавим значения этого коэффициента на концах сплайна

Сначала решается система из n - 1 линейных уравнений для с i . Затем определяются b i и d i по известным коэффициентам с i , а i известно - это значения функции f(x) в узловых точках. В каждое уравнение для определения с i входит только три неизвестных с последовательными значениями индексов c i - 1 ,c i ,c i +1 . Такая матрица, имеющая отличные от нуля только элементы главной и двух соседних диагоналей, называется трехдиагональной.

Программная реализация рассмотренного алгоритма приведена ниже (ПРОГРАММА 6.2). Приведен фрагмент, в котором рассчитываются коэффициенты сплайнов по узловым значениям интерполируемой функции.

Для формирования трехдиагональной матрицы Kc использован массив шагов аргумента h i . В процедуре Gauss рассчитывается вспомогательный массив cv, имеющий на 2 элемента меньше, чем массив с., так как с 0 и c n +1 известны и равны нулю. При большом числе уравнений для решения систем с трехдиагональной матрицей применяют метод прогонки , являющийся вариантом метода последовательных исключений. Результаты расчетов с использованием интерполяции сплайнами приведены на рис.6.4. В качестве интерполируемой функции был взят ток катушки электромагнита.

Как видно на рис.6.4, интерполяция кубическими сплайнами дает очень хорошее приближение в случае, если функция гладкая. В окружности на рисунке обозначен участок, где погрешность сплайна велика. Это связано с тем, что на этом участке происходит излом кривой тока, связанный с изменением сопротивления диода R D c прямого R пр на обратное R обр . При этом первая производная тока делает скачок, а сплайны по определению имеют равные первые производные справа и слева от узловой точки.

Как отмечалось ранее, интерполяция есть частный случай аппроксимации, критерием которой являются условия Лагранжа. Рассмотрим другой критерий аппроксимации - минимизацию среднеквадратичного отклонения приближающей функции от аппроксимируемой f(x) .