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

при .

Ітерація. Ітерації по параметру 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. Результати і висновки.

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

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