Міністерство освіти і науки України
Вінницький національний технічний університет
Інститут автоматики, електроніки та комп’ютерних систем управління
Кафедра МПА
Аналіз теоретичної бази інтерполювання функції
Вінниця ВНТУ – 2009
Вступ
Актуальність теми. Задача знаходження значення функції у міжвузловій точці за допомогою інтерполяційної формули Бесселя має важливе значення при вирішенні як наукових, так і практичних задач, оскільки дає можливість знаходження значення функції у будь-якій точці, в якій це потрібно. В багатьох випадках функція не має аналітичного вигляду, тобто він невідомий, а задана лише декількома точками та значеннями функції в цих точках. Тому для отримання значення функції в проміжних точках застосовуються інтерполяційна формули Гауса (1-а та 2-а), інтерполяційна формула Стірлінга та Бесселя. Кожна з цих формул має свої переваги та недоліки, що полягають у кількості обчислювальних операцій та в похибці обчислень.
Мета дослідження. Метою роботи є обчислення значення функції інтерполюванням за інтерполяційною формулою Бесселя.
Задачі дослідження:
● проаналізувати існуючі методи знаходження значення функції та обґрунтувати переваги інтерполюванням за інтерполяційною формулою Бесселя по відношенню до існуючих;
● розробити алгоритми розв’язку інтерполювання функції та здійснити вибір оптимального з них;
● розробити програму розв’язку значення функції інтерполюванням та провести їх тестування.
Об’єкт дослідження. Об’єктом дослідження є інтерполяційна формула Бесселя для інтерполювання функції.
Структура курсової роботи.
Курсова робота складається з трьох основних розділів. В першому розділі наведено аналіз теоретичної бази інтерполювання функції та приклад розв’язання поставленої задачі за формулою Бесселя. У другому розділі розроблено оптимальний алгоритм за критерієм комплексної ефективності, що враховує затрати часу та пам'яті для його виконання, за даним методом. Третій розділ містить інструкція користувача, лістинг та опис програми і результати тестування.
1. Аналіз теоретичної бази інтерполювання функції
1.1
Постановка задачі інтерполяції
Якщо задано певну довільну функцію на деякому проміжку , то обчислити її значення непросто. Для полегшення цієї задачі є метод інтерполювання функції. Який полягає у тому, що дана функція замінюється наближеним значенням, причому кінцевий результат залишається незмінним.
Нехай деяка функція у=f(х) задана таблицею (табл.1), тобто при значеннях аргументу х=х0, х1, ... , хn функція f(х) приймає відповідні значення у0, у1,... , уn.
Таблиця 1- Таблиця експериментальних значень
| .... | |||||
| .... |
Необхідно визначити значення у=f(х), .
Величина потрапляє між двома табличними значеннями, тому для обчислення значення функції необхідно запропонувати деякий характер її зміни між відомими експериментальними даними.
Інтерполяцію можна розглядати як процес визначення для даного аргументу х значення функції у=f(х) по її декількох відомих значеннях. При цьому розрізняють інтерполяцію у вузькому розумінні, коли х знаходиться між і , і екстраполювання, коли х знаходиться поза відрізком інтерполяції .
Задача інтерполяції полягає в наступному. На відрізку задані точки х0, х1, ... , хn, що називаються вузлами інтерполяції, і значення деякої функції f(x) у цих точках.
,
, (1)
...............
.
Потрібно побудувати функцію Рn(х) (інтерполюючу функцію), яка б задовольняла таким умовам:
,
, (2)
.................
,
тобто інтерполююча функція Рn(х) повинна приймати ті ж значення, що і функція f(х), яку ми визначаємо (що інтерполюється), для вузлових значень аргументу х0, х1, ... , хn.
Геометрично це означає, що потрібно знайти криву y=Pn(х) деякого визначеного типу, що проходить через задану систему точок Мi (хi,уi) . Очевидно, можна побудувати множину неперервних функцій, що будуть проходити через задані вузлові точки[1].
Заміна функції f(х)
її інтерполяційним многочленом Рn(x)
може знадобитися не тільки тоді, коли відома лише таблиця її значень, але і коли аналітичний вираз для f(х) відомо, проте є занадто складним і незручним для подальших математичних перетворень (наприклад, для інтегрування, диференціювання тощо). Іноді розглядаються задачі тригонометричної інтерполяції (інтерполююча функція – тригонометричний поліном). Інтерполюючою може бути також раціональна функція.
У загалі залежність, якій підпорядковується функція, може бути апроксимована многочленом степеня :
. (3)
Таку задачу називають задачею параболічної інтерполяції (або інтерполюванням).
Загалом є багато інтерполяційних формул та методів. До них відносяться такі: інтерполяційні формули Гаусса, Стірлінга та Бесселя (які є похідними від формул Гаусса), Ньютона (перша та друга) та багато інших.
1.2 Параболічна інтерполяція
Для визначення коефіцієнтів многочлена (3) необхідно мати вузлову точку. Аналітичне визначення коефіцієнтів інтерполяційного многочлена для точки зводиться до рішення системи лінійних рівнянь порядку, кожне з яких являє собою вираз (3), записаний для визначеної вузлової точки
, (4)
де .
Даним методом побудови інтерполяційного поліному зручно користуватися, маючи персональний комп’ютер і відповідні програми. Даний метод не є єдиним способом побудови інтерполяційного поліному. Інший підхід, яким часто користуються на практиці, називається методом Лагранжа[2].
1.3 Метод Лагранжа
Нехай при функція приймає відповідно значення . Многочлен степеня не вище , що приймає у вузлових точках задані значення, має вид:
(5)
Цей многочлен (5) називається інтерполяційною формулою Лагранжа і має такі властивості:
1. При заданій сукупності вузлових точок будова многочлена можлива тільки єдиним способом.
2. Многочлен Лагранжа може бути побудовано при будь-якому розташуванні вузлів інтерполяції (включаючи і нерівномірне).
У розгорнутому виді форма Лагранжа має вид:
(6)
При формула Лагранжа має вид:
, (7)
і називається формулою лінійної інтерполяції.
При одержимо формулу квадратичної інтерполяції:
(8)
1.4 Обернена інтерполяція
Нехай функція задана таблицею. Задача зворотної інтерполяції полягає в тому, щоб по заданому значенню функції визначити відповідне значення аргументу .
Якщо вузли інтерполяції нерівновіддалені,
задача легко вирішується за допомогою інтерполяційної
формули Лагранжа
(5). Для цього достатньо прийняти за незалежну змінну, а вважати функцією. Тоді отримаємо
, (9)
Розглянемо тепер задачу оберненої інтерполяції для випадку рівновіддалених вузлів інтерполяції. Припустимо, що функція f(х) монотонна і дане значення у знаходиться між і .
Замінюючи функцію першим інтерполяційним
многочленом Ньютона, одержимо:
.
Звідси
,
тобто .
Розмір визначаємо методом послідовних наближень як границю послідовності:
,
де
За початкове наближення приймаємо
. (10)
Для -го наближення маємо:
. (11)
На практиці ітераційний процес продовжують доти, поки не установляться значення, що відповідають необхідній точності, причому ,
де – останнє зі знайдених наближень. Знайдемо ,
визначаємо по формулі
,
звідки
. (12)
Ми застосували метод ітерації для розв’язку задачі оберненої інтерполяції, користуючись першою інтерполяційною
формулою Ньютона. Аналогічно можна застосувати цей спосіб і до другої формули Ньютона:
.
Звідси
Позначимо – початкове наближення.
Для -го наближення маємо:
(13)
Знайдемо
,
визначимо по формулі [2,3]
.
Далі розглянемо запропоновану інтерполяційну формулу Бесселя. Вона подібна до інтерполяційної формули Стірлінга і обидві вони є похідними від першої та другої інтерполяційних формул Гаусса.
1.5 Інтерполяційна формула Бесселя
Часто використовується інтерполяційна формула Бесселя, яка служить для знаходження значення функції у міжвузловій точці. Для виведення цієї формули скористаємось другою інтерполяційною формулою Гаусса:
у скороченому вигляді:
де х=х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).
Якщо вибрати за початкові значення x= x0 та y= y0, то, використовуючи вузли xk (k= 0, ±1, …, n), будемо мати:
(14)
Приймемо тепер за початкові значення х=х1 і у=у1 і використаємо вузли х1+к (к=0, 1,...,n). Тоді
причому відповідно індекси всіх різниць в правій частині формули (14) зростуть на одиницю. Замінивши в правій частині формули (14) q на q-1 і збільшивши індекси всіх різниць на 1 , отримаємо допоміжну інтерполяційну формулу
(15)
Взявши середнє арифметичне формул (14) і (15), після простих перетворень отримаємо інтерполяційну формулу Бесселя
інтерполяція функція бессель програма
(16)
Інтерполяційна формула Бесселя (16), як слідує з способу отримання її, представляє собою поліном, що співпадає з даною функцією y= f(x) в 2n+2 точках
x-n , x-(n-1),…, xn , xn+1.
В частинному випадку, при n=1, нехтуючи різницею ∆3y-1, отримаємо формулу квадратичної інтерполяції по Бесселю
,
В формулі Бесселя всі члени, які містять різниці непарного порядку, мають множник q-; тому при формула (16) значно спрощується :
Цей спеціальний випадок формули
Приклад розв’язку задачі:
Значення функції подано у табл. 2. Знайти значення .
Таблиця 2- Таблиця різниць функції
| 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 |
Розв’язок:
Приймемо і , тоді
.
Оскільки , то скористаємося формулою Бесселя. Маємо:
;
Звідси, використовуючи підкреслені різниці, отримаєм:
2. Розробка алгоритмів та вибір оптимального алгоритму
При розробці алгоритму обчислення значення функції за допомогою інтерполяційної формули Бесселя будемо використовувати формулу яка описана в теоретичних відомостях.
Аналіз формули та прикладу, наведеного в першому розділі, показує що для обчислення значення функції необхідно обчислити значеня кінцевих різниць а також значеннь q та р. Безпосереднє обчислення за формулою вимагає операцій додавання (віднімання), n - операцій ділення та - операцій множення. З врахуванням того, що час виконання операції множення та ділення відповідно в 1,14 та 2,33 рази більший за час виконання операції додавання (віднімання) при використанні математичного співпроцесора, загальна кількість операцій обчислення складає
Алгоритм можна побудувати таким чином, щоб спочатку обчислити всі всі знаменники поліному, а потім провести обчислення за основною формулою. В цьому випадку необхідно комірок пам’яті.
Інший спосіб побудови алгоритму полягає в тому, щоб проводити обчислення знаменників поліному одночасно з обчисленнями за основною формулою виходячи з факторіалу. В цьому випадку для збереження значень необхідно лише n-1 комірок пам’яті.
Комплексний коефіцієнт ефективності Ке одного алгоритму в порівнянні з іншим можна обчислити за формулою
де Кч – коефіцієнт ефективності за часом виконання;
Кn – коефіцієнт ефективності за затратами пам’яті алгоритму.
Оскільки коефіцієнт ефективності за часом виконання алгоритму можна приблизно оцінити за кількістю арифметичних операцій алгоритму, то комплексний коефіцієнт ефективності описаних вище алгоритмів складає
Для випадку коли n=9
Блок-схеми описаних вище алгоритмів відповідно на рис 2.1 та рис 2.2. В даних алгоритмах вважається, що матриця A використовуються для збереження таблиці різниць, значення x, x0, n, q – однойменні змінні [6].
3
.
Приклад програми обчислення значення
функції за допомогою
інтерполяційної формули Бесселя
3.1 Інструкція користувача
Після виклику Pascal ABC із середовища Windows на екрані з'являється командне вікно середовища Pascal ABC.
Це вікно є основним у Pascal ABC. У ньому відображаються символи команд, що набираються користувачем на клавіатурі, результати виконання цих команд, текст програми, що виконується, а також інформація про помилки виконання програми, яка розпізнана системою.
Ознакою того, що програма Pascal ABC готова до сприйняття і виконання чергової команди, є наявність в останньому рядку текстового поля вікна миготливої вертикальної риски.
У верхній частині командного вікна (безпосередньо під заголовком Pascal ABC) розташований рядок меню, що складається з шести меню –Файл, Правка, Вид, Программа, Сервис, Помощь. Під головним меню розміщена панель інструментів з піктограмами, що дозволяють виконувати деякі найбільше часто використовувані операції.
1. Відкриття меню здійснюється натисненням миші. Щоб вибрати будь-яку команду меню, досить установити курсор на імені команди і натиснути ліву кнопку миші.
2. Текст програми міститься в одному файлі: файл основної програми з іменем kursach.pas. Для відкриття його необхідно вибрати у меню Файл команду Открыть (Відкрити), що відкриває діалогове вікно з переліком PAS- файлів поточної папки.
3. Вибір необхідного файлу з цього списку і наступне натискання кнопки OK приводить до появи вікна Редактора/Налагодження, який дає змогу не тільки коректувати програму, але і проводити її відладку. Запуск програми здійснюється вибором в меню Программа команди Выполнить, або натисненням клавіші F9.
4. В результаті запуску програми з’явиться командне вікно, в якому необхідно ввести коефіцієнти розширеної матриці. По завершенні введення значень в командному вікні буде виведенне значення функції в заданій точці.
3.2 Опис програми
Текст програми міститься у файлі kursach.pas, де описані всі змінні та присвоєні їм певні значення, необхідні для обчислення значення функції інтерполюванням за формулою Бесселя, а також власний процес обчислення методу. З метою ефективного використання пам’яті для збереження початкових значень системи, вони зберігаються в динамічній пам’яті, що дозволяє відводити під них місце динамічного розміру в залежності від кількості заданих даних.
Всі дані оператори утворюють саму основну програму, правила користування якої непотрібно перераховувати ─ вони звичайні (як і в будь-якій програмі), це дозволяє значно спростити користування даною програмою.
Файл містить описи структури методу та функцій, що використовуються основною програмою: опис змінних, введення початкових даних та обчислення таблиці різниць, визначення порядкового номеру х0 та обчислення q та р, обчислення за основною формулою, виведення результатів.
У програмі використовується оператор циклу for.
Сама програма є проста та зрозуміла у користуванні.
3.3 Лістинг програми
program kursach;
uses crt;
var
A:ARRAY [1..30,1..30] OF REAL;
i,i1,N,j,X0,f:longint;
H,x,P,pp,q,p1:REAL;
begin
clrscr;
write('Vvedit pochatkovui element ');
readln(p);
write('Vvedit k-t elementiv ');
readln(n);
write('Vvedit krock ');
readln(h);
for i:=1 to n do
begin
writeln('Vvedit Y[',i,'] v tochci ',p);
a[1,I]:=p; p:=p+h;
readln(A[2,I]);
end;
for i:=1 to n do
for j:=1 to n-i do a[i+2,j]:=a[i+1,j+1]-a[i+1,j];
writeln('Vvedit tochky v iakii bydemo chykatu znachennie fynkcii: ');
readln(X);
for i:=1 to n do if (a[1,i]-X<H) then x0:=i-1;
q:=(X-A[1,x0])/h;
pp:=q-(1/2);p1:=1;
p:=(a[2,x0]+a[2,x0+1])/2+pp*a[3,x0-1];
for i:=1 to n do begin
p1:=p1*(sqr(pp)-(sqr(2*i-1))/4);
f:=1;
for i1:=1 to 2*i do f:=f*i1;
p:=p+(p1/f*(a[2+2*i,n-i+1]+a[2+2*i,n-i+1])/2)+((p*p1)/(f*(2*i+1))*a[2+2*i,n-i+1]);
end;
writeln(p);
readln;
end.
3.4 Тестування програми
На рис. 3.1 подано екранні зображення в ході виконання програми для вихідних даних прикладу, наведеного в теоретичних відомостях.
Рисунок 3.1- Введення початкових значень та даних з таблиці та виведення кінцевого результату.
Висновки
1. Проведено теоретичний аналіз обчислення значення функції за допомогою інтерполяційної формули Бесселя та порівняння з іншими методами, який показав що цей метод є більш точним і простим.
2. Опираючись на теоретичну базу було створенно ефективний алгоритм обчислення значення таблично заданої функції за методом, коефіцієнт ефективності якого в 2,65 разу вищий за другий.
3. Реалізованно програму, написану на мові програмування Турбо Паскаль 7.0, що має зручний та наочний інтерфейс і максимально спрощує роботу.
4. Здійснено тестування програми, яке підтвердило її правильну та коректну роботу.
Перелік посилань
1. Воробьева Г.Н., Данилова А.Н. Практикум по вычислительной математике. – М.: Высш. шк., 1990. - 187 с.
2. Копченова Н.В., Марон И.А. Вычислительная математика в примерах и задачах. – М.: Наука, 1972. – 250 с.
3. Волинець В.І. Конспект лекцій з курсів: Алгоритмічні мови і програмування. Обчислювальна техніка і програмування. - Вінниця, ВДТУ, 1996. – 42 с.
4. Димидович Б.П., Марон И.А. Основы вычеслительной математики.– М.: 1970, – 240с.
5. Волинець В.І., Ревенок В.І. Методичні вказівки до виконання лабораторних робіт з дисциплін: Алгоритмічні мови і програмування. Обчислювальна техніка і програмування. – Вінниця, ВДТУ, 1998. – 56 с.
6. Волинець В.І., Ревенок В.І. Методичні вказівки до виконання практичних та контрольних робіт з дисциплін: Алгоритмічні мови і програмування та Обчислювальна техніка і програмування.– Вінниця, ВДТУ, 1998. – 40 с.
7. Сердюченко В.Я. Розробка алгоритмів та програмування на мові Turbo Pascal. – Х.: Парітет, 1995. – 464 с.