Інтерполяційна схема Ейткена

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

Нехай дано дві точки на кривій : і . Побудуємо функцію :

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

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

Якщо на кривій  задані три точки ,  та , то, використовуючи введені лінійні функції  і , утворюємо нову функцію:

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

Продовжуючи даний процес далі, отримаємо послідовність інтерполяційних многочленів Лагранжа, яка становить суть інтерполяційної схеми Ейткена:

Схема Ейткена легко реалізується на ЕОМ. Організація обчислень за формулою (1) повинна бути така, що якщо заздалегідь невідома степінь інтерполяційного многочлена, який потрібно використовувати для обчислення , то має відбуватися поступове підвищення степені інтерполяційних многочленів за рахунок підключення нових вузлів. Рахунок ведеться до тих пір, поки йде уточнення наближеного значення , тобто поки величина спадає. Також відмітимо, що обчислювальний процес інтерполяційної схеми Ейткена зазвичай оформляється у вигляді наступної таблиці:

Інтерполяція функції використовуючи схему Ейткена — приклад:

Нехай деяка функція  задана таблицею своїх значень:

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

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

Блок-схема алгоритму інтерполяції табличної функції використовуючи схему Ейткена