Міністерство освіти і науки України
Черкаський національний університет Імені Богдана Хмельницького
Кафедра математики та методики навчання математики
Кваліфікаційна робота з математики
Застосування сплайн-функцій до розв’язування задач інтерполяції
Автор:
ВишемірськаТетяна Володимирівна
Четвертийкурс, денна форма навчання, математичний факультет
Науковийкерівник:
Докторфізико-математичних наук, професор
СтеблянкоПавло Олексійович
Черкаси 2010
Зміст
Вступ
1. В-сплайни
1.1 Базис із В-сплайнів
1.2 В-сплайни нульовогостепеня та рекурентна форма запису В-сплайнів вищих порядків
1.3 Лінійні В-сплайни
1.4 Квадратичні В-сплайни
2. Кубічні В-сплайни
2.1Формулизадання кубічних B-сплайнів
2.2Базису просторі кубічних сплайнів
2.3 Задачі інтерполяції зграничними умовами першого та другого роду
2.4.Апроксимаціякубічними В-сплайнами
2.5Практичністьвивчення кубічних В-сплайнів у вищих навчальних закладах
3. Практична частина
3.1Задача №1
3.2Задача №2
Висновки
Список використанихджерел
Вступ
Сплайн-інтерполяціяна сьогоднішній день є одним із найточніших методів наближення. В теорію наближеньсплайни ввійшли зовсім недавно і відразу ж зайняли в ній досить важливе місце. Буквальнопротягом кількох років для сплайнів були розв’язані апроксимаційні задачі, на розв’язанняяких для поліномів були потрачені десятиліття. З подальшим вивченням і застосуваннямсплайн-функцій, знадобилося їх певне спрощення, для полегшення розрахунків. Саметоді і з’явилися В-сплайни, які як виявилося не тільки є простішими для обчислень,але й дають більшу точність наближення, що є дуже важливим при розв’язуванні практичнихзадач.
Актуальність:Сьогоднісплайн-функції відіграють дуже важливу роль, вони входять в курс «Чисельні методи»,як додатковий метод інтерполяції, а також використовуються в курсі «Рівняння математичноїфізики» для розв’язування нерозв’язних диференціальних рівнянь; з допомогою сплайніві В-сплайнів (в основному кубічних) розв’язуються (з великою точністю) ті задачі,які не можна розв’язати іншими, відомими, методами.
В-сплайн– це крива з неперервними старшими похідними до n-ої, де n – порядок сплайна.
Метакурсової роботи: Розглянути кубічні В-сплайни, а також лінійні та квадратичніВ-сплайни, форми їх запису та формули для розрахунків інтерполяційних задач, рекурентніформули для представлення В-сплайнів 1-го, 2-го, 3-го та вищих порядків. З’ясуватипрактичність застосування Кубічних В-сплайнів у ВНЗ при розв’язуванні задач інтерполяції. Застосуватина практиці отримані знання.
Для досягненнямети були поставлені такі завдання:
– знайтиі опрацювати літературу із даної теми;
– систематизуватиопрацьований матеріал;
– отриматиформули для розрахунків інтерполяційних задач;
– визначити практичність кубічних В-сплайнів в порівнянні з іншими сплайнамиі В-сплайнами;
1B-сплайни
1.1Базис із В-сплайнів
Однимз найширше використовуваних представлень кривих в комп'ютерному баченні є представленняу вигляді В-сплайну. Важливо розрізняти сплайни і В-сплайни. В-сплайни є поліноміальнимифункціями. Сплайни є лінійною комбінацією В-сплайнів. У літературі сплайни зазвичайвизначаються як різні види степеневої функції. Для обчислень зручніше визначатисплайни рекурсивними функціями.
Приймемобез доведення наступну лему, яку буде використано для доведення важливої теореми:
Лема1.Нехай /> - множина сплайнів порядкуmдефекту 1 по розбиттю />. Якщо /> і сплайн /> із /> задовольняє умови />, /> то /> на />.
Теорема 1. Система із /> В-сплайнів
/>,/> (1) порядку /> за розбитям /> з носіями /> є базисом в />.
Доведення. Нехай
/>, />;(2) потрібно довести, що /> (/>). Безпосередньоіз визначення В-сплайнів (1) виплива, що /> при />; але тоді зурахуванням (2)
/>, /> і в силу леми 1 /> для />. Таким чином,
/>, />.(3)
Оскільки на проміжку /> />, а при /> />, то із (3) слідує, що />, так що
/>, />.
Для /> /> при /> і /> при />, а тому /> і
/>, />.
Розмірковуючианалогічно, далі прийдемо до рівності
/> що й треба було довести.
Наслідок1. Будь-який сплайн /> із /> єдиним чином представляєтьсяу вигляді
/>, />.(4)
Якщо сплайн/> із /> однозначно визначається деякимнабором із /> інтерполяційних умов, то, підставляючив ці умови замість /> суму (4), отримаємо системулінійних рівнянь для визначення коефіцієнтів />. Усилу скінченностіносіїв сплайнів /> в кожному рядочку визначникацієї системи, не дорівнюватимуть нулю лише /> елементів — значення сплайнів /> (або їх похідних) в одній ізточок /> розбиття />. При цьому не нульові елементи,які відповідають внутрішнім умовам інтерполяції, будуть розміщені вздовж головноїдіагоналі визначника. Саме це і забезпечує, принаймні для малих />, простоту обчислення коефіцієнтівлінійної комбінації (4) [1].
1.2 В-сплайн нульовогостепеня та рекурентна форма запису В-сплайнів вищих порядків
В-сплайномнульового степеня, побудованим на числовій прямій по розбиттю />, називається функція вигляду:
/> , /> (5)
Єдинеобмеження полягає в тому, що В-сплайни повинні відповідати умові:
/>
Зокрема,якщо />, то /> [2].
В-сплайнстепеня />, побудований на числовій прямійпо розбиттю />, визначається наступною рекурентноюформулою:
/> />, (6)
де />, />. (7)
При однаковійвідстані між сусідніми вузлами В-сплайни називаються однорідними, в протилежномувипадку неоднорідними. Для однорідних B-сплайнів, базисні B-сплайни однаковогостепеня є зміщеними екземплярами однієї функції [3].
Нерекурсивнимвизначенням базисних B-сплайнів є
/>, (8)
де />, /> [3]. (9)
1.3Лінійні B-сплайни
ЛінійніB-сплайни є неперервними, але не диференційованими.
Скориставшисьрекурентною формулою (6), отримаємо формулу для лінійного В-сплайна:
/> /> (10)
Підставившиу (10) формулу (5) маємо:
/> /> (11)
Або увипадку рівномірної сітки з кроком /> (/>) отримаємо:
/>/>(11’)
Нижчена малюнку 1 представлено графік В-сплайна 1-го порядку:
/>
Мал. 1 — Графік В-сплайна
1.4 Квадратичні B-сплайни
Із рекурентноїформули (6), отримаємо наступну форму запису квадратичного В-сплайна:
/>/> /> (12)
Теперми можемо, або скористатись лише формулою (11), підставивши її у (12) отримаємо:
/>/> (13)
А у випадкурівномірної сітки з кроком h матимемо:
/>(13’)
Або спершув (12) підставимо (10) і, зробивши відповідні перетворення, отримаємо квадратичнийВ-сплайн в вигляді:
/>, (14)
а потімв (14) підставимо (5) і отримаємо ту ж саму формулу (13) [4].
ГрафікВ-сплайна 2-го — /> - степеня представленона малюнку 2:
/>
Мал. 2 — Графік В-сплайна
В-сплайндовільного степеня /> може бути відміннимвід нуля лише на деякому відрізку (визначеному /> вузлами) [4].
2Кубічні B-сплайни
2.1Формули задання кубічних B-сплайнів
Зробившианалогічні дії, що й при квадратичному В-сплайні, ми отримаємо формулу (15) длякубічного В-сплайна:
/>
Зауваження.Кубічні В-сплайни зручніше нумерувати так, щоб сплайн/> був відмінний від нуля на відрізку/> [5]. Запишемо тепер /> у випадку рівномірної сітки(з кроком />) його:
/> (15’)
Типічнийграфік кубічного В-сплайну показано на мал. 3:
/>
Мал. 3 — Типічний графік кубічногоВ-сплайну
2.2Базис у просторі кубічних сплайнів
Функція/>:
а) двічінеперервно диференційовна на відрізку />;
б)відміннавід нуля тільки на чотирьох відрізках />
Відрізок/> називають носієм функції /> [6].
Доповниморозбиття /> допоміжними вузлами:
/>/>
/> , взятими довільно.
За розширеноюсіткою:
/>:/>/>можна побудувати сім’ю з /> кубічних В-сплайнів:
/>, />
Ця сім’яутворює базис в просторі кубічних сплайнів на відрізку />. Тим самим довільний кубічнийсплайн />, побудований по розбиттю /> із /> вузла, може бути представленийна цьому відрізку в вигляді лінійної комбінації:
/>
Умовамизадачі коефіцієнти /> цього розбиття визначаютьсяоднозначно [7].
2.3Задачі інтерполяції з граничними умовами першого та другого роду
У випадкуколи задані значення /> функції в вузлахсітки і значення/> і /> першої похідної функції накінцях сітки (задача інтерполяції з граничними умовами першого роду), коефіцієнти/> обчислюються із системи наступноговигляду:
/>, де />(16)
Післявиключення /> і /> отримується лінійна системаз невідомими /> і 3-діагональною матрицею,яку можна розв’язати, як методом Гауса, так і методом прогонки [8].
При розв’язаннізадачі інтерполяції другого роду використовують значення похідних другого порядкуна кінцях сітки: /> і />. І коефіцієнти /> вже обчислюються із системи:
/>/>(16’)
такимсамим чином, як і під час розв’язування задачі інтерполяції першого роду.
2.4Апроксимація кубічними В-сплайнами
Нехайзадана таблиця чисел /> і />, котрі є значеннями функції/> і її першої похідної /> у вузлах ai, i =0,1, ...,N. Необхідна апроксимувати функцію W(a) з допомогою цихданих.
Розглянемоапроксимацію кубічними В-сплайнами. Конструкція нормованого
/>
кубічногоВ-сплайна зазвичай задається так:
/> (17)
В правійчастині (17) стоять многочлени третього степеня виду:
/>/> (18)
Коефіцієнтиai, bi, ci, di визначаютьсяіз системи чотирьох рівнянь, отриманих при умовах: /> /> /> и />. В результаті її розв’язкуможна записати:
/>
/> (19)
/>, /> , />
При конкретизаціївиразу (18) використовуються формули (19), що задовольняють умови стику у вузлахai-2, ai-1, ai, ai+1 для сплайнів:
/> (20)
Та їхпохідних по a, позначених штрихом:
/> (21)
В роботіБ.Зав’ялова [6] для рівномірної сітки /> i=0,1,…, N, задовольняючи наступні умови (20), (21), отримано такий вираз для/>
/>
Тут />, /> а також з’ясовано, що S0=2/3,S*=1/6, S**=1/2h.
Загальнийінтерполяційний вираз, в якому використовуються нормовані кубічні В-сплайни(22), записуються так:
/>, (23)
де />, а />. Коефіцієнти />bi+1,bi+2визначаються із умов, що задовольняють значення функції W(a), відомих в деякихвузлах /> />. Зазвичай вибирають />, />, а /> задовольняють нерівність: />.
Запишемо(23) в розгорнутому вигляді. Для цього, використавши (22) отримаємо всі вирази для/>. Сплайн /> отримаємо із четвертої рівності(22), якщо там формально замінити x на 1+ x. Тоді
/> (24)
Вираздля /> береться безпосередньо із (22)
/> (25)
Сплайн/> записується на основі другоїрівності (22) шляхом формальної заміни x на x-1
/> (26)
І, нарештііз першого виразу (22), замінюючи x на x-2, отримаємо:
/>. (27)
Тоді остаточнийваріант інтерполяційного виразу, основаного на застосуванні нормованих кубічнихВ-сплайнів, отримаємо шляхом підстановки виразів (24)-(27) в (23)
/> (28)
/> />
Вираз(28) дає четвертий порядок апроксимації функції /> покроку h 0( h4 ). Якщо в формулі (28) виключити коефіцієнти,виразивши їх через значення апроксимуючої функції у вузлах, то отримаємо:
/>, де(29)
/> (30)
Більшвисокий порядок апроксимації можна отримати за допомогою так званих напруженихсплайнів, при цьому інтерполяційний вираз (29) зберігає свій вигляд, а функції,які входять до його складу задаються так:
/>, (31)де />
/>; />; />;
/>; />; />.
Інтерполяційнийвираз виду (29) використовується, як для визначення шуканих величин між вузламикоординатної сітки, так і для апроксимації частинних похідних, котрі входять доскладу повної системи рівнянь [8].
2.5Практичність вивчення кубічних В-сплайнів у вищих навчальних закладах
В-сплайниє більш практичні у використанні ніж природні сплайни, оскільки поліноміальні коефіцієнтиприродних сплайнів вимагають всіх /> вузловихточок. Їх обчислення залучає розв’язання /> вимірнихматриць. У цьому є два недоліки: переміщення однієї вузлової точки зачіпає всю кривуі під час розв’язування матриці можна зіткнутися з швидкою зміною кривої. З іншогобоку, В-сплайни складаються з сегментів кривих, залежних тільки від кількох вузловихточок. Це називається локальним контролем. Таким чином, переміщення вузлової точкизачіпає тільки маленьку частину кривої. B-сплайни мають ту ж саму неперервність, як і природнісплайни, але не інтерполюють їх вузлові точки. Тому, ми говоримо про наближеннябагатокутника, а не про вставку вузлової точки.
Першимкроком є вибір порядку базису сплайнів, щоб досягати бажану гладкість і полегшитиобчислювання.
Як найефективніші,були вибрані кубічні В-сплайни, тобто сплайни третього порядку, через наступні причини:
1. Поліноминижніх степенів дають дуже низьку гнучкість в управлінні формою кривої. В-сплайнипершого порядку (прямі лінії) не дають задовільної гладкості апроксимуючої кривої.В-сплайни другого порядку дають гладку криву, але проблема виникає в точках, дез'єднуються сегменти кривої. Щоб зрозуміти цю проблему, ми введемо нове означення:
Означення. Позначимо /> сегмент кривої. Якщо напрямі величина /> і /> рівні в точці з'єднання, крива,що складається з цих двох сегментів, називається /> неперервною.
В-сплайнидругого порядку /> і /> неперервні, що не гарантуєзадовільну неперервність в об'єднаних точках. Проблема вирішується, використовуючикубічні В-сплайни, які є />, /> і /> і неперервними.
2.Поліномивищого степеня віднімають багато часу в обчислювальному процесі і можуть нести небажаніскачки. Крива може «скакати» назад і вперед важко керованими способами.
3. Кажучи,що кубічні В-сплайни дають «задовільну» неперервність, мається на увазі,що око не може виявити геометричну неоднорідність степеня вище, ніж два і практичнодосить використовувати В-сплайни третього ступеня [9].
Отже,хоч кубічні В-сплайни і є методом, важчим у розрахунках, ніж інші, відомі методи,які застосовуються у задачах для наближення, але він дає набагато точніший результат,і є просто незамінним при розв’язуванні задач, які неможливо розв’язати іншими методами.
3.Практичначастина
3.1Задача №1
Потрібноінтерполювати (використовуючи задачу першого або другого роду) одну з відомих функцій,з допомогою кубічних В-сплайнів, у випадку рівномірної сітки розбиття.
Розв’язання: Для розв’язання цієїзадачі візьмемо функцію /> і будемоїї інтерполювати на відрізку />, розбившийого на 6 рівних частин (/>). Маєморівномірну сітку, отже будемо користуватися формулою (15’). Знайдемо /> і /> (задача інтерполяції першогороду): />,
/>(15’’) Виключимо із системи(16) /> і />: /> , />, (32)
і отримаємонаступну систему:
/>
, />(33) де
/>, />,
/>, />,(34)
/>, />.
Розв’язавшисистему (33), знайдемо коефіцієнти />, для шуканогосплайна:
/>
(де унашому випадку />).
Отже необхіднознайти і підставити відповідні значення та розв’язати матричне рівняння:
/>,
де /> - тридіагональна матриця, а/> - шуканий вектор коефіцієнтів.
Для нашоїфункції /> маємо наступні дані: