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

Недоліком інтерполювання за Лагранжем є те, що якщо для поліпшення наближення додати ще один вузол інтерполювання, доведеться всі обчислення проводити заново.

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

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

; (). (5.8)

Різниці

(5.9)

називають скінченними різницями першого порядку. Різниці сусідніх скінченних різниць першого порядку

(5.10)

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

(5.11)

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

Розглянемо поліном

. (5.12)

Визначимо його коефіцієнти. Коефіцієнт визначимо з умови проходження полінома через першу точку ()

. (5.13)

З умови проходження полінома через точку () одержимо значення

; . (5.14)

Аналогічно визначається решта коефіцієнтів

. (5.15)

Підставляючи отримані вирази у (5.12), одержуємо

. (5.16)

Це є перша інтерполяційна формула Ньютона (формула інтерполювання вперед).

Як бачимо, особливостями інтерполювання за Ньютоном є:

n при появі нового вузла додається лише новий член, решта не перераховується;

n коефіцієнти швидко зменшуються зі зростанням , бо у знаменнику міститься факторіал від .

Іноді використовується формула для інтерполювання назад

.

Візьмемо деяку функцію f(x) R і систему вузлів інтерполяції , , при і j. Вузли інтерполяції не є рівновіддаленими. Для цієї функції і вузлів утворимо відношення

.

Вони називаються розділеними різницями першого порядку. Одержавши їх, ми можемо утворити нові відношення

…,

Вони називаються розділеними різницями другого порядку. Взагалі, якщо ми уже визначили розділені різниці k- го порядку ,то розділені різниці (k+1)-го порядку знаходяться за допомогою формули

.

Іноді замість для позначення розділених різниць використовують позначення .

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

При скінченні і розділені різниці пов'язані співвідношенням у вигляді

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

За допомогою розділених різниць можна побудувати інтерполяційний многочлен Ньютона

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

5.2.3 Інтерполювання за Ермітом

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

Інтерполяційним поліномом Ерміта -го порядку називають поліном аргумента , який визначається з умов

; ;

; ;. ;

........... (5.17)

; ;. ;

...........

; ; .

Тут, як і раніше, - кількість вузлів інтерполяції.

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

Інтерполяційний поліном Ньютона (5.12) узагальнюється на випадок кратних вузлів таким чином:

(5.18)

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

5.2.4 Похибка інтерполяції та способи її зменшення

Зафіксуємо точку x та визначимо похибку інтерполяції r_n(x)=f(x)-P_n(x). Нехай та введемо функцію g(s)=f(s)-P_n(s)-kw(s), де w(s)=(s-x₀)(s-x₁)…(s-x_n). При s=x_i, i=0,1,…,n, w(x_i)=0. Тому g(x_i)=0, бо f(x_i)=P_n(x_i). Виберемо деяку точку x¹x_i, i = 0,1,…,n та виберемо коефіцієнт k так, щоб g(x)=0. Тоді f(x)-P_n(x)-kw(x)=0; k=(f(x)-P_n(x))/w(x).

Враховуючи, що w⁽ⁿ⁺¹⁾(s) = (n+1)! та те, що g(s) має n+2 нулі на [ a;b], то g'(s) має n+1 нуль, g''(s) має n нулів, …, g⁽ⁿ⁺¹⁾(s) має принаймні один нуль. Нехай це буде при s=x. Тоді

.

Звідси отримуємо оцінку для похибки інтерполювання

.

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

. (5.19)

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

(5.20)

Для визначення многочленів Чебишева часто користуються тригонометричною формою запису

, (5.21)

що приводить до таких самих виразів для , як і в (5.20).

Із тотожності

при маємо рекурентну формулу

.

Многочлен має коренів, які можна отримати, розв’язавши рівняння , або ;

(5.22)

Як бачимо з (5.22), всі коренів, що відповідають значенням знаходяться на відрізку [-1,1], причому ці точки не рівновіддалені, а згущуються ближче до кінця даного відрізка. З формули (5.21) також очевидно, що на відрізку [-1,1]

(5.23)

Доведено, що серед усіх можливих значень на відрізку корені многочлена мають ту чудову властивість, що для них величина

(5.24)

має найменше за модулем максимальне значення.

Беручи до уваги (5.24), запишемо

. (5.25)

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

, де .

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

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

Оцінка похибки має вигляд

.

5.2.5 Збіжність процесу інтерполяції

Розглянемо послідовність сіток

w_n: a=x₀<x₁<…<x_n-1 <x_n=b.

