Пусть задана таблица значений функции y i в узлах х 0 < х 1 < ... < х п .Обозначим h i = x i – x i -1 , i = 1, 2, ... , п .

Сплайн – гладкая кривая, проходящая через задан­ные точки (х i , y i ), i = 0, 1, ... , п . Интерполяция сплай­нами заключается в том, что на каждом отрезке [х i -1 , x i ]используется многочлен определенной степени. Наиболее часто применяется многочлен третьей степени, реже – второй или четвертой. При этом для определения коэффициентов многочленов используются условия непре­рывности производных в узлах интерполяции.

Интерполяция кубическими сплайнами представляет собой локальную интерполяцию, когда на каждом отрез­ке [х i -1 , x i ], i = 1, 2, ... , п применяется кубическая кри­вая, удовлетворяющая некоторым условиям гладкости, а именно, непрерывности самой функции и ее первой и вто­рой производных в узловых точках. Использование куби­ческой функции вызвано следующими соображениями. Если предположить, что интерполяционная кривая соот­ветствует упругой линейке, закрепленной в точках (х i , y i ),то из курса сопротивления материалов известно, что эта кривая определяется как решение дифференциального уравнения f (IV) (x ) = 0 на отрезке [х i -1 , x i ](для простоты из­ложения мы не рассматриваем вопросы, связанные с физи­ческими размерностями). Общим решением такого уравне­ния является многочлен 3-й степени с произвольными коэффициентами, который удобно записать в виде
S i (x ) = а i + b i (х - x i -1) + с i (x - x i -1) 2 + d i (x - x i -1) 3 ,
х i -1 £ х £ х i , i = 1, 2, ... , п .(4.32)

Коэффициенты функций S i (x )определяются из усло­вий непрерывности функции и ее первой и второй произ­водных во внутренних узлах x i , i = 1, 2,..., п - 1.

Из формул (4.32) при х = х i -1 получим

S i (x i- 1) = y i -1 = a i , i = 1, 2,..., п ,(4.33)

а при х = х i

S i (x i ) = а i + b i h i + с i h i 2 + d i h i 3 ,(4.34)

i = 1, 2,..., n .

Условия непрерывности интерполяционной функции записываются в виде S i (x i ) = S i -1 (x i ), i = 1, 2, ... , n - 1 и из условий (4.33) и (4.34) следует, что они выполнимы.

Найдем производные функции S i (x ):

S" i (x ) = b i + 2с i (х - x i -1) + 3di (х – x i -1) 2 ,

S" i (x ) = 2c i + 6d i (x - x i -1).

При x = x i -1 , имеем S" i (x i -1) = b i , S" (x i -1) = 2с i , а при х = х i получим

S" i (x i ) = b i + 2с i h i + 3dih i 2 , S" (x i ) = 2с i + 6d i h i .

Условия непрерывности производных приводят к уравнениям

S" i (x i ) = S" i +1 (x i ) Þ b i + 2с i h i + 3dih i 2 = b i +1 ,

i = l, 2,... , п - 1. (4.35)

S" i (x i ) = S" i +1 (x i ) Þ 2с i + 6d i h i = 2c i +1 ,

i = l, 2,..., n - 1. (4.36)

Всего имеем 4n – 2 уравнений для определения 4n не­известных. Чтобы получить еще два уравнения, исполь­зуют дополнительные краевые условия, например, требо­вание нулевой кривизны интерполяционной кривой в концевых точках, т. е. равенства нулю второй производ­ной на концах отрезка [а , b ] а = х 0 , b = х n :

S" 1 (x 0) = 2c 1 = 0 Þ с 1 = 0,

S" n (x n ) = 2с n + 6d n h n = 0 Þ с n + 3d n h n = 0. (4.37)

Систему уравнений (4.33)–(4.37) можно упростить и получить рекуррентные формулы для вычисления коэф­фициентов сплайна.

Из условия (4.33) имеем явные формулы для вычисле­ния коэффициентов a i :

a i = y i -1 , i= 1,..., n . (4.38)

Выразим d i через c i с помощью (4.36), (4.37):

; i = 1, 2,...,n ; .

Положим с n +1 = 0, тогда для d i получим одну формулу:

, i = 1, 2,...,n . (4.39)

Подставим выражения для а i и d i в равенство (4.34):

, i = 1, 2,..., n .

и выразим b i , через с i :

, i = 1, 2,..., n . (4.40)

Исключим из уравнений (4.35) коэффициенты b i и d i с помощью (4.39) и (4.40):

i = 1, 2,..., n -1.

Отсюда получим систему уравнений для определения с i :

Система уравнений (4.41) может быть переписана в виде

Здесь введено обозначение

, i =1, 2,..., n - 1.

Решим систему уравнений (4.42) методом прогонки. Из первого уравнения выразим с 2 через с 3:

c 2 = a 2 c 3 + b 2 , , . (4.43)

Подставим (4.43) во второе уравнение (4.42):

h 2 (a 2 c 3 + b 2) + 2(h 2 + h 3)c 3 + h 3 c 4 = g 2 ,

и выразим с 3 через с 4:

с 3 = a 3 с 4 + b 3 , (4.44)

Предполагая, что с i -1 = a i -1 c i + b i -1 из i -го уравне­ния (4.42) получим

c i = a i с i +1 + b i

, i = 3,..., n – 1, a n = 0, (4.45) c n +1 = 0,

c i = a i с i +1 + b i , i = n , n -1,..., 2, (4.48)

c 1 = 0.

3. Вычисление коэффициентов а i , b i , d i :

a i = y i -1 ,

i = 1, 2,..., n .

4. Вычисление значения функции с помощью сплай­на. Для этого найти такое значение i ,что данное значе­ние переменной х принадлежит отрезку [x i -1 , x i ] и вы­числить

S i (x ) = а i + b i (х - x i -1) + с i (x - x i -1) 2 + d i (x - x i -1) 3 . (4.50)

Слово сплайн (английское слово "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. Тогда:

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

Интерполяционные формулы Лагранжа, Ньютона и Стирлинга и др. при использовании большого числа узлов интерполяции на всем отрезке [a , b ] часто приводят к плохому приближению из-за накопления погрешностей в процессе вычислений . Кроме того, из-за расходимости процесса интерполяции увеличение числа узлов не обязательно приводит к повышению точности. Для снижения погрешностей весь отрезок [a , b ] разбивается на частичные отрезки и на каждом из них функциюзаменяют приближенно полиномом невысокой степени. Это называется кусочно-полиномиальной интерполяцией .

Один из способов интерполирования на всем отрезке [a , b ] является интерполирование сплайнами .

Сплайном называется кусочно-полиномиальная функция, определенная наотрезке [a , b ] и имеющая на этом отрезке некоторое количество непрерывных производных. Преимущества интерполяции сплайнами по сравнению с обычными методами интерполяции – в сходимости и устойчивости вычислительного процесса.

Рассмотрим один из наиболее распространенных в практике случаев – интерполирование функции кубическим сплайном .
Пусть на отрезке [a , b ] задана непрерывная функция. Введем разбиение отрезка:

и обозначим , .

Сплайном, соответствующим данной функциии узлам интерполяции (6) называется функция , удовлетворяющая следующим условиям:

1) на каждом отрезке , функция является кубическим многочленом;

2) функция , а также ее первая и вторая производные непрерывны на отрезке [a , b ] ;

Третье условие называется условием интерполирования . Сплайн, определяемый условиями 1) – 3), называется интерполяционным кубическим сплайном .

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

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

(7)

где искомые коэффициенты.

Продифференцируем (7) трижды по х :

откуда следует

Из условия интерполирования 3) получаем:

Из условий непрерывности функции вытекает.

2.2 Интерполяция с помощью кубического сплайна

Кубическим интерполяционным сплайном, соответствующим данной функции f(x) и данным узлам x i , называется функция S(x), удовлетворяющая следующим условиям:

1. На каждом сегменте , i = 1, 2, ..., N функция S(x) является полиномом третьей степени,

2. Функция S(x), а также ее первая и вторая производные непрерывны на отрезке ,

3. S(x i) = f(x i), i = 0, 1, ..., N.

На каждом из отрезков , i = 1, 2, ..., N будем искать функцию S(x) = S i (x) в виде полинома третьей степени:

S i (x) = a i + b i (x - x i - 1) + c i (x - x i - 1) 2 + d i (x - 1) 3 ,

x i - 1 Ј x Ј x i ,

где a i , b i , c i , d i - коэффициенты, подлежащие определению на всех n элементарных отрезках. Чтобы система алгебраических уравнений имела решение, нужно, чтобы число уравнений точно равнялось числу неизвестных. Поэтому мы должны получить 4n уравнения.

Первые 2n уравнения мы получим из условия, что график функции S(x) должен проходить через заданные точки, т. е.

S i (x i - 1) = y i - 1 , S i (x i) = y i .

Эти условия можно записать в виде:

S i (x i - 1) = a i = y i - 1 ,

S i (x i) = a i + b i h i + c i h + d i h = y i ,

h i = x i - x i - 1 , i = 1, 2, ..., n.

Следующие 2n - 2 уравнения вытекают из условия непрерывности первых и вторых производных в узлах интерполяции, т. е. условия гладкости кривой во всех точках.

S i + 1 (x i) = S i (x i), i = 1, ..., n - 1,

S i (x) = b i + 2 c i (x - x i - 1) + 3 d i (x - x i - 1),

S i + 1 (x) = b i + 1 + 2 c i + 1 (x - x i) + 3 d i + 1 (x - x i).

Приравнивая в каждом внутреннем узле x = x i значения этих производных, вычисленные в левом и правом от узла интервалах, получаем (с учетом h i = x i - x i - 1):

b i + 1 = b i + 2 h i c i + 3h d i , i = 1, ..., n - 1,

S i (x) = 2 c i + 6 d i (x - x i - 1),

S i + 1 (x) = 2 c i + 1 + 6 d i + 1 (x - x i),

если x = x i

c i + 1 = c i + 3 h i d i , i = 1,2, ..., n - 1.

На данном этапе мы имеем 4n неизвестных и 4n - 2 уравнений. Следовательно, необходимо найти еще два уравнения.

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

S 1 (x 0) = 0 и S n (x n) = 0,

c i = 0 и 2 c n + 6 d n h n = 0.

Уравнения составляют систему линейных алгебраических уравнений для определения 4n коэффициентов: a i , b i , c i , d i (i = 1, 2, . . ., n).

Эту систему можно привести к более удобному виду. Из условия сразу можно найти все коэффициенты a i .

i = 1, 2, ..., n - 1,

Подставляя, получим:

b i = - (c i + 1 + 2c i) , i = 1,2, ..., n - 1,

b n = - (h n c n)

Исключаем из уравнения коэффициенты b i и d i . Окончательно получим следующую систему уравнений только для коэффициентов с i:

c 1 = 0 и c n + 1 = 0:

h i - 1 c i - 1 + 2 (h i - 1 + h i) c i + h i c i + 1 = 3 ,

i = 2, 3, ..., n.

По найденным коэффициентам с i легко вычислить d i ,b i .

Вычисление интегралов методом Монте-Карло

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

Интерполирование функций

Пусть задана таблица значений функции f(xi) = yi (), в которой они расположены по возрастанию значений аргумента: x0 < x1 < … < xn. Чтобы построить кубический сплайн, требуется определить коэффициенты ai0, ai1, ai2, ai3...

Интерполяция сплайнами

Интерполяция сплайнами

Интерполяция сплайнами

Познакомимся с алгоритмом работы программы. 1. Вычисляем значения и 2. На основе этих значений считаем коэффициенты прогонки и о. 3. На основе полученных данных высчитываем коэффициенты 4...

Математическое моделирование технических объектов

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

Методы аппроксимации функций

На каждом отрезке интерполяционный многочлен равен константе, а именно левому или правому значению функции. Для левой кусочно-линейной интерполяции F(x)= fi-1, если xi-1 ?x

Методы аппроксимации функций

На каждом интервале функция является линейной Fi(x)=kix+li. Значения коэффициентов находятся из выполнения условий интерполяции в концах отрезка: Fi(xi-1)=fi-1, Fi(xi-1)=fi . Получаем систему уравнений: kixi-1+ li= fi-1, kixi+ li= fi , откуда находим ki=li= fi- kixi...

Методы решения системы линейных уравнений. Интерполяция

Постановка задачи интерполяции. На интервале задана система точек (узлы интерполяции) xi, i=0,1,…,N; a ? x i ? b, и значения неизвестной функции в этих узлах fn i=0,1,2,…,N. Могут быть поставлены следующие задачи: 1) Построить функцию F (x)...

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

3.1 Построение интерполяционного многочлена Лагранжа и сгущение значений Очевидный прием решения данной задачи - вычисление значений ѓ(x), воспользовавшись аналитическими значениями функции ѓ. Для этого - по исходной информации...

Если являются степенями {1, х, х2, …, хn}, то говорят об алгебраической интерполяции, а функцию называют интерполяционным полиномом и обозначим как: (4) Если () (5), то можно построить интерполяционный полином степени n и притом только один...

Практическое применение интерполирования гладких функций

Рассмотрим пример интерполяции для элементов множества. Для простоты и краткости возьмем =[-1;1], . Пусть точки и будут разными между собой. Поставим такую задачу: (12) построить многочлен, удовлетворяющий данным условиям...

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

Численные методы

Итак, как было сказано выше, задачей интерполяции является поиск такого многочлена, график которого проходит через заданные точки. Пусть функция y=f(x) задана с помощью таблицы (табл. 1)...

Численные методы решения математических задач

Кривые и поверхности, встречающиеся в практических задачах, часто имеют довольно сложную форму, не допускающую универсального аналитического задания в целом при помощи элементарных функций. Поэтому их собирают из сравнительно простых гладких фрагментов - отрезков (кривых) или вырезков (поверхностей), каждый из которых может быть вполне удовлетворительно описан при помощи элементарных функций одной или двух переменных. При этом вполне естественно потребовать, чтобы гладкие функции, которые используются для построения частичных кривых или поверхностей, имели схожую природу, например, были бы многочленами одинаковой степени. А чтобы получающаяся в результате кривая или поверхность оказалась достаточно гладкой, необходимо быть особенно внимательным в местах стыковки соответствующих фрагментов. Степень многочленов выбирается из простых геометрических соображений и, как правило, невелика. Для гладкого изменения касательной вдоль всей составной кривой достаточно описывать стыкуемые кривые при помощи много-членов третьей степени, кубических многочленов. Коэффициенты таких многочленов всегда можно подобратьтак, чтобы кривизна соответствующей составной кривой была непрерывной. Кубические сплайны, возникающие при решении одномерных задач, можно приспособить к посгрое нию фрагментов составных поверхностей. И здесь вполне естественно появляются бикубические сплайны, описываемые при помощи многочленов третьей степени по каждой из двух переменных. Работа с такими сплайнами требует уже значительно большего объема вычислений. Но правильно организованный процесс позволитучесть непрерывно нарастающие возможности вычислительной техники в максимальной степени. Сплайн-функции Пусть на отрезке , то есть Замечание. Индекс (t) у чисел а^ указывает на то. что набор коэффициентов, которым определяется функция 5(х), на каждом частичном отрезке Д, свой. На каждом из отрезков Д1, сплайн 5(х) является многочленом степени р и определяется на этом отрезке р + 1 коэффициентом. Всего частичных отрезков - то. Значит, для того, чтобы полностью определить сплайн, необходимо найти (р + 1)то чисел Условие) означает непрерывность функции 5(ж) и ее производных во всех внутренних узлах сетки ш. Число таких узлов m - 1. Тем самым, для отыскания коэффициентов всех многочленов получается р(т - 1) условий (уравнений). Для полного определения сплайна недостает (условий (уравнений). Выбор дополнительных условий определяется характером рассматриваемой задачи, а иногда и просто - желанием пользователя. ТЕОРИЯ СПЛАЙНОВ примеры решения Наиболее часто рассматриваются задачи интерполяции и сглаживания, когда требуется построить тот или иной сплайн по заданному массиву точек на плоскости В задачах интерполяции требуется, чтобы график сплайна проходил через точки что накладывает на его коэффициенты m + 1 дополнительных условий (уравнений). Остальные р - 1 условий (уравнений) для однозначного построения сплайна чаще всего задают в виде значений младших производных сплайна на концах рассматриваемого отрезка [а, 6] - граничных (краевых) условий. Возможность выбора различных граничных условий позволяет строить сплайны, обладающие самыми разными свойствами. В задачах сглаживания сплайн строят так, чтобы его график проходил вблизи точек (я»» У»), * = 0, 1,... , т, а не через них. Меру этой близости можно определять по-разному, что приводит к значительному разнообразию сглаживающих сплайнов. Описанные возможности выбора при построении сплайн-функций далеко не исчерпывают всего их многообразия. И если первоначально рассматривались только кусочно полиномиальные сплайн-функции, то по мере расширения сферы их приложений стали возникать сплайны, «склеенные» и из других элементарных функций. Интерполяционные кубические сплайны Постановка задачи интерполяции Пусть на отрезке [а, 6) задана сетка ш Рассмотрим набор чисел Задача. Построить гладкую на отрезке (а, 6] функцию которая принимает в узлах сетки о» заданные значения, то есть Замечание. Сформулированная задача интерполяции состоит в восстановлении гладкой функции, заданной таблично (рис. 2). Ясно, что такая задача имеет множество различных решений. Накладывая на конструируемую функцию дополнительные условия, можно добиться необходимой однозначности. В приложениях часто возникает необходимость приблизить функцию, заданную аналитически, при помощи функции с предписанными достаточно хорошими свойствами. Например, в тех случаях, когда вычисление значений заданной функции /(х) в точках отрезка [а, 6] связано со значительными трудностями и/или заданная функция /(х) не обладает требуемой гладкостью, удобно воспользоваться другой функцией, которая достаточно хорошо приближала бы заданную функцию и была лишена отмеченных ее недостатков. Задача интерполяции функции. Построить на отрезке [а, 6] гладкую функцию а(х), совпадающую в узлах сетки ш с заданной функцией /(х). Определение интерполяционного кубического сплайна Интерполяционным кубическим сплайном S(x) на сетке ш называется функция, которая 1) на каждом из отрезков, представляет собой многочлен третьей степени, 2) дважды непрерывно дифференцируема на отрезке [а, Ь], то есть принадлежит классу С2[а, 6], и 3) удовлетворяет условиям На каждом из отрезков сплайн S(x) является многочленом третьей степени и определяется на этом отрезке четырьмя коэффициентами. Всего отрезков - т. Значит, для того, чтобы полностью определить сплайн, необходимо найти 4т чисел Условие означает непрерывность функции S(x) и ее производных S"(x) и 5"(х) во всех внутренних узлах сетки ш. Число таких узлов - m - 1. Тем самым, для отыскания коэффициентов всех многочленов получается еще 3(m - 1) условий (уравнений). Вместе с условиями (2) получается условия (уравнения). Граничные (краевые) условия Два недостающих условия задаются в виде ограничений на значения сплайна и/или его производных на концах промежутка [а, 6]. При построении интерполяционного кубического сплайна наиболее часто используются краевые условия следующих четырех типов. A. Краевые условия 1-го типа. - наконцах промежутка [а, Ь] задаются значения первой производной искомой функции. Б. Краевые условия 2-го типа. - наконцах промежутка (а, 6) задаются значения второй производной искомой функции. B. Краевые условия 3-го типа. называются периодическими. Выполнения этих условий естественно требовать в тех случаях, когда интерполируемая функция является периодической с периодом Т = Ь-а. Г. Краевые условия 4-го типа. требуют особого комментария. Комментарий. Во внутренних узлах сепси третья производная функции S(x), вообще говоря, разрывна. Однако число разрывов третьей производной можно уменьшить при помоши условий 4-го типа. В этом случае построенный сплайн будет трижды непрерывно дифференцируем на промежутках Построение интерполяционного кубического сплайна Опишем способ вычисления коэффициентов кубического сплайна, при котором число величин, подлежащих определению, равно. На каждом из промежутков интерполяционная сплайн-функция ищется в следующем виде Здесь ТЕОРИЯ СПЛАЙНОВ примеры решения а числа являются решением системы линейных алгебраических уравнений, вид которой зависит от типа краевых условий. Для краевых условий 1-го и 2-го типов эта система имеет следующий вид где Коэффициенты зависят от выбора краевых условий. Краевые условия 1-го типа: Краевые услоемв 2-го типа: В случае краевых условий 3-го типа система для определения чисел записывается так Число неизвестных в последней системе равно тп, так как изусловия периодичности вытекает, что по = пт. Для краевых условий 4-го типа система для определения чисел, имеет вид где По найденному решению системы числа по и пт можно определить при помощи формул Важное замечание. Матрицы всех трех линейных алгебраических систем являются матрицами с диагональным преобладавшем. Тамие матрицы не вырождены, и потому каждая из этих систем имеет единственное решение. Теорема. Интерполяционный кубический сплайн, удовлетворяющий условиям (2) и краевому условию одного из перечисленных четырех типов, существует и единствен. Таким образом, построить интерполяционный кубический сплайн - это значит найти его коэффициенты Когда коэффициенты сплайна найдены, значение сплайна S(x) в произвольной точке отрезка [а, Ь] можно найти г!о формуле (3). Однако для практических вычислений больше подходит следующий алгоритм нахождения величины 5(ж). Пусть х 6 [х», Сначала вычисляются величины А и В по формулам а затем находится величина 5(ж): Применение этого алгоритма существенно сокращает вычислительные затраты на определение величины Советы пользователю Выбор граничных (краевых) условий и узлов интерполяции позволяет в известной степени управлять свойствами интерполяционных сплайнов. А. Выбор граничных (краевых) условий. Выбор граничных условий является одной из центральных проблем при интерполяции функций. Он приобретает особую важность в том случае, когда необходимо обеспечить высокую точность аппроксимации функции f(x) сплайном 5(ж) вблизи концов отрезка [а, 6). Граничные значения оказывают заметное влияние на поведение сплайна 5(ж) вблизи точек а и Ь, и это влияние по мере удаления от них быстро ослабевает. Выбор граничных условий часто определяется наличием дополнительных сведений о поведении аппроксимируемой функции f(x). Если на концах отрезка (а, 6] известны значения первой производной f"(x), то естественно воспользоваться краевыми условиями 1-го типа. Если на концах отрезка [а, 6) известны значения второй производной f"(x), то естественно воспользоваться краевыми условиями 2-го типа. Если есть возможность выбора между краевыми условиями 1-го и 2-го типов, то предпочтение следует отдать условиям 1- го типа. Если f(x) - периодическая функция, то следует остановиться накраевых условиях 3-го типа. В случае, если никакой дополнительной информации о поведении аппроксимируемой функции нет, часто используют так называемые естественные граничные условия Однако следует иметь ввиду, что при таком выборе граничны*условий точность аппроксимации функции f(x) сплайном S(x) вблизи концов отрезка (а, ft] резко снижается. Иногда используются краевые условия 1-го или 2-го типа, но не с точными значениями соответствующих производных, а с их разностными аппроксимациями. Точность такого подхода невысока. Практический опыт расчетов показывает, что в рассматриваемой ситуации наиболее целесообразным является выбор граничных условий 4-го типа. Б. Выбор узлов интерполяции. Если третья производная f""(x) функции терпитразрыв в не которыхточках отрезка [а, Ь], то для улучшения качества аппроксимации эти точки следует включить в число узлов интерполяции. Если разрывна вторая производная /"(х), то для того, чтобы избежать осцилляции сплайна вблизи точек разрыва, необходимо принять специальные меры. Обычно узлы интерполяции выбирают так, чтобы точки разрыва второй производной попадали внутрь промежутка \xif), такого, что. Величину а можно выбрать путем численного эксперимента (часто достаточно положить а =0,01). Существует набор рецептов по преодолению трудностей, возникающих при разрывной первой производной f"{x). В качестве одного из самых простых можно предложить такой: разбить отрезок аппроксимации на промежутки, где производная непрерывна, и на каждом из этих промежутков построить сплайн. Выбор интерполяционной функции (плюсы и минусы) Подход 1-й. Интерполяционный многочлен Лагранжа По заданному массиву ТЕОРИЯ СПЛАЙНОВ примеры решения (рис.3) интерполяционный многочлен Лагранжа определяется формулой Свойства интерполяционного многочленаЛагранжа целесообразно рассматривать с двух противоположных позиций, обсуждая основные достоинства отдельно от недостатков. Основные достоинства 1 -го подхода: 1) график интерполяционного многочлена Лагранжа проходит через каждую точку массива, 2) конструируемая функция легко описывается (число подлежащих определению коэффициентов интерполяционного многочлена Лагранжа на сетке и> равно m + 1), 3) построенная функция имеет непрерывные производные любого порядка, 4) заданным массивом интерполяционный многочлен определен однозначно. Основные недостатки 1 -го подхода: 1) степень интерполяционного многочлена Лагранжа зависит от числа узлов сетки, и чем больше это число, тем выше степень интерполяционного многочлена и, значит, тем больше требуется вычислений, 2) изменение хотя бы одной точки в массиве требует полного пересчета коэффициентов интерполяционного многочлена Лагранжа, 3) добавление новой точки в массив увеличивает степень интерполяционного многочлена Лагранжа на единицу и таиже приводит к полному пересчету его коэффициентов, 4) при неограниченном измельчении сетки степень интерполяционного многочлена Лагранжа неограниченно возрастает. Поведение интерполяционного многочлена Лагранжа при неограниченном измельчении сетки вообше требует особого внимания. Комментарии А. О приближении непрерывной функции многочленом. Известно (Вейерштрасс, 1885 год), что всякая непрерывная (а тем более гладкая) на отрезке функция может быть как угодно хорошо приближена на этом отрезке многочленом. Опишем этот факт на языке формул. Пусть f(x) - функция, непрерывная на отрезке [а, 6]. Тогдадл я любого е > 0 найдется такой многочлен Р„(х),чтодля любого х из промежутка [а, 6] будет выполняться неравенство (рис. 4) Отметим, что многочленов даже одной степени, приближающих функцию f(x) с указанной точностью, существует бесконечно много. Построим наотрезке [а, 6] сетку w. Ясно, что ее узлы, вообще говоря, не совпадают с точками пересечения графиков многочлена Рп(х) и функции f(x) (рис. 5). Поэтому для взятой сетки многочлен Рп(х) не является интерполяционным. При аппроксимации непрерывной функции интерполяционным многочленом Jla-гракжа его график не только не обязан быть близким графику функции f(x) в каждой точке отрезка [а, Ь), но может уклоняться от этой функции как угодно сильно. Приведем два примера. Пример 1 (Рунг, 1901 год). При неограниченном увеличении числа узлов для функции на отрезке [-1, 1] выполняется предельное равенство (рис.6) Пример 2 (Бериштейн, 1912год). Последовательность интерполяционных многочленов Лагранжа построенных на равномерных сетках шт для непрерывной функции /(х) = |х| на отрезке с возрастанием числе узлов т не стремится к функции /(х) (рис.7). Подход 2-й. Кусочно-лииейнм интерполяция При отказе от гладкости интерполируемой функции соотношение между числом достоинств и числом недостатков можно заметно изменить в сторону первых. Построим кусочно-линейную функцию путем последовательного соединения точек (xit у,) прямолинейными отрезками (рис. 8). Основные достоинства 2 -го подхода: 1) график кусочно-линейной функции проходит через каждую точку массива, 2) конструируемая функция легко описывается (число подлежащих определению коэффициентов соответствующих линейных функций для сетки (1) равно 2т), 3) заданным массивом построенная функция определена однозначно, 4) степень многочленов, используемых для описания интерполяционной функции, не зависит от числа узлов сетки (равна 1), 5) изменение одной точки в массиве требует вычисления четырех чисел (коэффициентов двух прямолинейных звеньев, исходящих из новой точки), 6) добавление дополнительной точки в массив требует вычисления четырех коэффициентов. Кусочно-линейная функция достаточно хорошо ведет себя и при измельчении сетки. я Основной недостаток 2-гоподхода: аппроксимирующая кусочно-линейная функция не является гладкой: первые производи ые терпят разрыв в узлах сетки (ушах интерполяции). Подход 3-й. Сплайн-интерполяция Предложенные подходы можно объединить так, чтобы число перечисленных достоинств обоих подходов сохранилось при одновременном уменьшении числа недостатков. Это можно сделать путем построения гладкой интерполяционной сплайн-функции степени р. Основные достоинства 3 -го подхода: 1) график построенной функции проходит через каждую точку массива, 2) конструируемая функция сравнительно легко описывается (число подлежащих определению коэффициентов соответствующих многочленов для сетки (1) равно 3) заданным массивом построенная функция определена однозначно, 4) степень многочленов не зависит от числа узлов сетки и, следовательно, не изменяется при его увеличении, 5) построенная функция имеет непрерывные производные до порядка р - 1 включительно, 6) построенная функция обладает хорошими аппроксимационными свойствами. Краткая справка. Предложенное название - сплайн - не является случайным - введенные нами гладкие ку-сочно-полиномиальныефункции и чертежные сплайны тесно связаны. Рассмотрим гибкую идеально тон кую линейку, проходящую через расположенные на плоскости (х, у) опорные точки массива. Согласно закону Бернулли-Эйлера линеаризованное уравнение изогнутой линейки имеет вид где S(x) - изгиб, М(х) - изменяющийся линейно от опоры к опоре изгибающий момент, Е1 - жесткость линейки. Функция S(x), описывающая формулинейки, является многочленом третьей степени между каждым и двумя соседними точками массива (опорами) и дважды непрерывно дифференцируема на всем промежутке (а, 6). Комментарий. 06 интерполировании непрерывной функции В отличие от интерполяционных многочленов Лагранжа, последовательность интерполяционных кубических сплайнов на равномерной сетке всегдасходится к интерполируемой непрерывной функции, причем с улучшением дифференциальных свойств этой функции скорость сходимости повышается. Пример. Для функции кубический сплайн на сетке с числом узлов m = 6 дает погрешность аппроксимации того же порядка, что и интерполяционный многочлен Ls(z), а на сетке с числом узлов m = 21 эта погрешность настолько мала, что в масштабе обычного книжного рисунка просто не может быть показана (рис.10) (интерполяционный многочлен 1>2о(г) дает в этом случае погрешность около 10 000 Ж). Свойства имтерполяцкокного кубического сплайна А. Алпроксимационмые свойства кубического сплайна. Аппроксимационные свойства интерполяционного сплайна зависят от гладкости функции f(x) - чем выше гладкость интерполируемой функции, тем выше порядок аппроксимации и при измельчении сетки тем выше скорость сходимости. Если интерполируемая функция f(x) непрерывна на отрезке Если интерполируемая функция f{x) имеет на отрезке [а, 6] непрерывную первую производную, то есть интерполяционный сплайн, удовлетворяющий граничным условиям 1-го или 3-го типа, то при h О имеем В этом случае не только сплайн сходится к интерполируемой функции, но и производная сплайна сходится к производной этой функции. В случае, если сплайн S(x) аппроксимирует на отрезке [а, Ь] функцию f(x), а его первая и вторая производные аппроксимируют соответственно функции Б. Экстремальное свойство кубического сплайна. Интерполяционный кубический сплайн обладает еще одним полезным свойством. Рассмотрим следующий пример. ример. Построить функцию/(х), минимизирующую функционал на классе функций из пространства С2, графики которых проходят через точки массива Среди всех функций, проходящих через опорные точки (х;, /(х,)) и принадлежащих указанному пространству, именно кубический сплайн 5(х), удовлетворяющий краевым условиям доставляет Экстремум (минимум) функционалу Замечание 1. Часто именно это экстремальное свойство берут в качестве определения интерполяционного кубического сплайна. Замечание 2. Интересно отметить, что интерполяционный кубический сплайн обладает описанным выше экстремальным свойством на очень широком классе функций, а именно, на классе |о, 5 ]. 1.2. Сглаживающие кубические сплайны О постановке задачи сглаживания Пусть заданы сетка и набор чисел Комментарий к исходным данным На практике часто приходится иметь дело со случаем, когда значения у, в массиве заданы с некоторой погрешностью. Фактически это означает, что для каждого указан интервал и любое число из этого интервала может быть взято в качестве значения у, . Величины у, удобно интерпретировать, например, как результаты измерений некоторой функции у(х) при заданных значениях переменной х, содержащие случайную погрешность. При решении задачи восстановления функции по таким ее «экспериментальным» значениям вряд ли целесообразно использовать интерполяцию, поскольку интерполяционная функция будет послушно воспроизводить причудливые осцилляции, обусловленные случайной компонентой в массиве {у,}. Более естественным является подход, основанный на процедуре сглаживания, призванной как-то уменьшить элемент случайности в результате измерений. Обычно в таких задачах требуется найти функцию, значения которой при х = ж, * = 0, 1,.... т, попадали бы в соответствующие интервалы и которая обладала бы, кроме того, достаточно хорошими свойствами. Например, имела бы непрерывные первые и вторые производные, или же ее график был бы не слишком сильно искривлен, то есть не имел бы сильных осцилляций. Задача подобного рода возникает и тогда, когда по заданному (точно) массиву требуется построить функцию, которая проходилабы нечереззаданныеточки, а вблизи них и к тому же изменялась достаточно плавно. Другими словами, искомая функция как бы сглаживала заданный массив, а не интерполировала его. Пусть заданы сетка ш и два набора чисел ТЕОРИЯ СПЛАЙНОВ примеры решения Задача. Построить гладкую на отрезке [а, А] функцию, значения которой в узлах сетки и» отличались от чисел у,- на заданные величины -Зшочтио. Сформулированная задача сглаживания состоит в восстановлении гладкой функции, заданной таблично. Ясно, что такая задача имеет множество различных решений. Накладывая на конструируемую функцию дополнительные условия, можно добиться необходимой однозначности. Определение сглаживающего кубического сплайна Сглаживающим кубическим сплайном S(x) на сетке ш называется функция, которая 1) на каждом из отрезков представляет собой многочлен третьей степени, 2) дважды непрерывно дифференцируема на отрезке [а, 6], то есть принадлежит классу С2 [а, Ь], 3) доставляет минимум функционалу где - заданные числа, 4) удовлетворяет граничным условиям одного из трех указанных ниже типов. Граничные (краевые) условия Граничные условия задаются в виде ограничений на значения сплайна и его производных в граничных узлах сетки ш. А. Граничные условия 1-го типа. - наконцах промежутка [а, Ь) задаются значения первой производной искомой функции. Граничные условия 2-го типа. - вторые производные искомой функции на концах промежутка (а, Ь] равны нулю. В. Граничные условия 3-го типа. называются периодическими. Теорема. Кубический сплайн S(x), минимизирующий функционал (4) и удовлетворяющий краевым условиям одного из указанных трех типов, определен однозначно. Определение. Кубический сплайн, минимизирующий функционал J(f) и удовлетворяющий граничным условиям i-готипа, называется сглаживающим сплайном i-готипа. Замечание. На каждом изотрезков(,сплайн 5(х) является миоючасном третьей степени и определяется на этом отрезке четырьмя коэффициентами. Всего отрезков - т. Значит, для того, чтобы полностью определять сплайн, необходимо найти 4т чисел Условие означает непрерывность функции 5(аг) и се производных во всех внутреннж узлах сетки о». Число таких узлов - m - 1. Тем самым, для отысивния коэффициентов всех многочленов получается 3(m - 1) условий (уравнений). Построение сглаживающего кубического сплайна Опишем способвычисления коэффициентов кубическогосплайна, при котором число величин, подлежащих определению, равно 2т + 2. На каждом из промежутков сглаживающая сплайн-функция ищется в следующем виде Здесь а числа и, являются решением системы линейных алгебраических уравнений, вид которой зависитот типа краевых условий. Опишем сначала, как находятся величины п*. Для краевых условий 1-го и 2-го типов система линейных уравнений для определения величин Hi записывается в следующем виде где известные числа). Коэффициенты зависят от выбора граничных условий. Граничные условия 1-го типа: Граничные условия 2-го типа: В случае граничных условий 3-го типа система для определения чисел записывается так: причем все коэффициенты вычисляются по формулам (5) (величины с индексами к и т + к считают я равными: Важно* замечание. Матрицы систем не вы рождены и потому каждая из этих систем имеет единственное решение. Если числа п,- найдены, то величины легко определяются по формулам где В случае периодических граничных условий Выбор еесоеш коэффициентов Выбор весовых коэффициентов р,-, входящих в функционал (4), позволяете известной степени управлять свойствами сглаживающих сплайнов. Если все и сглаживающий сплайн оказывается интерполяционным. Это, в частности, означает, что чем точнее заданы величины, тем меньше дошкн ы быть соотпетствуюшие весовые коэффициенты. Если же необходимо, чтобы сплайн прошел через точку (х^, Ук), то отвечающий ем у весовой множитель р\ следует поломить равным нулю. В практический вычислениях наиболее важым является выбор величин pi-Пусть Д, - погрешность измерения величины у,. Тогда естественно потребовать, чтобы сглаживающий сплайн удовлетворял условию или, что то же, В простейшем случае весовые коэффициенты pi можно задать, например, форму- где с - некоторая достаточно малая постоянная. Однако такой выбор весов р, не позволяет использовать «коридор», обусловленный погрешностями величин у,-. Более рациональный, но и более трудоемкий алгоритм определения величин р,- может выглядеть следующим образом. Если на fc-й итерации величины найдены,то полагают где е - малое число, которое выбирается экспериментально с учетом разрядной сетки компьютера, значений Д, и точности решения системы линейных алгебраических уравнений. Если на fc-й итерации в точке я, нарушилось условие (6), то последняя формула обеспечит уменьшение соответствующего весового коэффициента р,. Если же то на следующей итерации Увеличение р, приводит к более полному использованию «коридора» (6) и, в конечном счете, более плавно изменяющемуся сплайну. Немного теории А. Обоснование формул для вычисления коэффициентов интерполяционного кубического сплайна. Введем обозначения где m, - неизвестные пока величины. Их число равно m + 1. Сплайн, записанный в форме, где удовлетворяет условиям интерполяции и непрерывен на всем промежутке [а, Ь\: положив в формуле, получим соответственно Кроме того, он имеет на промежутке [а, 6] непрерывную первую производную: продифференцировав соотношение (7) и положив, пОлучим соответ-. ственно. Покажем, что числа т, можно выбрать так, чтобы сплайн-функция (7) имела на отрезке [а, 6] непрерывную вторую производную. Вычислим на промежутке вторую производную сплайна: В точке х, - 0 (при t = 1) имеем Вычислим на промежутке вторую производную сплайна В точке имеем Из условия непрерывности второй производной во внутренних узлах сетки а; получаем m - 1 соотношение где Добавляя к этим т - 1 уравнениям еще два, вытекающих и з краевых условий, получаем систему из m+ 1 линейного алгебраического уравнения с т + I неизвестной miy i = 0, 1. ... , m. Система уравнений для вычисления величин гщ в случае краевых условий 1-го и 2-го типов имеет вид где (краевые условия 1 -го типа), (краевые условия 2 -го типа). Для периодических краевых условий (краевыеусловия 3-го типа) сетку о; удлиняют еще на один узел и полагают Тогда система для определения величин го* будет иметь вид Для того чтобы получить систему уравнений для определения чисел го, в случае краевых условий 4-го типа, найдем на отрезке [ третью производную сплайна (7) и потребуем ее непрерывности во втором и (го - !)-м узлах сетки. Имеем Из последних двух соотношений получаем недостающие два уравнения, отвечающие краевым условиям 4 -го типа: Исключая из уравнений неизвестное гоо, а из уравнений неизвестное пц, в результате получим систему уравнений Отметим, что число неизвестных в этой системе равно го - I. 6. Обоснование формул дм вычисления юэффиие кто« сглаживающего субичессого сплайна. Введем обозначения где Zi и nj - неизвестные пока величины. Их число равно 2т + 2. Сплайн-функиия, записанная в форме непрерывна на всем промежутке (а, 6]: положив в этой формуле, получим соответственно Покажем, что числа z, и п, можно выбратьтак, чтобы сплайн, записанный в форме (8), имел на промежутке [а, 6] непрерывную первую производную. Вычислим первую производную сплайна S(x) на промежутке : В точке х^ - 0 (при t = 1) имеем Вычислим первую производаую сплайна 5(х) на промежутке : В точке имеем Из условия непрерывности первой производой сплайна во внутренних узлах сетки и --> получаем m - 1 соотношение Эту связь удобно записать в матричной форме Здесь использованы следующие обозначения Кроме того, сплайн на промежутке [а, 6} имеет непрерывную вторую производную: продифференцировав соотношение (8) и положив, получим соответственно Еше олю матричное соотношение получается из условия минимума функционала (4). Имеем Два последних матричных равенства можно рассматривать как линейную систему 2т+2 линейных алгебраических уравнений относительно 2т + 2 неизвестных. Заменяя в первом равенстве столбец г его выражением, полученным из соотношения (9), приходим к матричному уравнению ТЕОРИЯ СПЛАЙНОВ примеры решения для определения столбца М. Это уравнение имеет единственное решение вследствие того, что матрица A + 6HRH7 всегда невырождена. НаЙдяего, мылегко определяем г. Эамсшине. Элементы трелдмаголальн ых матриц А и Н определяющие я только параметрами сетки и (сс шагами hi) и не зависят от величин у^. Линейное пространство кубических сплайн-функций Множество кубических сплайнов, построенных на отрезке [а, 6) по сетке wcra+l узлом, является линейным пространством размерности т + 3: 1) сумма двух кубических сплайнов, построенных по сетке и>, и произведение кубического сплайна, построенного по сетке и>, на произвольное число тайнее являются кубическими сплайнами, построенными по этой сетке, 2) любой кубический сплайн, построенный по сетке и из узла, полностью определяется т + 1 значением величин у» в этих узлах и двумя граничными условиями - всего то + 3 параметрами. Выбрав в этом пространстве базис, состоящий из m + 3 линейно независимых сплайнов, мы можем записать произвольный кубический сплайн а(х) в виде их линейной комбинации причем единственным образом. Замечание. Подобное задание сплайна широко распространено в вычислительной практике. Особенно удобным является базнс, состоящий из так называемых кубических В -сплайнов (базовых, или фундаментальных, сплайнов). Применение Д-сплайнов позволяет существенно снизить требования к объему памяти компьютера. Л-сплайны. В -сплайномнулевой степени, построенным на числовой прямой по сетке ш, называется функция вила В -сплайн степени к ^ I, построенный на числовой прямой по сетке иг, определяется посредством рекуррентной формулы Графики В -сплайнов первой В,-1"(ж) и второй в\7\х) степеней представлены на рис. 11 и 12 соответственно. В-сплайн произвольной степени к может быть отличен от нуля только на некотором отрезке (определяемом к + 2 узлами). Кубические В-сплайны удобнее нумеровать так, чтобы сплайн В,-3* (я) был отличен от нуля на отрезке яг,-+2]. Приведем формулу для кубического сплайна третьей степени для случая равномерной сетки (с шагом Л). Имеем в остальных случаях. Типичный график кубического В-сплайна представлен на рис. 13. Займами*. функция а) дважды непрерывно дифференцируема на отрезке то есть принадлежат классу С2[а, »}, к б) отлична от нуля толь ко на четырех последовательных отрезках (Дополним сетку ш вспомогательными узлами взятыми совершенно произвольно. По расширенной сетке ш* можно построить семейство из m + 3 кубических В -сплайнов: Это семейство образует базис в пространстве кубических сплайнов на отрезке (а, Ь]. Тем самым, произвольный кубический сплайн S(z), построенный на отрезке |в, 6] посетке о; изт+1 узла, может быть представлен наэтом отрезке в виде линейной комбинации Условиями задачи коэффициенты ft, этого разложения определяются однозначно. ... В случае, когда заданы значения у* функции в узлах сетки и значения у о и Ут первой производной функции на концах сетки"(задача интерполяций с граничными условиями первого рода), эти коэффициенты вычисляются из системы следующего вида После исключения величин б-i и &m+i получается линейная система с неизвестными 5q, ... , Ьт и трех диаюнальной матрицей. Условие обеспечивает диагональное преобладание и, значит, возможность применения метода прогонки для ее разрешения. 3ММЧМЮ 1. Линейные системы аналогичного вида возникают лрн рассмотрении и других задач интерполяции. Зммчнм* 2. В сравнении с алгоритмами, описанными в раздеде 1.1, применение Я-сплайн в * задачах интерполяции позволяет уменьшит* объем хранимой информации, то есть сушественно снизить требования к объему памяти компьютере, хотя и приводит к увеличению числа операций. Построение сплайноаых кривых при помощи сплайн-функций Выше рассматривались массивы, точки которых были занумерованы так, что их абсциссы образовывали строго возрастающую последовательность. Например, случай, изображенный на рис. 14, когда у разных точек массива одинаковые абсциссы, не допускался. Это обстоятельств о определяло и выбор класса аппроксимирующих кривых (трафики функций), и способ их построения. Однако предложенный выше метод позволяет достаточно успешно строить интерполяционную кривую и в более общем случае, когда нумерация точек массива и их расположение на плоскости, как правило, не связаны (рис. 15). Более того, ставя задачу построения интерполяционной кривой, можно считать заданный массив неплоски м, то есть Ясно, что для решения этой общей задачи необходимо существенно расширить класс допусти мых кривых, включив в него и замкнутые кривые, и кривые, имеющие точки самопересечения, и пространственные кривые. Такие кривые удобно описывать при помощи параметрических уравнений Потребуем. дополнительно, чтобы функции обладали достаточной гладкостью, например, принадлежали классу С1 [а, /0] или классу Для отыскания параметрических уравнений кривой, последовательно проходящей через все точки массива, поступают следующим образом. 1-й шаг. На произвольно взятом отрезке }