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

Горлівський технікум донецького національного університету

Циклова комісія інформаційних технологій та прикладної математики

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

на тему: Інтерполяція сплайнами

Студент Ніколаєва Н.

Керівник Л.В. Остапова

м. Горлівка - 2012 рік

План

Вступ

1. Основні поняття теорії інтерполяції

1.1 Інтерполяція та екстраполяція

1.2 Види інтерполяції

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

2.1 Історія сплайнів

2.2 Постановка задачі

2.3 Види сплайнів

2.4 Метод прогонки для розв'язання систем лінійних рівнянь

2.5 Вивід формул методу інтерполяції сплайнами

2.6 Алгоритм методу інтерполяції функції кубічними сплайнами

2.7 Приклад використання інтерполяції кубічними сплайнами

Висновки

Список використаних джерел

Додаток

Вступ

Особливо інтенсивний розвиток інтерполяції сплайнами відбувся в 50-70 роки ХХ століття, традиційною прикладною сферою використання інтерполяційних сплайнів стали в даний час системи автоматизованого проектування. Однак потенційні можливості сплайнів значно ширше, ніж просто опис деяких кривих. У реальному світі велика кількість фізичних процесів за самою своєю природою є сплайнами. У механіці це деформація гнучкої пластини або стержня, зафіксованих в окремих точках; траєкторія руху тіла, якщо сила, що діє на нього змінюється ступінчасто (траєкторія штучного космічного об'єкта з активними та інерційними відрізками руху, траєкторія руху літака при ступінчастій зміні тяги двигунів і зміні профілю крила і т. д.). У термодинаміці це теплообмін в стержні, складеному з фрагментів з різною теплопередачею. У хімії - дифузія через шари різних речовин. В електриці - поширення електромагнітних полів через різнорідні середовища. Тобто, сплайн не надумана математична абстракція, а в багатьох випадках він є рішенням диференціальних рівнянь, що описують цілком реальні фізичні процеси. Інтерполяція сплайнами на сьогоднішній день є одним із найточніших методів наближення.

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

Мета виконання курсової роботи - самостійно вивчити метод інтерполяції сплайнами та скласти програму до нього мовою програмування Borland C++ 4.5.

1. Основні поняття теорії інтерполяції

1.1 Інтерполяція та екстраполяція

Функціональна залежність величини у від величин - це такий зв'язок, при якому кожному значенню спільності ставиться у відповідності єдине значення . Змінна функція від аргументу.

функція двох змінних.

функція однієї змінної .

Способи завдання функцій:

1. аналітичний (формули, послідовність дій);

2. графічний (графік - геометричне місце крапок площини , координати яких задовольняють рівнянню );

3. табличний (вказується значення функції для кожного значення аргументу).

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

Будемо розглядати табличну функцію (задану за допомогою таблиці).

Поставимо задачу інтерполяції функції.

Нехай у крапках відомі значення деякої функції ; в

крапках відомі значення першої похідної , і т.д., у крапках відомі значення ої похідної .

Крапки ( ; ) називаються вузлами інтерполяції, а сукупність пар чисел - вихідні данні інтерполяції.

Загальне число вихідних даних .

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

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

Нехай у вузлах дані значення функції . Геометрично це означає завдання в декартовій системі координат крапок з координатами .

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

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

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

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

Для інтерполяції необхідно вказати правило, що дозволяє по й, обчислювати значення точно або приблизно.

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

Похибкою інтерполяції називається різниця .

У похибці залежить від параметрів інтерполяції: число вузлів , їх розташування, вибір правила обчислення .

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

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

1.2 Види інтерполяції

Найбільш загальною формулою параболічної інтерполяції є інтерполяційна формула Лагранжа.

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

значення . (1.2.1)

Необхідно побудувати багаточлен P(x) такий, що .

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

Інтерполяційний багаточлен у формі Лагранжа:

(1.2.2)

Якщо функція задана значеннями:

в нерівновіддалених вузлах інтерполяції то потрібно побудувати інтерполяційну формулу Н'ютона для нерівновіддалених вузлів інтерполяції, так щоб в вузлах інтерполяції .

Інтерполяційний багаточлен Н'ютона через розділені різниці:

. (1.2.3)

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

Нехай функція задана значеннями у рівновіддалених вузлах інтерполяції де

, (1.2.4)

-крок інтерполяції.

Потрібно побудувати інтерполяційний багаточлен ступеня n такий, що Рn(х 0) =y0, Рn(х 1)= y1,…,Рn(хn)= yn.

Перша інтерполяційна формула Ньютона через кінцеві різниці :

, (1.2.5)

тоді

На практиці часто використовують формулу Ньютона в іншому виді. Для цього введемо змінну q=(х-хn)/ h, де h - крок інтерполяції, а q - число кроків. Тоді перша інтерполяційна формула Ньютона прийме наступний вид:

(1.2.6)

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

Нехай на відрізку дані n+1 різних значень аргументу x0,x1,…,xn, яким відповідають значення функції y0=f(x0), y1=f(x1),…,yn=f(xn), а крок інтерполяції постійний і дорівнює h, тобто хi+1= хi+ h (i=0,1,2,.., n-1).

Друга інтерполяційна формула Ньютона через кінцеві різниці :

(1.2.7)

На практиці використовують формулу Ньютона в іншому виді.

Покладемо q=(х-хn)/ h:

. (1.2.8)

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

2.1 Історія сплайнів

Початок розвитку теорії інтерполяції сплайнами і сам термін сплайн налічують з 1946 року зі статті Айзека Шонберга (англ. Isaac Jacob Schoenberg). Сплайном (spline) називали гнучку металеву лінійку - універсальне лекало, яке використовували креслярі для того, щоб гладко поєднати окремі точки на кресленні, тобто для графічного виконання інтерполяції. Більш того, крива, що описує деформацію гнучкої лінійки, зафіксованої в окремих точках, є сплайном. Отже, мається фізична модель сплайн-функції (або, навпаки, сплайн-функція є математичною моделлю гнучкої лінійки). Інтуїтивний підхід до використання кусочної функції в задачах апроксимації зустрічався в математиці протягом тривалого часу. Але, як зазначає радянський вчений Микола Корнійчук, вторгнення сплайнів в теорію наближення сталося через задачі інтерполяції, завдяки їх хорошим обчислювальним та апроксимативним властивостям.

Сплайн (англ. spline - планка, рейка) - функція, область визначення якої розбита на кінцеве число відрізків, на кожному з яких сплайн збігається з деяким алгебраїчним поліномом. Максимальний ступінь з використаних поліномів називається ступенем сплайна. Різниця між ступенем сплайна і отриманою гладкістю називається дефектом сплайна. Наприклад, безперервна ламана є сплайн ступеня 1 і дефекту

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



Рисунок 2.1.1 - Квадратичний сплайн з шести поліноміальних сегментів

Рисунок 2.1.2 - Кубічний сплайн, складений з семи поліноміальних сегментів інтерполяція сплайн програмування

2.2 Постановка задачі

Маємо таблично задану безперервну функцію на відрізку з рівно або нерівно віддаленими вузлами інтерполяції

(2.2.1)

де . (2.2.2)

Потрібно проінтерполювати функцію методом сплайнів та обчислити її значення у відповідній точці.

2.3 Види сплайнів

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

Сплайн Ерміта - це сплайн третього порядку, похідна якого приймає у вузлах сплайна задані значення. Сплайн Ерміта має безперервну першу похідну, але друга похідна у нього розривні.

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

Ідея методу інтерполяції сплайнами

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

2.4 Метод прогонки для розв'язання систем лінійних рівнянь

Нехай А - трьохдіагональна матриця, яка має вид:

.

Покладемо та запишемо дану систему в канонічному виді:

(2.5.1)

Виразимо з першого рівняння даної системи через :

(2.5.2)

Тепер з другого рівняння виразимо через :

(2.5.3)

Проводячи аналогічні міркування для останніх рівнянь системи, отримуємо:

(2.5.4)

де (2.5.5)

(2.5.6)

Розглянемо як працює метод прогонки. Спочатку (на прямому ході прогонки) ми визначаємо коефіцієнти та через відомі елементи матриці А, задані значення та раніше обраховані та :

(2.5.7)

Після обрахування коефіцієнтів та починається зворотний хід прогонки - визначення Так як

та

то: (2.5.8)

2.5 Вивід формул методу інтерполяції сплайнами

Розглянемо задачу (2.2.1)-(2.2.2).

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

а) на кожному сегменті функція є багаточленом третього ступеню;

б) функція , а також її перша та друга похідні, безперервні на ;

в) в вузлах значення даної функції співпадають зі значеннями кубічного сплайну

. (2.6.1)

Остання умова зветься умовою інтерполяції.

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

На кожному з відрізків будемо шукати функцію у виді багаточлена третього ступеню:

(2.6.2)

де - коефіцієнти, що підлягають визначенню.

З'ясуємо зміст введених коефіцієнтів.

Маємо:

(2.6.3)

(2.6.4)

(2.6.5)

по цьому

 (2.6.6)

З умов інтерполяції отримуємо, що

(2.6.7)

Довизначимо, крім цього,

. (2.6.8)

Далі, вимога безпервності функції приводить до умов

(2.6.9)

Звідси, враховуючи вираз для функцій отримуємо при рівняння:

(2.6.10)

Позначаючи , перепишемо ці рівняння в виді:

(2.6.11)

Умови безперервності першої похідної

(2.6.12)

приводять к рівнянням

(2.6.13)

З умов безперервності другої похідної отримуємо рівняння:

. (2.6.14)

Об'єднавши (2.6.11) - (2.6.14), отримаємо систему з рівнянь відносно невідомих

Дві відсутніх умови отримують, задаючи ті чи інші граничні умови для Припустимо, наприклад, що функція відповідає умовам Тоді, природно вимагати, щоб Звідси отримуємо

(2.6.15)

тобто

(2.6.16)

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

(2.6.17)

, (2.6.18)

. (2.6.19)

Переконаємося в тому, що ця система має єдине рішення. Виключимо з (2.6.17) - (2.6.19) змінні й отримаємо систему, яка містить тільки Для цього розглянемо два сусідніх рівняння (2.6.19) :

(2.6.20)

(2.6.21)

й віднімемо друге рівняння з першого. Тоді отримаємо

(2.6.22)

Підставивши знайдений вираз для в праву частину рівняння (2.6.18), отримаємо

(2.6.23)

Далі, з рівняння (2.6.19) отримуємо

(2.6.24)

. (2.6.25)

Та підставивши ці вирази до (2.6.20), приходимо до рівняння

(2.6.26)

Остаточно для визначення коефіцієнтів отримуємо систему рівнянь

. (2.6.27)

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

, (2.6.28)

(2.6.29)

Таким чином, доказано, що існує єдиний кубічний сплайн, що визначається умовами а)-в) та гранічними умовами

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

2.6 Алгоритм методу інтерполяції функції кубічними сплайнами

Для обчислення значення в довільній точці відрізка

1. визначаємо крок по формулі:

, (2.7.1)

2. виписуємо систему рівнянь (2.6.27) для визначення

3. коефіцієнти , знаходимо по формулах (2.6.7), (2.6.28), (2.6.29);

4. визначаємо, на який інтервал попадає точка х та, знаючи номер i0, обчислити значення сплайну у точці х по формулі:

, (2.7.2)

2.7 Приклад використання інтерполяції кубічними сплайнами

Дана таблична функція f(х):

Таблиця 2.8.1- таблична функція

хі	1	2	3	4
fі	5	3	2.5	2

Потрібно обчислити значення функції у точці х = 2.5, використовуючи сплайн-інтерполяцію.

Рішення.

Крок = const . h = hi = 1, i=. n = 3.

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

, .

Так як крок постійний, то система спрощується:

=>.

.

.

.

Вирішуємо цю систему рівнянь:

З першого рівняння виразимо та підставимо до другого рівняння: звідси

Визначимо коефіцієнти

, : .



,

s(x)=

Розглянемо точку х = 2.5, яка належить другому відрізку, тобто

Звідси слідує:

Відповідь:

Висновки

В ході виконання даної курсової роботи було розглянуто метод інтерполяції сплайнами та розроблена програма знаходження значення функції в визначеній точці на мові програмування Borland C++ 4.5.

Список використаних джерел

1. В.І. Крилов та ін "Обчислювальні методи", 1том, М., Наука, 1976 р., с.304.

2. Г.Н. Воробьева, А.Н. Данілова, "Практикум з чисельних методів", М., Вища школа, 1979 р., с.184.

3. Даніліна Н.І., "Чисельні методи", М., Вища школа, 1976 р., с. 368.

4. Демидович Б.П., Марон І.А., "Основи обчислювальної математики", М., Наука, 1963 р., с.660.

5. Волков О.А. Чисельні методи: Учеб. Посібник для вузів - 2-е видання., Испр. - М.: Наука. Гол. ред. Фіз.-мат. Літ., 1987. - 248 с.

6. Калоєров С.А. Програмування на мові С++: учбовий посібник. - Донецьк: "Південь-схід", 2009.

Додаток А.

Скласти програму для обчислення значення функції у точці, використовуючи сплайн-інтерполяцію.

Дана таблична функція f(х):

хі	1	2	3	4
fі	5	3	2.5	2

та точка х=2.5.

Лістінг програми:

#include <iostream.h>

#include <math.h>

void main()

{int n,k,r;

double xt,a,s,hi,hi1,l,m,p;

cout""Enter n - amount spline segments \n";

cin" n;

double *x=new double[n+1];double *f=new double[n+1];

double *alpha=new double[n-1];double *beta=new double[n-1];

double *c=new double[n];double *d=new double[n];double *b=new double[n];

cout""Enter "" (n+1) "" interpolation points x and function f values in them \n"; for (k=0;k<=n;k++)

{cout""x[""k""]="; \\ вводимо значення х та y

cin"x[k];

cout""f[""k""]=";

cin"f[k];

}

cout""Enter point xt \n";

cin"xt;

alpha[0]=0;beta[0]=0; c[0]=0; c[n]=0;

for (k=1;k<n;k++) \\ метод прогонки

{hi=x[k]-x[k-1];

hi1=x[k+1]-x[k];

l=2*(hi+hi1);

m=6*((f[k+1]-f[k])/hi1-(f[k]-f[k-1])/hi);

p= hi*alpha[k-1]+l;

alpha[k]=-hi/p;

beta[k]=(m-hi*beta[k-1])/p;

}

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

c[k]=alpha[k]*c[k+1]+beta[k]; \\ обратний прогон, знаходимо коефіцієнти с

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

{hi=x[k]-x[k-1];

d[k]=(c[k]-c[k-1])/hi; \\ знаходимо коефіцієнти d i b

b[k]=(hi/2*c[k])-((hi*hi)/6*d[k])+((f[k]-f[k-1])/hi);

}

r=0;

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

if (xt<=x[k]&xt>x[k-1]) r=k; \\ перевірка, на якому сегменті знаходится дана

if (r>0) {a=xt-x[r]; \\точка

s=f[r]+b[r]*a+((c[r]*pow(a,2))/2)+((d[r]*pow(a,3))/6);}

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

cout"f[k]""x^3+""b[k]""x^2+""c[k]""x+""d[k]"" x belongs [""

x[k-1]"",""x[k]""] \n";

cout""s(""xt"")=""s;

delete[]x;delete[]f;delete[]alpha;delete[]c;delete[]beta;delete[]d;delete[]b;

}

Результат роботи програми:

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

...