Методы интерполяции

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

Федеральное агентство связи

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

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

«Сибирский государственный университет

телекоммуникаций и информатики»

Кафедра: ПМ и К

Курсовая работа

по теме: Методы интерполяции

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

Пакичев А.И.

Проверил: Доцент

Рубан А. А.

Новосибирск, 2013

Содержание

1. Введение

2. Методы интерполяции

2.1 Формула Лагранжа

2.2 Формула Эйткена

2.3 Формула Ньютона

2.4 Метод кубических сплайнов

3. Графическое представление

1. Введение

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

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

Задачи интерполяции: научиться вычислять значение функции в любой наперед заданной точке.

Интерполяция иногда делится на два вида:

1) - собственная интерполяция.

2) - экстраполяция.

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

2. Методы интерполяции

2.1 Метод Лагранжа

Интерполяционный многочлен Лагранжа -- многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для  пар чисел , где все  различны, существует единственный многочлен  степени не более , для которого .

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

Лагранж предложил способ вычисления таких многочленов:

где базисные полиномы определяются по формуле:

 обладают следующими свойствами:

· являются многочленами степени 

·

·  при 

Отсюда следует, что , как линейная комбинация , может иметь степень не больше , и 

Код метода:

double p(double X,int n) // В качестве входных параметров используется

{ // double X - переменная относительно которой

double result=0,temp=1; // Нужно найти f(x), а также int n - количество

for (int i=0;i<=n;i++) // точек интерполяции. Матрицы x[], y[] заданы

{ // глобально.

for (int j=0;j<=n;j++)

if (i!=j)

temp*=(X-x[j])/(x[i]-x[j]);

result+=temp*y[i];

temp=1;

}

return result;

}

2.2 Метод Эйткена

Итерационно-интерполяционный метод Эйткена позволяет свести вычисления коэффициентов интерполяционного полинома Лагранжа, с учетом его равенства в узлах интерполяции с исходными данными к вычислению функциональных определителей второго порядка. При этом эффективность метода повышается в тех случаях, когда нет необходимости в получении приближенного аналитического выражения функции f(х), заданной таблично, а требуется лишь определить значение в некоторой точке х*, отличной от узловых точек. Этот метод заключается в последовательной линейной интерполяции. Процесс вычисления f(x*) состоит в следующем: необходимо пронумеровать узлы интерполяции, например, в порядке убывания их от х*. Затем для каждой узловой точки интерполяции строятся соотношения, которые является интерполяционными полиномами, построенными соответственно по узлам хi, хj, хk. Полученный полином является интерполяционным полиномом, построенный по узлам хi, xj, …, хk, хm. Это утверждение верное, так как Рn-1ij…k(х) и Рn-1j…km(x) являются интерполяционными полиномами. При его реализации предполагается, что функция гладкая, а также критерием оценки погрешности определяется некоторое значение, определяемое условиями конкретной задачи.

Код метода:

Double P(double X,int n) // В качестве входных параметров используется

{ // double X - переменная относительно которой

float l[n+1],result; // Нужно найти f(x), а также int n - количество

for (int i=0;i<=n;i++) // точек интерполяции. Матрицы x[], y[] заданы

l[i]=y[i]; // глобально.

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

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

{

l[j]=(l[j]*(x[i+j]-X)-l[j+1]*(x[j]-X))/(x[i+j]-x[j]);

result=l[j];

}

return result;

2.3 Метод Ньютона

Формула Ньютона:

где

Конечной разностью функции у=f(х) называется функция , где h - фиксированный шаг. Конечные разности иногда называются конечными разностями первого порядка.

Функция обозначается:

Принимаем

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

double Delta(double X, int n, double h) //Где n - порядок, h - шаг

{

if (n>1)

return (Delta(X+h,n-1,h)-Delta(X,n-1,h));

else

return (f(X+h)-f(X));

}

Код программы:

double Pn(double X, int h, int n) // В качестве входных параметров используется

{ // double X - переменная относительно которой

double result=y[0],qq,q; // Нужно найти f(x), а также int n - количество

q=(X-x[0])/h; // точек интерполяции. Матрицы x[], y[] заданы

for (int i=1;i<=n;i++) // глобально.

{

qq=1;

for (int j=1;j<=i;j++)

qq*=(q-j+1);

result+=Delta(x[0],i,h)*qq/fact(i);

}

return result+1;

}

{

float l[n+1],result;

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

l[i]=y[i];

2.4 Метод кубических сплайнов

Кубическим сплайном на сетке x0,x1,…xn называется функция S(х), которая обладает следующими свойствами:

на каждом интервале [хi-1, хi], где 1 i n, функция S(х) является кубическим многочленом (на каждом интервале свой многочлен).

на всем интервале [х0, хп] S(х) - дважды непрерывно дифференцируемая функция

на краях интервала вторая производная обращается в ноль (краевое условие).

Sґґ(x0)=Sґґ(xn)=0

3'. для периодических кубических сплайнов.

Sґґ(x0)=Sґґ(xn)=0 ; Sґ(x0)=Sґ(xn)=0

CM=d

Элементы матрицы С вычисляются по формуле:

, () - вектор правых частей.

Код программы:

const int n = 5;

double x[n];

double y[n];

float C[n-1][n-1];

float Cd[n-1][n];

double S(double X, int n)

{

int i,j;

float S,k1,k2,k3,k4;

float h[n],d[n-1],M[n+1],G[n-1];

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

h[i]=x[i+1]-x[i];

for (i=1,j=0;i<n;i++,j++)

d[j]=((y[i+1]-y[i])/h[i])-((y[i]-y[i-1])/h[i-1]);

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

for (j=0;j<n-1;j++)

{

if (i==j)

C[i][j]=(h[i]+h[i+1])/3;

if (j==i+1)

C[i][j]=h[i+1]/6;

if (j==i-1)

C[i][j]=h[i]/6;

if (fabs(i-j)> 1)

C[i][j] = 0;

}

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

for (j=0;j<n-1;j++)

Cd[i][j]=C[i][j];

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

Cd[i][n-1]=d[i];

Gauss(G,n-1);

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

M[i+1]=G[i];

i=3;

k1=M[i-1]*(pow((x[i]-X),3)/(6*h[i-1]));

k2=M[i]*(pow((X-x[i-1]),3)/(6*h[i-1]));

k3=(y[i-1]-((M[i-1]*h[i-1]*h[i-1])/6))*((x[i]-X)/h[i-1]);

k4=(y[i]-((M[i]*h[i-1]*h[i-1])/6))*((X-x[i-1])/h[i-1]);

S=k1+k2+k3+k4;

return S;

}

Для вычисления матрицы М используется метод гаусса отдельная функция Gauss:

void Gauss(float *y, int N)

{

int i, j, k;

float temp;

for (j=0;j<N;j++)

{

for (i=j+1;i<N;i++)

{

temp=Cd[i][j]/Cd[j][j];

for (k=j;k<=N;k++)

Cd[i][k]-=Cd[j][k]*temp;

}

}

y[N-1]=Cd[N-1][N]/Cd[N-1][N-1];

for (i=N-2;i>=0;i--)

{

float summa=0;

for (j=N-1;j>i;j--)

summa+=y[j]*Cd[i][j];

y[i]=(Cd[i][N]-summa)/Cd[i][i];

}

}

3. Графическое представление

Для графического представления работы методов написана функция graphic (int n, int method)

void graphic(int n, int method)

{

float X, Y;

initwindow(1000,640);

line(500,0,500,640);//y

line(490,20,500,0);

line(510,20,500,0);

outtextxy(520,10,"y");

line(0,320,1000,320);//x

line(990,310,1000,320);

line(990,330,1000,320);

outtextxy(985,330,"x");

X=-100;

moveto(500+X*20,160+(160-(Y*3)));

setcolor(4);

for (int i=0;i<=n;i++) //Отмечаем на графике заданные точки интерполяции

circle(500+x[i]*20,160+(160-(y[i])),5);

setcolor(10);

do

{

if (method==0) //Выбираем метод

{

Y=p(X,4);

outtextxy(520,850,"Lagranj");

}

if (method==1)

{

Y=P(X,4);

outtextxy(520,850,"Eytkin");

}

if (method==2)

{

Y=Pn(X,1,4);

outtextxy(520,850,"Newton");

}

if (method==3)

{

Y=S(X,n); // С помощью определенного метода находим y для

outtextxy(520,850,"Splayn"); // Заданного x

}

lineto(500+X*20,160+(160-(Y))); //И проводим к точке (x,y) линию от предыдущей точки

X=X+0.02;

}

while(X<=100);

getch();

closegraph();

}

Таким образом, например, для метода Лагранжа и значений точек интерполяции:

x[0]=1; x[1]=2; x[2]=3; x[3]=4; x[4]=5;

y[0]=1; y[1]=4; y[2]=9; y[3]=16; y[4]=25;

Получаем график функции:



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