Сплайн-функции

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

Сплайном называется составная функция , которая вместе с производными нескольких порядков непрерывна на всем отрезке , а на каждом частичном отрезке в отдельности является составляющей функцией:

.

Рассмотрим частный случай, когда функции являются алгебраическими многочленами вида:

где – коэффициенты, определяемые для каждого частичного отрезка.

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

Среди существующих сплайнов наиболее широкое распространение получили сплайны следующих типов: линейные, параболические, кубические, В-сплайны, эрмитовы сплайны, сглаживающие сплайны.

2.13.1. Линейный сплайн

Сплайн состоит из линейных многочленов вида:

. (2.71)

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

, (2.72)

. (2.73)

Обозначим . Тогда для каждого из многочленов можно записать

,

,

и для определения коэффициентов линейного сплайна (2.71) получим уравнения:

, (2.74)

(2.75)

Пример 2.7. Исходные данные приведены в таблице

Таблица 2.7.

		2, 5	3, 5	5, 5
	0, 9108	0, 7237	-0, 2004	-0, 5184	-0, 0848

Линейный сплайн строится в виде (2.71). По формулам (2.74) и (2.75) определяем коэффициенты линейных многочленов, приведенных в таблице:

Таблица 2.8.

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

Рис. 2.3. Интерполяция линейным сплайном

2.13.2. Параболический сплайн

Сплайн состоит из парабол, многочлены имеют вид:

(2.76)

Для определения коэффициентов сплайна дополнительно к условиям (2.48), (2.49) потребуем непрерывности первой производной сплайна на интервале , то есть:

. (2.77)

Обозначив , и, учитывая, что

, (2.78)

получим:

, (2.79)

, (2.80)

. (2.81)

Тогда коэффициенты определятся согласно (2.79), а (2.80) можно записать в виде:

. (2.82)

Если записать выражения для и в виде (2.82) и подставить их в (2.81), то в результате получим

, (2.83)

где

. (2.84)

Таким образом, уравнения (2.79), (2.82) и (2.83) образуют систему из уравнений для определения коэффициентов сплайна. Недостающее уравнение получается из дополнительного условия, которое накладывается на значение производной сплайна на правом конце интервала , то есть:

(2.85)

или

. (2.86)

Если подставить в (2.86) выражение для из (2.82), то формулу (2.86) можно переписать в виде:

,

где

.

Тогда

(2.87)

и

. (2.88)

Таким образом, параметры параболического сплайна вычисляются в следующем порядке: сначала в обратном порядке вычисляются коэффициенты по (2.87), (2.88), затем по (2.82) и , по (2.79).

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

Пример 2.8. Для исходных данных, приведенных в примере 2.7, построим параболический сплайн. Параболический сплайн строится в виде (2.76). Коэффициенты параболических многочленов определяются следующим образом: сначала по (2.87) находим коэффициент , затем по (2.88) вычисляются коэффициенты . Далее, пользуясь формулой (2.82) определяем коэффициенты , после чего высчитываем по (2.79) . Для нашего примера получаем следующие значения коэффициентов:

Таблица 2.9.

На рис. 2.4 приведены исходные данные в виде точек, и график параболического сплайна, а также для сравнения график исходной функции f (x).

Рис. 2.4. Интерполяция параболическим сплайном

2.13.3. Кубический сплайн

Сплайн состоит из многочленов вида:

, (2.89)

,

Для определения параметров кубического сплайна дефекта 1 потребуем дополнительно к (2.72), (2.73), (2.77) выполнение условия непрерывности второй производной:

. (2.90)

Первая и вторая производные отдельных многочленов сплайна соответственно равны:

(2.91)

. (2.92)

Тогда, обозначив , получим:

, (2.93)

, (2.94)

, (2.95)

. (2.96)

Последние два уравнения получены из (2.77) и (2.90).

Уравнения (2.93)-(2.96) составляют систему из уравнений для определения параметров сплайна. Для получения двух недостающих уравнений потребуем выполнения дополнительных условий на концах интервала :

, (2.97)

. (2.98)

Тогда из (2.97) следует

, (2.99)

а из (2.98) получим:

. (2.100)

Из уравнения (2.96) выразим

, (2.101)

и, подставляя его в (2.94), с учетом (2.93), получим

. (2.102)

