Черкаси 2009 4 страница

Тому для опису таких функцій застосовують інші типи опису. Для опису складних функцій можуть застосовуватися інші поліноми (поліном Ньютона, ортогональні поліноми Чебишева, Лежандра, Ерміта та ін.) з рівновіддаленими чи адаптивнопідібраними вузловими точками. Але існує інший метод наближення – інтерполювання сплайнами.

 

5.2. Сплайн-інтерполяція

 

При сплайн-інтерполяції зберігається умова проходження наближуючої функції через вузлові точки. Сплайн (spline) переводиться з англійської, як гнучка лінійка. Сплайн-функції різняться ступенем поліному, що зображає функцію. Сутністю сплайн-інтерполяції є моделювання фрагментів заданої функції рядом поліномів низького ступеню. Прикладом такого інтерполювання є кусково-лінійне інтерполювання (рис. 5.1), де кожна з функцій будується по двом сусіднім вузловим точкам. Такий же принцип побудови зберігається і для формування поліномів вищих порядків, тільки кількість точок, на основі яких будується кожен з поліномів може бути більшою. Так, наприклад, для кусково-квадратичного поліному на проміжку [ x₀, x_N ] береться кожен інтервал [ x_2k, x_2k+2 ] для побудови на ньому квадратичного поліному. Але при побудові такого сплайну кривизна в парних вузлах різко змінюється, що відбивається на якості апроксимації.

 

Найбільш оптимальною на даний момент є кусково-кубічна сплайн-інтерполяція [4, 11-13]. Вона широко застосовується у системах комп‘ютерної графіки та системах проектування з використанням комп‘ютера: CAD-системах (системи комп‘ютери­зованої допомоги в дизайні та кресленні) та GІS-системах (географічні інформаційні системи).

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

Означення. Припустимо, задані (N+1) точки, де їх абсциси х_і задовольняють умові а = x₀ < x₁ < …< x_N = b. Функція S(х) називається кубічним сплайном, якщо існують N кубічних поліномів S_k(х) з коефіцієнтами s_{k, 0}, s_{k, 1}, s_{k, 2} та s_{k, 3}, що задовольняють наступним умовам:

1) S(x) = S_k(x) = s_{k, 0} + s_{k, 1}(x-x_k) + s_{k, 2}(x-x_k)² + s_{k, 3}(x-x_k)³, де х Î [x_k, x_k+1], k = 0, 1, …, N-1;

2) кусочно-кубічний поліном (сплайн) заданий сукупністю точок S(x_k) = y_k, де k = 0, 1, …, N;

3) сплайн-функція складається з поліномів (гладких функцій), які сполучуються у вузлових точках S_k(x_k+1) = S_k+1(x_k+1), де k = 0, 1, …, N-2;

4) сплайн-функція буде неперервною, якщо існує і безперервна її перша похідна S’_k(x_k+1) = S’_k+1(x_k+1), де k = 0, 1, …, N-2;

5) радіус кривизни сплайн-функції визначений в кожній точці (гладкість функції), якщо існує і безперервна її друга похідна S’’_k(x_k+1) = S’’_k+1(x_k+1), де k = 0, 1, …, N-2.

Загальний вираз для кубічної сплайн-функції S_k(x) має вигляд:

, (5.13)

Кубічний поліноми для утворення сплайн-функції будується по трьом сусіднім точкам за загальною формулою:

(5.14)

де , , , де в свою чергу .

При формуванні сплайн-функції будуються N-1 рівнянь з N+1 змінними. Для їх розв‘язання систему треба доповнити двома додатковими рівняннями. В якості таких рівнянь вибирають обмеження в крайніх точках сплайну, що наведені в таблиці 5.1.

Таблиця 5.1

Обмеження в крайніх точках кубічного сплайну [4].

№	Тип сплайну	Обмеження в крайніх точках
	Зімкнений кубічний сплайн (найкращий, якщо відомі похідні): задається ,
	Природній кубічний сплайн (“релаксована крива”)	m 0 = 0, mN = 0
	Екстраполювання в крайніх обмежуючих точках
	постійна біля крайніх точок	m0 = m1, mN = mN-1
	Задавання в кожній крайній точці	,

 

Розглянемо побудову зімкненого кубічного сплайну. Якщо відома перша похідна у початковій точці, можна обчислити m ₀ і перше рівняння прийме вигляд:

(5.15)

Аналогічно обчислюємо останнє рівняння:

(5.16)

Отримуємо тридіагональну лінійну систему рівнянь:

(5.17)

Коефіцієнти сплайну обчислюємо за формулами:

(5.18)

Для зручності обчислень кожен кубічний сплайн доцільно записувати у формі вкладених перемножень:

, (5.19)

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

У випадку константного задавання обмежень частину експериментальних точок на початку і вкінці проміжку «обрізають» для усунення великих похибок, які виникають в цих діапазонах. Тому при плануванні експерименту такі обчислювальні особливості потрібно враховувати.

Приклад 1. Обчислимо зімкнений кубічний сплайн, що проходить через точки (0, 0), (1, 0.5), (2, 2) та (3, 1.5). Перша похідна задовольняє граничним умовам = 0.2 та = -1. Обчислимо проміжні величини:

 

h₀ = h₁ = h₂ = 1;

d₀ = (y₁ – y₀)/h₀ = (0.5 - 0)/1 = 0.5;

d₁ = (y₂ – y₁)/h₁ = (2.0 – 0.5)/1 = 1.5;

d₂ = (y₃ – y₂)/h₂ = (1.5 - 2)/1 = - 0.5;

u₁ = 6(d₁ – d₀) = 6(1.5 – 0.5) = 6;

u₂ = 6(d₂ – d₁) = 6(-0.5 – 1.5) = -12.

Складемо основні рівняння (перше і останнє рівняння складають за формулами з табл. 5.1., інші рівняння – за формулою (5.14)):

Підставимо конкретні значення:

При спрощенні системи отримаємо:

Обчислимо значення m₁ = 2.52 та m₂ = -3.72 Скористаємося додатковими рівняннями з таблиці 5.1:

Підставимо розраховані значення у формули (5.18), за якими обчислимо коефіцієнти сплайн-функцій. Отримаємо наступні вирази сплайн-функцій:

Графічний розв‘язок системи поданий на рис. 5.4.

Рис. 5.4. Зімкнений кубічний сплайн.

 

Приклад 2. При формуванні у середовищі MatLAB [14] зімкненого кубічного сплайну, який проходить через точки (0, 0.0), (1, 0.5), (2, 2.0), (3, 1.5), з першою похідною у граничних точках S’(0) = 0.2; S’(3) = -1, функція задається так:

 

> > X = [0 1 2 3]; Y = [0 0.5 2.0 1.5]; dx0 = 0.2; dxn = -1;

> > S = zspline (X, Y, dx0, dxn)

S =

0.4800 -0.1800 0.2000 0

-1.0400 1.2600 1.2800 0.5000

0.6800 -1.8600 0.6800 2.0000

Графік сплайну будують, використовуючи команду polyval, яку потрібно задавати для кожного відрізка сплайну окремо:

 

> > x1 = 0:.01: 1; y1 = polyval (S(1,:), x1-X(1));

> > x2 = 1:.01: 2; y2 = polyval (S(2,:), x2-X(2));

> > x3 = 2:.01: 3; y3 = polyval (S(3,:), x3-X(3));

> > plot (x1, y1, x2, y2, x3, y3, X, Y, ’.’)

 

Контрольні питання

1. Що називається інтерполяцією та екстраполяцією?

2. Від яких чинників залежить точність інтерполяції?

3. Який принцип апроксимації функцій поліномом Лагранжа?

4. Що називається кубічної сплайн-функції? Які умови забезпечують неперервність та гладкість сплайн-функції?

