«Програмна реалізація алгоритму обчислення значення функції за першим інтерполяційним многочленом Ньютона»

1 2 3

Ім'я файлу: Курсова.doc
Розширення: doc
Розмір: 455кб.
Дата: 22.06.2020
скачати

Міністерство освіти і науки України Вінницький національний технічний університет Факультет інформаційних технологій та комп'ютерної інженерії Кафедра комп'ютерних наук

КУРСОВА РОБОТА
з дисципліни «Чисельні методи»
на тему: «Програмна реалізація алгоритму обчислення значення функції за першим інтерполяційним многочленом Ньютона»

Студента 2 курсу, групи КН-18б

спеціальності 122 – «Комп'ютерні

науки»

Ясінський О.С.________

(прізвище та ініціали)

Керівник: к.т.н., доцент Крилик Л. В.
Національна шкала
Кількість балів
Оцінка ECTS

Члени комісії:

(підпис) (прізвище та ініціали)

(підпис) (прізвище та ініціали)

(підпис) (прізвище та ініціали)

м. Вінниця, 2020 рік

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

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

Факультет інформаційних технологій та комп’ютерної інженерії

ЗАТВЕРДЖУЮ

Зав. кафедри КН, проф., д.т.н.

______________ А. А. Яровий

(підпис)

«___» ______________ 2020 р.

ІНДИВІДУАЛЬНЕ ЗАВДАННЯ

на курсову роботу з дисципліни «Чисельні методи»
студенту Ясінському О. С. факультету ІТКІ, групи КН-18б
Тема: «Програмна реалізація алгоритму екстраполювання функції за першою інтерполяційною формулою Ньютона»
Вихідні дані:

- Кількість вузлів інтерполювання не більше 20.

- Кількість значущих цифр

.

Зміст до курсової роботи

Індивідуальне завдання

Анотація

Вступ

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

2. Розробка алгоритмів та вибір оптимального алгоритму

3. Приклад програми екстраполювання функції за першою інтерполяційною формулою Ньютона

Висновки

Перелік джерел посилань

Дата видачі «____» _________ 2020 р. Керівник _____________________

(підпис)

Завдання отримав_______________

(підпис)


	ЗМІСТ
ВСТУП………………….……………………………………………...		5
1 АНАЛІЗ ТЕОРЕТИЧНОЇ БАЗИ МЕТОДІВ ІНТЕРПОЛЮВАННЯ
ФУНКЦІЇ …………………………………………………………...		6
2 РОЗРОБКА АЛГОРИТМІВ ТА ВИБІР ОПТИМАЛЬНОГО
АЛГОРИТМУ……………………………………………………….		21
3 ПРИКЛАД ПРОГРАМИ ОБЧИСЛЕННЯ ЗНАЧЕННЯ ФУНКЦІЇ
ЗА ПЕРШИМ ІНТЕРПОЛЯЦІЙНИМ МНОГОЧЛЕНОМ
НЬЮТОНА……………………………………………………………		24
3.1	Інструкція користувача…………………………………………	25
3.2	Лістинг програми………………………………………………	26
3.3	Опис програми…………………………………………………	27
3.4	Тестування програми………………………………………….
ВИСНОВКИ…………………………………………………………….		28
ПЕРЕЛІК ДЖЕРЕЛ ПОСИЛАНЬ……………………………………		29

АНОТАЦІЯ
Об'єктом дослідження є перший інтерполяційний многочлен Ньютона. Розроблено оптимальний алгоритм та програму в середовищі С++ як за розміром пам'яті, необхідної для збереження даних, які обчислюються під час виконання алгоритму, так і за кількістю арифметичних операцій для обчислення за основною формулою. Програма має зручний та наочний інтерфейс, який максимально спрощує роботу з нею, та автоматичну перевірку коректності даних, що вводяться.

ВСТУП
Актуальність теми
Методи інтерполяції і наближення функцій використовуються в чисельних процедурах для локальної апроксимації експериментальних даних.
Інтерполяцію використовують для наближеного обчислення значень різних функцій. Крім того, параболічне інтерполювання найзручніше, оскільки многочлени, які прості за формою і не мають особливих точок, можуть набувати довільних значень. Їх легко обчислювати, диференціювати та інтегрувати. Інтерполяційні формули Ньютона мають певні переваги. Адже якщо до заданої системи рівновіддалених вузлів інтерполювання до-дати ще один, то відповідний многочлен Лагранжа треба будувати заново,

в многочлені Ньютона додається лише один новий доданок, а вже обчислені залишаються без змін.

Мета дослідження
Метою роботи є дослідження можливості використання першого інтерполяційного многочлена Ньютона для обчислення значення функції.
Задачі дослідження:
 проаналізувати існуючі методи інтерполювання функції та обґрунтувати переваги першого інтерполяційного многочлена Ньютона відносно існуючих;

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

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

Об'єкт дослідження. Об'єктом дослідження є перший інтерполяційний многочлен Ньютона.

1 АНАЛІЗ ТЕОРЕТИЧНОЇ БАЗИ МЕТОДІВ
ІНТЕРПОЛЮВАННЯ ФУНКЦІЇ
Інтерполяцію в інженерній та науковій практиці використовують для наближеного обчислення значень функцій. Якщо функція належить до класу алгебраїчних многочленів, то інтерполювання називають параболічним. Параболічне інтерполювання найзручніше, оскільки многочлени, які прості за формою і не мають особливих точок, можуть набувати довільних значень. Їх легко обчислювати, диференціювати та інтегрувати, однак у деяких випадках доцільніше використовувати інші класи інтерполювальних функцій.
Розглянемо класичні методи інтерполювання функції [1 – 12]. Формула Лагранжа дає можливість знайти вираз інтерполяційного

многочлена у явному вигляді:

( x  x ₀ )( x  x₁ )...( x  x_i _₁)( x  x_i _₁)...( x  x_n )

L_n( x )

y_i.

( x

 x

)( x

 x )...( x

 x

)( x

 x

)...( x

 x

)

i0

i 1

i 1

Щоб побудувати інтерполяційний многочлен Лагранжа, потрібно ви-конати значну обчислювальну роботу. Обсяг її суттєво зростає тоді, коли необхідно підвищувати порядок многочлена: якщо до заданої системи вузлів інтерполювання x_i (i  0,1, ..., n) додати ще хоч один вузол x_n_₁ , то для нової системи вузлів x_i (i  0,1, ..., n 1) многочлен Лагранжа потрібно будувати заново.
Якщо необхідно обчислити лише значення функції у певній точці, доцільно застосувати схему Ейткіна. Особливістю цієї схеми є однотипність обчислень.

^P0,1..,n ⁽^x⁾ ^	1	^P0,1..., n1 ⁽^x ⁾	x ₀	 x	,

	x _n x₀	^P1,2,..,n ⁽^x ⁾	x _n x

де P_0,1,..., _n_₁(x) і P_1,2...,_n (x) – значення інтерполяційних многочленів (n 1) -го степеня, обчислених у точці x на попередньому кроці обчислень.
Легко впевнитись, що P_0,1,...,_n (x_i )  y_i (i  0,1, ..., n) і P_0,1,2,...,_n (x) збігається
з інтерполяційним многочленом Лагранжа n -го степеня.

Отже, щоб обчислити в точці x значення інтерполяційного многочлена n -го степеня за схемою Ейткіна,потрібно в цій точці обчислити значення

лінійних, n 1 квадратичних, n  2 кубічних многочленів тощо, два многочлени (n 1) -го степеня і, нарешті, один многочлен n -го степеня. Всі ці

многочлени виражають через визначник 2-го порядку, а це робить обчислення однотипними, циклічними [7 – 12].

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

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

многочлені Ньютона додається лише один новий доданок, і вже обчислені залишаються без змін.

Розглянемо детально перший інтерполяційний многочлен Ньютона. Нехай значення функції f задано для рівновіддалених значень аргу-
менту x₀ , x₁  x ₀  h , x₂  x ₀  2h , …., x_n  x ₀  nh . Позначимо ці значення

функції відповідно через y₀ ,	y₁, y₂, … , y_n.
Побудуємо інтерполяційний многочлен n -го степеня вигляду:
P _n(x ) a ₀	 a₁(x  x ₀) a ₂(x  x ₀)(x  x₁)		(1.1)
 a₃(x  x ₀)(x  x₁)(x  x ₂)... a _n(x  x ₀)(x  x₁)...(x  x_n_₁)

так, щоб у вузлах інтерполювання x_i (i  0,1, ... ,n)		він набував значень y_i
(i  0,1, . . . , n ) , тобто задовольняв умову
P_n(x_i) y_i	(i  0,1, . . . ,n) .		(1.2)

Користуючись умовою (1.2), визначимо коефіцієнти a ₀ , a₁ ,..., a_n много-члена (1.1).
Покладемо в (1.1) x  x₀ . Тоді з (1.2) дістанемо
y ₀ P_n(x₀) a₀, a ₀ y₀.
Якщо x  x₁ , маємо
y₁ P _n(x₁) a ₀ a₁(x₁ x₀)
або, оскільки x₁  x ₀  h і a ₀  y₀ ,
y₁ y ₀ a₁h ,
звідси

_a₁ _ ^y1 ^ ^y 0 _ ^^y0 _.

h h
Аналогічно, якщо x  x₂ , дістанемо

y ₂ P_n( x ₂) a ₀ a₁( x ₂ x ₀) a ₂( x ₂ x ₀)( x ₂ x₁) .
Підставивши в цю формулу знайдені раніше значення коефіцієнтів a₀ та a₁і,врахувавши,що x₂ x ₀2h , x₂ x₁ h ,дістанемо
y ₂2y₁ y ₀ a ₂2!h².
Звідси

_a₂ _ ^y 2 ^ ²^y1 ^ ^y 0 _ ^² ^y0 _.

2!h ² 2!h²

Аналогічно, якщо x  x₃ ,

_a₃ _ ^y 3 ^ ³^y 2 ^ ³^y1 ^ ^y 0 _ ^³ ^y0 _.

3!h ³ 3!h³
Взагалі, для будь-якого k

	^k y	0	0
a 			(k  0,1,..., n) ( y ₀  y₀ ) .
k	k !h^k

Підставивши знайдені

значення

коефіцієнтів

a_k(k0,1,...,n)в

дістанемо

 y

² y

P (x ) y



(x  x

) 

(x  x

)(x  x ) 

2!h²



³ y

(x  x

)(x  x )(x  x

)...

3!h³



^k y

(x  x )(x  x )...(x  x

k 1

)

...

k !h^k



ⁿ y

(x  x

)(x  x )...(x  x

n1

n!hⁿ

(1.1),

(1.3)

Цей многочлен називають першим інтерполяційним многочленом Ньютона.

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

f (x ) P_n(x) .

(1.4)

Цю формулу називають першою інтерполяційною формулою Ньютона. На вигляд многочлен (і формула) Ньютона відрізняється від многочлена (і формули) Лагранжа. Але якщо ці многочлени побудовано для тієї

самої функції f та однієї й тієї самої системи вузлів x_i (i  0,1, . . . , n) , то

за теоремою про єдиність розв’язку інтерполяційної задачі вони тотожно дорівнюватимуть одна одній [6 – 12].

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

З формули (1.4) для n 1 дістанемо формулу лінійного інтерполювання

f (x ) y ₀	y₀	(x  x₀ ) ,	(1.5)
	h

а для n  2 – формулу квадратичного інтерполювання

f (x ) y			 y ₀	(x  x	) 	1	² y₀	(x  x	)(x  x ) .	(1.6)
			h			2! h²
	0			0				0	1

В обчислювальній практиці зручніше користуватися іншою формою запису многочлена Ньютона (1.3). Якщо покласти

x  x₀	 t ,то	x  x₁	 t 1 ,	x  x₂	 t 2,...,	x  x_n_₁	 t  n 1
h		h		h		h

і многочлен (1.3) матиме вигляд
P (x  th) y  t  y ^t⁽^t^¹⁾² y 

_n ₀ ₀ ₀ 2! ₀

t(t1)(t2)_3_y₀__..._t(t1)(t2)...(tn1)_n_y₀_,

3!n!
а перша інтерполяційна формула Ньютона (1.4)
f (x ) P_n(x ₀th) .
Різницю

( x )  P_n ( x ₀  th)  R_n ( x, f )

(1.7)

(1.8)
(1.9)

називають залишковим членом першої інтерполяційної формули Нью-тона.
Оскільки для функції f і системи рівновіддалених вузлів x_i
(i  0,1, . . . , n ) існує єдиний інтерполяційний многочлен степеня n , то
інтерполяційні многочлени Лагранжа і Ньютона збігатимуться між собою, тобто L_n ( x )  P_n ( x) . А тому й залишковий член інтерполяційної формули Ньютона (1.4) збігатиметься із залишковим членом формули Лагранжа. Отже,

R ( x, f )^f⁽ⁿ^¹⁾⁽^⁾( x  x )( x  x )...( x  x ) .

_n ( n 1)! ₀ ₁ _n
З введенням змінної t залишковий член R_n (x, f ) набуває вигляду

R (x, f )

_hn1

f ⁽ⁿ^¹⁾() t (t 1)(t 2)...(t  n).

(1.10)

(n 1)!

Якщо ввести позначення, що M _n_₁  max

_f ( n1) ₍_ ₎

, то для абсолютної

 x ₀, x_n

похибки інтерполяційної формули (1.8) дістанемо оцінку

R (x, f )



_hn1

t (t 1)...(t  n)

(1.11)

(n 1)!

n1

Користуючись формулою f ⁽ ⁿ ⁾ (x ) ⁿ f (x )/hⁿ , що встановлює зв'язок
між похідними і кінцевими різницями, залишковий член першої інтерполяційної формули Ньютона (1.10) можна записати так:
R (x, f )^ⁿ^¹^y0 t (t 1)...(t  n) .

_n (n 1)!
Інтерполяційний многочлен Ньютона містить різниці y₀ , ² y₀ ,...,

ⁿ y₀.Тому інтерполяційною формулою(1.4)або(1.8)зручно користуватися на початку таблиці, тобто для всіх x(x ₀ ,x₁) . Для цих значень x змінна t 1. Якщо x[ x₁ , x₂ ], то користуватись інтерполяційною формулою (1.8) недоцільно, бо t буде більшим за 1. У цьому разі за x₀ треба взяти вузол x₁ і в інтерполяційному многочлені використовувати різниці y₁ , ² y₁ ,

... , ⁿ y₁ . Тому формулу (1.4) (або (1.8) називають також інтерполяційною
1 2 3

скачати