Кусково-поліноміальна апроксимація

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

У тих випадках, коли відрізок , на якому виконується заміна функції інтерполяційним поліномом , є досить великим і відсутні підстави вважати функцію (яка, як правило, невідома) достатньо гладкою при , немає сенсу підвищувати точність інтерполяції за рахунок збільшення степені полінома . У таких випадках доцільно застосовувати кусково-поліноміальну апроксимацію, допускаючи, що функція апроксимації складається із окремих поліномів, як правило, невисокої степені, кожний із яких визначений на своїй частині відрізку .

Кусково-лінійна і кусково-квадратична інтерполяція

Найпростішим із поліномів, які використовують для кусково-поліноміальної апроксимації це поліноми першої степені, які утворюють ломану лінію, що проходить через задані точки.

Допустимо, що на системі вузлів відомі значення функції . Абсциси упорядковані наступним чином:

Необхідно апроксимувати кусково-лінійною функцією , виходячи із умов інтерполяції

, .

Якщо функцію взяти у вигляді , виходячи із умов інтерполяції, отримуємо систему із лінійних рівнянь

(9.17)

……………..

Кожна пара сусідніх рівнянь системи (9.17), яка має коефіцієнти з однаковими індексами є незалежною від інших пар і може розв’язуватись самостійно.

При кусково-квадратичній інтерполяції функція вибирається у вигляді квадратного трьох члена - . При кожна ланка кусково-квадратичної функції визначається трійкою коефіцієнтів , і , послідовним розв’язком трьохвимірних лінійних систем

де .

Недоліком кусково-квадратичної інтерполяції є те, що кривизна у парних вузлах різко змінюється, а це може викликати небажаний вигин або викривлення графіка функції .

Інтерполяційний сплайни

Побудова поліноміальної лінії за заданою сукупністю точок здійснюється у системах комп’ютерної графіки. Для цієї мети застосовують кубічний сплайни.

Сплайном називають функцію , яка визначена на відрізку раз неперервне диференційована і така, що на кожному проміжку - це многочлен -ої степені. Різниця називається дефектом сплайна.

Якщо сплайни апроксимує деяку функцію , яка задана своїми ординатами , і при цьому виконується умова , то такий сплайни називається інтерполяційним сплайном для функції .

Найбільш відомий і такий, що знайшов широке застосування, є кубічний сплайни дефекту 1. При цьому допускають, що вузли сплайна одночасно є і вузлами інтерполяції, тобто , .

Отже, кубічним сплайном дефекту 1, який на відрізку , інтерполює задану функцію називається функція

; ; , (9.18)

яка задовольняє такій сукупності умов:

· умові інтерполяції у вузлах сплайна - ;

· подвійній неперервній диференційованості на відрізку ;

· крайовим умовам - .

Визначений у такий спосіб сплайни називають ще креслярським сплайном[1]. Щоб побудувати кубічний сплайни (9.18) необхідно визначити його коефіцієнти, виходячи із умов інтерполяції

, при

гладкого спряження ланок сплайну

та крайових умов

, .

Із (9.18) знаходимо, що

. (9.19)

. (9.20)

Рис. 9.3 дає наочне уявлення про розташування вузлів і ланок кубічного сплайну.

Рисунок 9.3 – Розташування вузлів і ланок кубічного сплайну

Враховуючи значення функції , яке визначається формулою (9.18), та умови інтерполяції, знаходимо

де , .

Введемо позначення , . Тоді

, /

Виходячи із умов гладкого спряження ланок сплайну, отримаємо

Враховуючи співвідношення (9.18) – (9.20), маємо

, .

Крайові умови дають змогу знайти

або ,.

Таким чином, отримали наступну систему лінійних алгебраїчних рівнянь:

, (9.21)

, ; (9.22)

, (9.23)

, (9.24)

, ; (9.25)

, (9.26)

. (9.27)

В отриманій системі рівнянь коефіцієнти відомі і дорівнюють для всіх значень . Підставляючи їх значення в рівності (9.21) і (9.23), приходимо до наступних співвідношень:

, (9.28)

. (9.29)

Для спородження запису введемо таке позначення:

Величина носить назву роздільної різниці першого порядку або скорочено – роздільної різниці. Враховуючи, зроблене позначення рівняння (9.28) і (9.29) набудуть такого вигляду:

, .

Із отриманих рівнянь визначимо і об’єднаємо їх в одне

, . (9.30)

Тепер із (9.25) та (9.26) знайдемо

, , (9.31)

де - фіктивний коефіцієнт.

Знайдене значення дає змогу вилучити його із співвідношення (9.30)

, . (9.32)

В останньому виразі замінимо на

Отримані значення , і підставимо у рівняння (9.24). У результаті отримаємо

Після нескладних алгебраїчних перетворень приходимо до такого різницевого рівняння:

, (9.33)

де ; ; .

Змінюючи від 2 до , отримаємо систему лінійних алгебраїчних рівнянь

……………………………… (9.34)

Маємо систему із рівнянь, у якій невідомими є коефіцієнти сплайна , , …, ( і ).

Систему рівнянь (9.34) подамо у векторно-матричній формі ,

де

; ; .

Як видно із аналізу матриці рівняння має тридіагональну структуру. Такі рівняння носять назву стрічкових систем і для їх розв’язку метод Гауса трансформується у більш ефективний метод, який називається методом прогонки.

Допустимо, що існують такі набори чисел і , при яких

. (9.35)

В останній рекурентній формулі індекс зменшимо на одиницю

і отримане значення підставимо в рівняння (9.33). У результаті отримаємо

Із останнього рівняння знаходимо

. (9.36)

Порівнюючи між собою вирази (9.35) і (9.36) приходимо до висновку, що

, , , (9.37)

де .

Таким чином, застосування методу прогонки до розв’язку системи рівнянь (9.34) зводиться до обчислення коефіцієнтів прямої прогонки і за формулами (9.37) при , а потім до одержання значень зворотної прогонки за формулою (9.35), вважаючи, що . Після підстановки знайдених значень у рівняння (9.31), (9.32) отримуємо числові значення коефіцієнтів кубічного сплайну і . Коефіцієнти визначаються із умови

, .

Всі обчислювальні затрати на побудову природного сплайну, який складається із ланок складуть арифметичних операцій.

Всі розрахункові формули значно спрощуються, якщо кубічний сплайн будується на системі рівновіддалених вузлів - для всіх значень . У такому випадку замість роздільної різниці будемо мати кінцеві різниці функції - , .