Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Комп'ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
1999
Тип роботи:
Інші
Предмет:
Системи автоматизованого проектування ЗВТ
Група:
К
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
ДЕРЖАВНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
МЕТОДИ НАБЛИЖЕННЯ ФУНКЦІЙ
І Н С Т Р У К Ц І Я
до лабораторної роботи N 2
з курсу " Чисельні методи в інформатиці "
для студентів базового напрямку 6.0804
"Комп'ютерні науки"
Затверджено
на засіданні кафедри
"Системи автоматизованого
проектування"
Протокол N 14 від 03.04.1997 р.
Львів 1999
МЕТОДИ НАБЛИЖЕННЯ ФУНКЦІЙ. Інструкція до лабораторної ро боти N 2 з дисципліни " Чисельні методи в інформатиці " для студентів базового на прямку 6.08.04 "Комп'ютерні науки" / Укл. Мотика І.І., Каркульовський В.І., Чура І.І. - Львів: Видавництво ДУ "Львівська політехніка", 1999. - 12 с.
Укладачі Мотика І.І., канд. техн. наук, доц.
Каркульовський В.І., канд. техн. наук, доц.
Чура І.І., канд. техн. наук, доц.
Відповідальний за випуск С.П.Ткаченко, канд. техн. наук, доц.
Рецензенти Федасюк Д.В., канд. техн. наук, доц.
Близнюк М.Б., канд. техн. наук, доц.
1. МЕТА РОБОТИ
Мета роботи - ознайомлення з методами наближення функцій та їх практичним застосуванням.
2. ТЕОРЕТИЧНА ЧАСТИНА
2.1. Формулювання задачі наближення функцій
Вважають, що на множині дійсних чисел X визначено деяку дійсну функцію , якщо кожному числу x з цієї множини поставлено у відпо відність одне дійсне число y з множини Y. На практиці часто трапляються ви падки, коли знайти значення y для відповідних x досить важко. Крім того, часто аналітичний вираз функції взагалі невідомий, а відомі лише її значення у скінченній кількості точок. Ці значення можуть бути знайдені в результаті спостережень чи вимірювань в якому-небудь експерименті, або в результаті обчислень. Тому викликає потреба вихідну функцію на ближено замінити (апроксимувати) деякою іншою функцією , в певному розумінні близькою до і такою, що простіше обчислюється чи дослід жується.
Тоді при всіх значеннях аргументу з множини Х вважають Функцію , називають апроксимуючою. Близькість функцій і можна, зокрема, оцінювати в метричних просторах за допомогою відстані . По-різному вводячи відстань, дістають різні конкретні випадки задачі апроксимації.
Часто апроксимуючу функцію беруть у вигляді лінійної комбіна ції функцій деякого класу, які утворюють скінченну чи зчисленну множину , причому будь-яка скінченна система елементів лінійно незалеж на. Тобто беруть у вигляді:
, (1)
де – сталі коефіцієнти.
Як функції часто використовують многочлени.
Функцію в цьому випадку називають узагальненим многочленом. Надалі розглядатимемо наближення функцій узагальненими многочленами. У цьому випадку задачу апроксимації можна сформулювати так.
Задано функцію f(x). Потрібно знайти такий узагальнений многочлен , підібрати його коефіцієнти , щоб відхилення (в деякому розумінні) функції f(x) від на заданій множині Х було найменшим.
Нехай у точках з відрізку [а,в] відомі значен ня функції y=f(x):
.
Розглянемо один з випадків апроксимації, що називається інтерполя цією. Суть його полягає в тому, що коефіцієнти многочлена (1) добирають так, щоб у точках x(i=0,1,..,n) значення функцій і f(x) збіга лися, тобто:
(i=0,1,..,n). (2)
Точки x(i=0,1,..,n) називаються вузлами інтерполювання, а много член – інтерполяційним многочленом. Формулу y=, знайдену для обчислення значень функції y=f(x), називають інтерполяційною.
Задача інтерполювання матиме єдиний розв'язок, якщо при будь-якому розміщенні вузлів (серед яких немає таких, що збігаються ) визначник системи (2) не дорівнюватиме нулю. Системи функцій, які задовольняють таку умову, називають системами Чебишова. Очевидно, вимога лінійної неза лежності системи є необхідною умовою для того, щоб ця система функцій була системою Чебишова. При інтерполюванні узагальнений много член будують за деякою Чебишовською системою функцій.
На практиці систему часто беруть у вигляді послідовності не від'ємних степенів змінної x, тобто:
(i=0,1,..,n).
Тут узагальнені многочлени є звичайними алгебраїчними много членами.
.
Інтерполювання в цьому випадку називається поліноміальним, або параболічним.
2.2. Інтерполяційний многочлен Лагранжа
Нехай у точках x(i=0,1,..,n) , з відрізка [а,в] зада но значення функції y=f(x) : y=f(x). Треба побудувати такий поліном (степеня, не вищого за n), який у вузлах набуває тих самих значень, що й функція y=f(x), тобто:
(i=0,1,..,n). (3)
Щоб дістати інтерполяційний многочлен в явному вигляді, не обов'яз ково розв'язувати систему лінійних рівнянь, його можна побудувати безпо середньо так, щоб задовольнялась умова (3).
Многочлен шукається у вигляді лінійної комбінації деяких мно гочленів степеня n, причому коефіцієнтами цієї лінійної комбінації будуть задані значення функції y=f(x) у вузлах, тобто:
, (4)
де (i=0,1,..,n) – поки що невідомі многочлени степеня n. З умови (3) випливає, що многочлени мають задовольняти умову:
.
Тоді:
. (5)
Інтерполяційний многочлен, записаний у вигляді (5), називається інтерполяційним многочленом Лагранжа. Многочлени назива ються коефіцієнтами Лагранжа.
Величина:
, (6)
яка характеризує близькість полінома L(x) до функції f(x) у деякій точці x відрізка [а,в] називається залишковим членом інтерполяційної формули , який визначає величину похибки.
Оцінка для записується у вигляді:
, (7)
де .
Якщо вузли рівновіддалені, тобто i=1,2,..,n, то оцінка для залишкового члена набирає вигляду:
(8)
де .
Таким чином, для випадку рівновіддалених вузлів .
З оцінки (7) видно, що величина похибки многочлена Лагранжа зале жить від того, як вибрано вузли інтерполювання (вони визначають функцію . Оцінити при довільному розміщенні вузлів інтерполювання досить складно. Коли вузли рівновіддалені, то поблизу центрального вузла інтерполяційні екстремуми функції невеликі, поблизу крайніх вузлів дещо більші, а якщо x виходить за крайні вузли, то швидко зростає.
Знаходження значень y=f(x), якщо значення аргументу x лежить між крайніми вузлами, називають інтерполюванням, а якщо лежить поза крайні ми вузлами – то екстраполюванням. З попереднього випливає, що при екстраполяції далеко за крайні вузли похибка може бути досить великою.
Оскільки значення часто задаються наближено, то навіть і тоді, ко ли всі проміжні обчислення виконуються точно, результат дістаємо з похиб кою. Це неусувна похибка. Неусувна похибка формули Лагранжа не переви щує величини:
, (9)
де – максимальне значення абсолютних похибок величин
y=f(x) (i=0,1,2,...,n).
Остання похибка при (відповідно ) порів няно мала і дуже повільно зростає із збільшенням n.
У процесі обчислень виникає також похибка при заокругленні проміж них результатів. Практично цю похибку можна зробити значно меншою по рівняно із неусувною (похибкою обмеження), якщо проміжні обчислення про водити з більшою кількістю цифр, ніж це вимагається для табличних значень f(x). При оцінці похибки результату слід враховувати і похибку остаточного заокруглення. Повна похибка інтерполювання дорівнює сумі всіх перелічених вище похибок.
2.3. Скінченні різниці. Інтерполяційні многочлени Ньютона
Нехай – значення деякої функції y=f(x), що відповідають рівновіддаленим значенням аргументу
.
Величина називається скінченною різницею першого поряд ку функції f(x)в точці (з кроком h) і позначається або , тобто . Скінченна різниця друго го порядку в точці xi визначається рівностями:
.
Скінченна різниця n-го порядку функції y=f(x) в точці визначається рекурентною формулою:
,
де
Скінченні різниці зручно розміщувати у вигляді таблиці:
Така таблиця називається діагональною таблицею різниць. Всі різниці будемо записувати цілими числами в одиницях молодшого розряду значень функції у вузлах інтерполювання.
x
y
…
…
…
…
…
…
…
Можна записати формулу:
, (10)
де – біномні коефіцієнти. Остання формула виражає скінченні різниці через значення функції у вузлових точках.
Нехай для функції y=f(x) задано її значення для значень ар гументу, які утворюють арифметичну прогресію (i=0,1,...,n), де h – крок таблиці. Треба побудувати многочлен степінь якого був би не більшим за n, а значення його у вузлах інтерполювання збігалися б із значен ням функції y=f(x); тобто:
(i=0,1,2,...,n). (11)
Многочлен визначається у вигляді:
(12)
Коефіцієнти у (12) визначають так, щоб виконувались умо ви (11). Після деяких перетворень і застосування раніше введених означень скінченних різниць отримують співвідношення:
(13)
Формула (13) називається першою інтерполяційною формулою Ньютона. Доведено, що існує лише один інтерполяційний многочлен n-го степеня, значення якого у вузлах інтерполяції дорівнюють значен ням функції .
Тому інтерполяційний поліном (13) збігатиметься з інтерполяційним многочленом Лагранжа, побудованим для цього випадку. Ці многочлени тільки записані в різних формах.
Формулу Ньютона (13) можна подати в зручнішому для користування вигляді. Для цього вводять нову безрозмірну змінну t за формулою , або . Тоді формула (13) набирає вигляду:
(14)
Цей вигляд першої інтерполяційної формули Ньютона називають фор мулою Ньютона для інтерполювання вперед. Таку назву вона отримала то му, що в ній використовуються значення функції, дані у вузлах, які містяться вправо від (вперед, вниз по стовпчику).
Для інтерполювання в кінці таблиці користуються іншою формулою вигляду:
(15)
Це є друга інтерполяційна формула Ньютона для інтерполювання назад. У ній використовуються скінченні різниці, розміщені в діагональній таблиці різниць по діагоналі знизу вгору.
Оскільки інтерполяційні формули Лагранжа і Ньютона – різні форми запису інтерполяційного многочлена, то оцінки залишкових членів формул Ньютона будуть такими, як і для формули Лагранжа, побудованої за такими самими даними. Тому у повну похибку результату, знайденого за формулами Ньютона, крім похибки методу, входитиме неусувна похибка, а також похиб ка округлення.
Формулу Ньютона, як і формулу Лагранжа, можна використати і для екстраполювання, тобто для обчислення значення функції в точках, які ле жать за межами таблиці. Очевидно, що перша інтерполяційна формула Ньютона застосовується для інтерполювання вперед (t>0) і екстраполювання назад (t<0), а друга – для інтерполювання назад (t<0) та екстраполювання вперед (t>0).
3. КОНТРОЛЬНІ ЗАПИТАННЯ
1. Що таке апроксимація?
2. У чому полягає задача апроксимації?
3. Як будується інтерполяційний многочлен Лагранжа?
4. Як оцінюється залишковий член формули Лагранжа?
5. Як оцінюється повна похибка методу Лагранжа?
6. Що таке скінченні різниці і як вони визначаються?
7. Як будується перша інтерполяційна формула Ньютона?
8. Що таке інтерполювання вперед і назад?
9. Як використати формули Ньютона для екстраполювання?
10. Як оцінюється точність методу Ньютона?
4. ЛАБОРАТОРНЕ ЗАВДАННЯ
1. Ознайомитись із методами наближення функцій.
2.Одержати індивідуальне завдання.
3. Провести інтерполяцію за формулою Лагранжа та формулами Ньютона. Оцінити похибки результатів.
4. Порівняти ефективність і точність даних методів.
5. ЗМІСТ ЗВІТУ
1. Мета роботи.
2. Порівняльна характеристика методів наближення функцій.
3. Результати обчислень по кожному із методів.
4. Аналіз результатів, висновки.
6. СПИСОК ЛІТЕРАТУРИ
1. Бахвалов И.С., Жидков И.П., Кобельков Г.М. Численные методы. – М.: Наука, 1987. – 600 с.
2. Жалдак М.І., Рамський Ю.С. Чисельні методи математики. – К.: Рад.шк., 1984. – 206 с.
3. Маликов В.Т., Кветный Р.И. Вычислительные методы и применение ЭВМ. – К.: Вища шк., 1989. – 216 с.
4. Самарский А.А., Гулин А.В. Численные методы. – М.: Наука, 1989. – 432 с
5. Турчак Л.И. Основы численных методов. – М.: Наука, 1987. – 320 с.
НАВЧАЛЬНЕ ВИДАННЯ
МЕТОДИ НАБЛИЖЕННЯ ФУНКЦІЙ
І Н С Т Р У К Ц І Я
до лабораторної роботи № 2
з курсу “ Чисельні методи в інформатиці”
для базового напрямку 6.0804
“Комп’ютерні науки”
Укладачі Ігор Іванович Мотика
Володимир Іванович Каркульовський
Ігор Іванович Чура
Редактор О.М.Губарєва
Видавництво Державного університету "Львівська політехніка"
Львів, вул. Ф.Колесси, 2
Формат 60х84 1/16. Папір офсетний.
Умовн.-друк.арк. 0,7. Умовн.фарбо-відб. 0,7.
Тираж 15 прим. Зам.362.
Тиражування здійснене на кафедрі САПР.
Відповідальний за тиражування
доц. Каркульовський Володимир Іванович.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора