Програма, яка реалізує методи Течера-Тьюкі та Тіле раціональної інтерполяції функції

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

З (2) випливає, що

(6)

§2. Інтерполяційний многочлен у формі Лагранжа

За візьмемо систему функцій {1,x,x2,…, xn,…}. На довільному відрізку при фіксованому n функції 1,x,x2,…, xn є лінійно незалежні і визначник є визначником Вандермонда. А так як за припущенням xi ¹ xj, то

Із (5) та (6) випливає, що - многочлен n-го степеня, який перетворюється в нуль в точках в x0, x1,…, xi-1, xi+1,…, xn і рівний 1 в точці x0, тобто

і

.

Звідки маємо:

Підставивши значення Фі(х) в (5) отримаємо інтерполяційний многочлен у формі Лагранжа

Отримаємо тепер формулу для залишкового члена інтерполяційного многочлена у виді Лагранжа.

Теорема 2. Нехай f(x) Î C(n) [a,b] і існує f(n+1) (x). Тоді для довільного х Î [a,b] має місце наступна форма залишкового члена

(7)

де

Зауваження 2. З формули залишкового члена (7) випливає, що інтерполяційний многочлен у формі Лагранжа є точним для многочленів степеня n.

§3. Вимоги до обчислювальних алгоритмів

Наведені вище формули, що визначають N-точкову апроксимацію, громіздкі і мало придатні для розв¢язування обчислювальних задач. Визначимо коротко ті вимоги, котрі ставляться перед обчислювальним алгоритмом. Чисельні алгоритми для раціональних апроксимацій можна поділити на ті, за допомогою яких розв¢язують проблему коефіцієнтів і ті, за допомогою яких розв¢язують проблему значень. Проблема коефіцієнтів полягає у визначенні значень коефіцієнтів на підставі яких формується інтерполяційна функція. Проблема значень полягає в обчисленні значення інтерполяційної функції у вказаній наперед точці z, коли не потрібні проміжкові обчислення коефіцієнтів. Наприклад, метод відомий під назвою e-алгоритма розв¢язує проблему значень для апроксимацій Паде, оскільки він не зв¢язаний з проміжковим обчисленням коефіцієнтів. Описаний нижче модифікований алгоритм Течера-Тьюкі, котрий представляє раціональну апроксимацію в вигляді неперервного дробу, дає вирішення проблеми коефіцієнтів. Якщо потрібно знайти деяку таблицю значень інтерполюючої раціональної функції, то часто вигідніше розв¢язати спочатку проблему коефіцієнтів і потім обчислювати значення апроксимації в різних точках. Якщо потрібно обчислити одне значення, то іноді зручніше не звертатися до проміжкової задачі обчислення коефіцієнтів. Та на практиці обчислення поліномів і неперервних дробів є доволі швидкою процедурою і тому проблема коефіцієнтів особливо важлива. Відмітимо, що представлення інтерполюючої функції в виді неперервного дробу підвищує ефективність обчислень у порівнянні з використанням поліноміальних відношень, які характерні для апроксимацій Паде.

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

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

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

Розглянемо деякі алгоритми, які є найкращими серед існуючих.

§4. Метод обернених різниць Тіле.

Цей метод дає представлення N-точкової апроксимації Паде в виді неперервного дробу. В основному варіанті алгоритму вузли інтерполяції мають бути різні; елементи дробу, що відповідають випадку кратних вузлів, можуть бути отримані по неперервності. Обернені різниці визначаються наступними рівностями:

(8)

і в загальному випадку (для n>1)

Інтерполяційна функція, що відповідає вузлам , представляється в вигляді

(9)

Перевірка. Доведемо спочатку за індукцією наступну тотожність:

(10)

При n=0 відношення (10) має вигляд

це еквівалентно (8). При n>0 перетворимо останній знаменник (10) за допомогою тотожності:

яка після простих перетворень приймає вигляд

еквівалентний (8). Цим тотожність (10) доведена. Покладаючи в (10) послідовно , впевнюємося, що при відсутності випадкових скорочень дробів функція (9) інтерполює потрібні значення в n+1 вузлах і отже є (n+1)-точковою апроксимацією.