Базисные сплайны
Здесь
под знаком
интеграла
вместо обычного
сомножителя
стоит усеченная
степенная
функция, что
позволяет
заменить переменный
верхний предел
t
постоянной
величиной
b.
Из (7) следует
разностное
соотношение
то, полагая g(x) = xn+1, поручаем

Поскольку вне интервала (а, b), то это равенство -совпадает с (6) и лемма доказана.
Лемма
1.3.
Функции
являются
сплайнами
степени п дефекта
1 с конечными
носителями
минимальной
длины.
Доказательство.
Предположим,
что существует
сплайн
отличный
от нуля на интервале,
меньшем, чем
Такой
интервал, очевидно,
не может иметь
границей точку,
не являющуюся
узлом сетки
.
Поэтому пусть
это будет интервал
(xi
,
xi+n).
Возьмем
представление
сплайна дефекта
v
= 1 через усеченные
степенные
функции (1.4). Вследствие
того, что
при
в этом представлении![]()
.
Так как
при
то ее производные
до порядка n
— 1 равны нулю
в точке
xi+n.
Имеем

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

.
Ее определитель
пропорционален
определителю
Вандермонда
n-ro
порядка, который
отличен от
нуля, и система
имеет только
нулевое решение.
Наконец, из
того же условия
следует,
что
.
Значит,
и
лемма доказана.
Теорема
1.2.
Функции
линейно
независимы
и образуют
базис в пространстве
сплайнов
![]()
Доказательство.
Покажем сначала
линейную
независимость
функций
на
всей действительной
оси. Предположим
противное, т.
е. что существуют
такие постоянные
,
не все равные
нулю, что

Выбирая
получаем, что
и,
значит,
.
Беря затем
находим, что
и т.д.,
т.е.
Следовательно,
функции
линейно
независимы
на
![]()
Предположим
теперь, что
соотношение
(8) выполняется
только на [а,
b].
Это значит, что
на отрезках
обращаются
в нули сплайны
вида

Каждый
из них отличен
от нуля самое
большее на
интервале
Поэтому
из предположения
при
x
согласно
доказательству
леммы 3 следует,
что
0
на
интервалах
,
а
значит, и на
всей действительной
оси. В силу линейной
независимости
функций
на
должно
быть
и это для всех
i
=
0,
..,N-1.
Таким
образом, функции
линейно
независимы,
и так как согласно
теореме 1.1 размерность
пространства
равна
n+N,
то они образуют
базис в этом
пространстве.
Теорема доказана.
Функции
называются
базисными
сплайнами с
конечными
носителями
минимальной
длины (В-сплайнами).
В силу теоремы
1.2 всякий сплайн
может быть
единственным
образом записан

где — некоторые постоянные коэффициенты. Эту запись сплайна называют его представлением через В-сплайны.
Из теоремы 1.2 вытекает
Следствие
1.1.
Всякий сплайн
,
принадлежащий
,
с конечным
носителем
минимальной
длины с точностью
до постоянного
множителя
совпадает с
В-сплайном.
Доказательство.
Минимальным
конечным носителем
сплайна является
один из интервалов
Согласно (9)
![]()
Так
как
для
то, выбирая
последовательно
,
получаем, что
.
Аналогично,
для
Следовательно,
![]()
Замечание.
Представление
сплайнов через
B-сплайпы
в виде (9) имеет
смысл для конечного
отрезка [а, b].
Чтобы получить
его для всей
вещественней
оси, нужно положить
и
.
Тогда
точки
оказываются
узлами кратности
и при построении
B-сплайнов
с номерами
и
нужно учитывать
правило для
разделенных
разностей с
кратными узлами.
Мы не описываем
подробно эти
конструкции,
ибо все практические
задачи, где
используются
B-сплайны,
рассматриваются
на конечном
отрезке.
§3. Нормализованные базисные сплайны и представление ими многочленов
При практических вычислениях удобнее использовать не сами B-сплайны, а функции, получающиеся из них умножением на постоянные множители:
(1)
Эти
функции называются
нормализованными
В-сплайнами.
Нормирующий
множитель равен
среднему
арифметическому
шагов
на отрезке, где
B-сплайн
отличен от
нуля.
Тождество (2.4) для нормализованных 5-сплайнов имеет вид

С
его помощью
легко можно
построить
последовательность
сплайнов
Приведем
первые четыре
функции этой
последовательности
для случая
равноудаленных
узлов
hi
=
h.
Будем
обозначать
Точка
- это
середина
отрезка-носителя
В-сплайна. Тогда
имеем

