Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

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


Интерполяция методом кубического сплайна
скачать (166 kb.)

Доступные файлы (1):

1.doc166kb.06.12.2011 13:41скачать

Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
Федеральное агентство по образованию

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

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

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

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


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

…………………

Проверила:

Гадилова Ф.Г.

Уфа 2010



Содержание.

  1. Введение

    1. Цель работы………………….………………….…...…….3

    2. Постановка задачи………….………………….………….3

    3. Краткая литература………………………………………...3

  1. Практическая часть

2.1 Листинг программы с комментариями……..….................6

2.2 Пример работы программы…………………….………….7

2.3 Заключение……………………………………..…………..7

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

Введение.

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

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

Краткая литература:

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

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

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

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

Определение. Функция Sn,(x) называется сплайном степени n дефекта (-целое число, 0n+1) с узлами на сетке  (: a=x0< <xi<...<xn=b), если:

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

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

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

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

Пусть на отрезке [a,b] в узлах сетки  заданы значения некоторой функции

fi =f(xi), i=0,...,n.

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

S3(x)=аi0 +аi1(x - xi)+аi2(x - xi)2 +аi3(x - xi)3, x[xi, xi+1], (1.1)

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

S3(xi)=f(xi), i=0,...,n. (1.2)

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

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

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


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

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

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

б) S3(xi)=yi, i=0,1,...,n;

â) S"3(x0)=S"3(xn)=0.

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

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

, (1.4)

где hi = xi- xi-1 , mi= S"3(xi).

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

, (1.5)

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

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

, i=1,...,n.

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



. (1.6)

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

, (1.7)

. (1.8)

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

с n-1 неизвестными mi (i=1,...,n-1). Согласно условию (1.4) m0=mn=0.

Система линейных алгебраических уравнений (1.9) имеет трехдиагональную матрицу с диагональным преобладанием. Такие матрицы являются неособенными. Поэтому неизвестные m1 , m2 , ... , mn-1 находятся из системы (1.9) однозначно. После определения mi функция S3(x) восстанавливается по формуле (1.6).


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

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

. (1.10)

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



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

mi = i mi+1 + i , i=1,...,N-1, (1.11)

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

(ai +ci i-1)mi + bi mi+1 = di -cii-1.

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

0=0=0, . (1.12)

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

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

Код программы.
#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();

}

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

Заключение.

В данной курсовой работе была разработана программа для интерполирования функции sinx на отрезке [0, π] при равномерном разбиении с удвоением числа отрезков n. Краевые условия – равенство нулю второй производной S"3(а)=f"(а), S"(b)=f"(b) Результаты работы программы представлены в виде таблицы, содержащей максимальную погрешность и её оценку при каждом числе отрезков n. В колонке Δmax представлена максимальная погрешность |S3(x)-f(x)|, вычисленная в точках, находящихся между узлами сетки; Δk отношение погрешности предыдущей строки к данной (коэффициент уменьшения погрешности при удвоении n). Δk сохраняет значение до значений n = 640, выше которых в общей погрешности результата преобладает погрешность округления. Из таблицы видно, что с увеличением числа отрезков n точность

метода возрастает.

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

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

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

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



Скачать файл (166 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru