Магистерская работа. Магистерская курсач. Вдосконалення методу апроксимації даних
 Скачать 1.66 Mb.
|
|
Методи інтерполяції Для обчислення проміжних значень функції використовується апарат інтерполяції. При ньому справжня функція замінюється апроксимуючою функцією, яка в вузлових точках дає точні значення ординат і дозволяє обчислити значення інтерпольованої функції в проміжних точках [21]. Інтерполяція знаходить широке застосування в наукових дослідженнях та інженерній практиці. Областями застосування являються: 1) Моделювання. 2) Планування і статистична обробка експерименту. 3) Визначення значень функції при аргументах, які відсутні в таблиці даних. 4) Табулювання функції. 5) Подання складної функції в більш простому вигляді в визначених границях значень її аргументів [22]. 6) У всіх інших випадках, де потрібно виконати наближення одних функцій іншими, більш простими, з допустимою для практики точністю. 7) Коли необхідно знайти з високою точністю математичну модель об’єкта, характеристики якої отримані експериментально. Існує велика кількість методів інтерполяції [23]. Їх можна розділити на локальні і глобальні (рис.1.2). У разі локальної інтерполяції на кожному інтервалі будується окремий поліном. У разі глобальної інтерполяції відшукується єдиний поліном на всьому інтервалі. 28 Найпростішим і часто використовуваним видом локальної інтерполяції є лінійна (або кусочно-лінійна) інтерполяція [23]. Вона полягає в тому, що вузлові точки з'єднуються відрізками прямих, тобто через кожні дві сусідні точки проводиться пряма. Рисунок 1.2 – Класифікація методів інтерполяції Квадратична інтерполяція складніше лінійної, але вона забезпечує більш високу якість [24]. В якості інтерполяційної функції приймається квадратний тричлен. Квадратична інтерполяція зважаючи на можливу виродженість параболи (перетворення її в пряму) вимагає обчислень з подвоєною точністю для зменшення машинних помилок, пов'язаних з кінцевою розрядною сіткою ЕОМ. Для побудови інтерполяційних поліномів на заданих інтерполяційних вузлах застосовуються різні алгоритми [25]. Поліноми, які за цими алгоритмами утворюються, називаються поліномами Лагранжа, Ньютона, Гаусса та ін. Усі вони відносяться до глобальної інтерполяції. Але, незалежно від їх різних конструктивних особливостей, канонічна форма всіх цих поліномів на даних інтерполяційних вузлах і відповідних значеннях функції буде однією і тією ж. 29 Таким чином, при поліноміальній інтерполяції задача зводиться до найбільш простого випадку – рішенню системи лінійних алгебраїчних рівнянь. Сплайни мають кращі апроксимаційні властивості, які забезпечують мінімальну похибку [25]. Найбільш відомі сплайни, що складаються з фрагментів алгебраїчних поліномів не вище заданої степені. Як правило, це кубічні поліноми, або поліноми непарних степенів. Лінійний, кубічний, п’ятої степені. Вищі степені застосовуються не часто, зважаючи на ускладнення розрахунків [26]. Доцільність застосування певного виду сплайна ґрунтується на конкретних умовах задачі та обмеженнях реалізації [25]. Як правило основними вимогами є досягнення заданої точності апроксимації за прийнятих затрат часу та ресурсів на реалізацію. Таким чином, сплайн має наступні особливості [27]: 1) графік функції інтерполяції проходить точно через вузлові точки кожного сплайну; 2) у вузлових точках розриви функції і її похідних відсутні; 3) сплайни забезпечують високу точність інтерполяції на всьому діапазоні. У порівнянні з многочленами і сплайнами існує більш універсальний метод інтерполяції. Це інтерполяція дробово-раціональними функціями. Їх використовують коли варто адекватно відобразити властивості функції, пов’язані з різкими скачками, западинами, якщо функція не є обмеженою на скінченному проміжку. Це лише невеликий перелік інтерполяційних функцій та їх можливостей. Для більш широкого розуміння стану проблеми необхідно виконати огляд робіт інших авторів. 1.5 Огляд досвіду інших авторів В останні роки багато сучасних алгоритмів інтерполяції були розроблені і розвинені різними дослідниками. Вони вдосконалювали відомі методи та знаходили нові шляхи для підвищення точності інтерполяції. 30 Автор роботи [4] почав вивчення нового питання теорії наближень – завдання про знаходження при фіксованому n такої системи функцій , … , , для якої найкращі наближення функцій заданого класу поліномами ∑ ( ) були б найменшими. У цьому напрямку в подальшому було з'ясовано, наприклад, що для ряду важливих класів періодичних функцій найкращими у вказаному сенсі системами є тригонометричні поліноми. У джерелі [25] автор доводить, що інтерполяційні формули Лагранжа, Ньютона, Гаусса та ін. при використанні великої кількості вузлів інтерполяції часто призводять до поганого наближення через накопичення похибок в процесі обчислень. Крім того, через розбіжність процесу інтерполяції збільшення числа вузлів не обов'язково призводить до підвищення точності. Суттєво знизити похибку можна шляхом інтерполяції функції множиною поліномів невисокого порядку на вузьких інтервалах всього інтервалу інтерполяції. У роботі [28] представлено метод інтерполяції даних кубічними сплайнами. Отримані результати розповсюджуються на випадок, коли похідні напрямку і кривизни не сприймаються в якості даних, а отримані деяким локальним наближенням або передбачені вимогами форми. Автор статті [29] розробив метод інтерполяції з частинами розкладання по двом радіальним базисним функціям, для наближення функцій з полюсами. Метод був розроблений для застосування в антенних конструкціях, показано на прикладах, що матриця розсіювання для патч-антени, як функція деяких конструктивних параметрів може бути точно апроксимована новим методом. У роботі [30] побудовано двовимірний раціональний метод інтерполяції з використанням як значень функцій, так і часткових похідних інтерпольованої функції в якості даних інтерполяції. Подальші дослідження автори представили у роботах [31-33], де створили нову раціональну інтерполяцію з біквадратичним знаменником, використовуючи тільки значення інтерпольованої функції; розробили двовимірну раціональну інтерполяцію Ерміта для створення просторової поверхні з використанням як значень функцій, так і частинних похідних функції першого порядку; представили зважену раціональну кубічну 31 сплайн-інтерполяцію з використанням двох видів раціональних кубічних сплайнів з квадратичним знаменником. Порівняльна характеристика операторів інтерполяції внутрішніх просторів, для нерівномірно розподілених даних, наведена у роботі [34]. Перший – відомий поліноміальний оператор, який у певному сенсі узагальнює класичний інтерполяційний многочлен Лагранжа. Другий – можна отримати шляхом модифікації першого. Чисельні випробування та міркування щодо помилок показують, що обидва оператори мають дуже різні апроксимаційні характеристики і за допомогою відповідних модифікацій обидва можуть забезпечити бажаний результат. Автори роботи [35] представили метод збереження контурів зображення, на основі адаптивної осциляторної раціональної інтерполяційної функції, яка будується шляхом апроксимації ідеальної інтерполюючої функції ядра безперервними дробами. Це більш точне значення для ідеальної інтерполяції в просторовій або частотній області, ніж інші лінійні поліноміальні інтерполяційні функції ядра. Також представлені результати моделювання, що демонструють чудову продуктивність збільшення чіткості зображення. У роботі [36] розробники ввели, основані на блоці, зворотні відмінності, щоб розширити точкову інтерполяцію Тіле до раціональної інтерполяції, пов'язаної з блокуванням Тіле-подібним способом. Процес побудови можна охарактеризувати наступним чином: перш за все, розділити вихідний набір опорних точок на деякі підмножини (блоки), потім побудувати кожен блок, використовуючи будь-які засоби інтерполяції, лінійні або раціональні, і, нарешті, зібрати ці блоки методом Тіле сформувати всю інтерполяційну схему. Ясно, що в цьому випадку можна отримати безліч гнучких схем раціональної інтерполяції, включаючи класичну інтерполяцію безперервної фракції Тіле, як її окремий випадок. В якості продовження обговорюється двовимірна аналогія і наводяться чисельні приклади, що показують ефективність цього методу. У роботі [37] розглядається проблема збереження форми даних. Автори досліджували інтерполяцію, яка використовується для позитивних, монотонних і 32 опуклих функцій з використанням раціонального кубічного сплайна. Розроблена раціональна сплайн-схема має унікальне представлення, вона має два сімейства параметрів форми. Схема автоматична, користувачеві не потрібно турбуватися про пошук і вибір відповідного набору параметрів, як у випадку звичайного раціонального сплайна. У роботі [38] представлено метод інтерполяції з використанням пари раціональних спіралей для вирішення планарної та двоточкової задачі інтерполяції Ерміта. Спіральні сегменти, які використовуються, обмежені нульовою кривизною на одному кінці. Цей метод доцільний коли виникає необхідність інтерполяції між двома точками монотонної функції, при відомих тангенсах кутів нахилу в цих точках. Автори роботи [39] використали кусочно-раціональну кубічну функцію для візуалізації даних, розташованих по прямокутній сітці. Схема цього методу отримана шляхом накладання деяких обмежень на параметри при описі раціонального бікубічного сплайна, тоді як інші параметри залишаються у розпорядженні користувачів. Новий підхід до одновимірної напівкардинальної інтерполяції для природних кубічних сплайнів представлено у роботі [40]. Як результат, отримано рішення основане на методі полінома Лагранжа з відповідними локалізаційними та поліноміальними властивостями. Автори роботи [41] застосували теорему Нь’єтера про кусочно-алгебраїчні криві на перехресних розділеннях. А також використовуючи інтерполяцію уздовж кусочно-алгебраїчної кривої, вони представили метод побудови інтерполяційних множин Лагранжа для двовимірних сплайн-просторів на перехресних розділеннях. У роботі [42] автори описали апроксимуюче рішення на основі інтерполяції поліномом Лагранжа та сплайн функції для аналізу функціональних інтегральних рівнять типу Фредгольма. Цей метод поширюється на функціональні інтегральні рівняння. 33 У статті [43] автор використовує нейронні мережі для апроксимації складних характеристик, наприклад таких, як частотні залежності параметрів частотно-вибіркових НВЧ пристроїв. Точність такої апроксимації напряму залежить від належного вибору конфігурації та методу навчання нейронної мережі. Збільшення шарів нейронної мережі призводить до значного покращення її апроксимаційних характеристик. Отже, огляд робіт інших авторів у сфері апроксимації та інтерполяції функцій показав, що розроблено потужний математичний апарат, який може використовуватися для вирішення широкого кола задач. Але основна маса досліджень – це строга теорія математичної апроксимації, тобто розробка фундаментальних математичних положень. Використання технічної апроксимації зосереджено в основному навколо відновлення втрачених вихідних даних, але в технічній діагностиці насамперед важливо спрогнозувати поведінку вимірюваного параметру у майбутньому для оцінки залишкового ресурсу. Інтерполяція найчастіше використовується у технічних системах для розпізнавання образів та покращення їх якості. Проте використання інтерполяції також не позбавлене своїх недоліків, пов’язаних з поганим наближенням через накопичення похибок в процесі обчислень при великій кількості вузлів інтерполяції. Досить широко в останній час стали використовуватися нейронні мережі, але у діагностичних системах вони частіше за все виступають у ролі класифікаторів стану об’єкта, а не апроксиматорами. Усе це дозволило сформувати мету досліджень та завдання, які необхідно вирішити для досягнення цієї мети. 1.6 Мета і завдання досліджень Метоюроботи є розробка алгоритмічного та програмного забезпечення апроксимації даних вимірювань за допомогою попереднього використання алгоритмів інтерполяції, а також рекомендації щодо його ефективного використання в системах багатокласової діагностики. 34 Досягнення мети передбачає вирішення наступних задач: огляд та вибір методу апроксимації даних для системи багатокласової діагностики; огляд існуючих методів інтерполяції; дослідження ефективності різних інтерполяційних алгоритмів при використанні ідеальних (змодельованих) сигналів різної фізичної природи; розробка алгоритмічного забезпечення апроксимації даних за рахунок попереднього використання методів інтерполяції; розробка програмного забезпечення апроксимації даних в математичному пакеті MATLAB або на інших мовах програмування; розробка рекомендацій щодо ефективного використання розробленого програмного забезпечення в системах багатокласової діагностики. 35 РОЗДІЛ 2 ІНТЕРПОЛЯЦІЯ ЗМОДЕЛЬОВАНИХ ІДЕАЛЬНИХ СИГНАЛІВ Існує багато методів інтерполяції. Деякі з них є дуже гнучкими і можуть застосовуватися до різних даних. Інші є більш обмеженими і вимагають, щоб дані відповідали певним умовам. Кожен з цих методів має власний набір параметрів, що дозволяє його налаштовувати для конкретного набору даних [44]. У даному розділі буде розглянуто один з перших та найпростіших методів інтерполяції – метод Лагранжа. Проведено аналіз даного методу, що включає: опис, алгоритм інтерполяції у вигляді блок-схеми, реалізація алгоритму у програмному середовищі математичного пакету Matlab. Також проведено порівняльний аналіз результатів інтерполяції для ідеальних (змодельованих) знакозмінних сигналів різної природи (періодичного та неперіодичного) 2.1 Інтерполяційний метод Лагранжа Інтерполяційний поліном Лагранжа – многочлен мінімальної степені, що приймає необхідні значення в даному наборі точок. Для n+1 пар чисел ( , ), ( , )...( , ), де всі різні, існує єдиний многочлен L(x) ступеня не більше n, для якого L( ) = [45]. Інтерполяційний многочлен будується у вигляді лінійної комбінації многочленів степені n [46]: ( ) = ( ) + ( ) + ⋯ + ( ) (2.1) При цьому необхідно, щоб кожен многочлен ( ) перетворювався в нуль у всіх вузлах інтерполяції, за виключенням одного (і-го), де він повинен дорівнювати одиниці. Цим умовам при і=0 відповідає многочлен виду: 36 ( ) = ( )( )…( ) ( )( )…( ) (2.2) По аналогії з (2.2) отримаємо: ( ) = ( )( )…( ) ( )( )…( ) ( ) = ( )( )( )…( ) ( )( )( )…( ) ( ) = ( )…( )( )…( ) ( )…( )( )…( ) ( ) = ( )( )…( ) ( )( )…( ) (2.3) Підставимо в (2.1) вирази (2.2), (2.3), отримаємо: ( ) = ∑ ( )…( )( )…( ) ( )…( )( )…( ) (2.4) Ця формула визначає інтерполяційний многочлен Лагранжа. Виходячи з вищезазначеної формули, визначимо недоліки методу [47]: оскільки степінь многочлена Лагранжа визначається кількістю вузлів (мінус 1), то будь-яка спроба підвищити точність інтерполяції шляхом збільшення кількості вузлів тягне за собою збільшення ступеня полінома; формула для розрахунку досить громіздка. Кожна складова формули є многочленом n-го ступеня; якщо ступінь полінома вище 5, то на кривій з'являється "хвилястість", яка отримала назву ефекту Рунге-Мерей. Можливо поліпшити ситуацію шляхом підбору розташування вузлів в залежності від конкретної функції в інтерактивному режимі, але така процедура досить незручна. 37 Незважаючи на громіздкість формули (2.4), однією з переваг формули Лагранжа є можливість її запису безпосередньо по заданій таблиці значень функції. Для цього слід врахувати наступне правило: формула містить стільки доданків, скільки вузлів в таблиці; кожен доданок - це добуток дрібного коефіцієнта на відповідне значення ; чисельник коефіцієнта при містить добуток різниць x з усіма вузлами крім а знаменник повністю повторює чисельник при x= . Блок-схема алгоритму інтерполяції поліномом Лагранжа представлена на рис.2.1 [48]. Рисунок 2.1 – Блок-схема алгоритму обчислення многочлена Лагранжа 38 2.2 Інтерполяція методом Лагранжа 2.2.1 Дослідження гармонічної функції з частотою 20Гц Для подальших досліджень оберемо метод поліномів Лагранжа. У даному підрозділі буде проведено інтерполяцію поліномами Лагранжа гармонічної функції, як однієї з найбільш складних функцій (за рахунок наявності знакозмінного характеру) для апроксимації, особливо методом найменших квадратів (див. Розділ 3). Перший етап дослідів включає в себе моделювання гармонічної функції з частотою 20Гц виду: = + ( ) (2.10) де а, , с – константи; а – постійна складова сигналу або його математичне сподівання; b – характеризує амплітуду коливань; = 2 , де f – циклічна частота сигналу, Гц. Функція (2.10) буде містити N відліків (N=512, 1024, 2048, 4096, 8192). При цьому у вигляді змінних параметрів обрано кількість періодів гармонічного сигналу (р=1, 2, 3, 4, 5,6) та кількість вузлів, необхідних для інтерполяції (n=5, 9, 17, 33, 65). Для початку необхідно визначити оптимальну кількість вузлів інтерполяції. Критерієм вибору оптимального значення вузлів є мінімум максимального значення відносної похибки. Кожне дослідження буде проходити за умови, що у заданій кількості періодів початкового сигналу міститься вказана кількість відліків. Наприклад: а) 1024 відліки в одному періоді; б) 1024 відліки в двох періодах; і так далі. Отримані результати при р=1, N=512 та частоті дискретизації =10240Гц наведено у табл. 2.1. 39 Таблиця 2.1 – Дослідження похибки для різної кількості вузлів Кількість вузлів інтерполяції Максимальне значення відносної похибки 65 1012,9% 33 4,5797 ∙ 10 % 17 2,1372 ∙ 10 % 9 0,0414% 5 7,3052% З результатів дослідження можна зробити висновок, що для 17 вузлів похибка найменша і складає 2,1372 ∙ 10 %. Графіки інтерпольованого сигналу та отриманих похибок зображено на рис. 2.3. На графіках буде відображено тільки випадок з найменшим значенням максимуму відносної похибки. а) б) Рисунок 2.3 – Результати моделювання при р=1, N=512 та частоті дискретизації =10240Гц: а) графік функції; б) графік похибок Отримані результати при р=2, N=512 та частоті дискретизації =5120Гц наведено у табл. 2.2. 40 Таблиця 2.2 – Дослідження похибки для різної кількості вузлів Кількість вузлів інтерполяції Максимальне значення відносної похибки 65 866,0951% 33 4,9548 ∙ 10 % 17 0,0019% 9 10,5739% 5 50,4108% З результатів дослідження можна зробити висновок, що для 33 вузлів похибка найменша і складає 4,9548 ∙ 10 %. Графіки інтерпольованого сигналу та отриманих похибок зображено на рис. 2.4. а) б) Рисунок 2.4 – Результати моделювання при р=2, N=512 та частоті дискретизації =5120Гц: а) графік функції; б) графік похибок Отримані результати при р=3, N=512 та частоті дискретизації =3413,33Гц наведено у табл. 2.3. З результатів дослідження можна зробити висновок, що для 33 вузлів похибка найменша і складає 7,8431 ∙ 10 %. Графіки інтерпольованого сигналу та отриманих похибок зображено на рис. 2.5. 41 Таблиця 2.3 – Дослідження похибки для різної кількості вузлів Кількість вузлів інтерполяції Максимальне значення відносної похибки 65 1113% 33 7,8431 ∙ 10 % 17 1,0449% 9 98,466% 5 86,1196% а) б) Рисунок 2.5 – Результати моделювання при р=3, N=512 та частоті дискретизації =3413,33Гц: а) графік функції; б) графік похибок Отримані результати при р=4, N=512 та частоті дискретизації =2560Гц наведено у табл. 2.4. Таблиця 2.4 – Дослідження похибки для різної кількості вузлів Кількість вузлів інтерполяції Максимальне значення відносної похибки 65 703,6048% 33 1,1396 ∙ 10 % 17 58,234% 42 Продовження таблиці 2.4 Кількість вузлів інтерполяції Максимальне значення відносної похибки 9 56,1656% 5 52,5484% З результатів дослідження можна зробити висновок, що для 33 вузлів похибка найменша і складає 1,1396 ∙ 10 %. Графіки інтерпольованого сигналу та отриманих похибок зображено на рис. 2.6. а) б) Рисунок 2.6 – Результати моделювання при р=4, N=512 та частоті дискретизації =2560Гц: а) графік функції; б) графік похибок Отримані результати при р=5, N=512 та частоті дискретизації =2048Гц наведено у табл. 2.5. Таблиця 2.5 – Дослідження похибки для різної кількості вузлів Кількість вузлів інтерполяції Максимальне значення відносної похибки 65 1191,7% 33 0,0106% 17 780,2773% 43 Продовження таблиці 2.5 Кількість вузлів інтерполяції Максимальне значення відносної похибки 9 215,7521% 5 99,3848% З результатів дослідження можна зробити висновок, що для 33 вузлів похибка найменша і складає 0,0106%. Отримані результати при р=6, N=512 та частоті дискретизації =1706,67Гц наведено у табл. 2.6. Таблиця 2.6 – Дослідження похибки для різної кількості вузлів Кількість вузлів інтерполяції Максимальне значення відносної похибки 65 977,3028% 33 2,2872% 17 3378,7% 9 79,3792% 5 53,3239% З результатів дослідження можна зробити висновок, що для 33 вузлів похибка найменша і складає 2,2872%. |