Эти В-сплайны изображены на рис. 1.3, а, б, в, г соответственно.
В
§ 1 было отмечено,
что многочлены
Рп(х)
степени не выше
n
являются элементами
пространства
сплайнов
.Следовательно,
они представимы
через базисы
этих пространств,
в частности
через базис
из В-сплайнов
в пространстве
.
Для
вывода формул
воспользуемся
тождеством
(2). После умножения
обеих его частей
на число и
суммирования
по индексу i
получаем

Лемма 1.4. Справедливо тождество
в
предположении


Доказательство.
В формуле (4) положим
Тогда
получаем

Подставляя
в
(3), находим

Повторяя это преобразование n раз, получим справа

Теперь разложим обе части тождества (5) по степеням t. При этом

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

Подставляя
разложения
(6) и (7) в (5) и приравнивая
коэффициенты
при одинаковых
степенях t,
находим представления
мономов
через нормализованные
В-сплайны па
отрезке
![]()

В частности, при а = 0 получаем соотношение

которое для нормализованных 5-сплайпов играет ту же роль, что свойство (2.6) для самих 5-сплайнов.
Полученные формулы (8) решают вопрос о представлении произвольного многочлена п-й степени через нормализованные В-сплайны.
Заключение
В данной работе мы рассмотрели понятие сплайна и основные определения необходимые для работы с ним. Было изучено понятие базисного сплайна или B-сплайна, а так же уделено внимание его форме в виде нормализованного сплайна. Так же была создана программа для интерполяции сплайнов при помощи языка программирования высокого уровня C++.
Список литературы
Вержбицкий В.М. Основы численных методов – М.:Высш. шк., 2002.
Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л. Методы сплайн – функций - М.: Наука, 1980. 352 с
Бахвалов Н. С., Жидков Е. П., Кобельков Г. М. Численные методы. Учебное пособие. - 4-е издание – М.- СПб.: Физматлит, Невский диалект, Лаборатория базовых знаний, 2003
Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. - Мир, 1989
Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа - М.: Наука, 1976
Приложение
Листинг программы.
#include<conio.h>
#include<iostream>
using namespace std;
double KubichSplain ( int n, double *X, double *Y, double Xp )
{
double *Q, *L, *A, *B, *C, *D, DXp, Yp;
int i, j, k;
Q = new double [n];
L = new double [n];
A = new double [n];
B = new double [n];
C = new double [n];
D = new double [n];
for(i=0;i<n;i++)
if(Xp<=X[i])
{
k=i;
break;
}
Q[1] = (-1) * (X[2]-X[1])/2*(X[1]-X[0] + X[2]-X[1]);
L[1] = (3*(Y[2]-Y[1])/(X[2]-X[1]) - 3*(Y[1]-Y[0])/(X[1]-X[0])) / (2*(X[1]-X[0] + X[2]-X[1]));
C[n-1]=0;
C[0]=0;
for(i=3; i<n; i++)
{
Q[i-1]=(-1) * (X[i]-X[i-1]) / (2*(X[i-1]-X[i-2]+X[i]-X[i-1])+(X[i-1]-X[i-2])*Q[i-2]);
L[i-1]=(3*((Y[i]-Y[i-1])/(X[i]-X[i-1])-(Y[i-1]+Y[i-2])/
(X[i-1]-X[i-2]))-(X[i-1]-X[i-2])*L[i-2])/(2*(X[i-1]-X[i-2]+X[i]-X[i-1])+(X[i-1]-X[i-2])*Q[i-2]);
}
for(i=n-1; i>=2; i--)
C[i-1]=Q[i-1]*C[i]+L[i-1];
A[0]=Y[0];
for(i=1;i<n;i++)
{
A[i]=Y[i];
D[i]=(C[i]-C[i-1])/3.*(X[i]-X[i-1]);
B[i]=(Y[i]-Y[i-1])/(X[i]-X[i-1])+2.*(X[i]-X[i-1])*C[i]/3.+(X[i]-X[i-1])*C[i-1]/3.;
}
DXp=Xp-X[k];
//получение значения интерполирующей функции
Yp = A[k] + B[k]*DXp + C[k]*DXp*DXp + D[k]*DXp*DXp*DXp;
delete []A;
delete []B;
delete []C;
delete []D;
delete []Q;
delete []L;
return Yp;
}
void main ( void )
{
double *X, *Y, Xp;
int n, i;
system("CLS");
cout << "Enter n: ";
cin >> n;
X = new double [n];
Y = new double [n];
for ( i = 0; i < n; i ++ )
{
cout << "X[ " << i+1 << " ] = ";
cin >> X[i];
}
for ( i = 0; i < n; i ++ )
{
cout << "Y( " << X[i] << " ) = ";
cin >> Y[i];
}
cout << "Xp = ";
cin >> Xp;
cout << "Y( " << Xp << " ) = " << KubichSplain ( n, X, Y, Xp )<<"n";
getch();
delete []X;
delete []Y;
}