Міністерствоосвіти і науки України
Вінницькийнаціональний технічний університет
Інститут АЕКСУ
Факультет ФЕЛТ
Кафедра Електроніки
КУРСОВАРОБОТА
Здисципліни “Обчислювальна математика”
Алгоритм та програма знаходження значення функції за допомогою інтерполяційної формулиБесселя
2004
ЗАВДАННЯ
накурсову роботу з дисципліни
“Обчислювальнаматематика”
студентові гр. МП-02ТвердохлібуА.М. пропонується розробити
алгоритм та програму мовоюпрограмування Турбо Паскаль на знаходження значення функції /> за допомогоюінтерполяційної формули Бесселя
Основні вхідні дані:
1. Кількість вузлів табличнозаданої функції – не більше 100.
2. Похибка обчислень – небільше 0,001.
Основні вихідні дані:
1. Пояснювальна записка докурсової роботи.
2. Виконуваний файл програми.
АНОТАЦІЯ
В даній курсовій роботі розробленийефективний алгоритм та програма мовою Турбо Паскаль знаходження значенняфункції за допомогою інтерполяційної формули Бесселя. Розроблений алгоритм єдосить непоганим за розміром пам’яті, необхідної для збереження даних, котрі обчислюються в ході виконанняалгоритму, та за кількістю арифметичних операцій для обчислення за основною формулою.
ВСТУП
Задача знаходження значення функції уміжвузловій точці за допомогою інтерполяційної формули Бесселя має важливезначення при вирішенні як наукових, так і практичних задач, оскільки даєможливість знаходження значення функції у будь-якій точці, в якій це потрібно.В багатьох випадках функція не має аналітичного вигляду, тобто він невідомий, азадана лише декількома точками та значеннями функції в цих точках. Тому дляотримання значення функції в проміжних точках застосовуються інтерполяційнаформули Гауса (1-а та 2-а), інтерполяційна формула Стірлінга та Бесселя.Останні дві формули є похідними від першої та другої інтерполяційних формулГауса. Кожна з цих формул має свої переваги та недоліки, що полягають укількості обчислювальних операцій та в похибці обчислень.
Серед сучасного програмногозабезпечення є багато програм чисельного аналізу, до яких можна віднестивсесвітньо відомі пакети програм MathCad та MatLab. Вони, як правило, маютьзручний інтерфейс та є багатофункціональними. Але їх недоліком є те, що задачічисельного аналізу певного класу (наприклад, знаходження першої похідної)вирішуються за допомогою лише деякого одного методу. Крім того, вони займаютьбагато дискової пам’яті та вимагають певного часу для того, щоб навчитися нимикористуватися. Тому в даній курсовій роботі була поставлена задача розробитипрограму знаходження значення функції у міжвузловій точці за допомогоюінтерполяційної формули Бесселя, яка займала б небагато пам’яті та була бпростою у користуванні.
Курсова робота складається з трьохосновних розділів. В першому розділі наведені основні теоретичні відомості прометод знаходження значення функції у міжвузловій точці за допомогоюінтерполяційної формули Бесселя та приклад його застосування. У другому розділірозроблено алгоритм за даним методом. Третій розділ містить загальний описпрограми, лістинг програми та результати тестування.
ТЕХНІЧНЕЗАВДАННЯ
1.Основою для проведення роботи єнавчальний план кафедри Електроніки ВНТУ.
Замовник — кафедра ЕлектронікиВНТУ.
Виконавець – студент гр… МП – 02 ТвердохлібА.М.
2. Мета роботи.
Метою роботи є розробка ефективногоалгоритму та програми мовою Турбо Паскаль знаходження значення функції задопомогою інтерполяційної формули Бесселя.
3. Етапи виконання роботи.Зміст
Строки
виконання Чим закінчується етап
1.Отримання і узгодження завдання
Розробка ТЗ 2–й тиждень Технічне завданя 2.Розробка методу рішення 5–й тиждень Теоретичні відомості про метод, порівняльний аналіз, приклади застосування 3.Алгоритмізація 8–й тиждень Блок-схеми алгоритмів та їх порівняльний аналіз 4.Розробка і налагодження програми 12–й тиждень Опис, текст та результати тестування програми 5.Розробка документації на курсову роботу 15–й тиждень Пояснювальна записка(ПЗ) до курсової роботи 6.Захист курсової роботи 16–й тиждень ПЗ та виконуваний файл програми
4.1 Кількість вузлів таблично заданоїфункції – не більше 100.
4.2 Похибка обчислень – не більше0,001.
4.3 Алгоритм повинен бутиоптимізований за часом виконання та розміром.
4.4 Програма повинна бути розробленаза принципами структурного та модульного програмування.
5. Спосіб реалізації результатів.
Робота повинна закінчуватисьпередачею замовнику пояснювальної записки до курсової роботи та виконуваногофайла програми.
6. Техніко економічне обґрунтування.
В результаті виконання роботипланується розробити ефективний алгоритм та програму знаходження значенняфункції за допомогою інтерполяційної формули Бесселя з мінімальним часомвиконання та розміром.
7. Порядок розгляду і прийманняроботи:
7.1 Курсова робота приймається комісієюв складі двох викладачів за участю керівника роботи.
7.2 Програма перевіряється шляхомтестування на комп’ютері тестових завдань, розроблених замовником і виконавцемроботи.
8. Додаткові відомості.
Дане ТЗ може змінюватись ікорегуватись за спільною домовленістю замовника та виконавця.
ТЕОРЕТИЧНІ ВІДОМОСТІ. ІНТЕРПОЛяція ФУНКЦІЙ1. ПОСТАНОВКА ЗАДАЧІ ІНТЕРПОЛЯЦІЇ
Нехай деяка функція у=f(х)задана таблицею (табл.1), тобто при значеннях аргументу х=х0, х1,…, хn функція f(х)приймає відповідні значення
у0, у1,…, уn.
Таблиця 1Таблиця експериментальних значень
x
x0
x1
x2 ....
xn
y
y0
y1
y2 ....
yn
Також нехай необхідно визначитизначення у=f(х), (хi-1 потрапляє між двоматабличними значеннями, тому для обчислення значення функції необхіднозапропонувати деякий характер її зміни між відомими експериментальними даними.
Інтерполяцію можна розглядати якпроцес визначення для даного аргументу х значення функції у=f(х)по її декількох відомих значеннях. Прицьому розрізняють інтерполяцію у вузькому смислі, коли хзнаходиться між x0 і xn, і екстраполювання,коли х знаходиться поза відрізком інтерполяції [x0 ,xn].
Задача інтерполяції полягає внаступному. На відрізку [а, b] задані n+1 точки х0, х1,…, хn, що називаються вузлами інтерполяції, і значеннядеякої функції f(x) у цих точках.
f(x0) = y0;
f(x1) = y1;(1)
f(xn) = yn
Потрібно побудувати функцію Рn(х)(інтерполюючу функцію), яка б задовольняла таким умовам:
Pn(x0) = y0;
Pn(x1) = y1;(2)
Pn(xn) = yn
тобто інтерполююча функціяРn(х)повинна приймати ті ж значення, що і функція f(х), яку ми визначаємо (щоінтерпелюється), для вузлових значень аргументу х0, х1,…, хn.
Геометрично це означає, що потрібнознайти криву y=Pn(х) деякого визначеного типу, що проходитьчерез задану систему точок Мi (хi, уi) (i=0,1,2,..,n).Очевидно, можна побудувати множину неперервних функцій, що будуть проходитичерез задані вузлові точки.[1]
Заміна функції f(х) її інтерполяційним багаточленом Рn(x) може знадобитися не тількитоді, коли відома лише таблиця її значень, але і коли аналітичний вираз для f(х)відомо, проте є занадто складним і незручним для подальших математичнихперетворень (наприклад, для інтегрування, диференціювання та ін.). Інодірозглядаються задачі тригонометричної інтерполяції (інтерполююча функція –тригонометричний поліном). Інтерполюючою може бути також раціональна функція.
У загалі залежність, якоїпідпорядковується функція, може бути апроксимована багаточленом ступеня n:
Рn(x) = y = a0+ a1 ∙ x + a2 ∙ x2 +… + an∙ xn. (3)
Таку задачуназивають задачею параболічної інтерполяції (або інтерполюванням).
Загалом єбагато інтерполяційних формул та методів. До них відносяться такі: інтерполяційніформули Гауса (дві), Стерлінга та Бесселя (які є похідними від формул Гауса),Ньютона (дві) та багато інших.
2. ПАРАБОЛІЧНАІНТЕРПОЛЯЦІЯ
Для визначення коефіцієнтівбагаточлена (3) необхідно мати n+1 вузлову точку. Аналітичне визначеннякоефіцієнтів інтерполяційного багаточлена для n+1точки зводиться дорішення системи лінійних рівнянь n+1 порядку, кожне з яких являє собою вираз (3),записаний для визначеної вузлової точки
yi = a0+ a1 ∙ xi + a2 ∙ xi2+… + an ∙ xin,(4)
де i = 1, 2,… n+1.
Даним методом побудовиінтерполяційного поліному зручно користуватися, маючи персональний комп’ютер івідповідні програми. Даний метод не є єдиним способом побудови інтерполяційногополіному. Інший підхід, яким часто користуються на практиці, називаєтьсяметодом Лагранжа.[2]
3.МЕТОД ЛАГРАНЖА
Нехай при х=х0, х1,…, хnфункція f(х)приймає відповіднозначення у0, у1,…, уn. Багаточленступеня не вище n, що приймає у вузлових точках задані значення, маєвид:
Рn(х)=у=/>. (5)
Цей багаточлен (5) називаєтьсяінтерполяційною формулою Лагранжа і має такі властивості:
1. Призаданій сукупності вузлових точок будова багаточлена можлива тільки єдинимспособом.
2. БагаточленЛагранжа може бути побудовано при будь-якому розташуванні вузлів інтерполяції(включаючи і нерівномірне).
У розгорнутому виді форма Лагранжамає вид:
Рn(х)= /> +
+/>+
+ … + /> +
+ … + />.(6)
При n=1 формула Лагранжа маєвид:
Р(х) =/>(7)
і називається формулою лінійноїінтерполяції.
При n=2 одержимо формулуквадратичної інтерполяції:
Р(х)=/>. (8)
4. ЗВОРОТНА ІНТЕРПОЛЯЦІЯ
Нехай функціяу=f(х)задана таблицею. Задача зворотної інтерполяції полягає в тому, щоб по заданомузначенню функції у визначити відповідне значення аргументу х.
Якщо вузлиінтерполяції x0, x1, x2, … xnнерівновіддалені, задача легко вирішується задопомогою інтерполяційної формули Лагранжа (5). Для цього достатньо прийняти у занезалежну змінну, а х вважати функцією. Тоді отримаємо
x = />(9)
Розглянемо теперзадачу зворотної інтерполяції для випадку рівновіддалених вузлів інтерполяції.Припустимо, що функція f(х) монотонна і дане значення узнаходиться між y0=f(x0) і y1 = f(x1).
Замінюючи функціюу=f(x) першим інтерполяційним багаточленомНьютона, одержимо:
y = y0+ q Dy0+ />D2y0 + />D3y0 +…+ />Dny0 .
Звідси
q = />D2y0 /> – …–Dny0 />,
тобто q=j(q).
Розмір qвизначаємо методом послідовних наближень як границю послідовності:
q = />,
де qi= j (qi–1) (i=1, 2,…).
За початковенаближення приймаємо
q0 =/> (10)
Для i-гонаближення маємо:/>
qi= q0– D2y0/> – …–Dny0 />. (11)
На практиціітераційний процес продовжують доти, поки не установляться значення, щовідповідають необхідній точності, причому q » />qm, де m –останнє зі знайдених наближень. Знайдемо q,визначаємо х по формулі
/> = q,
звідки
х= x0+ q h.(12)
Ми застосувалиметод ітерації для рішення задачі зворотної інтерполяції, користуючись першою інтерполяційною формулою Ньютона. Аналогічно можназастосувати цей спосіб і до другої формули Ньютона:
y = yn+ qDyn–1 + />D2yn–2 + />D3 yn–3 + …
+ />Dny0 .
Звідси
q = />D2yn-2/> – …–Dny0 />...
Позначимо q0= /> – початкове наближення.
Для i-гонаближення маємо:
qi =q0–D2yn–2/> – …–Dny0 />... (13)
Знайдемо
q = />,
визначимо х по формулі
х = xn+ q h .[3], [2]
Далірозглянемо запропоновану мені інтерполяційну формулу Бесселя, яка частовикористовується для знаходження значення функції у між вузловій точці. Вонаподібна до інтерполяційної формули Стерлінга і обидві вони є похідними відпершої та другої інтерполяційних формул Гауса.
ІНТЕРПОЛЯЦІЙНАФОРМУЛА БЕССЕЛЯ
Часто використовується інтерполяційнаформула Бесселя. Для виведення цієї формули скористаємось другоюінтерполяційною формулою Гауса:
/>
у скороченому вигляді:
/>
де х=х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),будемо мати:
/> (1)
Приймемо тепер за початкові значеннях=х1 і у=у1 і використаємо вузли х1+к(к=0, />1,...,/>n). Тоді
/>
причому відповідно індекси всіхрізниць в правій частині формули (1) зростуть на одиницю. Замінивши в правійчастині формули (1) q на q-1 і збільшивши індекси всіх різниць на1, отримаємо допоміжну інтерполяційну формулу
/> (2)
Взявши середнє арифметичне формул (1)і (2), після простих перетворень отримаємо інтерполяційну формулу Бесселя
/> (3)
де />
Інтерполяційна формула Бесселя (3),як слідує з способа отримання її, представляє собою поліном, що співпадає зданою функцією y= f(x) в 2n+2 точках
x-n, x-(n-1),…,xn, xn+1.
В частинному випадку, при n=1,нехтуючи різницею ∆3y-1, отримаємо формулуквадратичної інтерполяції по Бесселю
P(x)=/>
Або
/>
де
/>
В формулі Бесселя всі члени, якімістять різниці непарного порядку, мають множник q-/>; тому при /> формула (3) значноспрощується :
/>
Цей спеціальний випадок формулиБесселя називається формулою інтерполювання на середину. Якщо вформулі Бесселя (3) зробити заміну по формулі />
то вона приймає більш симетричний вид
/>
де />
ЗАГАЛЬНИЙОПИС ПРОГРАМИ
В програмі використано кількапроцедур та функцій, в яких використовуються різноманітні позначення, змінні татому подібне. Тому далі буде дано пояснення (розшифровування) що яким символом,чи їх сукупністю позначено.
PROCEDURE vvod – процедура введення даних, тобтозадання початкових умов (кількість вузлів, задаються X та відповідні їм Y, а також X, в яких потрібно знайти значенняф-ї).
PROCEDURE ddd –дана процедура формує трикутнутаблицю різниць значень
ф-ї.
PROCEDURE rech- процедура рішення задачі заінтерполяційною формулою Бесселя.
PROCEDURE vivod- це процедура виведення результатівроботи програми, які виводяться файлі f2, який має назву «ANA.NAS».
FUNCTION pos1 (j, q: real): real; — функція, яка обчислює для формулиБесселя чисельник її доданків.
FUNCTION fak (j: integer): real; — функція для обрахунку факторіалав знаменнику доданків формули.
Також в програмі використовуютьсятакі позначення:
kol- позначено кількість точок (вузлів),в яких потрібно знайти значення функції.
zad- назва масива, в який заносимо ікси,значення функції в яких бажаємо знайти.
otv- назва масива для відповіднихігреків.
f1- це файл, який має назву «st1.tab», з нього читаються задані ікси таігреки.
f2- файл, який має назву «ana.nas», — це файл виведення, з ньогочитаються результати роботи програми.
n- кількість вузлів інтерполяції.
h- крок задання точок.
Література
1. Вычислительнаятехника в инженерных и экономических расчетах
/ А.В.Крушевский, А.В.Беликов, В.Д.Тищенко– Киев: «Высшая школа». Главное изд-во, 1985. – 290 с.
2. Дифференциальноеи интегральное исчисления /Н.С.Пискунов- Москва: «Наука». Главная редакцияфизико-математической литературы, 1978.-576 с.
3.Численыеметоды в инженерных исследованиях /В.Е.Краскевич, К.Х.Зеленский, В.И.Гречко — Киев: Главное изд-во «Высшая школа», 1986.-263 с.