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

МИНИСТЕРСТВО ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦИИ.

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

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

(Италия).

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

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

КУРСОВА РАБОТА.

ПО ДИСЦИПЛИНЕ.

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

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

|Выполнил: студент економічного | |факультету, групи 12-ТИ Воробйов | |А.А. | |Перевірив: Горяшин Ю. В. | | |.

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

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

1. Аннотация.

2. Содержание.

3. Глава № 1.

4. Глава № 2.

5.

Заключение

.

6.

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

.

7. Приложение.

8. Программа.

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

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

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

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

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

Глава 1.

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

Близьке уявлення функцій. Интерпояционные функції [pic] на відрізку [pic] по значенням їх у вузлах [pic] сітка [pic]- означає постоение інший функції [pic] такий, що [pic] У загальної постановці завдання интерполирования функції [pic] полягає у постоении [pic] з умов збіги значень функцій [pic] і [pic] на стеці [pic], а й збіги окремими вузлах похідних до порядку чи деяких інших співвідношень, пов’язаних [pic] і [pic].

Зазвичай [pic] будується в виде.

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

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

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

[pic].

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

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

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

[pic].

За такої визначенні кубічного сплайна, вона має ще вільних параметра, перебування яких сплайн накладаються додаткові крайові умови. Наприклад [pic] чи [pic] і [pic], чи деякі другие.

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

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

[pic] [pic]- задані числа, [pic].

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

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

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

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

1. для заміни складно вычисляемой функції інший, вычисляемой проще.

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

3. щоб одержати сглаживающих функций.

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

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

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

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

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

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

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

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

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

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

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

Интерполяционная формуладля наближеного обчислення значень функції [pic], заснованого обчислення на заміні приближаемой функції [pic] простіший що нето сенсі функцией.

[pic] |[pic] |[pic] |.

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

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

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

Интерполяционная формула Эверетта: Интерполяционные формули ГрегоріНьютона створені за спадним чи висхідним разностям, найдоцільніше запровадити у початку або кінець таблиці. У цьому задля досягнення високого рівня точності інколи доводиться розглядати різниці, віддалені досить далеке від цікавлять нас значень функції [pic] чи [pic]. Тому на згадуваній середніх ділянках таблиці краще результати дають интерполяционные формули, побудовані з урахуванням центральних разностей, тобто разностей, які стоять найближче схильні до центральної сотці, що містить [pic].

До интерполяционным формулам з центральними разностями ставляться формули Гаусса, Стирлинга, Бесселя, Эверетта і ще; формула Эверетта отримала найбільшого поширення, її було отримано 1900 г.:

[pic] де [pic]; [pic]; [pic].

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

[pic] для її коефіцієнтів запровадити позначення [pic] [pic] [pic] [pic] [pic] [pic] [pic].

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

Таблиця разностей: |x |y |[pic|[pic]|[pic]|[pic]|[pic]| | | |] | | | | | |[pi|[pi|[pic|[pic]|[pic]|[pic]|[pic]| |з] |з] |] | | | | | |[pi|[pi|[pic|[pic]|[pic]|[pic]|[pic]| |з] |з] |] | | | | | |[pi|[pi|[pic|[pic]|[pic]|[pic]|[pic]| |з] |з] |] | | | | | |[pi|[pi|[pic|[pic]|[pic]|[pic]|[pic]| |з] |з] |] | | | | | |[pi|[pi|[pic|[pic]|[pic]|[pic]| | |з] |з] |] | | | | | |[pi|[pi|[pic|[pic]|[pic]| | | |з] |з] |] | | | | | |[pi|[pi|[pic|[pic]| | | | |з] |з] |] | | | | | |[pi|[pi|[pic| | | | | |з] |з] |] | | | | | |[pi|[pi| | | | | | |з] |з] | | | | | |.

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

Тестовий пример.

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

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

Приймаємо [pic]=0,85; [pic]=0,9; [pic]=0,874.

Тоді [pic]=0,8 273 695; [pic]=0,8 075 238, і, далі, оскільки крок таблиці [pic]=0,05, то.

[pic].

Т, а б л і ц, а 2 |x |[pic] |[pic] |[pic] |[pic] |[pic] |[pic] | |0.6|0.9 120 049|-0.14 873|-0.1 057|0.29|0.2|-0.0| |0 | |3 |4 |5 |1 |4 | |0.6|0.8 971 316|-0.15 930|-0.1 027|0.31|0.1|0.2| |5 | |7 |9 |6 |7 | | |0.7|0.8 812 009|-0.16 958|-0.996|0.33|0.1|-0.0| |0 | |6 |3 |3 |9 |5 | |0.7|0.8 642 423|-0.17 954|-0.963|0.35|0.1|0.1| |5 | |9 |0 |2 |4 | | |0.8|0.8 462 874|-0.18 917|-0.927|0.36|0.1| | |0 | |9 |8 |8 |5 |[pic] | |0.8|0.8 273 695|-0.19 845|-0.891|0.38| | | |5 | |7 |0 |3 | | | |0.9|0.8 075 238|-0.20 736|-0.852| | | | |0 | |7 |7 | | | | |0.9|0.7 867 871|-0.21 589| | | | | |5 | |4 | | | | | |1.0|0.7 651 977| | | | | | |0 | | | | | | |.

Т, а б л і ц, а 2 |Эверетта | |[p|[pic] |[pic] | |ic| | | |] | | | |0 |0.52 000|0.8 227 369| |1 | |5 | |2 |-0.0632|-0.927| | |3 |8 | | |0.1 179|0.14| |0 |0.48 000|0.8 075 238| |1 | | | |2 |-0.0615|-0.891| | |7 |0 | | |0.1 160|0.15| |[pic][pic] |.

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

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

Перевірка виробляється безпосередньо з допомогою статечного низки для аналізованої функції Эверетта [pic] за яким одержимо [pic].

ГЛАВА № 2 MAIN[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

Заключение

.

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

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=.

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++;

і++; 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.

Конец.