Если выражения для и подставить в (2.95), то получим:

, (2.103)

где

. (2.104)

Уравнения (2.103) образуют систему из уравнения относительно неизвестных . Эта система является системой с трехдиагональной матрицей вида:

(2.105)

и вектором свободных членов , где - символ транспонирования.

Решение таких систем осуществляется методом прогонки, согласно которому решение представляют в виде:

, (2.106)

где – прогоночные коэффициенты. Чтобы получить выражения для этих коэффициентов, запишем формулы для определения и согласно (2.106) и, подставив их в (2.103), сравним полученное выражение с (2.106). При сравнении получим, что выражения для определения прогоночных коэффициентов будут иметь вид:

(2.107)

При этом, учитывая (2.99), полагают .

Таким образом, порядок вычисления коэффициентов кубического сплайна следующий: сначала определяют коэффициенты , , для чего необходимо, осуществляя прямой ход метода прогонки по формулам (2.107), найти значения , при , а затем, выполнив обратную прогонку, считая по формуле (2.106), вычисляются . При этом, согласно (2.99), Остальные коэффициенты сплайна определяются по следующим формулам: – (2.93), – (2.101), – (2.102), . Отметим, что преобладание в трехдиагональной матрице (2.105) диагональных элементов обеспечивает корректность и устойчивость метода прогонки.

Пример. 2.9. Для исходных данных, приведенных в примере 2.7, построим кубический сплайн. Сплайн строится в виде (2.89). Для интерполяции кубическим сплайном сначала согласно (2.107) вычисляются коэффициенты и , , причем x ₁= h ₁=0, после чего обратным ходом по (2.106) рассчитываются коэффициенты . Остальные коэффициенты без особого труда можно вычислить по формулам (2.93), (2.101)-(2.102). Занесем полученные значения коэффициентов в таблицу и отобразим полученный кубический сплайн на одном графике (рис. 2.5) с исходной функцией:

Таблица 2.10.

Рис. 2.5. Интерполяция кубическим сплайном

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

2.13.4.В-сплайны

Рассмотренные ранее полиномиальные сплайны имеют ряд существенных недостатков:

1) при увеличении вычисление коэффициентов становится значительно сложнее из-за увеличения числа уравнений (условий непрерывности функции и ее производных);

2) требуется достаточно большой объем памяти для хранения информации о сплайне: точек разбиения и значений коэффициентов сплайнов.

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

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

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

(2.108)

где – номер первой точки; – количество точек, по которым строится В-сплайн и указывается его порядок; – последовательность точек, причем , – разделенная разность -го порядка (см. п.2.5) для функции , которая является усеченной степенной функцией и определяется следующим образом

(2.109)

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

.

Если теперь представить в виде двух сомножителей

где

,

то, согласно формуле Лейбница, получим

. (2.110)

При этом учитывается, что разделенные разности для функции равны

для

Тогда можно записать

(2.111)

и (2.110) представить в виде

(2.112)

В обозначении В-сплайнов выражение (2.112) записывается в виде

(2.113)

или

. (2.114)

При этом

(2.115)

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

и

Узлы можно вычислить по формуле

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

(2.116)

где .

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

(2.117)

Соотношение (2.117) является системой из линейных алгебраических уравнений относительно неизвестных коэффициентов В матричном виде эта система имеет вид

(2.118)

где

.

3амечание 2.2. Рекуррентная формула (2.114) применима при условии, что строго возрастающая последовательность. В тоже время обычно задается только таблица значений функции в точках c помощью которых строится неубывающая последовательность . Поэтому при вычислении В-сплайна по рекуррентным формулам (2.114) может возникнуть ситуация ‘деления на ноль’. То же самое произойдет, если

или

. (2.119)

Самый простой способ выхода из этой ситуации состоит в том, что те слагаемые в (2.109), для которых выполняется условие (2.119), обращаются в нуль и вычисление В-сплайнов меньшего порядка не производится.

Пример 2.10. Для исходных данных, приведенных в примере 2.7, построим В-сплайн второго порядка. В-сплайн строится в виде (2.116). Неубывающая последовательность в данном случае имеет вид: 1; 1; 1; 3; 4, 5; 6; 6. Матрица и вектор получились следующими:

,

.

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

Рис. 2.6. Интерполяция В-сплайном 2-го порядка.