birmaga.ru
добавить свой файл

1
Интерполяционные кубические сплайны

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

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


Пример Бернштейна (1916 г.)

на [–1;1]






Пример Рунге (1925 г.)

на [–1;1]






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


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

Пусть на отрезке задана упорядоченная система несовпадающих точек: .

Определение. Сплайном S(x) дефекта d называется определенная на отрезке [ab] функция, md раз непрерывно дифференцируемая, которая на каждом отрезке [xk–1xk], , является многочленом m-ой степени.

Таким образом, , где l = m – d.

Если на некотором наборе точек значения сплайна S(x) совпадают со значениями функции f (x), то такой сплайн называется интерполяционным сплайном для функции f (x); при этом узлы сплайна , вообще говоря, могут не совпадать с узлами интерполяции.

Совпадение дефекта сплайна с его степенью (m = d) обеспечивает просто непрерывность сплайна. Интерес представляет построение сплайнов с большей гладкостью, то есть с малым дефектом. Наиболее известным и широко применяемым является кубический сплайн дефекта 1.

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


S(x) – многочлен степени не выше третьей при ;

(1)

;

(2)

.

(3)

Если при этом сплайн удовлетворяет условию

,

(4)

то он называется натуральным интерполяционным кубическим сплайном (НИКС).

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

Заметим, что сплайн – это не многочлен, но на каждом частичном отрезке является многочленом (свой для каждого частичного отрезка). Если на отрезке [xkxk–1] искать сплайн в виде , то задача об отыскании интерполяционного сплайна на всем отрезке [ab] сводится к отысканию 4n коэффициентов . Несмотря на то, что при этом получается система линейных уравнений с большим количеством нулевых коэффициентов, при больших n эта задача является довольно сложной.

Рассмотрим другой подход к отысканию вида сплайна.

Обозначим значения второй производной (их называют моментами) сплайна в узлах через Mk = S ''(xk), . Обозначим также через hk = xk – xk–1, .

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

S ''(x) =  (x – xk–1) +  (xk – x).

Поскольку в узлах xk вторая производная должна принимать значения Mk, то мы можем выразить и через Mk :



Значит,


.

(5)

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

,

(6)

.





Запишем S(x) в более удобном для дальнейших рассуждений виде:

,

(7)

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



Таким образом, (6) и (7) принимают вид:

,

(8)



.

(9)

Для того, чтобы была непрерывной, должны выполняться условия

.

Используя (8), получаем


После преобразований эти равенства принимают вид:


k Mk–1 + 2 Mk + k Mk+1 = dk, ,

(10)

где , , .

(11)

Cистема (10)-(11) называется системой определяющих соотношений через моменты.

Условия (4) в наших обозначениях перепишутся как


M0 = 0, Mn = 0.

(12)

Добавим (12) к (10)-(11), причем первое из этих условий запишем перед уравнениями (10), а второе условие – после (10). Тогда мы получаем систему (n+1) линейных уравнений с (n+1) неизвестными Mk, . Заметим, что полученная система имеет трёхдиагональную матрицу с преобладанием главной диагонали. В теме «Метод прогонки» было доказано, что решение такой системы существует и единственно. Следовательно, значения Mk, , определяются единственным образом, а значит, и сплайн единственен. При этом на каждом частичном отрезке сплайн определяется формулой (9). Таким образом мы доказали следующее утверждение.

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

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

Факт и скорость сходимости сплайн-интерполяционного процесса характеризует следующее утверждение, которое приведем без доказательства.

Теорема. Пусть S(x) – кубический сплайн дефекта 1, интерполирующий на системе узлов четырежды непрерывную на отрезке [a,b] функцию f(x). Тогда при любом фиксированном n найдется такая постоянная > 0, что для любого x[a,b] справедливо неравенство: , где .
Пример. Пусть функция f(x) задана таблицей своих значений:


k

0

1

2

3

xk

–4

–2

0

2

yk


12

2

4

6

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



Подставляем найденные значения в формулу (9):




– –