МЕТОДИ НАБЛИЖЕННЯ ФУНКЦІЙ.. Інструкція та методичні настанови з Чисельні методи в інформатиці. Робота № 400384

Перехід до торгівельного партнера Binance

МЕТОДИ НАБЛИЖЕННЯ ФУНКЦІЙ.

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Системи автоматизованого проектуваня

Інформація про роботу

Рік:

1999

Тип роботи:

Інструкція та методичні настанови

Предмет:

Чисельні методи в інформатиці

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ ДЕРЖАВНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" МЕТОДИ НАБЛИЖЕННЯ ФУНКЦІЙ І Н С Т Р У К Ц І Я до лабораторної роботи N 2 з курсу " Чисельні методи в інформатиці " для студентів базового напрямку 6.0804 "Комп'ютерні науки" Затверджено на засіданні кафедри "Системи автоматизованого проектування" Протокол N 14 від 03.04.1997 р. Львів 1999 МЕТОДИ НАБЛИЖЕННЯ ФУНКЦІЙ. Інструкція до лабораторної роботи N 2 з дисципліни " Чисельні методи в інформатиці " для студентів базового напрямку 6.08.04 "Комп'ютерні науки" / Укл. Мотика І.І., Каркульовський В.І., Чура І.І. - Львів: Видавництво ДУ "Львівська політехніка", 1999. - 12 с. Укладачі Мотика І.І., канд. техн. наук, доц. Каркульовський В.І., канд. техн. наук, доц. Чура І.І., канд. техн. наук, доц. Відповідальний за випуск С.П.Ткаченко, канд. техн. наук, доц. Рецензенти Федасюк Д.В., канд. техн. наук, доц. Близнюк М.Б., канд. техн. наук, доц. 1. МЕТА РОБОТИ Мета роботи - ознайомлення з методами наближення функцій та їх практичним застосуванням. 2. ТЕОРЕТИЧНА ЧАСТИНА 2.1. Формулювання задачі наближення функцій Вважають, що на множині дійсних чисел X визначено деяку дійсну функцію EMBED Equation.3, якщо кожному числу x з цієї множини поставлено у відповідність одне дійсне число y з множини Y. На практиці часто трапляються випадки, коли знайти значення y для відповідних x досить важко. Крім того, часто аналітичний вираз функції EMBED Equation.3 взагалі невідомий, а відомі лише її значення у скінченній кількості точок. Ці значення можуть бути знайдені в результаті спостережень чи вимірювань в якому-небудь експерименті, або в результаті обчислень. Тому викликає потреба вихідну функцію EMBED Equation.3 наближено замінити (апроксимувати) деякою іншою функцією EMBED Equation.3, в певному розумінні близькою до EMBED Equation.3 і такою, що простіше обчислюється чи досліджується. Тоді при всіх значеннях аргументу з множини Х вважають EMBED Equation.3 Функцію EMBED Equation.3, називають апроксимуючою. Близькість функцій EMBED Equation.3 і EMBED Equation.3 можна, зокрема, оцінювати в метричних просторах за допомогою відстані EMBED Equation.3. По-різному вводячи відстань, дістають різні конкретні випадки задачі апроксимації. Часто апроксимуючу функцію EMBED Equation.3 беруть у вигляді лінійної комбінації функцій деякого класу, які утворюють скінченну чи зчисленну множину EMBED Equation.3, причому будь-яка скінченна система елементів EMBED Equation.3 лінійно незалежна. Тобто EMBED Equation.3 беруть у вигляді: EMBED Equation.3, (1) де EMBED Equation.3 – сталі коефіцієнти. Як функції EMBED Equation.3 часто використовують многочлени. Функцію EMBED Equation.3 в цьому випадку називають узагальненим многочленом. Надалі розглядатимемо наближення функцій узагальненими многочленами. У цьому випадку задачу апроксимації можна сформулювати так. Задано функцію f(x). Потрібно знайти такий узагальнений многочлен EMBED Equation.3, підібрати його коефіцієнти EMBED Equation.3, щоб відхилення (в деякому розумінні) функції f(x) від EMBED Equation.3 на заданій множині Х було найменшим. Нехай у точках EMBED Equation.3 з відрізку [а,в] відомі значення функції y=f(x): EMBED Equation.3. Розглянемо один з випадків апроксимації, що називається інтерполяцією. Суть його полягає в тому, що коефіцієнти EMBED Equation.3 многочлена (1) добирають так, щоб у точках xEMBED Equation.3(i=0,1,..,n) значення функцій EMBED Equation.3 і f(x) збігалися, тобто: EMBED Equation.3 (i=0,1,..,n). (2) Точки xEMBED Equation.3(i=0,1,..,n) називаються вузлами інтерполювання, а многочлен EMBED Equation.3 – інтерполяційним многочленом. Формулу y=EMBED Equation.3, знайдену для обчислення значень функції y=f(x), називають інтерполяційною. Задача інтерполювання матиме єдиний розв'язок, якщо при будь-якому розміщенні вузлів (серед яких немає таких, що збігаються EMBED Equation.3) визначник системи (2) не дорівнюватиме нулю. Системи функцій, які задовольняють таку умову, називають системами Чебишова. Очевидно, вимога лінійної незалежності системи EMBED Equation.3 є необхідною умовою для того, щоб ця система функцій була системою Чебишова. При інтерполюванні узагальнений многочлен будують за деякою Чебишовською системою функцій. На практиці систему EMBED Equation.3 часто беруть у вигляді послідовності невід'ємних степенів змінної x, тобто: EMBED Equation.3 (i=0,1,..,n). Тут узагальнені многочлени є звичайними алгебраїчними многочленами. EMBED Equation.3. Інтерполювання в цьому випадку називається поліноміальним, або параболічним. 2.2. Інтерполяційний многочлен Лагранжа Нехай у точках xEMBED Equation.3(i=0,1,..,n) EMBED Equation.3, з відрізка [а,в] задано значення функції y=f(x) : yEMBED Equation.3=f(xEMBED Equation.3). Треба побудувати такий поліном EMBED Equation.3(степеня, не вищого за n), який у вузлах EMBED Equation.3 набуває тих самих значень, що й функція y=f(x), тобто: EMBED Equation.3 (i=0,1,..,n). (3) Щоб дістати інтерполяційний многочлен в явному вигляді, не обов'язково розв'язувати систему лінійних рівнянь, його можна побудувати безпосередньо так, щоб задовольнялась умова (3). Многочлен EMBED Equation.3 шукається у вигляді лінійної комбінації деяких многочленів степеня n, причому коефіцієнтами цієї лінійної комбінації будуть задані значення функції y=f(x) у вузлах, тобто: EMBED Equation.3, (4) де EMBED Equation.3 (i=0,1,..,n) – поки що невідомі многочлени степеня n. З умови (3) випливає, що многочлени EMBED Equation.3 мають задовольняти умову: EMBED Equation.3. Тоді: EMBED Equation.3. (5) Інтерполяційний многочлен, записаний у вигляді (5), називається інтерполяційним многочленом Лагранжа. Многочлени називаються коефіцієнтами Лагранжа. Величина: EMBED Equation.3, (6) яка характеризує близькість полінома LEMBED Equation.3(x) до функції f(x) у деякій точці x відрізка [а,в] називається залишковим членом інтерполяційної формули EMBED Equation.3, який визначає величину похибки. Оцінка для EMBED Equation.3 записується у вигляді: , (7) де EMBED Equation.3. Якщо вузли рівновіддалені, тобто EMBED Equation.3 i=1,2,..,n, то оцінка для залишкового члена набирає вигляду: EMBED Equation.3 (8) де EMBED Equation.3. Таким чином, для випадку рівновіддалених вузлів EMBED Equation.3. З оцінки (7) видно, що величина похибки многочлена Лагранжа залежить від того, як вибрано вузли інтерполювання (вони визначають функцію EMBED Equation.3. Оцінити EMBED Equation.3 при довільному розміщенні вузлів інтерполювання досить складно. Коли вузли рівновіддалені, то поблизу центрального вузла інтерполяційні екстремуми функції EMBED Equation.3 невеликі, поблизу крайніх вузлів дещо більші, а якщо x виходить за крайні вузли, то EMBED Equation.3 швидко зростає. Знаходження значень y=f(x), якщо значення аргументу x лежить між крайніми вузлами, називають інтерполюванням, а якщо лежить поза крайніми вузлами – то екстраполюванням. З попереднього випливає, що при екстраполяції далеко за крайні вузли похибка може бути досить великою. Оскільки значення EMBED Equation.3 часто задаються наближено, то навіть і тоді, коли всі проміжні обчислення виконуються точно, результат дістаємо з похибкою. Це неусувна похибка. Неусувна похибка формули Лагранжа не перевищує величини: EMBED Equation.3, (9) де EMBED Equation.3 – максимальне значення абсолютних похибок величин y=f(x) (i=0,1,2,...,n). Остання похибка при EMBED Equation.3 (відповідно EMBED Equation.3) порівняно мала і дуже повільно зростає із збільшенням n. У процесі обчислень виникає також похибка при заокругленні проміжних результатів. Практично цю похибку можна зробити значно меншою порівняно із неусувною (похибкою обмеження), якщо проміжні обчислення проводити з більшою кількістю цифр, ніж це вимагається для табличних значень f(x). При оцінці похибки результату слід враховувати і похибку остаточного заокруглення. Повна похибка інтерполювання дорівнює сумі всіх перелічених вище похибок. 2.3. Скінченні різниці. Інтерполяційні многочлени Ньютона Нехай EMBED Equation.3 – значення деякої функції y=f(x), що відповідають рівновіддаленим значенням аргументу EMBED Equation.3. Величина EMBED Equation.3 називається скінченною різницею першого порядку функції f(x)в точці EMBED Equation.3 (з кроком h) і позначається EMBED Equation.3 або EMBED Equation.3, тобто EMBED Equation.3. Скінченна різниця другого порядку в точці xi визначається рівностями: EMBED Equation.3. Скінченна різниця n-го порядку функції y=f(x) в точці EMBED Equation.3 визначається рекурентною формулою: EMBED Equation.3, де EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 Скінченні різниці зручно розміщувати у вигляді таблиці: Така таблиця називається діагональною таблицею різниць. Всі різниці будемо записувати цілими числами в одиницях молодшого розряду значень функції у вузлах інтерполювання. Можна записати формулу: EMBED Equation.3, (10) де EMBED Equation.3 – біномні коефіцієнти. Остання формула виражає скінченні різниці через значення функції у вузлових точках. Нехай для функції y=f(x) задано її значення EMBED Equation.3 для значень аргументу, які утворюють арифметичну прогресію EMBED Equation.3 (i=0,1,...,n), де h – крок таблиці. Треба побудувати многочлен EMBED Equation.3 степінь якого був би не більшим за n, а значення його у вузлах інтерполювання збігалися б із значенням функції y=f(x); тобто: EMBED Equation.3 (i=0,1,2,...,n). (11) Многочлен EMBED Equation.3 визначається у вигляді: EMBED Equation.3 (12) Коефіцієнти EMBED Equation.3 у (12) визначають так, щоб виконувались умови (11). Після деяких перетворень і застосування раніше введених означень скінченних різниць отримують співвідношення: EMBED Equation.3 (13) Формула (13) називається першою інтерполяційною формулою Ньютона. Доведено, що існує лише один інтерполяційний многочлен n-го степеня, значення якого у вузлах інтерполяції EMBED Equation.3 дорівнюють значенням функції EMBED Equation.3. Тому інтерполяційний поліном (13) збігатиметься з інтерполяційним многочленом Лагранжа, побудованим для цього випадку. Ці многочлени тільки записані в різних формах. Формулу Ньютона (13) можна подати в зручнішому для користування вигляді. Для цього вводять нову безрозмірну змінну t за формулою EMBED Equation.3, або EMBED Equation.3. Тоді формула (13) набирає вигляду: EMBED Equation.3 (14) Цей вигляд першої інтерполяційної формули Ньютона називають формулою Ньютона для інтерполювання вперед. Таку назву вона отримала тому, що в ній використовуються значення функції, дані у вузлах, які містяться вправо від EMBED Equation.3 (вперед, вниз по стовпчику). Для інтерполювання в кінці таблиці користуються іншою формулою вигляду: EMBED Equation.3 (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. Тиражування здійснене на кафедрі САПР. Відповідальний за тиражування доц. Каркульовський Володимир Іванович.

Інструкція та методичні настанови Чисельні методи в інформатиці

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись