Аппроксимация и интерполяция

 

 

 

 

 

          Оценка проекта (работы)_________

 

 

Члены комиссии ______________

 

______________

 

______________

 

 

 

 

МЕТОДЫ  АПРОКСИМАЦИИ И ИНТЕРПОЛЯЦИИ

Пояснительная записка  к курсовой работе

по дисциплине «Вычислительная  математика»

 

23.01 000000 471 ПЗ

 

 

 

 

 

 

 

 

 

Руководитель: И. А. Селиванова 
старший преподаватель

 

 

Студент: А. И. Колосов 
гр. Н-25031

 

2007 
Содержание

 

Введение………………………………………………………………………….3

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

2. Специальные формы записи  сплайнов…………………………………..8

2.1. 1я специальная форма записи сплайнов…………………………..8

Примеры……………………………………………………………………..12

2.2. 2я специальная форма записи сплайнов……………………….15

Примеры……………………………………………………………………..17

Выводы………………………………………………………………………….21

Библиографический список………………………………………………….22

Приложение…………………………………………………………………….23

 

Введение

 

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

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

Сплайн - группа сопряженных многочленов n-ного порядка, в местах сопряжения которых производные до n-1 порядка непрерывны.

 

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

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

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

Определение. Функция S_m(x) называется интерполяционным сплайном порядка т для функцииf(х), заданной таблицей

X	x0	xi	…	xn
У	y0	yi	…	yп

Рис 1.1 Общий  вид сплайн-функции

если:

1)  на каждом отрезке  [х_i; х_i+1] (i= 0, 1, ..., n-1) S(x) является многочленом порядка т;

2)  S(x) и ее производные до (т - 1)-го порядка включительно непрерывны на [х₀; х_n];

3)  S(x_i) = у_i   (i = 0, 1, ..., n) — непосредственно условие интерполяции.

Можно доказать, что эти условия достаточны для  существования сплайна порядка т (т > 2), но не гарантируют его единственности.

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

Пусть форма  этого стержня определяется функцией y = S(x). Из курса сопротивления материалов известно, что уравнение свободного равновесия имеет вид S^IV(x) = 0. Отсюда следует, что между каждой парой соседних узлов интерполяции функция S(x) является многочленом третьей степени, поэтому в практике аппроксимации функций наиболее популярны кубические сплайны. Согласно определению кубический сплайн S(x) можно представить в виде:

	(1.1)

Исходя из определения  сплайна, составим систему уравнений, позволяющую найти коэффициенты {a_i}, {b_i}, {c_i} и {d_i}:

(1.2)

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

(1.3)

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

1. S₁^I(x₀) = f ^I(x₀₎ 
   S_n^I(x_n) = f ^I(x_n)
2. S₁^II(x₀) = f ^II(x₀) 
   S_n^II(x_n) = f ^II(x_n)
3. Естественный кубический сплайн (частный случай ситуации п.2): 
   S₁^I(x₀) = 0 
   S_n^I(x_n) = 0

Преобразуем эти уравнения:

1. S₁^I(x₀) = b₁ + 2c₁x₀ + 3d₁x₀² =f ^I(x₀) 
   S_n^I(x_n) = b_n + 2c_nx_n + 3d_nx_n² =f ^I(x_n)
2. S₁^II(x₀) = 2c₁ + 6d₁x₀ =f^II(x₀) 
   S_n^II(x_n) = 2c_n + 6d_nx_n =f^II(x_n)
3. S₁^II(x₀) = 2c₁ + 6d₁x₀ = 0 
   S_n^II(x_n) = 2c_n + 6d_nx_n = 0

Составим систему  уравнений для вычисления коэффициентов {a_i}, {b_i}, {c_i} и {d_i}:

(1.4)

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

(1.5)

или на 2 таких

(1.6)

для описания естественного  кубического сплайна.

Пример: построить интерполяционную сплайн-функцию по следующим данным:

X	-1	1	3	f II(-1) = 3, f II(3) = -1.
f(x)	-2	2	3

 

Будем строить  сплайны вида . Составим систему вида (1.4), но вместо последних 2х уравнений возьмем пару (1.5):

Решая систему, получим следующие значения искомых коэффициентов:

Получим такие  сплайны:

Проверка:

Рис.1.2 сплайн-интерполяция таблично заданной функции

 

 

Специальные формы записи сплайнов

Система, получаемая при стандартной форме записи сплайна очень неудобна для вычислений из-за своей размерности. Чтобы упростить  вычисления, разработан ряд специальных форм записи сплайнов.

 

1я  специальная форма записи сплайнов

 

Введем несколько  обозначений:

		(2.1.1)
		(2.1.2)
		(2.1.3)
Приведем иллюстрацию  поведения переменных и на отрезке	Рис 2.1.1 Поведение и
		(2.1.4)
		(2.1.5)

Получим такую  запись сплайна отрезке  :

	(2.1.6)
	(2.1.7)

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

	(2.1.8)
	(2.1.9)

	(2.1.10)

Составим систему уравнений вида (2.1.10) для

(2.1.11)

Система, формируемая для , имеет n-1 уравнений и n+1 неизвестных . Чтобы такая система имела единственное решение, составим еще 2 уравнения, используя краевые условия, и выразим коэффициенты и :

по (2.1.8):             при i = 0      при i = n – 1	(2.1.12)
по (2.1.9):   при i = 0      при i = n – 1	(2.1.13)
Воспользуемся решениями п. 2 для . Получим	(2.1.14)

Преобразуем систему (2.1.11) в соответствии с подстановками (2.1.12) и (2.1.13):

1)  по (2.1.12)
	(2.1.15)

 

2)  по (2.1.13)
	(2.1.16)
3)  по (2.1.13) для естественного кубического сплайна
	(2.1.17)

Системы (2.1.15), (2.1.16) и (2.1.17) содержат лишь неизвестные и являются системами линейных алгебраических уравнений с трехдиагональной матрицей, которую удобно решать методом прогонки. После решения системы надо вычислить коэффициенты и по формулам (2.2.12) или (2.1.13). Для естественного кубического сплайна . Найдя все неизвестные , по формуле (2.1.6) восстановим куски интерполирующей функции. На этом построение кубического сплайна завершится.

 

Пример. Построить кубический сплайн для функции y=f(x), заданной таблицей:

x	-1	0	1	3	1)
f(x)	½	1	2	8	2)
h		1	1	2	3)
∆		½	1	3

1) Т.к. дополнительные условия описывают поведение 1й производной, составим систему вида (2.1.15):