Числові методи в інформатиці

Постановка задачі інтерполювання. Обчислення значень многочлена Лагранжа. Схема Ейткена.

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

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

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

На відрізку задано N точок що називаються вузлами інтерполяції, і значення деякої функції в цих точках: Потрібно побудувати функцію ( функцію, що інтерполює ), яка б збігалася з у вузлах інтерполяції і наближала її між ними, тобто таку, що Геометрична інтерпретація задачі інтерполяції полягає в тому, що потрібно знайти таку криву певного типу, що проходить через задану систему точок За допомогою цієї кривої можна знайти наближене значення де Задача інтерполяції стає однозначною, якщо замість довільної функції шукати многочлен степеня не вище N, що задовольняє умови

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

Визначення

Нехай маємо n значень xі, кожному з який відповідає своє значення yі. Потрібно знайти таку функцію F, що:

При цьому:

хі називають вузлами інтерполяції

пари (xі, yі) називають точками даних чи базовими точками

різницю між «сусідніми» значеннями xі-xі-1 — кроком

функцію F (x) — функцією, що інтерполює чи інтерполянтом.

Інтерполяцій́ний многочле́н Лагра́нжа — многочлен мінімального степеня, що приймає дані значення у даному наборі точок. Для n + 1 пар чисел , де всі різні, існує єдиний многочлен степеня не більшого від n, для якого .