5. Які бувають види кубічних сплайнів в залежності від обмежень в крайніх точках і які з них дозволяють отримати найвищу точність?

6. Чому точність інтерполяції кубічною сплайн-функцією вища ніж поліномом Лагранжа?

Розділ 6. Апроксимація експериментальних даних. Метод наймен­ших квадратів. Інтерполяція функцій за допомогою ортогональ­них поліномів

6.1. Апроксимація експериментальних даних. Метод найменших квадратів

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

Розглянемо задачу відновлення функції результатів спосте­режень методом найменших квадратів [6]. Це задача мінімізації функціоналу. При її розв‘язанні необхідно забезпечити мінімум міри відхилень експериментальних значень від обраної функції в (n+1) вузлових точках (х_і , у_і). Цільову функцію для цієї умови запишемо у вигляді:

(6.1)

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

(6.2)

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

У випадку, коли k = n (формула 6.2) функція j (х) збігається з інтерполяційним поліномом Лагранжа, побудованим по тих же вузлових точках. Для мінімізації цільової функції 6.1, функціоналу, необхідно, щоб перші похідні функціоналу І за його аргументами дорівнювали нулю (необхідна умова екстремуму функції [7]):

(6.3)

Обчислимо похідні функціоналу по невідомих:

(6.4)

Проведемо заміну:

(6.5)

Обчислимо наступні похідні:

(6.6)

Отримаємо рівняння:

(6.7)

У загальному випадку похідні функціоналу по невідомих:

(6.8)

Отримаємо систему рівнянь:

(6.9)

Якщо система має єдиний розв‘язок, то він визначає коефіцієнти полінома найкращого середньоквадратичного наближення. Отриманий поліном називається рівнянням регресії.

Приклад. Запишемо систему рівнянь, складену за методом найменших квадратів для функціонала: .

(6.10)

Якість апроксимації експериментальних даних поліномом j (х) оцінюється залишковою дисперсією:

(6.11)

де p – число ступенів свободи, яке обчислюється як різниця між числом дослідних значень n і кількістю коефіцієнтів апроксимуючого поліному m (p = n – m). Для функцій з різною кількістю коефіцієнтів апроксимуючого поліному значення дисперсії будуть різними, з них вибирають той, який має найменше значення .

 

6.2. Інтерполяція функцій ортогональними поліномами

 

Альтернативою методу найменших квадратів є метод, що оснований на використанні скалярних добутків базисних функцій [5, 11]. Якщо кожне рівняння системи:

(6.12)

помножити на відповідну базисну функцію j_j (х), j = 0, 1, …, m, отримаємо систему рівнянь у нормальний формі:

(6.13)

Система має (m+1) рівнянь відносно невідомих коефіцієнтів c_j , j=0, 1, …, m за значеннями функції f, що визначена на множині точок x_i , i=0, 1, …, n для будь-якого n ≥ т. Збільшення числа вузлових точок впливає лише на точність визначення скалярних добутків і не збільшує розмірності системи рівнянь.

Якщо в якості базисних функцій вибрати ортогональні поліноми (Лежандра, Чебишева, Ерміта та ін.), для яких , i ≠ j, , обчислення коефіцієнтів c_j значно спрощується:

(6.14)

У цьому випадку похибка ортогональна до всіх j_j (х), j = 0, 1, …, m, тобто:

(6.15)

Спільною характеристикою для ортогональних поліномів є форма системи рівнянь:

(6.16)

У загальному випадку систему можемо записати:

(6.17)

У даній системі – нижня трикутна матриця порядку (m+1). Розв‘язок задачі знайдемо з рівняння:

(6.18)

звідки:

(6.19)

Тобто, будь-який поліном n -го ступеню може бути представлений сукупністю базисних ортогональних поліномів виду:

(6.20)

Такий алгоритм дозволяє проводити наближення функції ортогональними поліномами за допомогою множення на відповідну базисну функцію (6.13), а потім представляти наближення звичайною поліноміальною формою (6.20). Загальні формули ортогональних поліномів Лежандра, Чебишева і Ерміта наведені в таблиці 6.1.

***

Апарат кусочно-лінійної інтерполяції (див. розділ 5) дозволяє ввести об‘єкти, на яких базується один із найбільш відомих сучасних сіткових чисельних методів — метод кінцевих елементів (п. 10.2.2). Досліджувана область розбивається сіткою, в загальному випадку нерівномірною. Вузлам сітки {t_n} ставиться у відповідність набір базисних функцій j_n(t), кожна з яких відповідає певному вузлу t_n, до того ж j_n(t_k)=d_kⁿ , j_n(t_k-1) = j_n(t_k+1) = 0, j_n(t_n)=1, а в інших точках вона обчислюється за допомогою кусково-лінійної інтерполяції.

 

Таблиця 6.1.

Властивості ортогональних поліномів [5]

Властивості	Поліном Лежандра	Поліном Чебишева	Поліном Ерміта
Область визначення
Рекурентна формула обчислення наступних поліномів
Загальна формула опису

 

Узагальнений інтерполяційний поліном F(t) в даному випадку можемо записати у вигляді:

(6.21)

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

 

6.3. Базисні сплайни (В-сплайни)

 

Сплайни з локальним носієм називають базисними сплайнами (B-сплайнами). Останнім часом в обчислювальній практиці широке розповсюдження набули B-сплайни (від англійського слова bell — дзвін (колокол)), зосереджені на скінченному відрізку [7, 11]. Вони використовуються як для інтерполяції функцій, так і в якості базисних функцій при побудові методів типу скінченних елементів.

B-сплайном (базисним сплайном) ступеню n-1 дефекту 1 відносно вузлів називається функція:

(6.22)

де .

Припустимо область розв‘язку задачі розбита рівномірною сіткою . Розглянемо кілька частинних випадків В-сплайнів.

При N = 2 В-сплайн (1-го порядку) будується найпростіше:

(6.23)

або

(6.24)

 

Рис. 6.1. В-сплайн першого порядку.

 

В-сплайн 2-го порядку запишемо у вигляді:

(6/25)

При , . Побудований сплайн має наступні властивості:

а) ,

б) , (6.26)

в) .

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

, (6.27)

де b — коефіцієнти інтерполяції, S — B-сплайн, індекс вказує на точку, для якої побудований сплайн і в якій він досягає максимуму. Система таких співвідношень, доповнюється граничними умовами. Отримана система для визначення коефіцієнтів розкладу буде мати тридіагональну матрицю з діагональною перевагою при виконанні обмеження на довжину сусідніх кроків: вони повинні різнитися не більше ніж в рази.

Кубічний В-сплайн (N = 4) має вигляд:

(6.29)

Після деяких спрощень можемо записати попередню формулу у вигляді:

Рис. 6.2. Графік кубічного В-сплайну.

 

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

Контрольні питання

1. Для яких задач використовують метод найменших квадратів?

2. В чому полягає суть методу найменших квадратів?

3. Як будується поліном найкращого середньоквадратичного наближення?

4. Яке рівняння називається рівнянням регресії?

5. Як оцінюється якість апроксимації експериментальних даних?

6. Назвіть види ортогональних поліномів?

7. Що називається базисним сплайном (В-сплайном)?

8. Назвіть види базисних сплайнів? Для яких задач вони застосовуються?

Частина 2.Чисельне диференціювання та інтегрування. Роз‘вязання диференційних рівнянь.

Розділ 7. Чисельне диференціювання та чисельне інтегрування

7.1. Чисельне диференціювання

 

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

 

7.1.1. Використання скінченних різниць

 

Звернемося до класичного визначення похідної. За визначенням похідна функції f(х) є нова функція, що дорівнює при кожному значенні х границі відношення прирощення функції () до відповідного прирощення аргументу Δ x, тобто: