ЧИСЕЛЬНІ МЕТОДИ
Основні відомості про методи апроксимації
методичні вказівки до лабораторної роботи № 6
для студентів напряму 6.050101 „Комп’ютерні науки”
Методичні вказівки обговорені та схвалені на засіданні Науково-методичної ради інституту комп’ютерних наук та інформаційних технологій Національного університету «Львівська політехніка». Протокол № ____ від _______________2017
Укладачі: Висоцька В.А., к.т.н., доцент кафедри ІСМ
Методичні вказівки до лабораторних робіт з дисципліни «Чисельні методи» для студентів напряму 6.050101 „Комп’ютерні науки” /Укл.: В.А.Висоцька.
Лабораторна робота № 6
на тему " Основні відомості про методи апроксимації "
Мета: вивчити основні поняття апроксимації та опрацювання експериментальних дослідних даних МНК. Опрацювання експериментальних дослідних даних. Набуття навичок з визначення параметрів моделі за мінімаксним методом.
Короткі теоретичні відомості
Математики минулого поєднували в своїх роботах вивчення явищ природи, отримували їх математичний опис (математичні моделі) та досліджували їх. На сьогоднішній день характерним є розширення додатків математики, що пов’язане з бурхливим розвитком обчислювальної техніки, адже швидкість операцій розрахунків стала просто фантастичною. Проте, думка про всемогутність сучасних обчислювальних машин породжує міф, що математики позбулися всіх проблем, пов’язаних як з чисельним розв’язком задач, так і з розробкою нових методів їх розв’язування. Але це не так. Можемо спостерігати математизацію інших розділів науки: хімії, економіки, біології, психології, медицини та конкретних розділів техніки. Процес математизації полягає в побудові математичних моделей процесів і явищ, а також в розробці нових методів їх дослідження та моделювання.
В фізиці чи механіці, побудова математичних моделей для опису різних явищ природи і вивчення цих моделей з метою пояснення старих чи передбачення нових ефектів явищ є традиційною. Прикладом успішного вивчення математичних моделей в поєднанні з опрацюванням результатів спостережень, задовго до появи обчислювальної техніки, було відкриття невідомої колись планети – Нептун. Але робота в цьому напрямку просувалась повільно, бо не вдавалось отримати розв’язок певних математичних задач і доводилось обмежуватись розглядом більш простіших моделей. Застосування обчислювальної техніки значно збільшило можливості в напрямку побудови і дослідження математичних моделей. Все частіше результати розрахунків дозволяють знаходити і передбачувати нові явища, що дає можливість говорити про математичний експеримент. В деяких напрямках довіра до результатів чисельних розрахунків така велика, що при розбіжності між результатами розрахунків та експериментами в першу чергу шукають помилку в результатах експериментів. Сучасні успіхи у вирішенні таких важливих для суспільства задач як атомні, космічні, економічні, не були б можливі без застосування сучасної обчислювальної техніки, класичних та новітніх методів обчислень.
Потреба чисельного розв’язку нових задач призвела до появи великої кількості нових методів. Теоретичні дослідження в галузі чисельних методів групуються навколо чисельних методів розв’язку так званих типових математичних задач, до яких відносять і апроксимацію (наближення) даних.
Необхідність в апроксимації (наближенні) функцій виникає при проведенні теоретичних досліджень і практичних розрахунків в багатьох областях техніки. Для функції, яка задана у вигляді таблиці, це перш за все пов’язано з бажанням отримати аналітичний вираз, так як його простіше дослідити та інтерпретувати. У випадку аналітично заданої функції часто корисно замінити дуже складний вираз більш простим так, щоб основні властивості функції зберігалися.
Окремий інтерес представляють наближення функцій, які є придатними для розрахунків із застосуванням обчислювальної техніки. В цьому випадку апроксимуюча функція може бути отримана, наприклад, у вигляді полінома, раціонального полінома нелінійного виду, рекурентної (ітераційної) формули, популярною стала сплайн-апроксимація, тощо.
Задача знаходження найкращого (чебишовського) рівномірного наближення виникає, наприклад, для:
- проектування контрольно-вимірювальних приладів, зокрема пірометрів або термометрів (градуювання, лінеаризація статичних характеристик);
- проектування різноманітних функціональних перетворювачів (опис відповідних функцій);
- реалізація алгоритмів обчислення спеціальних функцій на високопродуктивних процесорах опрацювання даних (апроксимація складних функціональних залежностей простими аналітичними виразами);
- побудова математичних моделей різноманітних неперервних процесів на основі дискретних вимірювань їх значень;
- в машинобудуванні для представлення контурів проекцій деталей з складними геометричними формами, а також аналітичного подання кривих, які задають траєкторію різальних інструментів в верстатах із програмним управлінням, тощо.
Крім того, апроксимацію дослідних даних, доцільно застосовувати у різноманітних задачах ущільнення масивів результатів вимірювань, що містять методичну похибку у відомих межах (це може бути телеметрична інформація або масиви геофізичних чи сейсмічних вимірювань).
Поряд з класичними поліномами й раціональними найкращими рівномірними наближеннями, все частіше розглядається наближення нелінійними виразами. Це пояснюється тим, що фізичні процеси здебільшого мають нелінійний характер і для більш адекватного їх представлення використовуються відповідні отримані теоретично або інтуїтивно побудовані нелінійні залежності. Вивчаються також можливості використання рівномірного наближення функцій для представлення розв’язків диференційних та інтегральних рівнянь, розглядаються й інші можливості застосування такого наближення.
В багатьох технічних задачах застовується сплайн-апроксимація функцій. При цьому необхідно, щоб абсолютна і відносна похибки ні в одній точці не перевищували наперед заданої величини. Це призводить до задачі знаходження параметрів чебишовського наближення. Якщо на кожному інтервалі (ланці сплайну) максимальна похибка наближення однакова, то таке наближення називається рівномірним сплайн-наближенням. У відомих випадках рівномірне наближення сплайном є оптимальним в тому сенсі, що при виборі границь ланок (вузлів) із умови рівномірності наближення при заданій кількості ланок отримуємо мінімальну похибку, а при заданій похибці – мінімальну кількість ланок.
Таким чином, поруч із наявним програмним забезпеченням (Maple, MathLab, тощо), актуальною є розробка прикладного забезпечення для персональних комп’ютерів, яке є орієнтоване на розв’язування задач, що зводяться до знаходження наближення функцій. Таке програмне забезпечення для персональних комп’ютерів повинно грунтуватися на аналізі задач з наближення функцій і включати нові теоретичні й практичні розробки.
6.1. Формулювання проблеми апроксимації даних
Проблема задачі апроксимації функцій виникає в найрізноманітніших технічних задачах. Різноманіття методів настільки велике, що іноді виникає наступне питання. Може наявність великої кількості різних методів наближення пояснюється простою відсутністю наукового підходу до постановки і розв’язування проблеми? Якби такий підхід існував, то може вдалось би запропонувати один оптимальний спосіб наближення? Слід визнати, що вибір методів наближення викликано різноманіттям постановок проблем. Різні розділи теорії наближень, наприклад інтерполявання, апроксимації, можна розглядати як вивчення поведінки абстрактних моделей.
Функції для опису математичних моделей можуть бути задані як аналітичним способом (формулою), так і табличним, при якому функція відома тільки при визначених дискретних значеннях агрументу. Якщо функціональні залежності отримані в результаті розранунків, які проведені за допомогою обчислювальної техніки або в процесі експериментів, то вони задаються саме табличним способом. Імовірно, що на практиці виникне потреба в інформації про значення функції в інших точках, відмінних від тих, що наведені в таблиці. І отримати такі значення можна шляхом складних розрахунків або проведенням ще ряду експериментів, які заберуть багато часу і ресурсів. Таким чином, для економії часу і коштів, доцільним є застосування різних задач апроксимації функцій при довільному значенні аргумента на основі наявних табличних даних.
Якщо відтворення значення функції відбувається за точними значеннями то застосовують інтерполяцію.
Така задача розв’язується, наприклад, заміною функції f(x) більш простішою функцією j(x), яку нескладно знайти при довільному значенні аргументу x на заданому інтервалі. Наближення функції f(x) більш простішою функцією називають апроксимацією (від латинської approximo – наближатися). Апроксимуючу функцію j(x) будують таким чином, щоб відхилення від f(x) на заданому проміжку було мінімальним. При цьому функцию j(x) будуть називати апроксимуючою (рис. 6.1).
Розв’язуючи задачі апроксимації, потрібно враховувати:
- вибір вузлів апроксимації, формування початкового вузла xo, вибір постійного кроку h, розрахунок усіх наступних вузлів (наприклад, якщо х0 = –0,3, h = 0,5, то х = (–0,3; 0,2; 0,7;…); при цьому з метою зменшення похибки апроксимації вузли обчислюються за спеціальними формулами;
- підбір апроксимуючої функції j(x), наприклад поліномом
В такому випадку апроксимація буде називатися поліноміальною. Коефіцієнти поліному a0, a1,…, an і його степінь n вибираються таким чином, щоб забезпечити найменше відхилення апроксимуючої функції від заданої. Крім того, наближення функцій може бути тригонометричним, експоненційними, логарифмічними та іншими виразами.
Якщо функція f(x) задається аналітичним виразом, то при побудові апроксимуючої функції потрібно дотримуватися мінімального відхилення однієї функції від іншої на деякій неперервній множині точок [a,b]. Така апроксимація буде називатися неперервною або інтегральною. Теоретично для найвдалішого наближення потрібно, щоб похибка на усіх точках відрізку відхилення апроксимуючої функції j(x) від функції f(x) була меншою від заданої величини e>0
, . В такому випадку кажуть, що функція j(x) рівномірно наближує функцію f(x) з точністю e на відрізку [a,b].
Також, дуже часто застосовують метод середньоквадратичного наближення, для якого найменше значення має величина
Для отримання точкового середньоквадратичного наближения функції f(x), яка задається таблично, апроксимуючу функцію j(x) будують виходячи з умови мінімуму величини:
Величина S являє собой суму квадратів відхилень апроксимируючої функції j(x) від f(x) на заданій множині точок х0,х1,…, хn. У випадку наближення поліномом, коефіцієнти а0, а1, …, аm підбираються, виходячи з умови, що величина S є мінімальною. Такий підхід до апроксимації називається методом найменших квадратів. В цьому випадку не обов’язково, щоб апроксимуюча функція проходила через вузли. Недоліком середньоквадратичного наближення є те, що функції j(x) та f(x) в окремих точках можуть суттєво відрізнятися. Найчастіше средньоквадратичне наближення застосовується для опрацювання експериментальних даних.
Ще одним способом точкової апроксимації є інтерполювання, за яким апроксимуюча функція приймає в заданих точках xi ті ж значення yi, що і функція f(x), тобто: j( xi)= yi, i=0,1,…, n; при цьому точки xi називаються вузлами інтерполяції. На рис. 6.2а і рис. 6.2б показано графік інтерполяційної функції і результати середньоквадратичного наближення. Точками на графіку марковані табличні значення функції f(x)
6.2. Формулювання задачі наближення функцій
Постановка задачі наближення функцій виникає в багатьох ситуаціях. Різні розділи теорії наближень, а саме інтерполяції, можна розглядати як вивчення абстрактних моделей деяких реальних класів проблем.
а) Найпростіша задача, що приводить до наближення функцій полягає в наступному. В дискретні моменти часу x1,…xn спостерігається значення функції f(x). Потрібно відновити її значення при інших x. Аналогічна задача виникає в наступному: в ході обчислень в комп’ютерних розрахунках доводиться багаторазово обчислювати одну і ту ж складну функцію в різних точках. Замість її безпосереднього розрахунку інколи доцільно обчислювати її значення в окремих точках, а значення в інших точках обчислювати, використовуючи інформацію про відомі точки.
Деколи з певних додаткових міркувань відомо, що функцію, яка наближує, доцільно шукати в вигляді:
Якщо параметри a1,…an визначаються із умови співпадіння f(x) і наближаючої функції в точках x1,…xn
. то такий спосіб наближення називають інтерполяцією.
Якщо a лежить за межами проміжку інтерполювання, то таке наближення називається екстраполяцією.
б) Часто буває відомо, що функція добре наближається функціями певного вигляду, наприклад многочленами, але не зрозуміло, як краще всього вибрати степінь многочлена, що наближує. Проблема ускладнюється, коли задані значення функції містять великі похибки.
в) В задачах планування експериментів виникає наступна проблема. Відомий вигляд функції, що добре наближує, наприклад, функція добре наближується многочленом другого степеня. В той же час значення функції, що вимірюються, містять великі похибки. Потрібно отримати найкраще наближення при мінімальному числі вимірюваних значень функції. Така задача виникає при плануванні експериментів в біології, хімії, фізиці, географії тощо.
Торкнемося докладніше планування експериментів на хімічних підприємствах. Наприклад, сорт капрону визначається цілим рядом параметрів, частина яких залежить від властивостей сировини, яка поступає, а частина піддається управлінню; потрібно максимально підвищити випуск капрону першого сорту. Для цього потрібно мати в розпорядженні функцію, що відображає залежність виходу продукції від всіх цих параметрів. Розглянемо випадок, коли ця функція є многочленом другого степеня від 10 параметрів. Такий многочлен містить 66 коефіцієнтів, тому для їх знаходження потрібно щонайменше 66 вимірювань. Кожне вимірювання містить суттєву випадкову похибку через наявність ряду неконтрольованих факторів і факторів, що не вимірюються; тому для пониження впливу випадковості необхідно збільшити число вимірювань. В той же час кожне вимірювання обходиться відносно дорого, бо потребує зміни режиму роботи реального підприємства, до того ж такі вимірювання часто потребують тривалого проміжку часу, тому що підприємство повинно вийти на стаціонарний режим роботи. В результаті аналізу всіх цих протирічь і виникла проблема наближення функцій, про яку йшла мов вище.
г) Задача наближення з’являється при написанні стандартних програм розрахунку елементарних і спеціальних функцій. Звичайно такі функції володіють спеціальними властивостями, які дозволяють значно зменшити обсяг розрахунків.
Проблема, що виникає, може бути сформульована так. Розглядаються всі функції , результати розрахунків яких записуються в k комірках комп’ютора, такі, що деяка норма похибки не перевищить e. Зі всіх таких функцій слід вибрати таку, розрахунок якої потребує мінімальних затрат часу.
В залежності від обставин норма може вибиратися по різному. В переважній більшості випадків береться на проміжку [a,b], на якому наближається функція. Досить часто потрібно підвищити точність в окремих точках. Наприклад, одна зі стандартних програм забезпечує похибку в нормі:
. Введення множника викликане вимогою мінімуму відносно похибки при малих x. Таким чином можуть по-різному тлумачитися вимоги мінімальності затрат часу ПК. Затрати можуть залежати від точки, в якій вираховується значення функції. Позначимо їх через . Якщо відсутня інформація про те, з якою частотою вираховуються значення функції в тих чи інших частинах відрізка, то доцільно в якості спільної міри затрат прийняти:
Якщо така інформація є, то можна прийняти:
д) Якщо функція задається графіком або складним аналітичним виразом, то виникають варіаційні задачі інших типів. Наприклад, нехай вирішено розбити відрізок [a,b] на частин:, ,
і на кожному відрізку наближають функцію многочленом
або дробово–раціональною функцію
Серед таких способів наближення шукають оптимальне в тому чи іншому сенсі. Найчастіше наперед накладаються умови фіксується число відрізків розбиття і проводиться оптимізація методу по n і m.
В окремому випадку, коли l=1, виникає задача найкращого рівномірного наближення многочленами чи дробово–раціональними функціями на фіксованому відрізку.
е) Вигляд наближаючої функції суттєво залежить від мети, з якою здійснюється наближення. Припустимо, що з деякою точністю функція може бути наближена многочленом 10-го степеня або виразом Якщо отримане наближення використовують в теоретичних дослідженнях для розв’язку задачі на моделюючому пристрої чи в технологічному процесі, то друга форма запису є більш зручною. Але якщо значення функції вираховується на ПК, то друга форма запису потребує при своїй реалізації більшого числа арифметичних операцій [76-80, 88, 92-93].
(Для ознайомлення з повним текстом статті необхідно залогінитись)