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

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

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

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

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

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

(8)

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

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

(9)

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

(10)

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

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

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

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

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

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

Представимо інтерполяційну функцію (9), що відповідає вузлам , в вигляді

(11)

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

, i = 0, 1, 2, … , n(12)

Частинний випадок відповідає Згідно (12) має виконуватися рівність і з врахуванням цього із (12) випливає, що . В модифікованій формі (13) ці рівності використовуються для обчислення коефіцієнтів , котрі мають бути скінченими і відмінними від нуля. Ці операції складають “нормальну” частину алгоритму, яка називається станом (а). Якщо в деякий момент ( з j = t + 1 ) виявляється, що для всіх де - залишкова інтерполяційна множина, то алгоритм переходить в стан (b); в цьому випадку інтерполяційна функція можливо існує, але вироджена. У всіх інших випадках, що відповідають стану (с) алгоритму, можна впевнено стверджувати, що апроксимація, яка нас цікавить, не існує. Закінчивши побудову сподіваної функції (11), потрібно перевірити, що її знаменник, який знаходиться по формулах (14) , не перетворюється в нуль у вузлах інтерполяції; якщо це не так, то можна показати, що потрібної апроксимації не існує. Відмітимо, що цей алгоритм є надійним в тому розумінні, що якщо апрксимація відповідна початковим даним не існує, то алгоритм відмічає це і дає на виході сигнал про помилку.

Вихідні дані. Визначаємо множину