Пусть задана таблица значений функции 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)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Уральский федеральный университет имени первого Президента России Б.Н.Ельцина»

Институт радиоэлектроники и информационных технологий - РТФ

Кафедра Автоматика и информационные технологии

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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К лабороторной работе ПО ДИСЦИПЛИНЕ «Численные методы»

Составитель И.А.Селиванова, ст.преподаватель.

ИНТЕРПОЛЯЦИЯ СПЛАЙНАМИ: Методические указания к практическим занятиям по дисциплине «Численные методы»

Указания предназначены для студентов всех форм обучения направления 230100 – «Информатика и вычислительная техника».

Ó ФГАОУ ВПО «УрФУ имени первого Президента России Б.Н.Ельцина», 2011

1. ИНТЕРПОЛЯЦИЯ СПЛАЙНАМИ. 4

1.1. Кубические сплайны. 4

1.2. Специальная форма записи сплайна. 5

1.3. Квадратичные сплайны. 13

1.4. Задание на практику. 18

1.5. Варианты заданий. 19

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

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

В случаях, когда промежуток [a ,b ], на котором требуется заменить функцию f (x ) велик, можно применить интерполяцию сплайнами.

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

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

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

Для построения искомого сплайна требуется найти коэффициенты
многочленов
,i =1,… n , т.е. 4 n неизвестных коэффициента, которые удовлетворяют 4 n -2 уравнениям (1), (2), (3). Чтобы система уравнений имела решение, добавляют еще два дополнительных (краевых) условия. Используется три типа краевых условий:

Условия (1), (2), (3) и одно из условий (4), (5), (6) образуют СЛАУ порядка 4 n . Решение системы можно провести с помощью метода Гаусса. Однако, выбрав специальную форму записи кубического многочлена, можно существенно снизить порядок решаемой системы уравнений.

1.2. Специальная форма записи сплайна.

Рассмотрим отрезок
. Введем следующие обозначения переменных:

Здесь
- длина отрезка
,

,
- вспомогательные переменные,

x – промежуточная точка на отрезке
.

Когда x пробегает все значения на интервале
, переменнаяизменяется от 0 до 1, а
изменяется от 1 до 0.

Пусть кубический многочлен
на отрезке
имеет вид:

Переменные и
определяются применительно к конкретному отрезку интерполяции.

Найдем значение сплайна
на концах отрезка
. Точка
является начальной для отрезка
, поэтому=0,
=1 и в соответствии с (3.8):
.

На конце отрезка
=1,
=0 и
.

Для интервала
точка
является конечной, поэтому=1,
=0 и из формулы (9) получаем:
. Таким образом, выполняется условие непрерывности функцииS (x ) в узлах стыковки кубических многочленов независимо от выбора чисел  i .

Для определения коэффициентов  i , i =0,… n продифференцируем (8) дважды как сложную функцию от x . Тогда

Определим вторые производные сплайна
и
:

Для многочлена
точкаявляется началом отрезка интерполяции и=0,
=1, поэтому

Из (15) и (16) следует, что на отрезке [a ,b ]сплайн-функция, «склеенная» из кусков многочленов 3-го порядка, имеет непрерывную производную 2-го порядка.

Чтобы получить непрерывность первой производной функции S (x ), потребуем во внутренних узлах интерполяции выполнения условия:

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

и система уравнений (17) будет иметь вид:

Пример .

Исходные данные:

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

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

Для разных краевых условий (4), (5), (6) найдем коэффициенты кубических сплайнов.

1. Рассмотрим первые краевые условия.

В нашем случае n =3,
,
,
. Чтобы найти
используем систему уравнений (3.18):

Вычислим и, используя формулы (7) и (11):

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

.

Решение системы:

С учетом первых краевых условий коэффициенты сплайна:

Рассмотрим определение коэффициентов сплайна с учетом краевых условий (3.5):

Найдем производную функции
:

Вычислим
и
:

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

Используя формулу (20) определим  0 и  3:

С учетом конкретных значений:

и вектор коэффициентов:

Рассчитаем значения кубического сплайна S(x) в серединах отрезков интерполяции.

Середины отрезков:

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

3.1.

Найдем и
:

В формулу (3.9) подставляем коэффициенты

3.2.

Найдем и
:

, для краевых условий (4), (5), (6):

3.3.

Найдем и
:

В формулу (9) подставляем коэффициенты
, для краевых условий (4), (5), (6):

Составим таблицу:

	(1 кр.усл.)	(2 кр.усл.)	(3 кр.усл.)

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

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

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

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

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

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

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

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

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

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

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

(7)

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

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

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

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

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

Слово сплайн (английское слово "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) для определения суммы квадратов отклонений примет вид:

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

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

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

Концепция интерполяции

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

В связи с интерполяцией рассматриваются три основные проблемы.

1) выбор интерполяционной функции L (x );

2) оценка погрешности интерполяции R (x );

3) размещение узлов интерполяции для обеспечения наивысшей возможной точности восстановления функции (x 1 , x 2 ,…,x n ).

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

Рис. 3.2 Иллюстрация интерполяции

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

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

Линейная интерполяция

Простейшим и часто используемым видом локальной интерполяции является линейная интерполяция. Она состоит в том, что заданные точки М (x i , y i ) (i = 0, 1, …, n ) соединяются прямолинейными отрезками, и функция f (x ) приближается к ломаной с вершинами в данных точках (рис. 3.3).

Рис. 3.3 Линейная интерполяция

Уравнения каждого отрезка ломаной линии в общем случае разные. Поскольку имеется n интервалов (x i , x i + 1), то для каждого из них в качестве уравнения

интерполяционного полинома используется уравнение прямой, проходящей через две точки. В частности, для i — го интервала можно написать уравнение прямой, проходящей через точки (x i , y i ) и (x i + 1 , y i + 1), в виде:

(3.2)

Следовательно, при использовании линейной интерполяции сначала нужно определить интервал, в который попадает значение аргумента x , а затем подставить его в формулу (3.2) и найти приближенное значение функций в этой точке.

На рисунке 3.4 представлен пример использования линейной интерполяции в программе MathCAD. Для линейной интерполяции используется функция linterp (x ,y ,z ). Здесь x , y – исходные данные, z – точка, в которой находится значение функции.

Рис. 3.4. Линейная интерполяция

Квадратичная интерполяция

В случае квадратичной интерполяции в качестве интерполяционной функции на отрезке (x i — 1 ,x i + 1) принимается квадратный трехчлен. Уравнения квадратного трехчлена имеет вид

y = a i x 2 + b i x + c i , x i — 1 x x i + 1 , (3.3)

Интерполяция для любой точки x [x 0 , x n ] проводится по трем ближайшим точкам.

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

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

Рассмотренные выше методы локальной интерполяции, по существу, является простейшим сплайном первой степени (для линейной интерполяции) и второй степени (для квадратичной интерполяции).

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

В общем случае для функции y = f (x ) требуется найти приближение y= j (x ) таким образом, чтобы f (x i ) = j (x i ) в точках x = x i , a в остальных точках отрезка [a, b ] значения

функций f (x ) и j (x ) были близкими между собой. При малом числе экспериментальных точек (например, 6-8) для решения задачи интерполяции можно использовать один из методов построения интерполяционных полиномов. Однако при большом числе узлов интерполяционные полиномы становятся практически непригодными. Это связано с тем, что степень интерполяционного полинома лишь на единицу меньше числа экспериментальных значений функций. Можно, конечно, отрезок, на котором определена функция, разбить на участки, содержащие малое число экспериментальных точек, и для каждого из них построить интерполяционные полиномы. Однако в этом случае аппроксимирующая функция будет иметь точки, где производная не является непрерывной, т. е. график функции будет содержать точки “излома”.

Кубические сплайны лишены этого недостатка. Исследования теории балок показали, что гибкая тонкая балка между двумя узлами достаточно хорошо описывается кубическим полиномом, и поскольку она не разрушается, то аппроксимирующая функция должна быть, по меньшей мере, непрерывно дифференцируемой. Это означает, что функции j (x ), j’ (x ), j» (x ) должны быть непрерывными на отрезке [a, b ].

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

1. на каждом сегменте [x i — 1 , x i ], i = 1, 2, ..., n функция y (x ) является полиномом третьей степени,

Функция y (x ), а также ее первая и вторая производные непрерывны на отрезке [a,b ],

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

Для всего интервала будет соответственно п кубических полиномов, отличающихся коэффициентами а i , b i , c i , d i . Чаще всего узлы при сплайновой интерполяции располагают равномерно, т.е. х i +1 -х i = const = h (хотя это и необязательно).

Необходимо найти четыре коэффициента при условии прохождения каждого полинома через две точки (x i , y i ) и (x i +1 , y i +1 ) , следствием чего являются следующие очевидные уравнения:

Первое условие соответствует прохождению полинома через начальную точку, второе - через конечную точку. Найти все коэффициенты из этих уравнений нельзя, так как условий меньше, чем искомых параметров. Поэтому указанные условия дополняют условиями гладкости функции (т.е. непрерывности первой производной) и гладкости первой производной (т.е. непрерывности второй производной) в узлах интерполяции. Математически эти условия записываются как равенства соответственно первой и второй производных в конце i -го и в начале (i +1 )-го участков.

Так как и , то

(y ’ (x i +1 ) в конце i -го участка равна у’ (х i +1 ) в начале (i +1 )-го),

(у» (х i +1 ) в конце i -го участка равна у» (х i +1 ) в начале (i +1)-го).

Получилась система линейных уравнений (для всех участков), содержащая 4n — 2 уравнения с 4n неизвестными (неизвестные a 1 , a 2 ,…, a n , b 1 ,…, d n - коэффициенты сплайнов). Для решения системы добавляют два граничных условия одного из следующих видов (чаще применяют 1):

Совместное решение 4n уравнений позволяет найти все 4n коэффициента.

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

Решим задачу об интерполяции с помощью программы MathCAD. Для этого воспользуемся встроенной функцией interp(VS,x,y,z) . Переменные x и y задают координаты узловых точек, z является аргументом функции, VS определяет тип

граничных условий на концах интервала.

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

Здесь cspline ( VX , VY ) возвращает вектор VS вторых производных при приближении в опорных точках к кубическому полиному;

pspline (VX , VY ) возвращает вектор VS вторых производных при приближении к опорным точкам к параболической кривой;

lspline (VX , VY ) возвращает вектор VS вторых производных при приближении к опорным точкам прямой;

interp (VS , VX , VY , x ) возвращает значение y (x ) для заданных векторов VS , VX , VY и заданного значения x .

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

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

Рис. 3.5 Кубическая сплайн интерполяция

Если функция задана дискретно, то для интерполяции задаются матрицы данных.

При глобальной интерполяции наиболее часто используется интерполяция полиномом n -ой степени или интерполяция Лагранжа.

Классический подход основывается на требовании строгого совпадения значений f (х ) и j (х ) в точках х i (i = 0, 1, 2, … n ).

Будем искать интерполяционную функцию j (х ) в виде полинома степени n .

Этот полином имеет n + 1 коэффициент. Естественно предположить, что n + 1 условий

j (x 0) = y 0 , j (x 1) = y 1 , . . ., j (x n ) = y n (3.4)

наложенные на полином

позволяют однозначно определить его коэффициенты. Действительно, требуя для j (х ) выполнение условий (3.4), получаем систему n + 1 уравнений с n + 1 неизвестными:

(3.6)

Решая эту систему относительно неизвестных a 0 , a 1 , …, a n мы получим аналитическое выражение полинома (3.5). Система (3.6) всегда имеет единственное решение, т.к. её определитель

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

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

Интерполяционная формула Лагранжа

Пусть известны значения некоторой функции f (х) в п+ 1 различных произвольных точках y i = f (x i ) , i = 0,…, п. Для интерполирования (восстановления) функции в какой-либо точке х, принадлежащей отрезку [х 0 ,х п ], необходимо построить интерполяционный полином n-го порядка, который в методе Лагранжа представляется следующим образом:

Причем нетрудно заметить, что Q j (x i ) = 0, если i ¹ j , и Q j (x i ) =1, если i = j . Если раскрыть произведение всех скобок в числителе (в знаменателе все скобки - числа), то получим полином n-го порядка от х, так как в числителе содержится n сомножителей первого порядка. Следовательно, интерполяционный полином Лагранжа не что иное, как обычный полином n-го порядка, несмотря на специфическую форму записи.

Оценить погрешность интерполяции в точке х из [х 0 ,х n ] (т.е. решить вторую

проблему интерполяции) можно по формуле

В формуле - максимальное значение (n+1)-й производной исходной функции f (х) на отрезке [х 0 ,х n ]. Следовательно, для того чтобы оценить погрешность интерполяции, необходима некоторая дополнительная информация об исходной функции (это должно быть понятно, так как через заданные исходные точки может проходить бесчисленное количество различных функций, для которых и погрешность будет разной). Такой информацией является производная n+1 порядка, которую не так просто найти. Ниже будет показано, как выйти из такого положения. Отметим также, что применение формулы погрешности возможно, только если функция дифференцируема n +1 раз.

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

if (cond , х, у )

Возвращает значение х, если cond отличен от 0 (истина). Возвращает значение у, если cond равен 0 (ложь) (рисунок 3.6).