/>/>/>/>/>Зміст
/>/> ВступРозділ IІнтерполювання функцій1.1 Постановка задачі1.2 Інтерполяційні формули Ньютона1.2.1 Перша інтерполяційна формула Ньютона1.2.2 Друга інтерполяційна формула Ньютона1.2.3 Оцінка похибок інтерполяційних формул Ньютона1.3 Інтерполяційні формули Гауса1.4 Інтерполяційна формула Бесселя1.5 Інтерполяційна формула Стірлінга1.6 Оцінки похибок центральних інтерполяційних формул1.7 Інтерполяційна формула Ньютона для нерівновіддаленихвузлів1.8 Приклади застосування інтерполяційних формул1.8.1 Приклад 11.8.2 Приклад 21.9 Програмна реалізація1.9.1 Призначення програми1.9.2 Основні процедури1.9.3 Інструкція по використанню програми1.9.4 Перевірка працездатності програмиРозділ ІІЛітератураДодатки
Вступ
У зв’язку з розвиткомобчислювальної техніки інженерна практика наших днів все частіше і частішезустрічається з математичними задачами, точний розв’язок яких отриматидостатньо важко. В таких випадках зазвичай звертаються до тих чи іншихнаближених обчислень. Ось чому наближені і чисельні методи математичногоаналізу отримали за останні роки широкий розвиток і набули виключно важливогозначення.
Чисельне розв’язання прикладнихзадач завжди цікавило математиків. Аналізускладнених моделей вимагав створення спеціальних, як правило, чисельних абоасимптотичних методів розв’язання завдань. Назвидеяких з таких методів — методи Ньютона, Ейлера, Лобачевського, Гауса,Чебишева, Ерміта, Крилова — свідчать про те, що їх розробкою займалисянайвидатніші вчені свого часу.
Чисельні методи є одним з могутніх математичнихзасобів розв’язання задач. Прості чисельні методи ми використовуємо скрізь,наприклад, при знаходженні квадратного кореня на листку паперу. Є завдання, дебез достатньо складних чисельних методів не вдалося б отримати відповіді. Класичнийприклад — відкриття Нептуна по аномаліях руху Урану.
Загалом у курсах чисельних методіввивчаються питання побудови, застосування і теоретичного обґрунтуванняалгоритмів наближеного розв’язання різних класів математичних задач. У наш часбільшість обчислювальних алгоритмів орієнтовано на використання швидкодіючихЕОМ, що значно впливає на підбір учбового матеріалу й на характер його викладу.Тількиобчислювальній машині під силу виконувати за короткий час об'єм обчислень вмільярди, трильйони і більше операції, які необхідні для вирішення багатьохсучасних завдань.
Варто відмітити деякі особливостіпредмету чисельних методів. По-перше, для чисельних методів характернамножинність, тобто можливість розв’язати одну й ту саму задачу різнимиметодами. По-друге, природничонаукові задачі і швидкий розвиток обчислювальноїтехніки змушують переоцінювати значення існуючих алгоритмів і призводять достворення нових. По-третє, чисельні методи разом із можливістю отримання результату заприйнятний час не повинні вносити у обчислювальний процес значних похибок.
У даній курсовій роботі розглядаєтьсязадача проінтерполяцію функції. Якщо задана функція y(x), то це означає, що будь-якомудопустимому значенню х ставиться у відповідність значення у. Однак, нерідковиявляється, що знаходження цього значення дуже трудомістке. Наприклад, у(х)може бути визначене як розв’язок складної задачі, в якій х виконує рольпараметра, або у(х) вимірюється в дорогому експерименті. При цьому можнаобчислити невелику таблицю значень функції, але пряме знаходження функції привеликому числі значень аргументу буде практично неможливо.
Функція у(х) може брати участь у будь-яких фізико-технічних або чисто математичних розрахунках,де її доводиться багато разів обчислювати. У цьому випадку вигіднозамінити функцію у (х) наближеною відомоюфункцією, тобто підібрати деяку функцію f(x), яка близька у певному сенсі доу(х) і легко обчислюється. Потім при всіх значеннях аргументу вважають,що />.
Більша частина класичногочисельного аналізу ґрунтується на наближеннімногочленами, оскільки з ними легко працювати. Однак для багатьох цілейвикористовують і інші класи функцій (див. [2]).
Вибравши вузлові точки і класфункцій, що наближають, ми повинні також вибратиодну певну функцію з цього класу за допомогою деякого критерію — міринаближення або «згоди». Перш, ніж почати обчислення, ми повинні вирішити також,яку точність ми хочемо мати у відповіді і який критерій ми оберемо длявимірювання цієї точності.
Все викладене можнасформулювати у вигляді чотирьох питань:
1. Які вузлими будемо використовувати?
2. Який класфункцій для наближення будемо використовувати?
3. Якийкритерій згоди ми застосуємо?
4. Якуточність ми хочемо?
Існує 3 класи або групи функцій, широко застосовуваних у чисельному аналізі. Перша групавключає в себе лінійні комбінації функцій 1, х, х2, ..., хn, що збігається зкласом усіх многочленів степені n (або менше). Другий клас утворюють функції cos aix, sin aix. Цей клас має відношення до рядів Фур'є та інтегралу Фур'є. Третя групаутворюється функціями e-az. Ціфункції зустрічаються в реальних ситуаціях. До них, наприклад, призводятьзадачі накопичення і розпаду.
Що стосується критерію згоди,то класичним критерієм згоди є «точний збіг у вузлових точках». Цей критеріймає перевагу завдяки простоті теорії та виконаннюобчислень, але також незручність через ігнорування похибки (шуму), щовиникає при вимірюванні або обчисленні значень у вузлових точках. Іншийвідносно хороший критерій — це «найменші квадрати». Він означає, що сумаквадратів відхилень у вузлових точках повинна бути найменшою можливою або,іншими словами, мінімізована. Цей критерійвикористовує помилкову інформацію, щоб отримати деяке згладжування шуму. Третійкритерій пов’язаний з ім'ям Чебишева. Основнаідея його полягає в тому, щоб зменшити максимальне відхилення домінімуму. Очевидно, можливі й інші критерії. Більшконкретно відповісти на поставлені 4 питання можна лише виходячи з умов і метикожної окремої задачі.
/>РозділI. Інтерполювання функцій
1.1 Постановка задачі
Однією з основних задач чисельногоаналізу являється задача про інтерполяцію функції. Багатьом з тих, хтостикається з науковими та інженерними розрахунками часто доводиться оперуватинаборами значень, отриманих експериментальним шляхом чи методом випадкової вибірки. Якправило, на підставі цих наборів потрібно побудувати функцію, зі значеннямиякої могли б з високою точністю збігатися інші отримувані значення. Така задачаназивається апроксимацією кривої.
Інтерполяцією називають такийрізновид апроксимації, при якій крива побудованої функції проходить точно черезнаявні точки даних. Існує також близька до інтерполяції задача, що полягає вапроксимації якої-небудь складної функції іншою, більш простою функцією. Якщодеяка функція занадто складна для продуктивних обчислень, можна спробуватиобчислити її значення в декількох точках, а по них побудувати, тобтоінтерполювати, більш просту функцію. Зрозуміло, використання спрощеної функціїне дозволяє одержати такі ж точні результати, які давала б початкова функція.Але, для деяких класів задач, досягнутий виграш у простоті і швидкостіобчислень може переважити отриману похибку у результатах. Варто також згадати ізовсім інший різновид математичної інтерполяції, відому за назвою «інтерполяціяоператорів». До класичних робіт по інтерполяції операторів відносяться теоремаРіса-Торина і теорема Марцинкевича(див. [3]), що є основою для багатьох інших робіт. В результаті виникаєнаступна математична задача.
Нехай функція /> задана таблицею:
/>.
Потрібно побудувати інтерполянту –функцію />, котра співпадає з функцією /> вточках />:
/> (1. 1. 1)
Основна мета інтерполяції – отриматишвидкий алгоритм обчислення значень /> і оцінити похибку />. Інтерполюючіфункції />, як правило, будуються в вигляділінійних комбінацій деяких елементарних функцій:/>, де /> — фіксованілінійно незалежні функції, /> - не визначені поки щокоефіцієнти.
Із умов (1. 1. 1) отримуємо систему п+1 рівняньвідносно коефіцієнтів />: />.
Припустимо, що система функцій /> така,що при будь-якому /> відмінний від нуля визначниксистеми:
/>.
Тоді по заданим /> однозначновизначаються коефіцієнти />. В якості системи лінійнонезалежних функцій /> частіше обирають: степеневіфункції /> (в цьому випадку /> — поліномстепені п); тригонометричні функції /> (f — тригонометричний поліном);використовують також раціональні функції та ін.
В даній курсовій роботі розглядаютьсяінтерполяційні поліноми.
Відомо, що будь-яка неперервна навідрізку /> функція /> може бути добренаближена деяким поліномом /> (див. [1], c.50):
Теорема Вейерштрасса: Для будь-якого /> існуєполіном /> степеня />, такий, що />.
Отже, будемо шукати інтерполяційнийполіном в вигляді:
/>, (1. 1. 2)
де /> - невизначені коефіцієнти.Покладемо />, тоді отримаємо систему лінійнихрівнянь:
/>
Визначникданої системи являється відмінним від нуля визначником Вандермонда (див. [9]):
/>.
Звідсивипливає, що інтерполяційний поліном (1. 1. 2) існує і він єдиний, хоча формйого запису існує багато.
Вякості базису /> ми взяли базис із одночленів />. Дляобчислень більш зручним являється базис поліномів Лагранжа /> степеня п абокоефіцієнтів Лагранжа:
/>
Неважкопобачити, що поліном степені п
/>
задовольняєцим умовам. Полином />, очевидно, визначається єдинимспособом. Дійсно, нехай існує ще один поліном />, тоді їх різниця /> є поліномстепені п, який перетворюється в нуль в п+1 точках />. Це можливо тільки при />.
Поліном/> приймаєзначення /> в точці /> і рівний нулю у всіхостанніх вузлах /> при />. Звідси випливає, щоінтерполяційний поліном:
/> (1.1. 3)
маєстепінь не вище п і />. Формулу (1. 1. 3) називають формулою Лагранжа. Числоарифметичних дій для обчислення по (1. 1. 3) пропорційно />. Для оцінки близькості полінома /> дофункції /> покладають, що існує п+1– шанеперервна похідна />. Тоді має місце формула дляпохибки
/>.
При оцінці похибки результатівповинні враховуватись як похибки методу інтерполяції (залишковий член), так іпохибка округлення при обчисленнях.
1.2 Інтерполяційні формули Ньютона
Часто інтерполювання ведеться дляфункцій, заданих таблицями з рівновіддаленими значеннями аргументу (тобтотакими, що будь-який />(вузол інтерполяції) можнапредставити у вигляді /> - деяка постійна величина, яка називаєтьсякроком інтерполяції). Для таких таблиць побудова інтерполяційних формул, атакож проведення обчислень по ним значно спрощується.
Для побудови формули Ньютонанеобхідно ввести поняття кінцевих різниць.
Кінцевими різницями називають різниціміж значеннями функції в сусідніх вузлах (точках />) інтерполяції:
/>/>/>/>/>/>/>/>/>/>/>/>/>
/>
де /> Отримані кінцеві різницібудемо називати кінцевими різницями першого порядку. З різниць першого порядкуотримаємо різниці другого порядку:
/>/>/>/>/>/>/>/>/>/>/>/>/>
де /> />.
Повторюючи процедуру, отримаємокінцеві різниці третього порядку:
/> />
Для кінцевих різниць />-го порядку:
/> />
В результаті отримаємо таблицюкінцевих різниць:
/>
/>/>/>/>/>/>/>/>/>/>/>
/>/>/>/>/>/>/> /> /> /> /> /> />
/>/>/>/>/>
/>/>
/>
.............
/>
Залучивши визначення похідної, можнавиявити певний зв'язок між кінцевими різницями і похідними. А саме, якщовраховувати, що />, то можна сказати, що придостатньо малих /> має місце наближена рівність/> тобто перші різниці характеризуютьпершу похідну функції /> по значенням якої вони складені.Скориставшись цим, маємо для других різниць: />
/>,
тобто />, і, взагалі, />. (1.2. 1)
Таким чином, на кінцеві різниці можнадивитись як на деякий аналог похідних. Звідси справедливість багатьох їх властивостей,однакових зі властивостями похідних.
Відмітимо лише найпростішівластивості кінцевих різниць:
1. кінцевірізниці сталої дорівнюють нулю;
2. сталиймножник у функції можна виносити за знак кінцевої різниці;
3. кінцеварізниця від суми двох функцій дорівнює сумі їх кінцевих різниць в одній і тійже точці.
Враховуючи роль, яку відіграютьмногочлени в теорії інтерполювання, подивимось, що представляють собою кінцевірізниці многочленна.
Так як многочлен в своїй канонічнійформі є лінійна комбінація степеневих функцій, покладемо спочатку />. Використовуючибіноміальне розвинення п-ого степеня двочлена, отримаємо:
/>
тобто перша кінцева різницястепеневої функції /> є многочлен степеня п-1 зістаршим членом />. Якщо взяти тепер кінцеву різницювід функції
/>, (1. 2. 2)
то в силу лінійних властивостей />, можна записати />. Перший доданок в цій сумі, якз’ясовано, є многочлен (п-1)-го степеня, другий, аналогічно, — многочленстепеня п-2, і т. д. отже, перша кінцева різниця многочленна (1. 2. 2) в точці /> з короком /> є многочлен зі старшим членом />,друга кінцева різниця – многочлен зі старшим членом />, …, />-та різниця –многочлен зі старшим членом />.
При /> отримуємо постійну різницю п-гопорядку /> для многочлена (1. 2. 2), кінцевірізниці більш високих порядків дорівнюють нулю.
Тобто, головний висновок ізпопередніх роздумів: п-і кінцеві різниці многочленна п-ого степеня постійні, а(п+1)-ші і всі наступні рівні нулю.
Однак, більш важливим для розуміннясуті поліноміального інтерполювання є твердження, обернене зробленому вищевисновку. А саме, що якщо кінцеві різниці п-го порядку деякої функції /> постійнів будь-якій точці /> при різних фіксованих кроках />, тоця функція /> є многочлен степеня п.
Для функції />, заданої таблицею своїхзначень /> у вузлах />, де />, кінцевірізниці різних порядків зручно поміщати в одну загальну таблицю з вузлами ізначеннями функції. Цю загальну таблицю називають таблицею кінцевих різниць.
1.2.1 Перша інтерполяційна формулаНьютона
Нехай для функції /> задані значення /> для рівновіддалених значеньнезалежної змінної: />, де /> - крок інтерполяції. Необхіднопідібрати поліном /> степені не вище п, якийприймає в точках /> значення
/> (1. 2. 3)
Умови (1. 2. 3) еквівалентні тому, що />.Слідуючи Ньютону, будемо шукати поліном у вигляді
/>
Використовуючи загальний степінь,вираз (1. 2. 3)запишемо так:
/>
Наша задача заклечається у визначеннікоефіцієнтів /> полінома />. Покладаючи /> у вираз (1. 2. 5), отримаємо />.
Щоб знайти коефіцієнт />, складемопершу кінцеву різницю />. Припускаючи в останньому виразі />, отримаємо: />; звідки />. Для визначення коефіцієнта /> складемо кінцеву різницю другогопорядку />.Покладаючи />, отримаємо: />; звідки />. Послідовно продовжуючи цей процес,ми виявимо, що />, де />.
Підставляючи знайдені значеннякоефіцієнтів /> у вираз (1. 2. 5) отримаємоінтерполяційний поліном Ньютона
/>. (1. 2. 6)
Легко побачити, що поліном (1. 2. 6.)повністю задовольняє вимогам поставленої задачі. Дійсно, по-перше, степіньполіному /> не вище п, по-друге, /> і
/>
Замітимо, що при /> формула (1. 2.6) перетворюється в ряд Тейлора для функції />. Дійсно, />Крім того, очевидно, />.Звідси при /> формула (1. 2. 6) приймає вид поліномуТейлора: />.
Для практичного використанняінтерполяційну формулу Ньютона (1. 2. 6) зазвичай записують в дещоперетвореному вигляді. Для цього введемо нову змінну /> за формулою />; тоді
/>
підставляючи ці вирази у формулу (1.2. 6), отримаємо:
/>, (1. 2. 7)
де /> являє собою кількість кроків,необхідних для досягнення точки />, виходячи із точки />. Це і єкінцевий вигляд першої інтерполяційної формули Ньютона.
Формулу (1. 2. 7) вигідновикористовувати для інтерполювання функції в околі початкового значення />, де /> малеза абсолютною величиною.
Якщо у формулі (1. 2. 7) покластип=1, то отримаємо формулу лінійного інтерполювання: />. При п=2 будемо мати формулупараболічного або квадратичного інтерполювання
/>.
Якщо дана необмежена таблиця значень />, точисло /> в інтерполяційній формулі (1. 2.7) може бути довільним. Практично в цьому випадку число /> обирають так, щобрізниця /> була постійною із заданоюточністю. За початкове значення /> можна приймати довільне табличнезначення аргументу />.
Якщо таблиця значень функціїскінчена, то /> - число обмежене, а саме: /> неможе бути більше числа значень функції />, зменшеного на одиницю.
Відзначимо, що при застосуванніпершої інтерполяційної формули Ньютона зручно використовувати горизонтальнутаблицю різниць, так як потрібні значення різниць функції знаходяться увідповідному горизонтальному рядку таблиці.
1.2.2 Друга інтерполяційнаформула Ньютона
Перша інтерполяційна формула Ньютонапрактично незручна для інтерполювання функції поблизу вузлів таблиці. В такомувипадку зазвичай застосовують другу інтерполяційну формулу Ньютона. Виведемо цюформулу.
Нехай маємо систему значень функції /> длярівновіддалених значень аргументу />, де /> - крок інтерполяції.Побудуємо поліном наступного вигляду:
/>
або, використовуючи узагальненустепінь, отримуємо:
/>. (1. 2. 8)
Наша задача полягає у визначеннікоефіцієнтів /> таким чином, щоб виконувались умови(1. 2. 3). Для цього необхідно і достатньо, щоб
/> (1. 2. 9)
Покладемо /> у формулі (1. 2. 8). Тоді будемомати: />,отже />.
Далі беремо від лівої і правоїформули (1. 2. 8) кінцеві різниці першого порядку
/>.
Звідси, вважаючи /> і враховуючи відношення(1. 2. 9) будемо мати:
/>. Отже />.
Покладаючи /> знаходимо: />. І таким чином />.
Характер закономірності коефіцієнтів /> достатньозрозумілий. Застосовуючи метод математичної індукції, можна строго довести, що
/> (1. 2. 10)
Підставляючи ці значення у формулу (1.2. 8) будемо мати остаточно
/>/> (1. 2. 11)
Формула (1. 2. 11) носить назву другоїінтерполяційної формули Ньютона.
Введемо більш зручний запис формули (1.2. 11). Нехай />, тоді
/> і т. д.
Підставивши ці значення у формулу (1.2. 11), отримаємо:
/>/>. (1.2.12)
Це і є загальний вигляд другоїінтерполяційної формули Ньютона. Для наближеного обчислення значень функції />вважають,що />.
Як перша, так и друга інтерполяційніформули Ньютона можуть бути використані для екстраполяції, тобто, длязнаходження значень функції /> для значень аргументів />,котрі лежать за межами таблиці. Якщо /> і /> близько до />, товигідно використовувати першу інтерполяційну формулу Ньютона, причому тоді />. Якщож /> і/> близькодо />,то зручніше використовувати другу інтерполяційну формулу Ньютона, причому тоді />.Таким чином, перша інтерполяційна формула Ньютона використовується дляінтерполяції вперед і екстраполяції назад, а друга інтерполяційна формулаНьютона, навпаки, – для інтерполяції назад і екстраполяції вперед (див. [8]).
Відмітимо, що операція екстраполяції,взагалі кажучи, менш точна, ніж операція інтерполяції у вузькому значенніслова.
1.2.3 Оцінка похибокінтерполяційних формул Ньютона
Для функції /> ми побудувалиінтерполяційний поліном Ньютона /> , який приймає в точках /> заданізначення />. Виникає питання, наскількиблизько побудований поліном наближається до функції /> в інших точках, тобтонаскільки великий залишковий член />. Для визначення цього степеня наближення накладемо на функцію/> додатковіобмеження. А саме, ми будемо припускати, що в області зміни />: />,котра містить вузли інтерполювання, функція /> має всі похідні /> до (п+1)-го порядкувключаючи.
Введемо допоміжну функцію
/>, (1. 2. 12) де /> і
/> - постійний коефіцієнт, котрий будеобрано нижче.
Функція />, очевидно, має п+1 корінь в точках />. Підберемо тепер коефіцієнт /> такимчином, щоб /> мала (п+2)-ий корінь в будь-якій,але фіксованій точці відрізка />, яка не співпадає з вузламиінтерполювання (мал. 1). Для цього достатньо покласти
/>.
Звідси, так як />, то
/> (1. 2. 13)
При цьому значення множника /> функції /> має п+2 кореня навідрізку /> і буде обертатись в нуль накінцях кожного з відрізків
/>. Застосовуючи теорему Ролля [11] до кожного із цих відрізків,переконуємось, що похідна /> має не менше п+1 кореня навідрізку />.
/>
Малюнок 1. Графік функції />
Застосовуючи теорему Ролля допохідної />, мипереконаємося, що друга похідна /> перетворюється в нуль не менше празів на відрізку />.
Продовжуючи ці роздуми, прийдемо довисновку, що на відрізку /> похідна /> має хоча б один корінь,котрий позначимо через />, тобто />.
Із формули (1. 2. 11) так як />, маємо: />. При />, отримуємо: /> Звідси/>.(1. 2. 14)
Порівнюючи праві частини формул (1. 2. 13) і (1. 2. 14), будемо мати:
/>, тобто
/>. (1. 2. 15)
Так як /> довільне, то формулу (1. 2. 15) можна записати і так:
/>, (1. 2. 16)
де /> залежить від /> і лежить всередині відрізка />.
Відмітимо, що формула (1. 2. 16) справедлива для всіх точоквідрізка />, в тому числі і для вузлівінтерполювання.
На основі формули (1. 2. 16) отримаємо залишковий член першоїінтерполяційної формули Ньютона:
/>, (1. 2. 17)
де /> - деяка внутрішня точканайменшого проміжку, що містить всі вузли /> і точку />.
Аналогічно, покладаючи в формулі (1. 2. 17) />, отримаємо залишковий член другоїінтерполяційної формули Ньютона:
/>, (1. 2. 18)
де /> - деяка внутрішня точканайменшого проміжку, що містить всі вузли /> і точку />.
Зазвичай при практичних обчисленняхінтерполяційна формула Ньютона обривається на членах, що містять такі різниці,які в межах заданої точності можна вважати постійними.
Вважаючи, що /> майже постійними дляфункції /> і /> достатньо малим, івраховуючи, що />, наближено можна покласти:
/>.
В цьому випадку залишковий членпершої інтерполяційної формули Ньютона наближено рівний
/>.
При таких самих умовах длязалишкового члена другої інтерполяційної формули Ньютона отримаємо вираз
/>.
1.3 Інтерполяційні формулиГауса
При побудові інтерполяційних формулНьютона використовуються лише значення функції, що лежать з однієї сторонипочаткового наближення, тобто, ці формули носять односторонній характер (див.[3]).
В багатьох випадках виявляютьсякорисними інтерполяційні формули, що містять як наступні, так і попереднізначення функції по відношенню до її початкового наближеного значення. Найбільшвживаними серед них являються ті, що містять різниці, розміщені угоризонтальному рядку діагональної таблиці різниць даної функції, що відповідаєпочатковим значенням /> і />, або в рядках, що безпосередньопримикають до неї. Ці різниці /> називаються центральними різницями,причому /> і т. д.
Відповідні їм формули називаютьінтерполяційними формулами із центральними різницями. До їх числа відносятьсяформули Гауса, Стірлінга і Бесселя.
Постановка задачі. Нехай маємо 2п+1 рівновіддаленівузли інтерполяції:
/>,
де />, і для функції /> відомі її значення в цих вузлах />, потрібно побудувати такий поліном /> степеніне вище 2п, що />. Із останньої умовивипливає, що
/> (1. 3. 1)
для всіх відповідних значень і та k.
Будемо шукати поліном у вигляді:
/>
Вводячи узагальнені степені (див [3]),отримаємо:
/>
Застосовуючи для обчисленнякоефіцієнтів /> такийже спосіб, що і при виведенні інтерполяційних формул Ньютона, і враховуючиформулу (1. 3. 1), послідовно знаходимо:
/>
Далі вводячи змінну /> і зробившивідповідну заміну у формулі (1. 3. 3), отримаємо першу інтерполяційну формулуГауса:
/>
або, коротше,
/>
де />.
Перша інтерполяційна формула Гаусамістить центральні різниці
/> .
Аналогічно можна отримати другуінтерполяційну формулу Гауса, котра містить центральні різниці /> . Друга інтерполяційна формула Гаусамає вигляд:
/>
або, в скорочених позначеннях,
/>
де />.
Формули Гауса застосовуються дляінтерполювання в середині таблиці поблизу />. При цьому перша формула Гаусазастосовується при />, а друга – при />.
1.4 Інтерполяційна формулаБесселя
Для того, щоб вивести формулу Бесселявикористаємо другу інтерполяційну формулу Гауса (1. 3. 6).
Візьмемо /> рівновіддалених вузлівінтерполювання /> з кроком />, і нехай /> - заданізначення функції />.
Якщо обрати за початкове значення /> і />, то,використовуючи вузли />, будемо мати:
/>
прикладний задачаінтерполяційний формула
Візьмемо тепер за початкове значення /> і /> івикористаємо вузли />. Тоді />, причому відповідноіндекси всіх різниць в правій частині формули (1. 4. 1) зростуть на одиницю. Якщозамінити в правій частині формули (1. 4. 1) /> на /> і збільшивши індексивсіх різниць на 1, отримаємо допоміжну інтерполяційну формулу:
/>
Взявши середнє арифметичне формул (1.4. 1) і (1. 4. 2), після нескладних перетворень отримаємо інтерполяційнуформулу Бесселя:
/>
де />.
Тобто, інтерполяційна формула Бесселя(1. 4. 3), як слідує із способу отримання її, представляє собою поліном, якийспівпадає з даною функцією /> в /> точках />.
В окремому випадку, при п=1, нехтуючирізницею />, маємо формулу квадратичноїінтерполяції по Бесселю:
/>
або />, де />.
У формулі Бесселя всі члени, котрімістять різниці непарного порядку, мають множник />, тому при /> формула (1. 4. 3) значноспрощується:
/>
Цей спеціальний випадок формули Бесселяназивається формулою інтерполювання на середину. Якщо у формулі (1. 4. 3)зробити заміну змінної за формулою />, то вона приймає більш симетричнийвигляд:
/>
де />.
Формула Бесселя використовується дляінтерполювання всередині таблиці при значеннях q, близьких до 0.5. Практичновона використовується при />.
1.5 Інтерполяційна формула Стірлінга
Якщо взяти середнє арифметичне першоїінтерполяційної формули Гауса (1. 3. 4) та другої формули Гауса (1. 3. 6), тоотримаємо формулу Стірлінга:
/>
де />.
Легко бачити, що /> при />.
Формула Стірлінга використовуєтьсядля інтерполювання в середині таблиці при значеннях />, близьких до нуля.Практично її використовують при />.
1.6 Оцінки похибокцентральних інтерполяційних формул
Приведемо залишкові члени для формулГауса, Стірлінга і Бесселя [12].
1. Залишковийчлен інтерполяційних формул Гауса (1. 3. 4) і (1. 3. 6) та інтерполяційноїформули Стірлінга (1. 5. 1).
Якщо 2п – порядок максимальноїрізниці таблиці, яка використовується
і />, то />,
де />.
Якщо ж аналітичний вираз функції /> невідомий,то при /> малому покладають [2]: />.
2. Залишковийчлен інтерполяційної формули Бесселя (1. 4. 3).
Якщо 2п+1 – порядок максимальноївикористовуваної різниці таблиці і />, то
/>,
де />.
Якщо ж функція /> задана таблично і крок h малий, то приймають:
/>.
Найбільш простий вигляд формула маєпри q=0.5, так як всі члени, що містять різниці непарного порядку зникають. Цейспеціальний випадок формули Бесселя називається формулою інтерполювання насередину. Її використовують для ущільнення таблиць [4], тобто для складаннятаблиць з більш малим кроком. Для залишкового члена при q=0.5 маємо:
/>.
1.7 Інтерполяційна формулаНьютона для нерівновіддалених вузлів
Для побудови інтерполяційних формул увипадку довільного розташування упорядкованих не співпадаючих вузлів /> напроміжку />, замість кінцевих різницьвикористовують розділені різниці, або інакше, різницеві відношення.
Через значення функції /> спочаткувизначають розділені різниці першого порядку:
/> (1. 7. 1)
На різницях (1. 7. 1) шукаютьсярозділені різниці другого порядку:
/>
і т.д. Таким чином, якщо визначеніk-ті різницеві відношення />, то /> — ті визначаються завдяки ним рівністю:
/> (1. 7. 2)
Нехай /> - деяка функція ізвідомими значеннями у вузлах />, а /> - довільна фіксованаточка. За означенням розділеної різниці першого порядку (1. 7. 1) маємо: />звідки
/> (1. 7. 3)
Для розділеної різниці другогопорядку по точкам /> записуємо представлення: /> наслідкомякого являється вираз /> Підставляючи його у формулу (1. 7. 2),приходимо до рівності
/>
Формально, на основі рекурентноговідношення (1. 7. 2) цей процес може бути продовжений. В результаті можназаписати формулу, яка описує своєрідне розкладання /> по добуткам різниць />,коефіцієнтами якого являються розділені різниці різних порядків:
/> (1. 7. 4)
Якщо /> - многочлен степені п,то процес подібного розкладання вичерпується. Розкладання буде складатись з п+1доданка, і всі вони будуть мати конкретні коефіцієнти, так як остання, якамістить />, розділена різниця в (1. 7. 4), тобто /> має (п+1)-ийпорядок і, значить, дорівнює нулю. Таким чином, для довільного многочленнастепені п справедлива тотожність
/>
Припустимо, що цей многочлен /> являєтьсяінтерполяційним для деякої функції />. Тоді у всіх вузлах /> вінповинен мати однакові з нею значення, а отже повинні бути однаковими і їхрозділені різниці. Звідси приходимо до інтерполяційної формули Ньютона длянерівновіддалених вузлів:
/>
Підставивши /> замість /> у формулу (1. 7. 4), з урахуванням (1. 7. 5) отримуємо точну рівність
/>
другий доданок якої може розглядатисьв якості залишкового члена, тобто
/>, (1. 7. 6)
де />.
Так як для обчислення різниці /> необхіднознання значення /> поряд з відомими значеннями />,представлений формулою (1. 7. 5)вираз /> фактично можна використовуватитільки для оцінювання похибки інтерполювання за формулою (1. 7. 5) через максимальні величини модуліврозділених різниць (п+1)-го порядку або для одержання інших виразів залишковогочлена при тих чи інших припущеннях про дану функцію. Зокрема, якщо функція /> має(п+1)-шу похідну, то залишковий член (1. 7. 6) може бути приведений до вигляду />.
При практичному використанняінтерполяційної формули (1. 7. 5) доводиться покладатися на зменшення модулів доданків /> призбільшенні номера доданка. Таке зменшення відбувається до деяких пір; потімпочинається зростання їх модулів із-за впливу похибок заокруглення.
1.8 Приклади застосуванняінтерполяційних формул
1.8.1 Приклад 1
Використовуючи першу і другуінтерполяційну формулу Ньютона і Гауса, а також інтерполяційні формулиСтірлінга і Бесселя необхідно знайти значення функції />, заданої таблицею (табл. 1) призначенні аргументу />. При цьому крок />.
Таблиця 1. Значення функціїxi yi 1,50 15,132 1,55 17,422 1,60 20,393 1,65 23,994 1,70 28,160 1,75 32,812 1,80 37,857
Розв’язання:
Складемо спочатку таблицю кінцевихрізниць (табл. 2).
Таблиця 2. Кінцеві різниціі xi yi yi 2yi 3yi
/>1,50
/>15,132 2,290
/>0,681 -0,051 1 1,55 17,422 2,971 0,630 -0,065 2 1,60 20,393 3,601 0,565 -0,079 3 1,65 23,994 4,166 0,486 -0,093 4 1,70 28,160 4,652 0,393 5 1,75 32,812 5,045 6 1,80 37,857
При складанні таблиці різниць обмежимосярізницями третього порядку, оскільки вони практично постійні.
· За першоюінтерполяційною формулою Ньютона (1. 2. 7), приймаючи />, /> (табл. 2),отримаємо:
/>;
/>;
/>
· За другоюінтерполяційною формулою Ньютона (1. 2. 11), приймаючи />, /> (табл. 2),отримаємо:
/>;
/>;
/>
· За першоюінтерполяційною формулою Гауса (1. 3. 4), приймаючи />, />, матимемо:
/>.
Отже, отримаємо:
/>
· За другоюінтерполяційною формулою Гауса (1. 3. 6), приймаючи />, />, отримаємо:
/>;
/>
· Заінтерполяційною формулою Стірлінга, підставляючи відповідні коефіцієнти ізтаблиці різниць (табл. 2) у формулу (1. 5. 1) отримаємо:
/>
· Заінтерполяційною формулою Бесселя, підставляючи відповідні коефіцієнти із таблицірізниць (табл. 2) в формулу (1. 4. 3) отримаємо:
/>
Тепер проведемо оцінку отриманихрезультатів. Введемо наступні позначення:
ІФН – інтерполяційна формула Ньютона;
ІФГ — інтерполяційна формула Гауса;
ІФБ — інтерполяційна формула Бесселя;
ІФС — інтерполяційна формулаСтірлінга.
Для зручності результати запишемо увигляді таблиці (табл. 3):ІФН 1-ша ІФН 2-га ІФГ 1-ша ІФГ 2-га ІФБ ІФС 20,7930 20,7929 20,7931 20,79486 20,5784 20,7930
Таблиця 3. Отримані результати.
Тепер визначимо похибку отриманихрезультатів. Для цього від значення, отриманого за допомогою першої ІФН,віднімемо результати, отримані зі допомогою інших формул. В результатіотримаємо таку розрахункову табличку (табл. 4):ІФН 2-га ІФГ 1-ша ІФГ 2-га ІФБ ІФС 0,00015 0,00013 0,00186 0,21457 0,00001
Таблиця 4. Абсолютні похибкирезультатів.
Тоді, щоб отримати відносну похибкурезультату, необхідно абсолютні похибки поділити на відповідні отриманінаближені значення />, отримані за формулами (1. 2. 7),(1. 2. 11), (1. 3. 4), (1. 3. 6), (1. 4. 3), (1. 5. 1). Тобто маємо (табл. 5):ІФН 2-га ІФГ 1-ша ІФГ 2-га ІФБ ІФС 0,00070% 0,00062% 0,00893% 1,04270% 0,00004%
Таблиця 5. Відносні похибки.
Бачимо, найкраще наближення дозначення, одержаного за ІФН 1-ою, досягається інтерполяційною формулою Стірлінга.
Висновок. Як зазначалося вище (див.пункт 1.6), ІФС краще використовувати, для інтерполювання в середині таблиці, вчому ми і переконалися в даному прикладі, оскільки /> знаходиться всередині таблиці.
1.8.2 Приклад 2
Знайти значення функції />,заданої таблицею (табл. 6) при значенню аргументу />, використовуючиінтерполяційну формулу Ньютона для нерівновіддалених вузлів. При розрахункахвраховувати лише розділені різниці першого і другого порядків.
Таблиця 6. Значення функціїxi f(xi)
/>/>0,698
/>2,22336
/>0,706 2,24382
/>0,714 2,26446
/>0,727 2,29841
/>0,736 2,32221
/>0,747 2,35164
/>0,760 2,38690
/>0,769 2,41162 0,782 2,44777
Розв’язання:
Оскільки в умові сказановикористовувати лише розділені різниці другого і третього порядку, то формулаНьютона для нерівновіддалених вузлів (1. 7. 5) матиме вигляд:
/>,
де />.
Попередньо обчислимо необхіднізначення розділених різниць (табл. 7).
Таблиця 7. Розділені різниціі xi f(xi) f(xi,xi+1) f(xi,xi+1,xi+2) 0,698 2,22336 0,02046 0,00018 1 0,706 2,24382 0,02064 0,01331 2 0,714 2,26446 0,03395 -0,01015 3 0,727 2,29841 0,02380 0,00563 4 0,736 2,32221 0,02943 0,00583 5 0,747 2,35164 0,03526 -0,01054 6 0,760 2,38690 0,02472 0,01143 7 0,769 2,41162 0,03615 8 0,782 2,44777
Для визначення /> приймаємо />. Длязручності складаємо допоміжну розрахункову таблицю (табл. 8), звідки отримаємо:
/>
Таблиця 8. Розрахункова таблиця
/>
1.9 Програмна реалізація
1.9.1 Призначення програми
Дану програму було розроблено з метоюнадання можливості за допомогою ЕОМ обчислювати наближені значення функції увипадку, коли функція задана таблично, використовуючи для цього інтерполяційніформули для рівновіддалених вузлів (1. 2. 7), (1. 2. 11), (1. 3. 4), (1. 3. 6),(1. 4. 3), (1. 5. 1) та інтерполяційну формулу (1. 7. 5)- для нерівновіддаленихвузлів. Крім того, враховано можливість отримання загального виглядувідповідного інтерполяційного поліному наближення з метою подальшоговикористання при, наприклад, плануванні експериментів в біології, фізиці,хімії, географії, медицині та ін. галузях науки.
Так як програма, більшою мірою,призначення для використання в навчальних цілях, то в ній передбаченаможливість вибору початкових даних згідно варінтів лабораторних робіт,наведених в [7], що дає можливість зменшити витрати часу при введені даних длястудентів.
1.9.2 Основні процедури
Програмну реалізацію було здійснено вінтегрованому середовищі розробки Microsoft Visual Studio 2008 Team System у проекті типуVisual C# з використанням мови програмування С# на базі технології .NETFramework 2.0. Програма має назву «InterPolation».
Розглянемо основні процедури іфункції програми та їх призначення:
/> DeltaCount– функція для побудови таблиці кінцевих різниць по заданим данним (вхіднимиданими є введені користувачем значення функції типу double);
/> Fact – функція для обчисленняфакторіалів, необхідних для застосування формул (5), (9), (12), (13), (15), (16).Вхідними даними для цієї функції слугує степінь полінома n, введеного користувачем, яка має типinteger;
/> EvalNewtonNerivni – функція, якаперевіряє, чи вузли інтерполяції є рівновіддаленими, чи нерівновіддаленим. Увипадку нерівновіддалених вузлів обчислює наближене значення функції заформулою (20). Дана функція використовує вже написану функцію DeltaCount, для отриманнянеобхідних для формули данних.
/> EvalFFNewton – функція, яка застосовуєпершу інтерполяційну формулу Ньютона згідно з введеними даними і використовуючифункцію DeltaCount та функцію Fact. Результатом її виконання буденаближене значення функції згідно формули (5) типу double;
/> FFNewton – функція, що виводитьформулу (5) і обчислене згідно функції EvalFFNewton наближення функції;
/> EvalSFNewton — функція, яка застосовуєдругу інтерполяційну формулу Ньютона згідно з введеними даними і використовуючифункцію DeltaCount та функцію Fact. Результатом її виконання буде наближене значення функції згідно формули(9) типу double;
/> FFNewton – функція, що виводитьформулу (9) і обчислене згідно функції EvalSFNewton наближення функції;
Аналогіно відповідно працють функції EvalFFGauss і FFGauss для першої формули Гауса, EvalSFGauss і SFGauss для другої формули Гауса, EvalFStirling і FStirling для формули Стірлінга та EvalFBessel і FBessel для формули Бесселя.
/> GetX0 – функція для визначення умовногонуля /> відповіднодо формул, які застосовуються, тобто тут також використовується функція DeltaCount;
/> PaintPlot – функція для побудовиграфіку. В даному випадку сам графік будується в електронній таблиці Excel, результат імпортується в С# і відбувається вивід у вікнопрограми;
/> WhereIsX – функція, яка визначає, дезнаходиться х у таблиці кінцевих різниць (ближче до початку, кінця чи до середени)і відповідно до того як написано вище в теоретичній частині у випадку, коликористувач забуде обрати формулу для обчислень, сама обирає, яку формулу краще застосовувати;
Тобто це основні функції тапроцедури, окрім них в програмі ще використовуються допоміжні функції длязчитування даних, для перевірки правильності введених даних, для зберіганнярезультатів у файл, для запуску тестового прикладу, який розглядався в пункті1.8.1 і т.д.
1.9.3 Інструкція повикористанню програми
Для запуску програми «InterPolation» потрібно відкрити папкуRelease і запустити InterPolation.ехе. В результаті з’явиться вікно програми(мал. 2).
/>
Мал. 2. Інтерфейс основної формипрограми
У полі «х» вводиться значенняаргументу, для якого необхідно наближено обчислити значення функції, заданоївідповідною таблицею. У полі «степінь многочлена» користувачеві необхідноввести степінь многочленна для наближення функції. У поле «крок» потрібноввести крок h, а в полі «Розміри таблиці» вводитьсякількість даних фіксованих значень функції. Потім у відповідному віконціобирається формула, яка застосовується для наближення. Після цього натискаємокнопку «Застосувати» і у вікні ще з’являється табличка для вводу хі, уі. Післязаповнення таблиці потрібно натиснути кнопку «Інтерполяція» для того, щобпрограма виконала необхідні обчислення і видала результат. Крім того, з правогобоку є випадаючий список «Варіант», де користувач може обрати один із 30-тиваріантів вихідних даних, що містяться в [7], потім знову ж таки обрати степіньполінома, х, формули, які хоче застосовувати. В меню «Файл» користувач можеобрати «Тестовий варіант». В результаті програма виведе всі результатиобчислень згідно прикладу 1 (пункт 1.8.1) (мал. 3):
/>
Мал. 3. Тестовий варіант
В меню файл користувач також можеобрати «Зберегти». В результаті програма збереже результати роботи програми уфайл. Тип файлу визначає сам користувач. Тобто, якщо, наприклад, зберегтирезультати обчислень тестового варіанту у текстовому документі, то відкрившицей файл будемо мати наступне (мал. 4):
/>
Мал. 4. Лістинг результатів
1.9.4 Перевірка працездатності програми
Покажемо працездатність програми наприкладі 1 (пункт 1.8.1). Для цього можна самостійно ввести всі необхідні даніабо обрати в меню файл, як зазначалося вище, пункт «тестовий варіант». Як видноз результатів, отриманих при застосуванні програми (мал. 3), всі формули дають майжеоднакове наближення, окрім формули Бесселя (дану формулу краще використовуватипри />). Особливо добре це видно зграфіка. Тепер порівняємо отриманий результат із розрахунками, отриманими задопомогою електронної таблиці Excel (див. мал. 5).
/>
Мал. 5. Результати обчислень велектронній таблиці Excel
Тобто бачимо, що отримані результатидещо відрізняються (на 0,01). Це пов’язано з тим, що в електронній таблиціменша точність обчислень, ніж у програмі. Однак, збільшуючи степінь поліномаотримаємо практично однакові результати.
Код програми в додатку 1.
Література
1. ИльинВ.А., Позняк Э. Г., Основы математического анализа, ч. II.- М.: Наука, 1980,с.50
2. ДемидовичБ. П., Марон И. А., Основы вычеслительной математики, Наука, 1970.
3. http://miest.narod.ru
4. КопченоваН.В., Марон И.А. – Вычислительная математика в примерах и задачах. «Наука»Москва, 1972г.
5. ТурчакЛ.И. – Основы численных методов. «Наука» Москва, 1987г.
6. ВержбицкийВ. М., Численные методы. Математический анализ и обыкновенные дифференциальныеуравнения. «Высшая школа» Москва, 2001
7. ВоробьеваГ. Н., Данилова А. Н. Практикум по вычислительной матиматике, изд.-II, «Высшаяшкола», Москва, 1990
8. Калиткин Н. П., Численные методы. — М.: Наука, 1978
9. Полия Г.,Сеге Г. Теория функций (специальная часть).- М., 1978
10. БусловВ.А., Яковлев С.Л. Численные методы ІІ. Решение уравнений. Курс лекций.Санкт-Петербург, 2001
11. Бахвалов Н.С.,Жидков Н.П., Кобельников Г.М. — Численные методы, М., Наука, 1987
12. ХаусхолдерА. С., Основы численногоанализа.-М., 1953