Дослідження методів інтерполяції

9



Міністерство освіти та науки України

Вінницький національний технічний університет



Інститут автоматики та електроніки комп’ютерних систем управління

Кафедра автоматики та інформаційно

вимірювальної техніки











Дослідження методів інтерполяції



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

з дисципліни моделювання на ЕОМ

Завдання на курсову роботу №18



























2008


Зміст



	Анотація

	Вступ

		Задача інтерполяції

	1.1	Сплайн інтерполяція

		Вибір методів технічних та інструментальних засобів вирішення задачі

		Алгоритми методів

		Алгоритмізація розв’язання задачі

		Вхідні данні

		Розробка та опис логічної частини програми

	4.3	Результати обчислень

		Розв’язання задачі в пакетах прикладних програм

		Інструкція користувачеві

	Висновки

	Література

	Додатки:

	Додаток А Лістинг програми


Анотація



В даній курсовій роботі проведено дослідження методу сплайнів для вирішення задачі інтерполяції. Було розроблено задачу знаходження інтерполяції напруги в точках Т=75С, 93С.

Проведено тестування: меню, та всієї програми в цілому. Тести показали, що програма готова до використання. Описано алгоритм розв'язку поставленої задачі. Складено програму на мові Turbo C++.


Вступ



Сучасний час характерний різким розширенням розділів математики, багато в чому зв’язаним з створенням і розвитком засобів обчислювальної техніки. В результаті появи ЕОМ з програмним управлінням набагато зросла швидкість виконання математичних задач. Використовуючи ЕОМ і розширення математичної освіти різко збільшило можливості побудови і дослідження математичних моделей, а також вирішити ряд важливих науково-технічних задач. Проте можна сказати ще одне - числові машини можна використовувати ефективно лише за умови глибокого знання чисельних методів математики. Математичне моделювання-засіб дослідження реальних об’єктів та явищ використаних у геофізиці, хімії, геології, біології, медицині, психології, лінгвістиці та ін. науках. 

Математичне моделювання можна розглядати як засіб вивчення реальної системи шляхом заміни її більш зручною для експерементального дослідження системи (моделлю), яка зберігає суттєві риси оригіналу.

Математичне моделювання включає такі етапи: дослідження об’єкта і створення його математичного опису; побудова алгоритму, який моделює поведінку об’єкта; перевірка адекватності моделі і об’єкта; використання моделі. 

Ефективність математичного моделювання в більшості визначається ефективністю використовуваних для розрахунків моделей обчислювальних методів і алгоритмів.

В практичній діяльності людини часто виникають такі задачі, коли маючи обмежену кількість експериментальних даних, треба спрогнозувати, які наслідки слід очікувати при інших умовах експерименту над тим же об'єктом. В математиці для цієї мети широко використовують рівняння різного вигляду, які з той чи іншою похибкою моделюють поведінку об'єкта. Підбір таких рівнянь називають апроксимацією експериментальних даних. Зокрема, апроксимація усередині області одержання експериментальних даних називається інтерполяцією, а за межами цієї області – екстраполяцією.

У більшості випадків підбір підходящих рівнянь ускладнюється тим, що експериментальні дані отримані приблизно і вміщують похибку експерименту та обчислювань.

Інтерполяція сплайнами третього порядку - це швидкий, ефективний і стійкий спосіб інтерполяції функцій. Нарівні з раціональною інтерполяцією, сплайн - інтерполяція є одній з альтернатив поліноміальної інтерполяції. У основі сплайна-інтерполяції лежить наступний принцип. Інтервал інтерполяції розбивається на невеликі відрізки, на кожному з яких функція задається поліномом третьоього степеня. Коефіцієнти полінома підбираються так, щоб виконувалися певні умови (які саме, залежить від способу інтерполяції). Загальні для всіх типів сплайнів третього порядку вимоги - безперервність функції і, зрозуміло, проходження через задані їй точки. Додатковими вимогами можуть бути лінійність функції між вузлами, безперервність вищих похідних і так далі. Основними перевагами сплайна-інтерполяції є її стійкість і мала трудомісткість. Системи лінійних рівнянь, які потрібно вирішувати для побудови сплайнів, дуже добре обумовлені, що що дозволяє отримувати коефіцієнти поліномів з високою точністю.


1. Задача інтерполяції



Мета інтерполяції – побудування функції , яка приймає в окремих точках  (вузли інтерполяції) значення,



 (1)



що збігається з раніше заданими значеннями в цих точках невідомої функції . Геометрично це означає, що потрібно знайти криву  певного типу, яка проходить через систему точок  (рисунок 1).





Рисунок 1.1- Інтерполяція даних



В загальних випадках ця задача має нескінчену множину розв’язків чи зовсім не має розв’язку, але вона стає однозначною, якщо замість довільної функції  шукати поліном  ступеня не вище , який задовольняє умову (1), тобто






Інтерполяційну формулу , як правило, використовують для наближеного обчислення значень даної функції  для . Така операція зветься інтерполяцією. Треба відзначити, що в вузькому розумінні, коли , та екстраполяція коли  знаходиться за межами інтервалу , тобто  чи . 



Сплайн інтерполяція



У випадку, який показаний на рисунку 2, необхідно задати всі кубічні функції В найбільш загальному випадку ці багаточлени мають такий вигляд: 







де  - постійні, які визначені вказаними умовами 

Перші (2m) умов потребують, щоб сплайни стикалися в заданих точках: 







Наступні (2m-2) умов потребують, щоб в місцях дотику сплайнів були рівні перші та другі похідні








	Рисунок 1.1.1 - Сплайн інтерполяція

	

	Система алгебраїчних рівнянь має розв`язок, якщо кількість рівнянь дорівнює кількості невідомих. Для цього необхідні ще два рівняння. Як правило, використовують такі додаткові умови:

	

	 

	

	Отриманий таким чином сплайн зветься “природнім кубічним сплайном”. При знайдених коефіцієнтах сплайна використовують цю кусково – гладку поліноміальну функцію для інтерполяції.

	Якщо спеціально вибрати вигляд кубічних багаточленів, можна значно спростити задачу (зменшити кількість рівнянь). В випадку, коли окремі кубічні рівняння мають вигляд:

	

	

	

	кожне з рівнянь  містить тільки два невідомих коефіцієнти. Після того, як перше рівняння записано, з кожним наступним рівнянням додається тільки один невідомий коефіцієнт. При цьому при ,  а при 

	Отже, всі умови, крім умов для других похідних, задовольняються. Другі похідні виражені для внутрішніх точок відношеннями: 

	

	

	

	а для двох зовнішніх:

	

	

	

	таким чином, система рівнянь, яку розв`язуємо, є лінійною, а її матриця – тридіоганальною:

	

	

	

	

	Методи розв`язування таких систем добре розроблені.

	
2. Вибір методів технічних та інструментальних засобів вирішення задачі

	

Був обраний метод сплайнів, тому що цей метод дозволяє отримати аналітичну кусково – поліноміальну функцію.

Інтерполяція сплайнами - це швидкий, ефективний і стійкий спосіб інтерполяції функцій. Нарівні з раціональною інтерполяцією, сплайн - інтерполяція є однією з альтернатив поліноміальної інтерполяції. Основними якостями сплайн - інтерполяції являється її стабільність і мала трудомісткість. Системи лінійних рівнянь, які потрібно вирішувати для побудови сплайнів, дуже добре обумовлені, що дозволяє отримувати коефіцієнти поліномів з високою точністю. У результаті навіть про дуже великих N обчислювальна схема не втрачає стійкість. Побудова таблиці коефіцієнтів сплайна вимагає O(N) операцій, а обчислення значення сплайна в заданій точці - усього лише O(log(N)).

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


3. Алгоритми методів



Метод реалізований за допомогою двох функцій, які викликаються в головній підпрограмі. На рисунку 3.1 представлений алгоритм головної програми.







main





Gauss

spline







Рисунок 3.1 – Алгоритм головної програми



Алгоритми функцій spline та function подані нижче.




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

  mas[i+KOL-1][i*3]=-1;

  mas[i+KOL-1][i*3+1]=-2*h;

  mas[i+KOL-1][i*3+2]=-3*pow(h,2);

  mas[i+KOL-1][i*3+3]=1;

  mas[i+2*(KOL-1)-1][i*3+1]=-1;

  mas[i+2*(KOL-1)-1][i*3+2]=-3*h;

  mas[i+2*(KOL-1)-1][i*3+4]=1;

i=0;i<KOL-2;i++

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

  mas[i][i*3]=h;

  mas[i][i*3+1]=pow(h,2);

  mas[i][i*3+2]=pow(h,3);

  mas[i][(KOL-1)*3]=yi[i+1]-yi[i];

i=0;i<KOL-1;i++

y=0,i,h;

Spline



















































Gauss





1



Рисунок 3.2 – Алгоритм функції spline





x>=xi[i]&&x<=xi[i+1]

i=0;i<KOL-1;i++

1















		

Кінець

y



 y=yi[nom]+mas[3*nom][kStl-1]*(x-xi[nom])+mas[3*nom+1][kStl-1]*pow(x-xi[nom],2)+mas[3*nom+2][kStl-1]*pow(x-xi[nom],3);

nom=i;

   break;	0	1









































Рисунок 3.3 – Продовження алгоритму функції spline




	

Gauss

	

	

int nUr=0;nUr<kStr;nUr++

	

	

	

	

mas[nUr][nUr]==0

	

			0	1

	

	

	

	

int nUr1=nUr+1;nUr1<kStr;nUr1++

	

	

	

	

	

mas[nUr1][nUr]!=0

	

	                                   0                                           1

	

	

	

	

int nPer=0;nPer<kStl;nPer++

	

	

	

	

t=mas[nUr][nPer];      mas[nUr][nPer]=mas[nUr1][nPer];

 mas[nUr1][nPer]=t;

	

	

	

	

	







double VE=mas[nUr][nUr];





int nPer=0;nPer<kStl;nPer++









mas[nUr][nPer]/=VE;









1







Рисунок 3.4 – Алгоритм фунції Gauss



Gauss







double PE=mas[nUr1][nUr];

int nUr1=nUr+1;nUr1<kStr;nUr1++

1



















int nPer=0;nPer<kStl;nPer++





	

int nPer=kStl-2;nPer>=0;nPer--

mas[nUr1][nPer]-=mas[nUr][nPer]*PE	





























nUr=nPer-1;nUr>=0;nUr--





	

Кінець

mas[nUr][kStl-1] =mas[nUr][nPer]*mas[nPer][kStl-1];

mas[nUr][nPer]=0;	























Рисунок 3.5 – Продовження алгоритму фунції Gauss




4. Алгоритмізація розв’язання задачі



4.1 Вхідні данні



Вхідними даними для вирішення інтерполяції напруги вольтметра в точках Т=75С, 93С методом сплайнів є тарировочна таблиця для термопари. Яка наведена нижче:



Т,С

20

40

60

80

100

120

U, мВ

-0,67

-0,25

-0,17

0,61

1,06

1,52



Вхідними даними в програмі є змінні xi та yi, що приймає значення заданих в тарировочній таблиці. 



xi[KOL]={20,40,60,80,100,120};

yi[KOL]={-0.67,-0.25,-0.17,0.61,1.06,1.52};



Змінна xi приймає значення типу int, а змінна yi – double.



4.2 Розробка та опис логічної частини програми



Значення інтерполяційного поліному за допомогою кубічних сплайнів обчислюється функцією Spline(), що має аргументом одну змінну типу double (значення температури) і повертає значення типу double (значення напруги).	

Для розв’язку системи рівнянь методом Гауса використовується функція Gauss() що не має аргументів та не повертає значень.

Для обчислення обох функцій використовуються дані у глобальних масивах xi[6] – масив значень температури, yi[6] – масив значень напруги та масив коефіцієнтів рівнянь mas[15][16].

Результати обчислень фунцією Gauss() знаходяться в останньому стовпці mas.

Графічне подання результатів:







Оцінка похибки.

З графіка видно, що похибка незначна на всьому діапазоні представлення функції.



4.3 Результати обчислень



Результатом роботи програми є те, що виводяться кінцеві результати: Значення інтерполяційного поліному для Т=750 і Т=930:



T=75, U=0.408483;

T=93, U=0.940465.


5. Розв’язання задачі в пакетах прикладних програм



Для реалізації сплайн інтерполяції в Мachcad вбудовані три функції які слугують для отримання вектора другої похідної сплайн функції при різному виді інтерполяції. В нашому випадку використовується функція cspline(vX,vY), що повертає вектор vs других похідних при наближенні до опорних точок кубічного поліному.

На рисунку 5.1 показаний розвязок сплайн інтерполяції кубічного поліному.





Рисунок 5.1 – Сплайн інтерполяція кубічного поліному



5.1 Інструкція користувачеві



Дана програма вирішує задачу інтерполяції в точках Т=750 і Т=930 методом сплайнів.


Програма має досить непоганий інтерфейс для коректної роботи програми, використання її досить просте, і труднощів з використанням даної програми не викликатиме. 

Головне меню має вигляд.



 

Рисунок 6.1 – Вікно меню



Меню має три підменю «Виконання», «Допомога» та «Вихід».

Підменю «Виконання» виводить розрахунок інтерполяції на екран.





Рисунок 6.1 – Розрахунок інтерполяції



В свою чергу підменю «Допомога» містить наступні пункти «Справка» і «Автор». 






Рисунок 6.3 – Справка



Вихід з програми забезпечується підменю «Вихід», або клавішею «Esc».


Висновки



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

В першій главі було розглянуто варіантний аналіз чисельних методів моделювання зміни температури термопари.	

В другій главі розглянуто вибір методі та інструментальних засобів рішення даної задачі.

В третій главі розглянуто алгоритм рішення задачі.

В четвертій главі було зроблено планування вхідних та вихідних даних, описано алгоритм рішення керуючої програми, та її структури. 

В пятій главі було представлено розвязання даної задачі в Machcad.

В шостій було представлено інструкція користувачеві, для коректної роботи програми.

Написана програма широко використовується в обчислювальній математиці. Під час виконання роботи були закріплені знання та навички використання мови C++.


Література



Заварыкин В. М. и др. Численные методы: Учеб. пособие для студентов физ.-мат. спец пед. ин-тов/В. М. Заварыкин, В. Г. Житомирский, М. П. Лапчик.-М.: Просвещение, 1990.-176 с.

Квєтний Р.Н. Методи комп`ютерних обчислень ./ Вінниця: ВДТУ,2001 – 148с.

Маликов В. Т., Кветный Р. Н. Вычислительные методы и применение ЭВМ. – К.: Вища школа, 1989.

Кветный Р. Н. Математическое моделирование в задачах проектирования средств автоматики и информационно-измерительной техники. – К.:УМК ВО,1989. – 256 с.

Дубовой В.М., Квєтний Р.Н. Програмування комп’ютеризованих систем управління та автоматики. – Вінниця: ВДТУ, 1997. – 208 с.

Р.Н.Кветний Методи комп’ютерних обчислень. Навчальний посібник.- Вінниця: ВДТУ, 2001.-148с.


ДОДАТОК



Додаток А 



#include<stdio.h>

#include<conio.h>

#include<math.h>

#include<process.h>

#define KOL 6

int kStr=3*(KOL-1);

int kStl=kStr+1;

int xi[KOL]={20,40,60,80,100,120};

double yi[KOL]={-0.67,-0.25,-0.17,0.61,1.06,1.52};

double mas[(KOL-1)*3][(KOL-1)*3+1]={{0}};

double Spline(float x);

void Gauss();

main()

{

clrscr();

printf("Spline:\n");

printf("T=75,U=%lf\n",Spline(75));

printf("T=93,U=%lf\n",Spline(93));

getch();

}

double Spline(float x)

{

double y=0;

int i,h;

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

{

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

mas[i][i*3]=h;

mas[i][i*3+1]=pow(h,2);

mas[i][i*3+2]=pow(h,3);

mas[i][(KOL-1)*3]=yi[i+1]-yi[i];

}

for(i=0;i<KOL-2;i++)

{

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

mas[i+KOL-1][i*3]=-1;

mas[i+KOL-1][i*3+1]=-2*h;

mas[i+KOL-1][i*3+2]=-3*pow(h,2);

mas[i+KOL-1][i*3+3]=1;

mas[i+2*(KOL-1)-1][i*3+1]=-1;

mas[i+2*(KOL-1)-1][i*3+2]=-3*h;

mas[i+2*(KOL-1)-1][i*3+4]=1;

}

mas[3*(KOL-1)-2][2]=1;

mas[3*(KOL-1)-1][3*(KOL-1)-2]=1;

mas[3*(KOL-1)-1][3*(KOL-1)-1]=3*(xi[KOL-1]-xi[KOL-2]);

Gauss();

int nom;

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

if(x>=xi[i]&&x<=xi[i+1])

{

nom=i;

break;

}

y=yi[nom]+mas[3*nom][kStl-1]*(x-xi[nom])+mas[3*nom+1][kStl-1]*pow(x-xi[nom],2)+mas[3*nom+2][kStl-1]*pow(x-xi[nom],3);

return y;

}

void Gauss()

{

for(int nUr=0;nUr<kStr;nUr++)

{

if(mas[nUr][nUr]==0)

{

for(int nUr1=nUr+1;nUr1<kStr;nUr1++)

{

if(mas[nUr1][nUr]!=0)

{

for(int nPer=0;nPer<kStl;nPer++)

{

double t;

t=mas[nUr][nPer];

mas[nUr][nPer]=mas[nUr1][nPer];

mas[nUr1][nPer]=t;

}

goto m1;

}

}

m1:

}

double VE=mas[nUr][nUr];

for(int nPer=0;nPer<kStl;nPer++)

mas[nUr][nPer]/=VE;

for(int nUr1=nUr+1;nUr1<kStr;nUr1++)

{

double PE=mas[nUr1][nUr];

for(int nPer=0;nPer<kStl;nPer++)

mas[nUr1][nPer]-=mas[nUr][nPer]*PE;

}

}

for(int nPer=kStl-2;nPer>=0;nPer--)

for(nUr=nPer-1;nUr>=0;nUr--)

{

mas[nUr][kStl-1]-=mas[nUr][nPer]*mas[nPer][kStl-1];

mas[nUr][nPer]=0;

}

}