Алгоритм та програма інтерполювання функції при рівномірному розміщенні вузлів за допомогою інтерполяційного многочлена Лагранжа

 

 

ЗМІСТ

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

АНОТАЦІЯ

 

Об’єктом дослідження  є інтерполяційний многочлен  Лагранжа для інтерполювання функцій. Розроблено оптимальний алгоритм та програму в середовищі системи C++ як за розміром пам'яті, необхідної для збереження даних, котрі обчислюються в ході виконаного алгоритму, так і за кількістю арифметичних операцій для обчислення за основною формулою. Програма має зручний та наочний інтерфейс, котрий максимально спрощує роботу з нею, та автоматичну перевірку коректності даних, що вводяться.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВСТУП

Актуальність теми.

На практиці часто виникає задача  відшукання функції за заданим значенням аргументу. Цю задачу вирішують методами інтерполяції функції. Є декілька прийомів розв’язку такої задачі, а саме: користуючись схемою Ейткіна, за допомого першої та другої формул Ньютона, а також за допомогою формул Гаусса, Стірлінга, Бесселя, але найпростішим є застосування інтерполяційної формули Лагранжа. Формула Лагранжа є досить  зручна і використовується не лише у випадку рівновіддалених вузлів, але й у випадку вузлів інтерполяції, заданих довільно, що дає можливість широкого її застосування у порівняні з іншими формулами інтерполювання.

 

Мета дослідження.

Метою роботи є дослідження можливості використання інтерполяційного многочлена Лагранжа  для інтерполювання функцій.

 

Задача дослідження:

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

 

Об’єкт дослідження. Об’єктом дослідження є многочлен Лагранжа для інтерполювання функції.

 

Структура курсової роботи.

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

 

 

 

 

 

1 АНАЛІЗ ТЕОРЕТИЧНОЇ  БАЗИ МЕТОДІВ  ІНТЕРПОЛЮВАННЯ ФУНКЦІЇ

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

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

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

Нехай на відрізку визначено певний клас функцій , наприклад клас алгебраїчних многочленів, а в точках цього проміжку задано значення деякої функції . Наближену заміну функції на відрізку однією з функцій цього класу так, щоб функція в точках набувала тих самих значень, що й функція , тобто щоб , називають інтерполюванням, або інтерполяцією. Точки називають вузлами інтерполювання, функцію — інтерполюючою функцією, а формулу , за допомогою якої обчислюють значення функції у проміжку , — інтерполяційною формулою [3].

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

                                    y

                        y=P_n(x)

 

                        y=F(x)

 

                                     

                                       y₀

 

 

    x

                                 0      a=x₀      x₁    x₂ x_k     x_k+1  b=x_n 

Рисунок 1 – Геометрична інтерпретація інтерполювання функції

 

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

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

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

 

 ,                                        (1)

 

степеня , який задовольняв би умови

 

   ,                                                    (2)    

 

Для визначення  коефіцієнтів многочлена (1), який задовольняє умови (2), запишемо систему -го лінійних рівнянь вигляду [4]:

 

Ця система  має єдиний розв'язок, бо її визначник  є визначником Вандермонда, який не дорівнює нулю, бо вузли різні. А тому й задача параболічного інтерполювання має єдиний розв'язок, тобто існує єдиний алгебраїчний многочлен виду (1.1), що задовольняє умови (2). Многочлен , який задовольняє умови (2), називають інтерполяційним многочленом, наближену рівність – інтерполяційною формулою, а різницю – залишковим членом інтерполяційної формули. Хоч інтерполяційний многочлен, що задовольняє умови (2), і єдиний, проте можливі різні форми його запису.

Інтерполяційний многочлен будують тоді, коли:

1)  функцію  задано таблично для деяких значень аргументу, а треба знайти її значення для значень аргументу, яких у таблиці немає;

2)  функцію  задано графічно, наприклад за  допомогою самописного приладу,  а треба знайти її наближений  аналітичний вираз;

3)  функцію  задано аналітично, але її вираз  досить складний і незручний для виконання різних математичних операцій (диференціювання, інтегрування тощо) [5].

Тоді  залежно від вибору критерію згоди й, зокрема, від кількості, точок узгодження і (будемо називати їхніми вузлами),  тобто точок, у яких відома інформація про і, можливо, її похідних, можна розглянути різні конкретні способи   інтерполяції.  А саме, у даному розділі буде  досить докладно розглядатися класична лагранжева  інтерполяція, що служить основою багатьох    чисельних методів, зокрема, наближеного диференціювання і інтегрування. Також отримаємо знання про інтерполяційну схему Ейткіна, окремими випадками якого є, з одного боку, многочлен Тейлора (при ), з іншого боку - многочлен Лагранжа (при )  [2].

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

 

                                     .                                               (3)

 

Шукатимемо  інтерполяційний многочлен  у такому вигляді:

 

            (4)

 

де коефіцієнти  невідомі. Кожний доданок виразу (4) є многочленом степеня , причому при кожному з коефіцієнтів множника немає.

Визначимо коефіцієнти  , використавши умову (3). Поклавши в (4) , дістанемо

 

звідки

 

 

Якщо в (4) покласти , то

 

 

а отже

 

 

Аналогічно  обчислюємо

 

 

Підставивши  ці значення коефіцієнтів в (4), дістанемо вираз інтерполяційного многочлена

 

                       (5)

 

Многочлен виду (5) називають інтерполяційним многочленом Лагранжа, а наближену рівність

 

                                                                                                          (6)

– інтерполяційною формулою Лагранжа.

Інтерполяційний многочлен Лагранжа можна записати компактніше. Для цього введемо  многочлен  -го степеня вигляду

 

                                                                (7)

 

Продиференціювавши по цей добуток, дістанемо:

 

Поклавши тут  , матимемо

 

                                 (8)

 

Підставивши (7) і (8) в (5), знайдемо

 

                                                                     (9)

Вирази  , ,  що є коефіцієнтами при у многочлені Лагранжа, називають коефіцієнтами Лагранжа.

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

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

 

                                                                                (10)