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

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Уфимский государственный авиационный технический университет

КУРСОВАЯ РАБОТА

«Интерполяция методом кубического сплайна»

Выполнил: студент гр. ПО-232

Проверила: Гадилова Ф.Г.

Уфа 2010

СОДЕРЖАНИЕ

Введение

1. Определение сплайна

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

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

4. Метод прогонки

5. Код программы

6. Обзор работы программы

Заключение

Список использованной литературы

ВВЕДЕНИЕ.

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

Постановка задачи: разработать программу для интерполяции произвольной функции методом кубического сплайна. В качестве отладочного примера используем функцию sinx на промежутке [0;р] , а так же вычислим погрешность ?max (максимальная погрешность), ?ос (оценочная погрешность), ?dk (коэффициент уменьшения погрешности).

1 ОПРЕДЕЛЕНИЕ СПЛАЙНА

Пусть отрезок [a,b] разбит на n равных частей [x_i, x_i+1], где x_i=a+ih, i=0,...,n, x_n=b, h=(b-a)/n.

Сплайном называется функция, которая вместе с несколькими производными непрерывна на всем заданном отрезке [a,b], а на каждом частичном отрезке [x_i, x_i+1] в отдельности является некоторым алгебраическим многочленом.

Максимальная по всем частичным отрезкам степень многочленов называется степенью сплайна, а разность между степенью сплайна и порядком наивысшей непрерывной на [a,b] производной - дефектом сплайна.

Определение. Функция S_n,(x) называется сплайном степени n дефекта (-целое число, 0n+1) с узлами на сетке (: a=x₀< <x_i<...<x_n=b), если:

а) на каждом отрезке [x_i,x _i+1] функция S_n, (x) является многочленом степени n, то есть для x[x_i, x_i+1] , i=0,...,n-1;

б) S _n,(x)C^n-v[a,b] (для целого k>0 через C^k =C^k[a,b] обозначается множество k раз непрерывно дифференцируемых на [a,b] функций).

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

На практике широкое распространение получили сплайны третьей степени, имеющие на [a,b] непрерывную, по крайней мере, первую производную. Эти сплайны называются кубическими и обозначаются S₃(x) (без указания дефекта).

Пусть на отрезке [a,b] в узлах сетки заданы значения некоторой функции f_i =f(x_i), i=0,...,n.

Интерполяционным кубическим сплайном S₃(x) называется сплайн

S₃(x)=а_i0 +а_i1(x - x_i)+а_i2(x - x_i)² +а_i3(x - x_i)³, x[x_i, x_i+1], (1.1)

удовлетворяющий условиям

S₃(x_i)=f(x_i), i=0,...,n. (1.2)

Сплайн (1.1) на каждом из отрезков [x_i, x_i+1], i=0,...,n-1 определяется четырьмя коэффициентами, и поэтому для его построения на всем промежутке [a,b] необходимо определить 4n коэффициентов. Для их однозначного определения необходимо задать 4n уравнений.

Условие (1.2) дает 2n уравнений, при этом функция S₃(x_i), удовлетворяющая этим условиям, будет непрерывна во всех внутренних узлах.

Условие непрерывности производных сплайна , r=1,2 во всех внутренних узлах x_i, i=1,...,n-1 сетки дает 2(n-1) равенств.

3 АЛГОРИТМ ПОСТРОЕНИЯ ИНТЕРПОЛЯЦИОННОГО КУБИЧЕСКОГО СПЛАЙНА

Пусть каждому значению аргумента x_i, i=0,...,n соответствуют значения функции f(x_i)=y_i и требуется найти функциональную зависимость в виде сплайна (1.1), удовлетворяющего перечисленным ниже требованиям:

а) функция S₃(x_i) непрерывна вместе со своими производными до второго порядка включительно;

б) S₃(x_i)=y_i, i=0,1,...,n;

в) S"₃(x₀)=S"₃(x_n)=0.

Сформулированная выше задача имеет единственное решение.

Вторая производная S"₃(x) непрерывна и, как видно из выражения (1.1), линейна на каждом отрезке [x_i-1, x_i], (i=1,...,n), поэтому представим ее в виде

, (1.4)

где h_i = x_i- x_i-1 , m_i= S"₃(x_i).

Интегрируя обе части равенства (1.4), получим

, (1.5)

где A_i и B_i - постоянные интегрирования.

Пусть в (1.5) x=x_i и x=x_i-1, тогда используя условия б), получим

, i=1,...,n.

Из этих уравнений находим A_i и B_i, и окончательно формула (1.5) принимает вид

. (1.6)

Из формулы (1.6) находим односторонние пределы производной в точках x₁,x₂ ,...,x_n-1:

, (1.7)

. (1.8)

Приравнивая выражения (1.7) и (1.8) для i=1,...,n-1, получим n-1 уравнение

(1.9)

с n-1 неизвестными m_i (i=1,...,n-1). Согласно условию (1.4) m₀=m_n=0.

Система линейных алгебраических уравнений (1.9) имеет трехдиагональную матрицу с диагональным преобладанием. Такие матрицы являются неособенными. Поэтому неизвестные m₁ , m₂ , ... , m_n-1 находятся из системы (1.9) однозначно. После определения m_i функция S₃(x) восстанавливается по формуле (1.6).

4 МЕТОД ПРОГОНКИ

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

. (1.10)

В нашем случае согласно (1.9)

интерполяция кубический сплайн погрешность

Решение системы ищется в виде

m_i = _i m_i+1 + _i , i=1,...,N-1, (1.11)

где A_i , B_i - прогоночные коэффициенты. Используя выражение для m _i-1 из (1.11), исключим это неизвестное из i-го уравнения системы. Получаем

(a_i +c_{i i-1})m_i + b_i m_i+1 = d_i -c_ii-1.

Сравнивая это соотношение с (1.11), выводим рекуррентные формулы для прогоночных коэффициентов _i, _i (прямая прогонка):

₀=₀=0, . (1.12)

Очевидно, что m_n-1=_n-1 (при с_n-1=0). Все остальные неизвестные находим по формулам (1.11), используя выражения для прогоночных коэффициентов (1.12).

Величины _i и a_i +c_ii-1 не зависят от правой части системы. Поэтому если вычислить их и запомнить, то для решения систем, отличающихся только правыми частями, потребуется 5(n-1) арифметических операций.

5 КОД ПРОГРАММЫ

#include <iostream.h>

#include <math.h>

#include <conio.h>

#include<iomanip.h>

using namespace std;

const int N=5121;

int main()

{

cout.setf(ios::left);

int i, n;

double max,max2,dK,oc,x1,A,B,h,x[N],a[N],b[N],c[N],d[N],y[N],mu[N],m[N],S3[N];

A=0;

B=3.141592653589;

max=0;

max2=0;

cout<<" ================="<<endl;

cout<<" | n | max | d ocenka | dk |"<<endl;

cout<<" -----------------------------"<<endl;

for(n=5;n<=5120;n=2*n)

{

h=(B-A)/n;

for(i=0; i<=n; i++)

x[i]=A+i*h;

a[0]=a[n]=1;

b[0]=c[n]=0;

d[0]=-sin(A);

d[n]=-sin(B);

for(i=1; i<n; i++)

{

a[i]=2*h/3;

b[i]=h/6;

c[i]=h/6;

d[i]=(sin(x[i+1])-2*sin(x[i])+sin(x[i-1]))/h;

}

y[0]=-b[0]/a[0]; //прогоночные коэффициенты

mu[0]=d[0]/a[0]; //прогоночные коэффициенты

for(i=1; i<n; i++) //прямая прогонка

{

y[i]=-b[i]/(a[i]+c[i]*y[i-1]);

mu[i]=(d[i]-c[i]*mu[i-1])/(a[i]+c[i]*y[i-1]);

}

m[n]=mu[n];

for(i=n-1; i>0; i--)

m[i]=y[i]*m[i+1]+mu[i]; //Решение системы

for(i=1; i<=n; i++) //Определение конечной формулы

{

x1=x[i-1]+h/2;

S3[i]=((x[i]-x1)*sin(x[i-1])+(x1-x[i-1])*sin(x[i]))/h+(pow((x[i]-x1),3)-

h*h*(x[i]-x1))*m[i-1]/(6*h)+(pow((x1-x[i-1]),3)-h*h*(x1-x[i-1]))*m[i]/(6*h);

}

max=fabs(S3[1]-sin(x[0]+h/2)); // максимальная погрешность

for(i=1; i<=n; i++)

{

x1=x[i-1]+h/2;

if(fabs(S3[i]-sin(x1))>max) max=fabs(S3[i]-sin(x1));

}

if(n>5)

{

dK=max2/max;

oc=max2/16;

}

if(n==5)

cout<<" |"<<setw(8)<<n<<"|"<<setw(15)<<max<<"|"<<setw(15)<<"-

"<<"|"<<setw(15)<<"-"<<"|"<<endl;

if(n>5)

cout<<" |"<<setw(8)<<n<<"|"<<setw(15)<<max<<"|"<<setw(15)<<oc

<<"|"<<setw(15)<<dK<<"|"<<endl;

max2=max;

}

getch();

}

6 ОБЗОР РАБОТЫ ПРОГРАММЫ

ЗАКЛЮЧЕНИЕ

В данной курсовой работе была разработана программа для интерполирования функции sinx на отрезке [0, р] при равномерном разбиении с удвоением числа отрезков n. Краевые условия - равенство нулю второй производной S"₃(а)=f"(а), S"(b)=f"(b) Результаты работы программы представлены в виде таблицы, содержащей максимальную погрешность и её оценку при каждом числе отрезков n.

В колонке Д_max представлена максимальная погрешность |S₃(x)-f(x)|, вычисленная в точках, находящихся между узлами сетки; Дk отношение погрешности предыдущей строки к данной (коэффициент уменьшения погрешности при удвоении n). Дk сохраняет значение до значений n = 640, выше которых в общей погрешности результата преобладает погрешность округления. Из таблицы видно, что с увеличением числа отрезков n точность метода возрастает.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Практическое руководство по сплайнам. Де Бор К. М. Радио и связь, 1985.

2. Методы сплайн-функций. Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л. - М.: Наука. 1980 г.

3. Теория сплайнов и её приложения. Альберг Дж., Нилсон Э., Уолш Дж.: М. Мир, 1972.

Размещено на Allbest.ru