Інтерполювання за Ньютоном 2 страница

Рис. – 5.1

Залишковий член такої інтерполяції .

Оцінка залишкового члена залежить від диференціальних властивостей функції f(x).

Нехай . Позначимо - коливання функції f(x) на проміжку . Тоді використовується лема.

Лема (варіант теореми про середнє).

Нехай . Якщо величини однакового знака, то існує точка така, що .

За допомогою цієї леми доводиться теорема про оцінку залишкового члена лінійного інтерполяційного сплайна.

Теорема. Якщо , то . Дійсно, , де . З наведеної вище леми маємо , де . Отже,

.

З поліпшенням гладкості функції f(x) оцінка похибки її інтерполяції лінійними сплайнами також поліпшується. А саме, якщо , то , де .

Для можна одержати оцінку .

Подальше збільшення гладкості функції f(x) не дає підвищення порядку апроксимації. Відбувається насичення алгоритму.

Збіжність

Нехай на задана послідовність сіток : , k=1,2,3 …, які задовольняють умову при . Для будується інтерполяційний сплайн . Інтерполяційний процес вважається збіжним, якщо при для будь-якої функції f(x) з деякого класу. Звідси випливає можливість інтерполяції з наперед заданою точністю

.

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

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

Якщо , де k =1,2, то похибка . Маємо збіжність інтерполяції порядку .

Кубічний інтерполяційний сплайн

Кубічні сплайн-функції моделюють дуже старий механічний пристрій, яким користувалися креслярі. Вони брали гнучкі рейки, виготовлені з досить пружного матеріалу, наприклад з дерева. Ці рейки закріплювали, підвішуючи важки в точках інтерполяції, що відповідають інтерполяційним вузлам. Рейка або механічний сплайн набирали форму з найменшою потенційною енергією. Остання умова має свій математичний вираз f^(IV)(x) º 0. Якщо при цьому сплайн не руйнується, то тоді функція та її похідні повинні бути неперервними на [ х₀,х_n ]. З теорії балок відомо, що функція f(х) між кожною парою заданих точок може бути представлена поліномом 3-го степеня

f(x) = a_i + b_i(x - x_i) + c_i(x - x_i)² + d_i(x - x_i)³,

де х_i-1<х<х_i. При цьому між кожною парою сусідніх вузлів поліноми з'єднуються неперервно (так само, як їх перші та другі похідні).

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

Кубічну сплайн-функцію, що задовольняє умови f"(х₁)=f"(х_n)=0, називають природним кубічним сплайном. З математичної точки зору було доведено [Алберг, 1972], що вона є єдиною функцією з мінімальною кривизною серед усіх функцій, що інтерполюють функцію в заданих точках та мають квадратично інтегровану другу похідну. У цьому змісті кубічний сплайн буде самою гладкою функцією, що інтерполює задані точки.

Побудова кубічного сплайна - простий і чисельно стійкий процес. Для треба визначити 4 коефіцієнти для кожного проміжку , тобто 4n параметрів. Вимагається щоб у внутрішніх вузлах сплайн і його похідні до 2-го порядку були неперервними

, i=1,…,n-1; r=0,1,2.

Це дає 3n-3 умови для визначення параметрів, ще n+1 умова міститься у вимозі S₃(x_i) = y_i, i=0,1,…,n.. Разом маємо 4n-2 умови. Ще 2 умови, необхідні для однозначного визначення коефіцієнтів сплайна, як правило, задаються у вигляді граничних умов, тобто умов у точках a й b. Розглянемо природні граничні умови .

Позначивши та враховуючи її лінійність, одержуємо

, . (5.27)

Двічі інтегруючи (5.27), одержуємо

, (5.28)

, (5.29)

де А та B - постійні інтегрування. Вищезгадані умови дають

(5.30)

З них одержуємо

Підставляючи A та B в (5.29), одержуємо

(5.31)

. (5.32)

З (5.28) знаходимо значення однобічних похідних для вузла x_i, i=1,2,…,n-1

(5.33)

Вимагаючи неперервності у вузлі x_i одержуємо

, де i=1,…,n-1. (5.34)

Отже, отримуємо систему рівнянь відносно M_i вигляду

(5.35)

із квадратною матрицею A

і квадратною матрицею Н

.

Координатами вектора F є значення y₀,y₁,…,y_n.

Для матриці A ненульові елементи розміщені на головній діагоналі й двох сусідніх з нею. Такі матриці називаються тридіагональними. Для невиродженої матриці A виконана умова діагональної переваги . Отже, система (5.35) однозначно розв'язувана, тобто існує єдиний кубічний інтерполяційний сплайн.

Вигляд граничних умов змінює деякі елементи матриці A, але в кожному разі вона залишається матрицею з діагональною перевагою. Розв’язок системи (5.35) із тридіагональною матрицею A може бути знайдений методом прогонки.

Випадки використання кубічного сплайна

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

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

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

Якщо на кінцях відрізка відомі значення 1-ї похідної , то природно скористатися граничними (крайовими) умовами 1-го типу.

1 Граничні (крайові) умови 1-го типу. Якщо відомо, що , то для визначення маємо систему рівнянь

(5.36)

Якщо на кінцях відрізка відомі значення 2-ї похідної , то природно скористатися граничними (крайовими) умовами 2-го типу.

2 Граничні (крайові) умови 2-го типу. Якщо відомо

, то є система рівнянь

. (5.37)

Якщо є можливість вибору між граничними (крайовими) умовами 1-го та 2-го типів, то перевагу потрібно надати умовам 1-го типу.

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

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

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

3 Граничні (крайові) умови 3-го типу. Якщо - періодична функція , то і система рівнянь має вигляд

. (5.38)

Приклад реалізації алгоритмів інтерполяції функцій на псевдокоді

//розв’язує СЛАР методом Гауса

//M – матриця системи і вільні члени

//X – вектор відповідей

//n – кількість невідомих

linequ(M,n,e,X):

//доступна в модулі naz.pas

End

//X – значення аргумента

//Y – значення функції

//xi – значення аргумента, для якого потрібно знайти значення

// функції

//h – крок

//змінні DY, D2Y і т.д. – скінченні різниці

//змінні SDY, SD2Y і т.д. – розділені різниці

//відшукуємо значення інтерполюючого многочлена при x=xi

Find_PX(X,Y,n,h):

1 n:=X.length;

2 for i:=1 to n do

3 DY[i]:=Y[i+1]-Y[i]

Done

5 for i:=1 to (n-1) do

6 D2Y[i]:=DY[i+1]-DY[i]

Done

8 for i:=1 to (n-2) do

9 D3Y[i]:=D2Y[i+1]-D2Y[i]

Done

11 for i:=1 to (n-3) do

12 D4Y[i]:=D3Y[i+1]-D3Y[i]

Done

14 for i:=1 to n do

15 SDY[i]:=Y[i+1]-Y[i]/(X[i+1]-X[i])

Done

17 for i:=1 to (n-1) do

18 D2Y[i]:=SDY[i+1]-SDY[i]/(X[i+2]-X[i])

Done

20 for i:=1 to (n-2) do

21 D3Y[i]:=SD2Y[i+1]-SD2Y[i]/(X[i+3]-X[i])

Done

23 for i:=1 to (n-3) do

24 D4Y[i]:=SD3Y[i+1]-SD3Y[i]/(X[i+4]-X[i])

Done

26 t:=(xi-X[1])/h

27 return X[1]+(t/factorial(1))*DY[1]+((t*(t-1))/factorial(2))*D2Y[1]+((t*(t-1)*(t-2))/factotrial(3))*D3Y[1]+((t*(t-1)*(t-2)*(t-3))/factorial(4))*D4Y[1];

End

//R­ – дані сплайна

//eps – точність обчислень

//xi – значення аргумента, при якому потрібно знайти значення функції //

//відшукуємо значення кубічного сплайна в точці xi

Find_Spline(R,eps,xi)

1 linequ(R,R.length,1E-6,М)

2 k:=2

3 s31:=(X[k+1]-xi)*(X[k+1]-xi)*(2*(xi-X[k])+1)*Y[k]+(xi-X[k])*(xi-X[k])*(2*(X[k+1]-xi)+1)*Y[k+1]

4 s32:=(X[k+1]-xi)*(X[k+1]-xi)*(xi-X[k])*M[k]+(xi-X[k])*(xi-X[k])*(xi-X[k+1])*М[k+1]

5 return s31+s32

end

Оцінка похибки та збіжності при інтерполяції кубічними сплайнами

Якщо , то похибка інтерполяції кубічним сплайном

, де , .

Якщо , r=1,2,3,4, то оцінка має вигляд для .

Із цих оцінок треба встановити збіжність інтерполяційного процесу на послідовності сіток .

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

.

Приклад. Апроксимувати функції на відрізку [-2;2], використовуючи лінійний сплайн і природний кубічний сплайн.

Дослідження проведемо на рівномірних сітках з кількістю вузлів інтерполяції: 5, 7, 9, 15, 51, 101 відповідно. Визначимо відносну похибку інтерполяції сплайнами на різних сітках. Результати занесемо до таблиці.

Аналіз результатів показує, що точність апроксимації істотно залежить від кількості вузлових точок.

Число вузлів	Лінійний сплайн	Кубічний сплайн	Куб. сплайн по другій похідній
	0,0625	0,024	0,0092
	0,0278	0,011	0,0038
	0,0156	0,0061	0,002
	0,0051	0,002	0,0007
	0,0004	0,00016	0,000055
	0,0001	0,000036	0,000014

Апроксимаційні властивості кубічного сплайна

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

Якщо інтерпольована функція неперервна на відрізку , тобто , то

при .

Якщо інтерпольована функція має на відрізку неперервну першу похідну, тобто , а - інтерполяційний сплайн, що задовольняє граничні умови 1-го або 3-го типу, то при

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

На випадок, якщо , сплайн апроксимує на відрізку функцію , а його 1-а та 2-а похідні апроксимують відповідно функції та :

5.2.7 Застосування інтерполяції для складання таблиць

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

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

Щоб помилка інтерполяції не перевищувала за абсолютною величиною деяке а, необхідно вибрати h, яке задовольняло б умову

5.3 Метод найменших квадратів

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

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

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

, (5.39)

де функції , ,..., називатимемо базовими функціями. Потрібно визначити невідомих коефіцієнтів () з умови, щоб квадрат середньоквадратичного відхилення (СКВ) апроксимуючої функції від апроксимованої (обчисленого для заданих значень аргумента )

(5.40)

був мінімальним (саме тому відповідний метод називається МНК). Квадрат СКВ (5.40) є функцією невідомих коефіцієнтів (). Тому для пошуку його мінімуму необхідно знайти частинних похідних за окремими коефіцієнтами