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

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

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

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

(11)

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

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

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

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

і значення функції

при .

Ітерація. Ітерації по параметру j=1, 2, … починаються із стану (а) і в невиродженому випадку проводяться до кінця. У випадку виродженості відбувається перехід до стану (b) або (c).

Стан (а). Вибираємо, якщо це можливо, так, що і далі вважаємо

(13)

,

Якщо j=n, вважаємо t=n і переходимо до закінчення; інакше повторюємо ітерацію з j:=j+1.

Якщо вибір з умовою неможливий, то переходимо в стан (b).

Стан (b). Якщо при всіх , то параметру t присвоюється значення j-1 у відповідності з поточним значенням j і відбувається перехід до закінчення для перевірки знаменника.

Стан (с). Перехід в цей стан відбувається тоді і тільки тоді, коли при всіх , але при деякому . В стані (с) процедура алгоритму зупиняється і подається сигнал похибки, який означає, що потрібна інтерполяція не може бути здійснена.

Закінчення. Якщо перехід до закінчення відбувся при t=0, то - потрібна нам апроксимація. Якщо перехід відбувся при t=1,2,…,n, то вважаємо

, (14)

при i= 2, 3, … , t-1. Якщо при всіх , то отриманий результат є коректним. В противному випадку, коли при деякому j , , отриманий результат є некоректним і дається сигнал, що потрібна нам апроксимація не існує.

§6. Результати і висновки.

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