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

 

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

Справедлива така теорема.

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

 

                                                                                  (11)

 

де  [5-14].

 

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

Якщо в ( )-му вузлах інтерполювання функція набуває значень , то значення інтерполяційного многочлена степеня п в точці , що не збігається з вузлами інтерполювання, можна обчислити за формулою

 

  

 

де   і — значення інтерполяційних многочленів ( )-го степеня, обчислених у точці х на попередньому кроці обчислень. Легко впевнитись, що і збігається з інтерполяційним многочленом Лагранжа -го степеня (таблиця 1).

 

Таблиця 1

		Різниця
0					…
1					…
…	…	…	…	…	…	…	…	…	…	…
					…

 

Отже, щоб  обчислити в точці х значення інтерполяційного многочлена -го степеня за схемою Ейткіна, треба в цій точці обчислити значення лінійних, -1 квадратичних, -2 кубічних многочленів і так далі, два многочлени ( -і)-го степеня і, нарешті, один многочлен -го степеня. Всі ці многочлени виражають через визначник 2-го порядку, а це робить обчислення однотипними, циклічними [2,5,10].

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

Для побудови формули Ньютона необхідно ввести поняття кінцевих різниць.

Кінцевими різницями називають різниці  між значеннями функції в сусідніх вузлах (точках ) інтерполяції:

   

    

 

             

 

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

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

Перша інтерполяційна формулу Ньютона (12).

 

       (12)

 

На практиці часто використовують формулу Ньютона  в іншому вигляді. Для цього введемо  заміну , де h - крок інтерполяції, а q - число кроків. Тоді перша інтерполяційна формула Ньютона прийме вигляд (13):    

 

                (13)

 

Формулу (13) зручно використати для інтерполювання на початку відрізку інтерполяції [a; b] , де q мале за абсолютною величиною.

Якщо  за число вузлів інтерполяції прийняти  n-1, то отримаємо формулу лінійного інтерполювання

 

При n=2  отримаємо формулу параболічного, або квадратичного інтерполювання

 

 

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

Часто користуються формулами центральних різниць, до яких відносяться формули Гаусcа, Бесселя, Стірлінга.

Інтерполяційна  формула Гаусса – формула, яка використовує в якості вузлів інтерполяції   найближчі до точки інтерполяції x вузли. Якщо формула написана

за вузлами ,  то вона зветься формулою Гаусса для інтерполяції вперед (14),

 

          (14)

 

а формула написана за вузлами    зветься формулою Гаусса для інтерполяції назад (15).

 

          (15)

В формулах (14) і (15) використані кінцеві різниці, які визначаються в такий спосіб [5]:

   .

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

Часто використовується інтерполяційна формула Бесселя, яка служить для знаходження значення функції у міжвузловій точці. Для виведення цієї формули скористаємось другою інтерполяційною формулою Гаусса (14):

 

        (16)

 

у скороченому  вигляді (17):

 

         (17)

 

де   .

Інтерполяційна формула Бесселя застосовується при інтерполяції функцій для значень х , близьких середині а між двома вузлами, тут природно брати парне число вузлів х _{— до} ..., х _—1 , x ₀ , x ₁ ..., x _до , x _{до + 1} , і розташовувати їх симетрично відносно а (x ₀ < а < x ₁ ).

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

                                                     

де  .

Легко побачити, що  при 

Формула   Стірлінга використовується для інтерполювання в середині таблиці при значеннях q, близьких до нуля. Практично її використовують при │q│≤ 0,25 [12,13,14].

 

 

 

 

 

 

Приклад розв’язування задачі:

 

Побудувати  інтерполяційний многочлен Лагранжа одинадцятого степеня для функції , заданої аналітично:   за такими даними: кроком , на проміжку та знайти значення функції у точці використовуючи формулу (5), розв’язок подано в табл. 2.

 

Розв’язання.

          ,        ,        .

 

Таблиця 2

	0	1	2	3	4	5	6	7	8	9	10
	1	2	3	4	5	6	7	8	9	10	11
	0,16667	0,08334	0,04545	0,02778	0,01852	0,01316	0,009804	0,007576	0,006024	0,004902	0,004065

 

 

 

Знайдемо  інтерполяційний многочлен Лагранжа.

 

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

 

 

Перевіримо вірність результату, для цього скористаємося схемою Горнера.

 

2 РОЗРОБКА АЛГОРИТМІВ ТА ВИБІР  ОПТИМАЛЬНОГО 

АЛГОРИТМУ

 

При розробці алгоритму  обчислення значення функції, яке відповідає заданому значенню аргументу, будемо використовувати формулу (5), що наведена в розділі 1.

Аналіз формули  (5) та прикладу наведеного в першому розділі показує, що для обчислення значення аргументу необхідно 16 операцій додавання, 204 операцій віднімання, 236 операцій множення та 10 операцій ділення.

З врахуванням того, що час виконання операцій множення та ділення відповідно в 1,14 та 2,33 рази більший за час виконання операцій додавання (віднімання) при використанні арифметичного співпроцесора, загальна кількість операцій обчислення значення функції  використовуючи многочлен Лагранжа складає

 

 

Алгоритм можна побудувати таким чином, щоб спочатку перевірити умову, чи не збігається значення аргумента з будь-яким із вузлів . Якщо ця умова не підтвердилась, то проводяться відповідні обчислення, що передбачені у блоках 7-12. В цьому випадку для збереження значень аргументу та функції необхідно 2 комірки пам’яті. Блок-схема першого алгоритму подана на рис. 2.1.

Інший спосіб побудови алгоритму  полягає в тому, що для знаходження  значення аргументу застосована  схема Ейткіна  (рис. 2.2).

Аналіз формули  показує, що для обчислення значення аргументу  необхідно  264 операцій віднімання, 198 операцій множення та 66 операцій ділення

 

 

В даному випадку для  збереження результатів обчислення необхідно також 2 комірки пам’яті.

Комплексний коефіцієнт ефективності одного алгоритму в порівнянні з іншим можна обчислити за формулою:

,

 

де  - коефіцієнт ефективності за часом виконання алгоритму;

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

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

 

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

 

 

Рисунок 2.1 –  Блок-схема першого алгоритму  обчислення значення функції з використанням  інтерполяційного многочлена Лагранжа

 

Рисунок 2.1 –  Продовження

 

 

 

 

 

 

 

Рисунок 2.2 –  Блок-схема другого алгоритму  обчислення значення функції за схемою Ейткіна

 

 

 

 

3 ПРИКЛАД ПРОГРАМИ ІНТЕРПОЛЮВАННЯ ФУНКЦІЇ ЗА ДОПОМОГОЮ ІНТЕРПОЛЯЦІЙНОГО МНОГОЧЛЕННА ЛАГРАНЖА

 

3.1 Інструкція користувача

 

Після виклику C++ із середовища Windows на екрані з'являється командне вікно середовища C++.

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

Ознакою того, що програма C++ готова до сприйняття і виконання чергової команди, є наявність в останньому рядку текстового поля вікна миготливої вертикальної риски.

У верхній частині командного вікна (безпосередньо під заголовком C++) розташований рядок меню, що складається з 11 меню – Файл, Правка, Пошук, Вигляд, Проект, Виконати, Налаштування, Сервіс, CVS, Вікно, Довідка. Під головним меню розміщена панель інструментів з піктограмами, що дозволяють виконувати деякі найбільше часто використовувані операції.