Кажуть, що інтерполяційний поліном рівномірно збігається до заданої функції , якщо при max (x -x_n-1) ® 0 . Справедливі такі теореми.

Теорема Фабера. Для будь-якої послідовності сіток w_n знайдеться така, що збіжність відсутня.

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

Приклад. Використовуючи інтерполяційний поліном Ньютона, визначити f(0.14), де y=f(x) задана таблично.

x		0.1	0.2	0.3	0.4	0.5
y		0.1002	0.2013	0.8045	0.4108	0.5211

Розв’язання. Складаємо таблицю скінченних різниць, користуючись пакетом Excel:

	A	B	C	D	E	F	G
	x	y
			=B3-B2	=C3-C2	=D3-D2	=E3-E2	=F3-F2
	0,1	0,1002	=B4-B3	=C4-C3	=D4-D3	=E4-E3
	0,2	0,2013	=B5-B4	=C5-C4	=D5-D4
	0,3	0,3045	=B6-B5	=C6-C5
	0,4	0,4108	=B7-B6
	0,5	0,5211

У результаті отримаємо таке:

	A	B	C	D	E	F	G
	x	y
			0,1002	0,0009	0,0012	-0,0002	0,0001
	0,1	0,1002	0,1011	0,0021	0,0010	-0,0001
	0,2	0,2013	0,1032	0,0031	0,0009
	0,3	0,3045	0,1063	0,0040
	0,4	0,4108	0,1103
	0,5	0,5211

Для розрахунку f(0.14) скористаємося інтерполяційним поліномом Ньютона, покладаючи, що x₀=0.1 та h =0.1; тоді q=(x-x₀)/h =(0,14-0,1)/0,1=0,4. Звідси за формулою визначаємо:

f(0.14) ≈0,1002+0,1011*0,4+0,0021*0,4*(-0,6)/2+ +0,1010*0,4*(-0,6)*(-1,6)/6 ≈ 0,1405, або у MS Excel у даному випадку, формула матиме такий вигляд: =B3+Q*C3+Q*(Q-1)*D3/ФАКТР(2)+Q*(Q-1)*(Q-2)*

*E3/ФАКТР(3), де Q - адреса комірки із розрахованим значенням q.

При цьому похибка наближення дорівнює R4=|f(0.14)-P₃(0.14)| <0.0001*0.4*0.6*1.6*2.6/4!= 4.16*10-6, або у MS Excel =ABS(F3*Q*(Q-1)*(Q-2)*(Q-3))/ФАКТР(4).

5.2.6 Інтерполяція за допомогою сплайнів

Підвищення точності інтерполювання вимагає збільшення вузлів інтерполяції. Це призведе до зростання степеня інтерполяційних многочленів. Але в умовах відсутності додаткової інформації про задану таблично функцію останні дають досить значну похибку. На практиці рідко проводять інтерполяцію поліномами степенів вище третього, тому що, по-перше, вони дають значні похибки й, по-друге, при нескінченному збільшенні порядку n інтерполяційного полінома Р_n(х) послідовність P_n не є збіжною (відповідно до теореми Фабера). Цей факт уперше виявив Рунге в 1901 р. В цьому випадку більш ефективним є використання сплайнів, що на проміжку між вузлами інтерполювання є поліномами невисокого степеня. На всьому проміжку інтерполяції сплайн - це функція, що склеєна з різних частин поліномів. Отже, розглянемо на відрізку систему вузлів . Сплайном називається функція, що визначена на , має на ньому неперервні похідні порядку і на кожному частковому відрізку збігається з деяким многочленом степеня не вище . При цьому хоча б на одному з відрізків степінь многочлена дорівнює . Якщо , маємо інтерполюючий сплайн. Визначити сплайн можна також так. Поліноміальним сплайном порядку m та дефекту k називається функція S_m,k(x) на сітці a=x₀<x₁<…<x_n-1<x_n=b така, що:

1) кожному проміжку ;

2) число k називається дефектом сплайна, якщо , 0<k<m;

3) розглянемо сплайн дефекту 1. S_m,1 = S_m. Інтерполяційним сплайном називається S_m(x), якщо S_m(x_i)=y_i, i = 0, 1, …, n.

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

Нехай - розбиття відрізка : , - задані значення.

Сплайном першого степеня називається:неперервна на відрізку , лінійна на кожному частковому проміжку функція f(x). Його позначення S₁(x). Нехай . Вираз для сплайна S₁(x) на цьому проміжку

(5.26)

y

*

*

*

*

*

*

*

O