Реферат: Аналіз теоретичної бази інтерполювання функції

--PAGE_BREAK--
1.4 Обернена інтерполяція
Нехай функція <img width=«61» height=«21» src=«ref-1_1896480568-157.coolpic» v:shapes="_x0000_i1069"> задана таблицею. Задача зворотної інтерполяції полягає в тому, щоб по заданому значенню функції <img width=«15» height=«17» src=«ref-1_1896470101-89.coolpic» v:shapes="_x0000_i1070"> визначити відповідне значення аргументу <img width=«13» height=«15» src=«ref-1_1896469641-84.coolpic» v:shapes="_x0000_i1071">.

Якщо вузли інтерполяції <img width=«89» height=«24» src=«ref-1_1896480898-175.coolpic» v:shapes="_x0000_i1072"> нерівновіддалені, задача легко вирішується за допомогою інтерполяційної формули Лагранжа (5). Для цього достатньо прийняти <img width=«15» height=«17» src=«ref-1_1896470101-89.coolpic» v:shapes="_x0000_i1073"> за незалежну змінну, а <img width=«13» height=«15» src=«ref-1_1896469641-84.coolpic» v:shapes="_x0000_i1074"> вважати функцією. Тоді отримаємо
<img width=«388» height=«47» src=«ref-1_1896481246-1129.coolpic» v:shapes="_x0000_i1075">,       (9)
Розглянемо тепер задачу оберненої інтерполяції для випадку рівновіддалених вузлів інтерполяції. Припустимо, що функція f(х) монотонна і дане значення у знаходиться між <img width=«76» height=«24» src=«ref-1_1896482375-180.coolpic» v:shapes="_x0000_i1076"> і <img width=«73» height=«23» src=«ref-1_1896482555-173.coolpic» v:shapes="_x0000_i1077">.

Замінюючи функцію <img width=«75» height=«25» src=«ref-1_1896482728-164.coolpic» v:shapes="_x0000_i1078"> першим інтерполяційним многочленом Ньютона, одержимо:
<img width=«491» height=«35» src=«ref-1_1896482892-1030.coolpic» v:shapes="_x0000_i1079">.
Звідси


<img width=«416» height=«47» src=«ref-1_1896483922-867.coolpic» v:shapes="_x0000_i1080">,
тобто <img width=«60» height=«21» src=«ref-1_1896484789-163.coolpic» v:shapes="_x0000_i1081">.

Розмір <img width=«13» height=«17» src=«ref-1_1896484952-87.coolpic» v:shapes="_x0000_i1082"> визначаємо методом послідовних наближень як границю послідовності:
<img width=«65» height=«29» src=«ref-1_1896485039-188.coolpic» v:shapes="_x0000_i1083">,
де <img width=«148» height=«24» src=«ref-1_1896485227-271.coolpic» v:shapes="_x0000_i1084">

За початкове наближення приймаємо
<img width=«79» height=«47» src=«ref-1_1896485498-242.coolpic» v:shapes="_x0000_i1085">. (10)
Для <img width=«9» height=«17» src=«ref-1_1896485740-80.coolpic» v:shapes="_x0000_i1086">-го наближення маємо:
<img width=«461» height=«48» src=«ref-1_1896485820-907.coolpic» v:shapes="_x0000_i1087">. (11)
На практиці ітераційний процес продовжують доти, поки не установляться значення, що відповідають необхідній точності, причому <img width=«47» height=«24» src=«ref-1_1896486727-135.coolpic» v:shapes="_x0000_i1088">,де <img width=«17» height=«15» src=«ref-1_1896486862-88.coolpic» v:shapes="_x0000_i1089"> – останнє зі знайдених наближень. Знайдемо <img width=«13» height=«17» src=«ref-1_1896484952-87.coolpic» v:shapes="_x0000_i1090">,визначаємо <img width=«13» height=«15» src=«ref-1_1896469641-84.coolpic» v:shapes="_x0000_i1091"> по формулі
<img width=«72» height=«43» src=«ref-1_1896487121-198.coolpic» v:shapes="_x0000_i1092">,
звідки


<img width=«77» height=«24» src=«ref-1_1896487319-173.coolpic» v:shapes="_x0000_i1093">                                     . (12)
Ми застосували метод ітерації для розв’язку задачі оберненої інтерполяції, користуючись першою інтерполяційною формулою Ньютона. Аналогічно можна застосувати цей спосіб і до другої формули Ньютона:
<img width=«495» height=«33» src=«ref-1_1896487492-997.coolpic» v:shapes="_x0000_i1094">.
Звідси
<img width=«440» height=«47» src=«ref-1_1896488489-922.coolpic» v:shapes="_x0000_i1095">
Позначимо <img width=«81» height=«47» src=«ref-1_1896489411-251.coolpic» v:shapes="_x0000_i1096">– початкове наближення.

Для <img width=«9» height=«17» src=«ref-1_1896485740-80.coolpic» v:shapes="_x0000_i1097">-го наближення маємо:
<img width=«448» height=«47» src=«ref-1_1896489742-910.coolpic» v:shapes="_x0000_i1098"> (13)
Знайдемо
<img width=«65» height=«29» src=«ref-1_1896485039-188.coolpic» v:shapes="_x0000_i1099">,
визначимо <img width=«13» height=«15» src=«ref-1_1896469641-84.coolpic» v:shapes="_x0000_i1100"> по формулі [2,3]
<img width=«77» height=«24» src=«ref-1_1896490924-169.coolpic» v:shapes="_x0000_i1101">.


Далі розглянемо запропоновану інтерполяційну формулу Бесселя. Вона подібна до інтерполяційної формули Стірлінга і обидві вони є похідними від першої та другої інтерполяційних формул Гаусса.



1.5 Інтерполяційна формула Бесселя
Часто використовується інтерполяційна формула Бесселя, яка служить для знаходження значення функції у міжвузловій точці. Для виведення цієї формули скористаємось другою інтерполяційною формулою Гаусса:
<img width=«575» height=«88» src=«ref-1_1896491093-1592.coolpic» v:shapes="_x0000_i1102">
у скороченому вигляді:
<img width=«496» height=«47» src=«ref-1_1896492685-1003.coolpic» v:shapes="_x0000_i1103">
де х=х0+qh.

Візьмемо 2n+2 рівновіддалених вузлів інтерполювання

x-n, x-(n-1),..., x0,..., xn-1, xn, xn+1 ,

з кроком h, і нехай

yi= f(xi), (i =-n,…,n+1),

— задані значення функції y= f(x). <img width=«12» height=«23» src=«ref-1_1896493688-73.coolpic» v:shapes="_x0000_i1104">

Якщо вибрати за початкові значення x= x0 та y= y0, то, використовуючи вузли xk (k= 0, ±1, …,<img width=«15» height=«16» src=«ref-1_1896493761-88.coolpic» v:shapes="_x0000_i1105"> n), будемо мати:


<img width=«395» height=«88» src=«ref-1_1896493849-1248.coolpic» v:shapes="_x0000_i1106"> (14)
Приймемо тепер за початкові значення х=х1 і у=у1 і використаємо вузли х1+к (к=0, <img width=«15» height=«16» src=«ref-1_1896493761-88.coolpic» v:shapes="_x0000_i1107">1,...,<img width=«15» height=«16» src=«ref-1_1896493761-88.coolpic» v:shapes="_x0000_i1108">n). Тоді
<img width=«175» height=«43» src=«ref-1_1896495273-343.coolpic» v:shapes="_x0000_i1109">
причому відповідно індекси всіх різниць в правій частині формули (14) зростуть на одиницю. Замінивши в правій частині формули (14) q на q-1 і збільшивши індекси всіх різниць на 1, отримаємо допоміжну інтерполяційну формулу
<img width=«424» height=«88» src=«ref-1_1896495616-1532.coolpic» v:shapes="_x0000_i1110"> (15)
Взявши середнє арифметичне формул (14) і (15), після простих перетворень отримаємо інтерполяційну формулу Бесселя

інтерполяція функція бессель програма

<img width=«428» height=«109» src=«ref-1_1896497148-1541.coolpic» v:shapes="_x0000_i1111"> (16)

<img width=«76» height=«43» src=«ref-1_1896498689-202.coolpic» v:shapes="_x0000_i1112">


Інтерполяційна формула Бесселя (16), як слідує з способу отримання її, представляє собою поліном, що співпадає з даною функцією y= f(x) в 2n+2 точках
x-n, x-(n-1),…, xn, xn+1.
В частинному випадку, при n=1, нехтуючи різницею ∆3y-1, отримаємо формулу квадратичної інтерполяції по Бесселю
<img width=«428» height=«43» src=«ref-1_1896498891-812.coolpic» v:shapes="_x0000_i1113">,

<img width=«227» height=«24» src=«ref-1_1896499703-380.coolpic» v:shapes="_x0000_i1114">

<img width=«91» height=«41» src=«ref-1_1896500083-251.coolpic» v:shapes="_x0000_i1115">
В формулі Бесселя всі члени, які містять різниці непарного порядку, мають множник q-<img width=«16» height=«41» src=«ref-1_1896500334-109.coolpic» v:shapes="_x0000_i1116">; тому при <img width=«41» height=«41» src=«ref-1_1896500443-156.coolpic» v:shapes="_x0000_i1117"> формула (16) значно спрощується :
<img width=«412» height=«93» src=«ref-1_1896500599-1420.coolpic» v:shapes="_x0000_i1118">
Цей спеціальний випадок формули Бесселя називається формулою інтерполювання на середину.        Якщо в формулі Бесселя (3) зробити заміну по формулі <img width=«71» height=«41» src=«ref-1_1896502019-192.coolpic» v:shapes="_x0000_i1119"> то вона приймає більш симетричний вид


<img width=«513» height=«141» src=«ref-1_1896502211-3044.coolpic» v:shapes="_x0000_i1120">

<img width=«129» height=«43» src=«ref-1_1896505255-306.coolpic» v:shapes="_x0000_i1121">
Приклад розв’язку задачі:

Значення функції <img width=«140» height=«25» src=«ref-1_1896505561-267.coolpic» v:shapes="_x0000_i1122"> подано у табл. 2. Знайти значення <img width=«56» height=«21» src=«ref-1_1896505828-159.coolpic» v:shapes="_x0000_i1123">.
Таблиця 2- Таблиця різниць функції <img width=«64» height=«21» src=«ref-1_1896505987-162.coolpic» v:shapes="_x0000_i1124">

<img width=«13» height=«15» src=«ref-1_1896469641-84.coolpic» v:shapes="_x0000_i1125">

<img width=«15» height=«17» src=«ref-1_1896470101-89.coolpic» v:shapes="_x0000_i1126">

<img width=«23» height=«21» src=«ref-1_1896506322-107.coolpic» v:shapes="_x0000_i1127">

<img width=«29» height=«24» src=«ref-1_1896506429-122.coolpic» v:shapes="_x0000_i1128">

<img width=«29» height=«24» src=«ref-1_1896506551-121.coolpic» v:shapes="_x0000_i1129">

<img width=«29» height=«24» src=«ref-1_1896506672-123.coolpic» v:shapes="_x0000_i1130">

<img width=«29» height=«24» src=«ref-1_1896506795-123.coolpic» v:shapes="_x0000_i1131">

<img width=«29» height=«24» src=«ref-1_1896506918-123.coolpic» v:shapes="_x0000_i1132">

<img width=«29» height=«24» src=«ref-1_1896507041-122.coolpic» v:shapes="_x0000_i1133">

<img width=«29» height=«24» src=«ref-1_1896507163-123.coolpic» v:shapes="_x0000_i1134">

2

-4.58579





















-11.68216















3

-16.26795



-6.04989

















-17.73205



0.01801











4

-34



-6.03188



-0.00878













-23.76393



0.00923



0.00504







5

-57.76393



-6.02265



-0.00374



-0.00321









-29.78658



0.00549



0.00183



0.00218



6

-87.55051



-6.01716



-0.00191



-0.00103



-0.00287





-35.80374



0.00358



0.0008



0.00069



7

-123.35425



-6.01358



-0.00111



-0.00034









-41.81732



0.00247



0.00046







8

-165.17157



-6.01111



-0.00065













-47.82843



0.00182











9

-213



-6.00929

















-53.83772















10

-266.83772



















Розв’язок:

Приймемо <img width=«44» height=«24» src=«ref-1_1896507286-126.coolpic» v:shapes="_x0000_i1135"> і <img width=«57» height=«19» src=«ref-1_1896507412-135.coolpic» v:shapes="_x0000_i1136">, тоді

<img width=«187» height=«43» src=«ref-1_1896507547-370.coolpic» v:shapes="_x0000_i1137">.
Оскільки <img width=«68» height=«41» src=«ref-1_1896507917-214.coolpic» v:shapes="_x0000_i1138">, то скористаємося формулою Бесселя. Маємо:

<img width=«208» height=«41» src=«ref-1_1896508131-389.coolpic» v:shapes="_x0000_i1139">;
Звідси, використовуючи підкреслені різниці, отримаєм:
<img width=«559» height=«266» src=«ref-1_1896508520-5027.coolpic» v:shapes="_x0000_i1140">


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

Аналіз формули та прикладу, наведеного в першому розділі, показує що для обчислення значення функції необхідно обчислити <img width=«73» height=«53» src=«ref-1_1896513547-413.coolpic» v:shapes="_x0000_i1141"> значеня кінцевих різниць а також значеннь q та р. Безпосереднє обчислення за формулою вимагає <img width=«101» height=«53» src=«ref-1_1896513960-456.coolpic» v:shapes="_x0000_i1142"> операцій додавання (віднімання), n — операцій ділення та <img width=«70» height=«50» src=«ref-1_1896514416-400.coolpic» v:shapes="_x0000_i1143">  — операцій множення. З врахуванням того, що час виконання операції множення та ділення відповідно в 1,14 та 2,33 рази більший за час виконання операції додавання (віднімання) при використанні математичного співпроцесора, загальна кількість операцій обчислення складає
<img width=«343» height=«42» src=«ref-1_1896514816-840.coolpic» v:shapes="_x0000_i1144">
Алгоритм можна побудувати таким чином, щоб спочатку обчислити всі всі знаменники поліному, а потім провести обчислення за основною формулою. В цьому випадку необхідно <img width=«85» height=«61» src=«ref-1_1896515656-534.coolpic» v:shapes="_x0000_i1145"> комірок пам’яті.

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

Комплексний коефіцієнт ефективності Ке одного алгоритму в порівнянні з іншим можна обчислити за формулою
<img width=«137» height=«34» src=«ref-1_1896516190-463.coolpic» v:shapes="_x0000_i1146">
де Кч – коефіцієнт ефективності за часом виконання;

Кn – коефіцієнт ефективності за затратами пам’яті алгоритму.

Оскільки коефіцієнт ефективності за часом виконання алгоритму можна приблизно оцінити за кількістю арифметичних операцій алгоритму, то комплексний коефіцієнт ефективності описаних вище алгоритмів складає
<img width=«243» height=«58» src=«ref-1_1896516653-855.coolpic» v:shapes="_x0000_i1147">
Для випадку коли n=9
<img width=«304» height=«31» src=«ref-1_1896517508-1236.coolpic» v:shapes="_x0000_i1148">
Блок-схеми описаних вище алгоритмів відповідно на рис 2.1 та рис 2.2. В даних алгоритмах вважається, що матриця A використовуються для збереження таблиці різниць, значення x, x0, n, q – однойменні змінні [6].


    продолжение
--PAGE_BREAK--