Метод апроксимації функції
Постановка задачі інтерполяції функції. Інтерполяційний многочлен у формулі Лагранжа. Вимоги до обчислювальних алгоритмів. Метод обернених різниць Тіле. Аналіз модифікованого алгоритму Течера-Тьюкі на предмет його використання в обчислювальних задачах.
Рубрика | Математика |
Вид | практическая работа |
Язык | украинский |
Дата добавления | 16.11.2009 |
Размер файла | 81,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Вступ
Однією із задач, які розвязує сучасна обчислювальна математика, є проблема наближення функції однієї змінної та багатьох дійсних змінних іншими функціями більш простої, взагалі кажучи будови, які легко обчислюються на електронно-обчислювальних машинах. Інша назва цієї задачі - апроксимування функції. Ця задача може постати, наприклад, у випадку, коли або функція задана своїми значеннями у вигляді таблиці результатів експерименту, або коли функція має складну аналітичну будову і знаходження її значення у деяких точках викликає обчислювальні труднощі. Так, зокрема, всі широко вживані на практиці функції sin(x), cos(x), exp(x), ln(x), ch(x), sh(x) та багато інших визначаються при обчисленнях на ЕОМ за допомогою функціональних рядів або ланцюгових дробів.
В останні роки різко зріс інтерес до класичних методів раціональної апроксимації функцій. Це повязано з тим, що такі апроксимації знайшли різноманітне застосування в обчислювальних задачах теоретичної фізики та механіки. Потрібно відмітити також, що останнім часом ми стаємо свідками позитивної тенденції, згідно якої сучасні математичні дослідження все більше і більше ініціюються найбільш передовими фізичними теоріями та прикладними обчислювальними задачами, серед яких і спроби обєднати слабкі, електромагнітні, сильні та гравітаційні взаємодії у фізиці і проблеми ефективної компресії аудіо-візуальної інформації на підставі аналізу спектра сигналу в обчислювальній математиці та ще багато інших не менш цікавих задач.
В даній науково-дослідній роботі зроблена спроба аналізу одного з прикладних методів апроксимації функції - метода Течера-Тьюкі на предмет його придатності до використання в обчислювальних задачах та наявність переваг перед іншими методами.
1. Постановка задачі інтерполяції функції
Нехай дійсна функція f(x) неперервна на проміжку [a,b] та визначена своїми значеннями в точках множини
Х={x0, x1, … , xn}, де Х [a,b].
Потрібно знайти значення функції в точці х, яка відмінна від заданих. Виходячи з деяких додаткових міркувань, наближаючу функцію будемо шукати у вигляді
f(x) g(x, ) , де - деякі параметри.
Означення 1. Якщо параметри визначаються з умови рівності значень
, i = 0,1,…,n
то точки називаються вузлами інтерполяції, а такий спосіб наближення функції називається інтерполяцією або інтерполюванням.
Означення 2. У випадку, коли апроксимуючу функцію вибирають у вигляді лінійної комбінації функцій із заданої сукупності, тобто
(1)
то говорять про лінійну інтерполяцію, а функцію називають узагальненим інтерполяційним многочленом.
Означення 3. Якщо апроксимуюча функція не може бути подана у вигляді (1), то таке наближення називається нелінійною інтерполяцією.
Означення 4. Величина
називається залишковим членом узагальненого інтерполяційного многочлена.
Надалі будемо вважати, що та , коли ij, тобто розглядається така задача інтерполяції, коли всі вузли різні.
Виберемо в - просторі неперервних на функцій, скінчену або злічену сукупність функцій , таких, що довільна скінчена система їх є лінійно незалежною. На практиці найчастіше використовують такі системи функцій:
, , ,
де - деяка числова послідовність.
Коефіцієнти в (1) визначимо з умови, що наближуючий агрегат збігається у вузлах інтерполяції із значенням функції, тобто
, i=0,1,…,n(2)
З (1) та (2) випливає, що для знаходження коефіцієнтів отримуємо систему лінійних алгебраїчних рівнянь
і якщо
то при довільних значеннях , i=0,1,…,n система має єдиний розвязок
, (3), де
(4)
формується з за правилом Крамера.
Означення 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). Тоді для довільного х [,] має місце наступна форма залишкового члена
(7)
де
Зауваження 2. З формули залишкового члена (7) випливає, що інтерполяційний многочлен у формі Лагранжа є точним для многочленів степеня n.
3. Вимоги до обчислювальних алгоритмів
Наведені вище формули, що визначають N-точкову апроксимацію, громіздкі і мало придатні для розвязування обчислювальних задач. Визначимо коротко ті вимоги, котрі ставляться перед обчислювальним алгоритмом. Чисельні алгоритми для раціональних апроксимацій можна поділити на ті, за допомогою яких розвязують проблему коефіцієнтів і ті, за допомогою яких розвязують проблему значень. Проблема коефіцієнтів полягає у визначенні значень коефіцієнтів на підставі яких формується інтерполяційна функція. Проблема значень полягає в обчисленні значення інтерполяційної функції у вказаній наперед точці z, коли не потрібні проміжкові обчислення коефіцієнтів. Наприклад, метод відомий під назвою -алгоритма розвязує проблему значень для апроксимацій Паде, оскільки він не звязаний з проміжковим обчисленням коефіцієнтів. Описаний нижче модифікований алгоритм Течера-Тьюкі, котрий представляє раціональну апроксимацію в вигляді неперервного дробу, дає вирішення проблеми коефіцієнтів. Якщо потрібно знайти деяку таблицю значень інтерполюючої раціональної функції, то часто вигідніше розвязати спочатку проблему коефіцієнтів і потім обчислювати значення апроксимації в різних точках. Якщо потрібно обчислити одне значення, то іноді зручніше не звертатися до проміжкової задачі обчислення коефіцієнтів. Та на практиці обчислення поліномів і неперервних дробів є доволі швидкою процедурою і тому проблема коефіцієнтів особливо важлива. Відмітимо, що представлення інтерполюючої функції в виді неперервного дробу підвищує ефективність обчислень у порівнянні з використанням поліноміальних відношень, які характерні для апроксимацій Паде.
Важливо і бажано, щоб застосовувані методи коректно працювали у випадку наявності кратних вузлів інтерполяції. Іншою бажаною ознакою чисельних методів раціональної апроксимації є надійність. Не завжди існує раціональна функція певного виду, що задовольняє накладеним умовам інтерполяції. Надійний метод апроксимації має вказати, що задача не має розвязку. Чисельний алгоритм повинен розрізняти задачі що мають і не мають розвязків з врахуванням помилок представлення та округлення. Аналіз цього питання приводить нас до поняття стійкості алгоритму, яке тісно звязане з поняттям надійності. Алгоритм стійкий, якщо малі зміни початкових даних приводять до невеликих змін результату. Хороший алгоритм раціональної інтерполяції повинен бути в змозі виділити ті випадки, коли початкові дані приводять до нестійкого результату.
Відмітимо, що рекурентні методи знаходження інтерполюючої раціональної функції можуть бути звязані з припущенням, що існують проміжкові апроксимації. У випадку існування потрібної інтерполяції надійний алгоритм повинен спрацьовувати навіть у випадку, коли деякі проміжкові апроксимації вироджені або не існують.
Всі ці якісні характеристики хорошого алгоритма навряд чи є повністю сумісними, тому вибір “найкращого” зумовлює наявність тих чи інших компромісів. В будь-якому випадку для практичного застосування нам потрібен алгоритм ефективний, надійний і стійкий.
Розглянемо деякі алгоритми, які є найкращими серед існуючих.
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) , не перетворюється в нуль у вузлах інтерполяції; якщо це не так, то можна показати, що потрібної апроксимації не існує. Відмітимо, що цей алгоритм є надійним в тому розумінні, що якщо апрксимація відповідна початковим даним не існує, то алгоритм відмічає це і дає на виході сигнал про помилку.
Вихідні дані. Визначаємо множину
і значення функції
при .
Ітерація. Ітерації по параметру 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 , , отриманий результат є некоректним і дається сигнал, що потрібна нам апроксимація не існує.
Результати і висновки
Мною була складена програма, яка реалізує методи Течера-Тьюкі та Тіле раціональної інтерполяції функції. За результатами роботи програми можна впевнено стверджувати, що метод Течера-Тьюкі є значно надійніший ніж метод обернених різниць Тіле. Так за рахунок чого ж досягається більша надійність, якщо обидва методи базуться на подібному представленні інтерполяційної функції ? Справа в тому, що в алгоритмі Течера-Тьюкі вибір того чи іншого вузла інтерполяції із заданої сукупності проводиться в ітераційному процесі. Саме в такий спосіб вдається обійти деякі особливі випадки, коли інтерполяційна функція існує, але серед проміжкових інтерполяцій є вироджені. Але за вищу надійність доводиться платити і вищою ресурсоємністю обчислень. По кількості ресурсоємних машинних операцій при знаходженні коефіцієнтів метод Течера-Тьюкі перевершує відповідний показник алгоритма Тіле в середньому більш ніж у три рази.
В загальному можна зробити висновок, що, поки-що, ідеального методу раціональної апроксимації функцій не розроблено (і невідомо, чи буде колись розроблено, оскільки саме представлення інтерполюючої функції в виді ланцюгового дробу накладає певні обмеження), хоча певні досягнення все ж таки є, і алгоритм Течера-Тьюкі яскраве підтвердження тому.
Подобные документы
Будування сіткової функції. Методи прямокутників і трапецій, підвищення їх точності. Інтерполяційний многочлен Лагранжа другого степеня. Формула Сімпсона для чисельного інтегрування. Похибка формули Сімпсона. Обчислення наближеного значення інтеграла.
презентация [99,6 K], добавлен 06.02.2014Метод Гаусса, метод прогонки, нелинейное уравнение. Метод вращения Якоби. Интерполяционный многочлен Лагранжа и Ньютона. Метод наименьших квадратов, интерполяция сплайнами. Дифференцирование многочленами, метод Монте-Карло и Рунге-Кутты, краевая задача.
курсовая работа [4,8 M], добавлен 23.05.2013Метод решения задачи, при котором коэффициенты a[i], определяются непосредственным решением системы - метод неопределенных коэффициентов. Интерполяционная формула Ньютона и ее варианты. Построение интерполяционного многочлена Лагранжа по заданной функции.
лабораторная работа [147,4 K], добавлен 16.11.2015Умови та особливості використання модифікованого методу Ейлера для отримання другої похідної в кінцево-різницевій формі. Два обчислення функції за крок. Метод Ейлера-Коші як частковий випадок методу Рунге-Кутта. Метод четвертого порядку точності.
презентация [171,0 K], добавлен 06.02.2014Крайова задача для звичайного диференціального рівняння. Метод Рунге-Кутта, метод прогнозу і корекції та метод кінцевих різниць для розв’язання лінійних крайових задач. Реалізація пакетом Maple. Оцінка похибки й уточнення отриманих результатів.
контрольная работа [340,6 K], добавлен 14.08.2010Лінійні, квадратичні та кубічні В-сплайни. Отримання форми запису сплайнів, виведення формул для розрахунків інтерполяційних задач. Застосування кубічних В-сплайнів в математичній теорії і обчислювальних задачах. Практичність вивчення кубічних В-сплайнів.
контрольная работа [678,5 K], добавлен 20.11.2010Формулювання задачі мінімізації. Мінімум функції однієї та багатьох змінних. Прямі методи одновимірної безумовної оптимізації: метод дихотомії і метод золотого перерізу. Метод покоординатного циклічного спуску. Метод правильного і деформованого симплексу.
курсовая работа [774,0 K], добавлен 11.08.2012Випадок однорідної крайової задачі. Розв’язання виродженого крайового виразу. Теорема Коші, іі доведення. Означення узагальненої функції Гріна крайової задачі. Формулювання алгоритму відшукання узагальненої функції Гріна. Приклади роз'язання завдань.
лекция [108,5 K], добавлен 24.01.2009Сутність фізичного та геометричного змісту похідної, особливості його використовування у математичних задачах. Означення диференціалу, формула його обчислення. Екстремуми функцій двох змінних. Правила знаходження найбільшого і найменшого значення функції.
презентация [262,6 K], добавлен 20.05.2015Означення та приклади застосування гармонічних функцій. Субгармонічні функції та їх деякі властивості. Розв’язок задачі Діріхле з використанням функції Гріна. Теореми зростання та спадання функції регулярної в нескінченній області (Фрагмена-Ліндельофа).
курсовая работа [349,0 K], добавлен 10.09.2013