Скачать

Інтерполювання функцій

Зміст

Вступ

Розділ 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 Приклад 1

1.8.2 Приклад 2

1.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)), отримаємо:

Застосовуючи для