Модифікований алгоритм Течера-Тьюкі, Детальна інформація

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

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

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

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

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

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

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

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

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



(8)



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



, представляється в вигляді

(9)

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

(10)

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



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



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



і отже є (n+1)-точковою апроксимацією.

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

(5. Модифікований алгоритм Течера-Тьюкі.

, в вигляді

(11)