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

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

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

1.doc

166kb.

06.12.2011 13:41

скачать

---

Смотрите также:
• Каждый отрезок кубического сплайна есть полином третьей степени S [ документ ]
• «Интерполяция Кубического Сплайна» [ документ ]
• Интерполяция функций с помощью сплайна [ документ ]
• Контрольные работы [ документ ]
• Аппроксимация сигналов и функций [ лекция ]
• Задачи по численным методам (на Delphi) [ документ ]
• Интерполяция методом Эйткена [ документ ]
• Решение: определим заданную функцию f(x) [ документ ]
• Задача - Расчет цепей постоянного тока всеми методами [ лабораторная работа ]
• Интерполяция функций [ документ ]
• Исследование теплопроводности методом пластины [ документ ]
• по математике [ лекция ]

1.doc

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

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

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

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

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


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

…………………

Проверила:

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

Уфа 2010

Содержание.

1. 
   Введение
   

1. 
   Цель работы………………….………………….…...…….3
   
2. 
   Постановка задачи………….………………….………….3
   
3. 
   Краткая литература………………………………………...3
   

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

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

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

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

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

Введение.

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

Постановка задачи: разработать программу для интерполяции произвольной функции методом кубического сплайна. В качестве отладочного примера используем функцию 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 дефекта  (-целое число, 0n+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_i_i-1.

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

₀=₀=0, . (1.12)

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

Величины _i и a_i +c_i_i-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"₃(а)=f"(а), S"(b)=f"(b) Результаты работы программы представлены в виде таблицы, содержащей максимальную погрешность и её оценку при каждом числе отрезков n. В колонке Δ_max представлена максимальная погрешность |S₃(x)-f(x)|, вычисленная в точках, находящихся между узлами сетки; Δk отношение погрешности предыдущей строки к данной (коэффициент уменьшения погрешности при удвоении n). Δk сохраняет значение до значений n = 640, выше которых в общей погрешности результата преобладает погрешность округления. Из таблицы видно, что с увеличением числа отрезков n точность

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

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

1. 
   Практическое руководство по сплайнам. Де Бор К. М. Радио и связь, 1985.
   
2. 
   Методы сплайн-функций. Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л.-М.: Наука. 1980г.
   
3. 
   Теория сплайнов и её приложения. Альберг Дж., Нилсон Э., Уолш Дж.: М.Мир, 1972
   

---

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

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

---