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

1 2 3 4 5

Ім'я файлу: курсач.docx
Розширення: docx
Розмір: 367кб.
Дата: 03.05.2023
скачати
Пов'язані файли:
Лікарські чаї.docx
interaktyvni_formy_roboty.docx
стрельченко 26.docx
Додатки запоріжавтоматика.docx
ВР1715 доповідь.doc
Синтаксична організація ( доповідь).docx
Лабораторне заняття 4 (12 год).doc
Курсова робота Виктория.docx

Міністерство освіти і науки України Вінницький національний технічний університет

Факультет інформаційних технологій та комп'ютерної інженерії Кафедра комп'ютерних наук

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

з дисципліни «Чисельні методи»

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

08-22.КР.ЧМ.13.19.147 ПЗ

Студента2 курсу, групи 2КН-19б спеціальності 122 – «Комп’ютерні науки» МолдавановаВ.В. (прізвище та ініціали) Керівник: к.т.н., доцент Крилик Л.В. Національна шкала Кількість балів: Оцінка: ECTS Члени комісії:
(підпис)	(прізвище та ініціали)
(підпис)	(прізвище та ініціали)

м.Вінниця, 2021 рік

Факультет інформаційних технологій та комп’ютерної інженерії

ЗАТВЕРДЖУЮ

Зав. кафедри КН, проф., д.т.н.

А. А. Яровий

(підпис)

«»2021 р.

ІНДИВІДУАЛЬНЕ ЗАВДАННЯ

на курсову роботу з дисципліни «Чисельні методи» студентаМолдавановаВ.В факультету ІТКІ, групи 2КН-19б

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

Вихідні дані:

Кількість вузлів інтерполювання не більше 20.
Кількість значущих цифр m=5.

Зміст до курсової роботиІндивідуальне завдання Анотація

Вступ

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

Висновки

Перелік джерел посилань

Дата видачі «»2021 р. Керівник

(підпис)
Завдання отримав

(підпис)

АНОТАЦІЯ

Об'єктом дослідження є друга інтерполяційна формула Ньютона. Розроблено оптимальний алгоритм та програму в середовищі С++, як за розміром пам'яті, необхідної для збереження даних, які обчислюються під час виконання алгоритму, так і за кількістю арифметичних операцій для обчислення за основною формулою. Програма має зручний та наочний інтерфейс, який максимально спрощує роботу з нею, та автоматичну перевірку коректності даних, що вводяться.

ЗМІСТ

ВСТУП 5

АНАЛІЗ ТЕОРЕТИЧНОЇ БАЗИ МЕТОДІВ ІНТЕРПОЛЮВАННЯ ФУНКЦІЙ 6
1. Інтерполяція. Аналіз методів інтерполювання функцій 6
2. Скінченні різниці та їх властивості 8
3. Другий інтерполяційний многочлен Ньютона 10
РОЗРОБКА АЛГОРИТМІВ ТА ВИБІР ОПТИМАЛЬНОГО АЛГОРИТМУ 17
ПРИКЛАД ПРОГРАМИ ОБЧИСЛЕННЯ ЗНАЧЕННЯ ФУНКЦІЇ ЗА ДРУГОЮ ІНТЕРПОЛЯЦІЙНОЮ ФОРМУЛОЮ НЬЮТОНА 21
1. Інструкція користувача 21
2. Лістинг програми 21
3. Опис програми 24
4. Тестування програми 25

ВИСНОВКИ 26

ПЕРЕЛІК ДЖЕРЕЛ ПОСИЛАНЬ 27

ВСТУП

Актуальність теми

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

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

Мета дослідження

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

Задачі дослідження:

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

Об'єкт дослідження. Об'єктом дослідження є друга інтерполяційна формула Ньютона.

Структура курсової роботи

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

АНАЛІЗ ТЕОРЕТИЧНОЇ БАЗИ МЕТОДІВ ІНТЕРПОЛЮВАННЯ ФУНКЦІЙ

Інтерполяція. Аналіз методів інтерполювання функцій

До обчислювальних задач аналізу звичайно відносять методи інтерполяції і наближення функцій, які використовуються, зокрема, в чисельних процедурах для локальної апроксимації експериментальних даних. Як відомо, інтерполяцію використовують для наближеного обчислення значень різних функцій. В даному розділі розглядаються найпростіші інтерполяційні формули: многочлен Лагранжа, схема Горнера, схема Ейткіна, формули Ньютона тощо. Формула Лагранжа дає можливість знайти вираз інтерполяційного многочлена у явному вигляді. Якщо треба обчислити лише значення функції у певній точці, доцільно застосувати схему Ейткіна. Особливістю цієї схеми є однотипність обчислень. Інтерполяційну схему Ейткіна використовують тоді, коли вузли інтерполювання не є рівновіддаленими, а також при оберненому інтерполюванні та екстраполюванні функції. Інтерполяційні формули Ньютона також мають певні переваги. Адже якщо до заданої системи рівновіддалених вузлів інтерполювання додати ще один, то відповідний многочлен Лагранжа треба будувати заново, а в многочлені Ньютона додається лише один новий доданок, а вже обчислені залишаються без змін.

Нехай на відрізку ^[𝑎; 𝑏^]визначено певний клас функцій ^{𝑃(𝑥)^}, наприклад клас алгебраїчних многочленів, а в точках 𝑥₀, 𝑥₁, … , 𝑥_𝑛цього проміжку задано значення деякої функції 𝑦 = 𝑓⁽𝑥₁⁾, … , 𝑦_𝑛= 𝑓(𝑥_𝑛) . Наближену заміну функції

𝑓 на відрізку ^[𝑎; 𝑏^]однією з функцій 𝑃(𝑥) цього класу так, щоб функція 𝑃(𝑥) в

точках 𝑥₀, 𝑥₁, … , 𝑥_𝑛набувала тих самих значень, що й функція 𝑓 , тобто щоб

𝑃⁽𝑥_𝑖⁾= 𝑦_𝑖(𝑖 = 0,1, … , 𝑛), називають інтерполюванням або інтерполяцією. Точки

𝑥₀, 𝑥₁, … , 𝑥_𝑛називають вузлами інтерполювання, функцію 𝑃(𝑥) інтерполюючою функцією, а формулу 𝑓(𝑥) ≈ 𝑃(𝑥), за допомогою якої обчислюють значення функції 𝑓 у проміжку ^[𝑎; 𝑏^]– інтерполяційною формулою.

З геометричного погляду задача інтерполювання полягає в знаходженні кривої

𝑦 = 𝑃(𝑥) певного класу, яка проходить через точки площини з координатами

(𝑥_𝑖, 𝑦_𝑖) (𝑖 = 0,1, … , 𝑛).

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

Розглянемо задачу параболічного інтерполювання, яку сформулюємо так: в n1 різних точках x₀, x₁,..., x_nзадано значення функції f : y ₀+ f ( x₀), y₁ + f ( x₁),..., y_n+ f( x_n) треба побудувати многочлен степеня n, який задовольняв би умови:
𝑃_𝑛⁽𝑥⁾= 𝑎₀𝑥^𝑛 + 𝑎₁𝑥^𝑛−1 + ⋯ + 𝑎_𝑛−1𝑥 + 𝑎_𝑛, (1.1)

𝑃_𝑛⁽𝑥_𝑖⁾= 𝑦_𝑖(𝑖 = 0,1, … , 𝑛). (1.2)

Для визначення n1коефіцієнтів многочлена (1.1), який задовольняє умови (1.2), запишемо систему (n+1) -го лінійних рівнянь вигляду
𝑎₀𝑥^𝑛 + 𝑎₁𝑥^𝑛−1 + ⋯ + 𝑎_𝑛−1𝑥₀+ 𝑎_𝑛= 𝑦₀,

_ﻟ0 0

𝑎₀𝑥^𝑛 + 𝑎₁𝑥^𝑛−1 + ⋯ + 𝑎_𝑛−1𝑥₁+ 𝑎_𝑛= 𝑦₁,

1 1

_❪… … … … … … … … … … … … … … … … … … . ,

𝗅𝑎 𝑥^𝑛 + 𝑎 𝑥^𝑛⁻¹ + ⋯ + 𝑎 𝑥 + 𝑎 = 𝑦 .

0 𝑛

1 𝑛

𝑛−1 𝑛 𝑛 𝑛

Ця система має єдиний розв’язок, бо її визначник є визначником Вандермонда, який не дорівнює нулю, бо вузли 𝑥_𝑖(𝑖 = 0,1,2, … , 𝑛) різні. А тому й задача параболічного інтерполювання має єдиний розв’язок, тобто існує єдиний алгебраїчний многочлен вигляду (1.1), що задовольняє умови (1.2). Многочлен

𝑃_𝑛⁽𝑥⁾, який задовольняє умови (1.2) називають інтерполяційним многочленом, наближену рівність 𝑓(𝑥) ≈ 𝑃_𝑛⁽𝑥⁾– інтерполяційною формулою, а різницю

𝑅_𝑛⁽𝑓, 𝑥⁾𝑓⁽𝑥⁾− 𝑃_𝑛⁽𝑥⁾– залишковим членом інтерполяційної формули. Хоч

інтерполяційний многочлен, що задовольняє умови (1.2), і єдиний, проте можливі

різні форми його запису.

Визначимо класичні методи інтерполяції:

інтерполяція Лагранжа;
інтерполяція за формулами Ньютона;
інтерполяція за схемою Ейткіна;
інтерполяція за формулами центральних різниць (Гаусса, Стірлінга, Бесселя);
обернене інтерполювання.

^{Розглянемо}^дані^методи^{детальніше.}^{Інтерполяцій}́ ^ний^{многочле}_́^нЛагранжа — многочлен мінімального степеня, що приймає дані значення у даному наборі точок. Для (n+1) пар чисел (𝑥₀; 𝑦₀), (𝑥₁; 𝑦₁), … , (𝑥_𝑛; 𝑦_𝑛) де всі 𝑥_𝑖різні, існує єдиний многочлен L(x) степеня не більшого від n, для якого L(𝑥_𝑖)= 𝑦_𝑖. У найпростішому випадку 𝑛 = 1 - це лінійний многочлен, графік якого — пряма, що проходить через дві задані точки. Загальний вигляд многочлена Лагранжа:
𝑛

_𝐿₍_𝑥₎₌_∑⁽𝑥 − 𝑥₀⁾⁽𝑥 − 𝑥₁⁾… ⁽𝑥 − 𝑥_𝑖−1⁾⁽𝑥 − 𝑥_𝑖+1⁾… ⁽𝑥 − 𝑥_𝑛⁾_𝑦_,

𝑛

𝑖=0

⁽𝑥_𝑖− 𝑥₀⁾⁽𝑥_𝑖− 𝑥₁⁾… ⁽𝑥_𝑖− 𝑥_𝑖−1⁾⁽𝑥_𝑖− 𝑥_𝑖+1⁾⁽𝑥_𝑖− 𝑥_𝑛⁾^𝑖

а наближена рівність

𝑓⁽𝑥⁾≈ 𝐿_𝑛⁽𝑥⁾

називається інтерполяційною формулою Лагранжа [3-6].

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

Якщо функцію fзадано в двох точках 𝑥₀, 𝑥₁, то її значення в точці 𝑥 ∈ (𝑥₀, 𝑥₁) можна обчислити за формулою лінійного інтерполювання вигляду:

𝑃 ⁽𝑥⁾= ¹

𝑦₀𝑥₀− 𝑥_|_.

0,1

_𝑥₁_−𝑥₀^|𝑦₁𝑥₁− 𝑥

Якщо в (n+1-му вузлах інтерполювання 𝑥_𝑖(𝑖 = 0,1,2, … , 𝑛) функція fнабуває значень 𝑦_𝑖(𝑖 = 0,1,2, … , 𝑛) , то значення інтерполяційного многочлена степеня n в точці 𝑥 ∈ (𝑥₀, 𝑥₁), що не збігається з вузлами інтерполювання, можна обчислити за формулою:

^𝑃0,1,…,𝑛

⁽𝑥⁾= ¹

𝑥_𝑛−𝑥₀

_|^𝑃0,1,…,𝑛−1⁽^𝑥⁾^𝑥0 ⁻^𝑥_|_.

^𝑃1,2,…,𝑛⁽^𝑥⁾^𝑥𝑛 ⁻^𝑥

Скінченні різниці та їх властивості

Темою курсової роботи є інтерполяція функції за другою формулою Ньютона. Розглянемо детально перший інтерполяційний многочлен Ньютона. Для роботи з даним методом потрібно ознайомитися з поняттям «скінченних різниць» та їх властивостями.

Нехай 𝑦_𝑖(𝑖 = 0,1,2, … , 𝑛) – значення функції 𝑓, обчислені для рівновіддалених значень аргументу 𝑥_𝑖(𝑖 = 0,1,2, … , 𝑛), 𝑥_𝑖+1− 𝑥_𝑖= ℎ (𝑖 = 0,1,2, … , 𝑛 − 1) , де h – крок таблиці. Скінченними або табличними, різницями першого порядку, або першими різницями, називають числа, які дорівнюють приростам значень функцій:
𝑦₁− 𝑦₀= 𝑓⁽𝑥₀+ ℎ⁾− 𝑓⁽𝑥₀⁾= ∆𝑦₀= ∆𝑥₀,

𝑦₂− 𝑦₁= 𝑓⁽𝑥₀+ 2ℎ⁾− 𝑓⁽𝑥₀+ ℎ⁾= ∆𝑦₁= ∆𝑓⁽𝑥₀+ ℎ⁾,

𝑦_𝑛− 𝑦_𝑛−1= 𝑓⁽𝑥₀+ 𝑛ℎ⁾− 𝑓⁽𝑥₀+ ⁽𝑛 − 1⁾ℎ⁾= ∆𝑦_𝑛−1= ∆𝑓⁽𝑥₀+ ⁽𝑛 − 1⁾ℎ⁾.

Прирости різниць першого порядку називають різницями другого порядку або другими різницями:
∆²𝑦₀= ∆𝑦₁− ∆𝑦₀, ∆²𝑦₁= ∆𝑦₂− ∆𝑦₁, … , ∆²𝑦_𝑛−2= ∆𝑦_𝑛−1− ∆𝑦_𝑛−2.

Взагалі, різниці будь-якого порядку 𝑘, або 𝑘 -i різниці, утворюються з різниць (𝑘 − 1)-го порядку за формулами:
∆^𝑘𝑦₀= ∆^𝑘−1𝑦₁− ∆^𝑘−1𝑦₀,

∆^𝑘𝑦₁= ∆^𝑘−1𝑦₂− ∆^𝑘−1𝑦₁,

∆^𝑘𝑦_𝑚= ∆^𝑘−1𝑦_𝑚+1− ∆^𝑘−1𝑦_𝑚.

Вважають, що за означенням ∆⁰𝑦_𝑘=𝑦_𝑘.

Послідовні різниці зручно записувати у вигляді таблиць. Використовують

дві форми таблиць: діагональну (табл. 1.1) і горизонтальну (табл. 1.2) [4-12].
Таблиця 1.1 – Діагональна таблиця скінченних різниць

𝑥_𝑖	𝑦_𝑖	∆𝑦_𝑖	∆²𝑦_𝑖	∆³𝑦_𝑖	∆⁴𝑦_𝑖	∆⁵𝑦_𝑖
𝑥₀	𝑦₀
		∆𝑦₀
𝑥₁	𝑦₁		∆²𝑦₀
		∆𝑦₁		∆³𝑦₀
𝑥₂	𝑦₂		∆²𝑦₁		∆⁴𝑦₀
		∆𝑦₂		∆³𝑦₁		∆⁵𝑦_𝑖
𝑥₃	𝑦₃		∆²𝑦₂		∆⁴𝑦₁
		∆𝑦₃		∆³𝑦₂
𝑥₄	𝑦₄		∆²𝑦₃
		∆𝑦₄
𝑥₅	𝑦₅

Діагональну таблицю різниць дістають тоді, коли табличні різниці в кожному стовпці записують між відповідними значеннями зменшуваного і від’ємника. В горизонтальній таблиці табличні різниці записують в одному рядку з від’ємником.
Таблиця 1.2 – Горизонтальна таблиця скінченних різниць

𝑥_𝑖	𝑦_𝑖	∆𝑦_𝑖	∆²𝑦_𝑖	∆³𝑦_𝑖	∆⁴𝑦_𝑖	∆⁵𝑦_𝑖
𝑥₀	𝑦₀	∆𝑦₀	∆²𝑦₀	∆³𝑦₀	∆⁴𝑦₀	∆⁵𝑦_𝑖
𝑥₁	𝑦₁	∆𝑦₁	∆²𝑦₁	∆³𝑦₁	∆⁴𝑦₁
𝑥₂	𝑦₂	∆𝑦₂	∆²𝑦₂	∆³𝑦₂
𝑥₃	𝑦₃	∆𝑦₃	∆²𝑦₃
𝑥₄	𝑦₄	∆𝑦₄
𝑥₅	𝑦₅
∑		4 ∑ ∆𝑦_𝑖 𝑖=0	3 ∑ ∆²𝑦_𝑖 𝑖=0	2 ∑ ∆³𝑦_𝑖 𝑖=0	1 ∑ ∆⁴𝑦_𝑖 𝑖=0	∆⁵𝑦_𝑖
S	𝑦₅− 𝑦₀	∆𝑦₄− ∆𝑦₀	∆²𝑦₃− ∆²𝑦₀	∆³𝑦₂− ∆³𝑦₀	∆⁴𝑦₁− ∆⁴𝑦₀

Як у діагональній, так і в горизонтальній таблицях скінченні різниці всіх порядків умовимось записувати в одиницях нижчого розряду значень функцій у вузлах інтерполювання. Далі дотримуватимемося цього правила. Щоб проконтролювати правильність обчислення табличних різниць, таблицю доповнюють двома додатковими рядками  і S . У рядок  заносять суми різниць
кожного із стовпців, а в рядок S – різниці між крайніми (останньою і першою) різницями кожного стовпця. Легко впевнитись, що сума різниць будь-якого стовпця таблиці дорівнює різниці між крайніми різницями попереднього стовпця.

Властивості скінченних різниць:

Скінченні різниці сталої C дорівнюють нулю, тобто ∆^𝑘𝐶 = 0.
Сталий множник C можна виносити за знак скінченної різниці

∆^𝑘(𝐶𝑓⁽𝑥⁾) = 𝐶∆^𝑘𝑓(𝑥).

Скінченні різниці алгебраїчної суми функцій дорівнюють алгебраїчній сумі скінченних різниць цих функцій, тобто:

∆^𝑘(𝑓⁽𝑥⁾± 𝑔⁽𝑥⁾) = ∆^𝑘𝑓(𝑥) ± ∆^𝑘𝑔(𝑥).

Скінченна різниця функції 𝑓⁽𝑥⁾= 𝑥^𝑛 (n– натуральне)

∆⁽𝑥^𝑛⁾= 𝑛ℎ𝑥^𝑛−1 + ^𝑛(𝑛⁻¹⁾ℎ²𝑥^𝑛−2 + ⋯ + 𝑛ℎ^𝑛−1𝑥 + ℎ^𝑛,

2!

справді,

∆⁽𝑥^𝑛⁾= (𝑥 + ℎ)^𝑛 − 𝑥^𝑛.

Другий інтерполяційний многочлен Ньютона

Якщо значення аргументу лежить ближче до кінця відрізка інтерполювання, то застосувати першу інтерполяційну формулу Ньютона невигідно, бо не вистачатиме скінченних різниць функції вищих порядків. Якщо, наприклад, треба обчислити значення функції в точці x(x_n_₂,x_n_₁), то для першого інтерполяційного многочлена Ньютона є лише перша і друга різниці, а для значення аргументу x(x_n_₁,x_n) – лише перша різниця функції.

Тому в кінці відрізка інтерполювання користуються многочленом вигляду:
𝑃₍_𝑥)= 𝑏₀+ 𝑏₁⁽𝑥 − 𝑥₁⁾+ 𝑏₁⁽𝑥 − 𝑥_𝑛⁾⁽𝑥 − 𝑥_𝑛−1⁾+

+ ⋯ +𝑏_𝑛⁽𝑥 − 𝑥_𝑛⁾⁽𝑥 − 𝑥_𝑛−1⁾… ⁽𝑥 − 𝑥₁⁾_.(1.3)
^{Коефіцієнти}^b0, ^b1, ^b2, …, ^bn многочлена (1.3) визначають так, щоб його значення в рівновіддалених вузлах інтерполювання збігалося із значенням відповідної функції, тобто щоб виконувались умови ^Pn⁽^xi⁾⁼^yi⁽ⁱ⁼^0,1,^...,ⁿ⁾^[5-12].
Підставивши послідовно в формулу (1.3) замість x значення x_n, x_n_₁, ..., x₀, знаходимо коефіцієнти b₀ , b₁ , ..., b_n. Якщо в (1.3) покласти x = x_n, то дістанемо

b₀ y_n.Аналогічно, поклавши x x_n_₁, маємо

^𝑦𝑛−1 ⁼^𝑏0 ⁺^𝑏1⁽^𝑥𝑛−1 ⁻^𝑥𝑛⁾.
Але x_n_₁ x_n hі b₀ y_n, тому
_𝑏₌^𝑦𝑛 ⁻^𝑦𝑛−1 ₌^𝛥𝑦𝑛−1_.