Побудова інтерполяційного многочлена та обчислення по ньому значення функції для заданого аргументу

Інформатика, програмування

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Міжнародна «Ліга розвитку науки і освіти» (Росія)

Міжнародна асоціація розвитку науки, освіти і культури Росії

(Італія )

Міжнародний «ІНСТИТУТ УПРАВЛІННЯ»

(м. Архангельськ)

Курсова робота

З ДИСЦИПЛІНИ

«Інформатика і програмування»

Тема: «Побудова інтерполяційного многочлена та обчислення по ньому значення функції для заданого аргументу»

Архангельськ

2004

Анотація
Мета курсової: для функції заданої в таблиці побудувати інтерполяційниймногочлен і обчислити по ньому значення функції для заданого значенняаргументу. Скласти блок схему алгоритму і програму на одному з моввисокого рівня (С + +) для обчислення заданого інтерполяційногомногочлена. У програмі передбачити можливості введення будь-якого числазначень функції для чого організувати зберігання її значення за допомогоюлінійного списку.

Зміст

1. Анотація

2. Зміст

3. Глава № 1

4. Глава № 2

5. Висновок

6. Список літератури

7. Додаток

8. Програма

Введення.

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

Чисельний метод рішення задачі - це певна послідовністьоперацій над числами, тобто обчислювальний алгоритм, мовою якогоє числа і арифметичні дії. Така примітивність мовидозволяє реалізувати чисельні методи на ЕОМ, що робить їх потужними іуніверсальними інструментами дослідження. Чисельні методи використовуються втих випадках, коли не вдається знайти точне рішення виникаєматематичної задачі. Це відбувається головним чином, тому, що шуканерішення звичайно не виражається у звичних для нас елементах або іншихвідомих функціях. Навіть для досить простих математичних моделейіноді не вдається отримати результат рішення в аналітичній формі. У такихвипадках основним інструментом вирішення багатьох математичних задач виступаютьчисельні методи, що дозволяють звести рішення задачі до виконання кінцевогочисла арифметичних дій над числами, при цьому результати виходятьтакож у вигляді числових значень.

Багато чисельні методи розроблені давно, однак при ручнихобчисленнях вони могли використовуватися лише для вирішення вузького кола недуже складних завдань, і лише з появою високо продуктивних ЕОМпочався період бурхливого розвитку методів обчислювальної математики та їхвпровадження в практику. Чисельні методи придбали найважливіше значення якпотужне математичне засіб вирішення практичних завдань у різнихгалузях науки і техніки.

інтерполяція, інтерполяція, - наближене або точне знаходженнябудь-якої величини з відомим окремим значенням або інших величин,пов'язаних з нею. У первинному розумінні-відновлення функції (точнеабо наближене) із відомих її значень або значень її похідних взаданих відрізках.

Основне застосування інтерполяції - це обчислення значеннітабульованого функції для неузлових (проміжних) значень аргументу,тому інтерполяції часто називають «мистецтвом читання таблиць міжрядками ». (П. Ф. Фільчаков)

Глава 1

Основні напрямки дослідження: розв'язність завданняінтерполювання, найпростіших інтерполяційних формул, застосуванняінтерполяції для побудови наближених інтерполяційних формул,застосування інтерполяції для побудови наближених і чисельних методіввирішення різних завдань математики і її додатків.

Наближене подання функцій. Інтерпояціонние функції навідрізку за значеннями її у вузлах сітка - означає побудовиіншої функції такий, що У більш загальній постановці завданняінтерполювання функції полягає в побудови не тільки зумов збігу значень функцій і на стеку, а йзбіги в окремих вузлах похідних до якогось порядку або деякихінших співвідношень, пов'язаних і.

Зазвичай стоїться у вигляді

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

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

Найчастіше використовуючи а л г е б р а й ч е с к о е інтерполяція:
. Існує ряд явних уявлень алгебраїчних інтерполяційнихмногочленів. Наприклад інтерполяційний многочлен Лагранжа має вигляд:

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

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

На практиці найчастіше використовуються параболічні або кубічніполіномінальние сплайни. Інтерполяція кубічних сплайнів дефекту 1 дляфункції щодо сітки називає функцію, яка ємногочленів 3-го ступеня на кожному з відрізків, що належить класудвічі безперервно диференційовних функції і задовольняє умовам

При такому визначенні кубічного сплайн, він має ще вільнихпараметра, для знаходження яких на сплайн накладаються додатковікрайові умови. Наприклад або та, або деякі інші.

Поліноміальні інтерполяційний сплайн довільного ступеня mдефекту r визначається як функція, яка задовольняє, крім умов
і, ще додатково умов збігу в вузлах сітки значеньфункції і інтерпольоване функції та їх похідних додеякого порядку.

Часто при обробці емпіричних даних коефіцієнти в
визначають виходячи з вимоги мінімізації суми

- Задані числа,.

Така побудова функції називають інтерполяцією за методомнайменших квадратів.

інтерполяція функцій багатьох змінних має ряд принциповихі алгебраїчних труднощів. Наприклад у випадку алгебраїчної інтерполяціїінтерполяційний многочлен Лагранжа фіксованого ступеня, взагалі кажучи,не існує для довільної схеми різних вузлів інтерполяції. УЗокрема для функцій двох змінних такий многочлен сумарноюмірою не вище n може бути побудований по вузлах лише за умови, щоці вузли не лежать на алгебраїчної кривої порядку n.

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

інтерполяція функцій і чисельні методи. Інтерполяція функціївикористовується:

1. для заміни складно обчислює функцію іншого, що обчислюється простіше

2. для наближеного відновлення функції на всій області завдання по значенням її в окремих точках або по іншим відомим величинам

3. для отримання згладжує функцій

4. для наближеного знаходження граничних значень функції

5. в задачах прискорення збіжності послідовностей і рядів і в інших питаннях.

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

Наприклад взявши за корінь лінійного інтерполяційногоалгебраїчного многочлена, побудованого за значенням і у вузлі
або за значеннями і у вузлах і, приходятьвідповідно до методу Ньютона і методу січних

,де - розділена різниця функцій для вузлів і.

Інший підхід до побудови чисельних методів рішення рівняння
= 0 заснований на інтерполяція оберненої функції. Нехай уяк інтерполяційний формули для функції узятий інтерполяційнийалгебраїчний многочлен Лагранжа, побудований по вузлах Тодіза наступне наближення до кореня рівняння = 0 береться величина
.

Чисельне інтегрування. Апарат інтерполювання функції лежить воснові побудови багатьох квадратурні і кубатурних формул. Такого родуформули будуються шляхом заміни інтегрувальне функції на всій області або наїї складові частини інтерполяційним многочленами того чи іншого виду іподальшою інтеграцією цих многочленів. Наприклад квадратурні формулинайвищої алгебраїчної ступеня точності, так звані квадратурніформули Гаусса:

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

Викладена вище схема побудови формул для наближеного обчисленняінтегралів застосовна і в багатовимірному випадку

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

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

Інтерполяційні формула-для наближеного обчислення значеньфункції, заснованого обчислення на заміні наближаємося функціїбільш простою в якомусь сенсі функцією

| | |

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

У ряді випадків (наприклад, при інтерполяція алгебраїчнимимногочленами) параметри можуть бути явно виражені з системи, татоді безпосередньо використовується для наближеного обчисленнязначень функції.

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

Інтерполяційні формула Еверетта:
Інтерполяційні формули Грегорі-Ньютона побудовані за тих, що сходять абовисхідним різницям, найбільш доцільно застосовувати на початку чи кінцітаблиці. При цьому для досягнення високого ступеня точності іноді доводитьсярозглядати різниці, віддалені досить далеко від нас цікавлятьзначень функції або. Тому на середніх ділянках таблиці кращерезультати дають Інтерполяційні формули, побудовані на базі центральнихрізниць, тобто різниць, які найближче розташовані до центральноїсотці, яка містить.

До інтерполяційним формулами з центральними дивовижними речами відносятьсяформули Гауса, Стірлінга, Бесселя, Еверетта і багато інших; формула
Еверетта одержала найбільше поширення, вона була отримана 1900:

де;;.

Формулі Еверетта так само можна надати форму, найбільш зручну дляобчислення:

якщо для її коефіцієнтів ввести позначення

Коефіцієнти Кращий час обчислювати за такою рекурентнихформулі, яка безпосередньо випливає з:
;;

Таблиця різниць:
| x | y | [pic ||||| | | |] | | | | |
| [pi | [pi | [pic ||||| | c] | c] |] | | | | |
| [pi | [pi | [pic ||||| | c] | c] |] | | | | |
| [pi | [pi | [pic ||||| | c] | c] |] | | | | |
| [pi | [pi | [pic ||||| | c] | c] |] | | | | |
| [pi | [pi | [pic | | | | |
| c] | c] |] | | | | |
| [pi | [pi | [pic | | | | |
| c] | c] |] | | | | |
| [pi | [pi | [pic | | | | |
| c] | c] |] | | | | |
| [pi | [pi | [pic | | | | |
| c] | c] |] | | | | |
| [pi | [pi | | | | | |
| c] | c] | | | | | |

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

Тестовий приклад.

П р и м е р. Функція задана таблицею на сегменті.
Визначимо за допомогою інтерполяції значення.

Р е ш е н и е. За даними значень функції складаємо таблицюрізниць (табл. 1), з яких видно, що четверті різниці в даномуприкладі практично рівні постійні, а п'ятий різниці практично рівнінулю, і тому ми їх в подальших обчисленнях не будемо брати доувагу.

Приймаються = 0,85; = 0,9; = 0,874.

Тоді = 0,8273695; = 0,8075238, і, далі, так як крок таблиці = 0,05, то

Т а б л и ц а 2
| x | | | | | | |
| 0.6 | 0.9120049 | -0.014873 | -0.001057 | 0.000029 | 0.000002 | -0.000000 |
| 0 | | 3 | 4 | 5 | 1 | 4 |
| 0.6 | 0.8971316 | -0.015930 | -0.001027 | 0.000031 | 0.000001 | 0.0000002 |
| 5 | | 7 | 9 | 6 | 7 | |
| 0.7 | 0.8812009 | -0.016958 | -0.000996 | 0.000033 | 0.000001 | -0.000000 |
| 0 | | 6 | 3 | 3 | 9 | 5 |
| 0.7 | 0.8642423 | -0.017954 | -0.000963 | 0.000035 | 0.000001 | 0.0000001 |
| 5 | | 9 | 0 | 2 | 4 | |
| 0.8 | 0.8462874 | -0.018917 | -0.000927 | 0.000036 | 0.000001 | |
| 0 | | 9 | 8 | 8 | 5 | |
| 0.8 | 0.8273695 | -0.019845 | -0.000891 | 0.000038 | | |
| 5 | | 7 | 0 | 3 | | |
| 0.9 | 0.8075238 | -0.020736 | -0.000852 | | | |
| 0 | | 7 | 7 | | | |
| 0.9 | 0.7867871 | -0.021589 | | | | |
| 5 | | 4 | | | | |
| 1.0 | 0.7651977 | | | | | |
| 0 | | | | | | |

Т а б л и ц а 2
| Еверетта |
| [p | | |
| ic | | |
|] | | |
| 0 | 0.52000 | 0.8227369 |
| 1 | | 5 |
| 2 | -0.0632 | -0.000927 |
| | 3 | 8 |
| | 0.01179 | 0.0000014 |
| 0 | 0.48000 | 0.8075238 |
| 1 | | |
| 2 | -0.0615 | -0.000891 |
| | 7 | 0 |
| | 0.01160 | 0.0000015 |
| |

Всі обчислення за формулою Еверетта представлені в табл. 2.

Всі необхідні значення різниць (і самої функції, які ми втабл. 2 позначили як різниці нульового порядку) взяті з табл. 1.
Перші три рядки в табл. 2 заповнені значеннями для і, анаступні три рядки відповідно значеннями для і.
Перемноживши (не знімаючи проміжних результатів) коефіцієнти нарозташовані в тому ж рядку, ми і отримаємо шукане значення функції
, Як суму добутків

Перевірка здійснюється безпосередньо за допомогою степеневого ряду длярозглянутої функції Еверетта згідно з яким отримаємо

ГОЛОВА № 2
MAIN

Висновок

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

Список літератури

1. Архангельський Н.А. Обчислювальні методи алгебри у прийомах і завдання. М.: МАИ, 1976.

2. Васильєв Ф.П. Чисельні методи розв'язування екстремальних задач. М.:

Наука, 1988.

3. Васильків Ф.В., Василькова М.М. Комп'ютерні технології обчислень у математичному моделюванні: Учеб. Посібник. М.:

Фінанси і статистика, 1999.

4. Фільчаков П.Ф., Довідник з вищої математики. Київ: Наукова думка, 1974.

5. Фільчаков П.Ф., Чисельні методи. Київ: Наукова думка, 1976.

6. Велика математична енциклопедія. М.: Олма-Пресс, 2004

7. Демидович Б.П., Марон И.А. Основи обчислювальної математики. М.:

Наука, 1970.

8. Тихонов А.Н., Вступні лекції з прикладної математики. М.:

Наука, 1984.

9. Каліткін М.М., Чисельні методи. М.: Наука, 1987.

10. Корн Г., Корн Т. Справочник по математиці. М.: Наука, 1984.

-----------------------

початок l_msp = NULL; l_fll = NULL; l_f = NULL; w_u = NULL; r_u = NULL; l_u = NULL; w_v = NULL; r_v = NULL; l_v = NULL;

h = FileFunction () ;

w_f = l_f;

TableMin ();

TableMax ();

BBEDuTE X =

u = UX (x, h);

VX (u);

p = Summa ();

«OTBET:» p

Кінець

початок

! feof (in)

l_f == NULL

l_w = w_f

R_f-> radr = w_f

Ні

так

fscanf (in, "% f", & w_f -> x); fscanf (in, "% f", & w_f-> y);

R_f = w_f;

W_f = l_f;

W_f = l_f-> radr;

H = (w_f-> x) - (l_f-> x)

FileFunction ()

TableMin

початок

s = w_f-> y; w_f = w_f-> radr; s1 = w_f-> y; p = s1-s;

L_msp == NULL

L_msp = w_msp;

R_msp-> radr1 = w_msp

так

немає

l_fll == NULL

R_msp-> radr1 = w_msp

L_msp = w_msp;

так

немає

w_fll-> a = p; r_fll = w_fll; w_msp-> z = p; r_msp = w_msp;

w_f! = r_f

немає

w_msp = l_msp;

так

r_msp = w_msp; w_msp = l_msp;

w_msp! = r_msp

w_msp-> z = p;

w_msp-> z = p; l_msp = w_msp;

L_msp == NULL

s = c; w_msp = w_msp-> radr1; c = w_msp-> z ; s1 = w_msp-> z; p = s1-s; r_fll-> radr2 = w_fll; w_fll-> a = p; r_fll = w_fll; r_msp-> radr1 = w_msp;

c = w_msp - > z; l_msp = NULL;

i = 1; iradr; i ++;

I = (i/2)

w_f = l_f; i> = 1; i -

w_f = w_f-> radr;

u = (x-(w_f-> x))/h; l_u = w_u; w_u-> u = u; r_u = w_u;

i = 1; iu); r_u-> uadr = w_u; w_u-> u = u1; r_u = w_u;

Кінець

VX (float u)

початок

v = 1-u; l_v = w_v; r_v-> vadr = w_v; w_v-> v = v; r_v = w_v ;

i = 1; iv); r_v-> vadr = w_v; w_v-> v = v1; r_v = w_v;

Кінець

Summa ( )

початок

i = 1; w_f = l_f; w_fll = l_fll; w_u = l_u; w_v = l_v;

w_f! = r_f

w_f = w_f-> radr; i ++;

I = i/2

w_f = l_f; i> = 1; i -

w_f = w_f-> radr;

s = (w_f-> y) * (w_v-> v); w_f = w_f-> radr; s1 = (w_f-> y) * (w_u - > u); w_f = l_f;

w_f! = r_f

w_f = w_f-> radr; i ++;

i + +; j = i;

; i> = 1; i -

w_fll = w_fll-> radr2;

i = j;

i = (( i/2) -1); i> = 1; i -

w_fll = w_fll-> radr2;

w_v = w_v-> vadr; s = s + (w_fll - > a) * (w_v-> v); i = j;

i = ((i/2)); i> = 1; i -

w_fll = w_fll -> radr2;

w_fll! = r_fll

i == 0

j -;

i = j; j = i-1; i = j;

w_fll = l_fll; w_f = l_f;

Кінець

p = s1 + s;

w_u! = r_u

i = j * 2;

w_fll = w_fll-> radr2;

i = ((i/2)); i > = 1; i -, j + +

w_u = w_u-> uadr; s1 = s1 + (w_fll-> a) * (w_u-> u); i = j-1; j = 0; i = i-1;

i = j-1;

w_fll = w_fll-> radr2;

; i> = 1; i -

j = i;

j = i; w_u = l_u;

w_f = w_f-> radr; i ++;

w_f! = r_f

Кінець