Реферат: Модифікований алгоритм Течера-Тьюкі
формується з за правилом Крамера.
Означення 5. Система функцій , i=0,1,…,n називається системою Чебишова порядка n, якщо узагальнений многочлен
,
який має більше ніж n коренів на , тотожньо рівний нулеві, тобто для всіх і=0,1,…,n.
Теорема 1. Для того, щоб для довільної функції існував узагальнений інтерполяційний многочлен для будь-якого набору вузлів , і=0,1,…, n , необхідно і досить, щоб була системою функцій Чебишова на . При виконанні цих умов узагальнений інтерполяційний многочлен буде єдиним.
Відомо, що всі три вище наведені сукупності функцій є системами функцій Чебишова на довільному .
Якщо визначник (4) розвити за і-м стовпчиком, то (3) перепишеться у вигляді
де , i,k=0,1,…,n – відповідні алгебраїчні доповнення, і тоді
Якщо згрупувати подібні члени при однакових значеннях, то отримаємо
(5)
Зауваження 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-алгоритма розв¢язує проблему значень для апроксимацій Паде, оскільки він не зв¢язаний з проміжковим обчисленням коефіцієнтів. Описаний нижче модифікований алгоритм Течера-Тьюкі, котрий представляє раціональну апроксимацію в вигляді неперервного дробу, дає вирішення проблеми коефіцієнтів. Якщо потрібно знайти деяку таблицю значень інтерполюючої раціональної функції, то часто вигідніше розв¢язати спочатку проблему коефіцієнтів і потім обчислювати значення апроксимації в різних точках. Якщо потрібно обчислити одне значення, то іноді зручніше не звертатися до проміжкової задачі обчислення коефіцієнтів. Та на практиці обчислення поліномів і неперервних дробів є доволі швидкою процедурою і тому проблема коефіцієнтів особливо важлива. Відмітимо, що представлення інтерполюючої функції в виді неперервного дробу підвищує ефективність обчислень у порівнянні з використанням поліноміальних відношень, які характерні для апроксимацій Паде.