Лекція : Інтерполяційні многочлени Ньютона першого і другого виглядів

1. Постановка задачі інтерполювання

2. Поняття про скінчені різниці та їх властивості

3. Інтеропляційний многочлен Ньютона першого вигляду

4. Інтеропляційний многочлен Ньютона другого вигляду

Загальна постановка задачі інтерполювання (інтерполяція – знаходження по ряду значень функції проміжних її значень) полягає у наступному: нехай на відрізку [a;b] в n+1 даних точках x ,x ,…,x відомі значення деякої функції f(x) :

y =f(x ), y =f(x ), …, y =f(x ).

Треба визначити значення функції f(x) в точці хЄ[a;b], що не збігається з даною.

Звичайно, з такою постановкою задачі розв’язок задачі невизначено. Більш конкретно задача інтерполювання функції f(x) полягає в тому, щоб побудувати функцію F(x), що належить певному класу функцій і та що в даних точках х набуває тих же значень y =f(x ), що і функція f(x): F(x )=y (i=0,1,…,n).

Тоді для х Є[a;b] наближено покладають f(x)=F(x).

Точки x ,x ,…,x називають вузлами (чи полюсами ) інтерполяції, а функцію F(x) – інтерполяційною функцією.

Звичайно інтерполяційну функцію шукають серед многочленів P (x), степінь яких не перевищує n і які задовольняють умові P (x )=y =f(x ), P (x )=y =f(x ),...,P (x )=y =f(x ). (1)

Неважко показати, що існує тільки один многочлен P (x) степені не вище n, що задовольняє всі умови (1).

Задача алгебраїчного (параболічного) інтерполювання функції y=f(x) на [a;b] полягає у відшуканні аналітичного вираження многочлена P (x), що задовольняє умові (1).

Многочлен P (x), визначений по умові (1), називається інтерполяційним многочленом для f(x), а формули для її побудови – інтерполяційними формулами.

Заміна функції y=f(x) її інтерполяційним многочленом f(x)=P (x), хЄ[a;b] називається інтерполюванням (алгебраїчним) функції.

Звичайно, при цьому виникає питання про оцінку похибки наближеної формули (2).

Геометричний зміст інтерполювання – заміна кривої y=f(x) параболою y=P (x) (порядка n), що проходить через задані точки (x ;y ), (х1;у1),...,(хn;yn).

Формулу (2) вважають інтерполяційною, якщо хЄ[x ;x ], тобто знаходиться між вузлами інтерполяції, якщо ж х [x ;x ], тобто знаходиться зовні відрізка, то формулу (2) називають екстраполяцією. В дальнішому ця відміність не враховується.

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

Нехай функція представлена у вигляді таблиці:

 

Х0 Х1 ... Хі ... Хn
Y0 Y1 ... Yi ... Yn

Вузли інтерполяції рівностоящі з кроком h, тобто х1=х0+h, x2=x0+2h, ..., xn=xn-1+h=x0+nh. Різниці

y1-y0= y0,

y2-y1= y1,

......................... (1)

yi+1-yi= yi,

........................,

yn-yn-1= yn-1.

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

Різниці перших скінчених різниць y1- y0= 2y0, y2- y1= 2y1,..., yі+1- yі= 2yі,..., yn-1- yn-2= 2yn-2 (2)

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

k-1y1- k-1y0= ky0,

k-1y2- k-1y1= ky1,

............................................, (3)

k-1yi+1- k-1yi= kyi, (k=(1,n) ; 0y=y).

...........................,

k-1yn-(k-1)- k-1yn-k= kyn-k ,

Формули (3) носять рекурентний характер, вони виражають різницю k-го порядку через різниці (k-1) порядку. Однак послідовні наближення можна виразити і безпосередньо через значення функції. Дійсно, із формули (1) слідує, що yi=yi+1-yi=у(хі+h)-y(xi). Далі із формули (2), враховуючи (1), знаходимо

y2i= yі+1- yі=(уі+2-уі+1)-(уі+1-уі)=уі+2-2уі+1+уі=у(хі+2h)-2y(xi+h)+y(xi) і так далі. В загальному

kyi= , де - біномінальний коефіцієнт (0!=1)

Нерідко буває корисні обернені формули, які дають вирази значень функції через скінчені різниці. Із співвідношення (1) випливає, що у1=у0+ y0, аналогічно у2=у1+ y1=(у0+ y0)+ y1, Але враховуючи (2), 2y0= y1- y0 і у2=у0+2 y0+ 2y0.

Розмірковуючи аналогічно, можна визначити значення уk при любому k через y0 і різниці до k-го порядку:

, де =у0.

Перерахуємо деякі властивості скінчених різниць:

1) 1) Якщо с=const, то с=0;

2) 2) (cf(x))=c f(x);

3) 3) (f1(x)+f2(x))= f1(x)+ f2(x);

4) 4) m( nf(x))= m+nf(x).

Користуючись цими властивостями для многочлена y=Pn(x)=a0xn+a1xn-1+...+an-1x+an. Знаходимо першу різницю

у= Pn(x)=a0 (xn)+a1 (xn-1)+...+an-1 (x).

Враховуючи, що (хn)= (x+h)-xn=nhxn-1+ , одержимо

Pn(x)=a0nhxn-1+(a0 .

Таким чином, перша різниця многочлена степені n зі старшим членом а0хn є многочлен степені n-1 зі старшим членом а0nhxn-1. Обчислюючи аналогічним чином різниці любого порядку, впевнимось у справедливості наступного твердження: Якщо Рn(x)- многочлен степені n зі старшим членом а0хn, то для любого k<n різниця kPn(x) є многочлен степені n-k зі старшим членом n(n-1)...(n-k+1)a0hkxn-k; різниця n-го порядку постійна, а для k>n різниця рівна нулю.

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

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

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

Ітак, нехай задані вузли інтерполяції з кроком h: x0,x1=x0+h, x2=x0+2h, ...,xn=x0+nh.

Розглянемо многочлен степені n, записаний у вигляді:

Pn(x)=q0+q1(x-x0)+...+qk(x-x0)...(x-xk-1)+...+qn(x-x0)...(x-xn-1) (1) і визначемо його коефіцієнти q0, q1..., qk,...,qn.

Поставимо в (1) х=х0, тоді Pn(x1)=qn+q1(x1-x0), Pn(x1)=y1=y0+q1(x1-x0), q1= ;

Потім при х=х2 одержимо

Pn(x2)=q0+q1(x2-x0)+q2(x2-x0)(x2-x1);

y2=y0+ , у2-у0-2 у0=q22h2;

q2= .

Аналогічно, одержимо q3= , ..., qk= , ...,qn= .

Підставляючи всі одержані коефіцієнти у (1), тоді

Pn(x)=y0+ . (2)

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

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

Надамо формулі (2) деякий інший вигляд, ввівши змінну t= . Оскільки x-x0=th, x-x1=x-x0-h=th-h=(t-1)h, x-x2=(t-2)h,…,x-xn-1=(t-(n-1))h, то підставивши одержані значення в (2), маємо

Pn(x)=Pn(x0+th)=y0+ (3)

Це і є кінцевий вигляд першої інтерполяційної формули Ньютона. Поклавши в формулі (3) n=1, одержимо лінійну інтерполяцію P1(x)=P1(x0+th)=y0+ y0t, а при n=2 – квадратну P2(x)=P2(x0+th)=y0+ y0t+

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

Враховуючи, що вузли інтерполяції рівновіддалені, і враховуючи, що многочлен Ньютона записаний у вигляді (3), маємо (4), де Мn+1=max , a x b.

Коли вираз f(n+1)(x) невідомий, але є додатковий вузол інтерполяції хn+1 для оцінки Rn(x), то користуються формулою , (5).

Звідси отримуємо дуже зручну оцінку похибки лінійної інтерполяції

, де найбільше значення модуля других різниць.

4. Інтеропляційний многочлен Ньютона другого вигляду.

Формулу

Pn(x)=y0+ або

Pn(x)=Pn(x0+th)=y0+ називають інтерполяційною формулою інтерполювання вперед, так як вона будується з використанням значення функції і її різниць в початковому вузлі інтерполяції х0. ЇЇ зазвичай застосовують при інтерполяції в точках х, близьких до х0 ( для зменшення похибки інтерполювання ). Якщо ж потрібно інтерполювати в точках х, близьких до вузла інтерполяції хn, то краще користуватися так званою формулою для інтерполяції назад. Для виводу її представимо Pn(х) у вигляді

Pn(x)=b0+b1(x-xn)+b2(x-xn)(x-xn-1)+…+bk(x-xn)…(x-xn-(k-1))+…bn(x-xn)…(x-x1). (6)

Підставляючи в формулу (6) послідовно х=хn, x=xn-1, …, x=x0. Отримаємо х=хn, Pn(xn)=b0, b0=Pn(xn)=yn;

x=xn-1, Pn(xn-1)=yn-1=b0+b1(xn-1-xn)=b0-b1h, yn-1-yn=-b1h, b1= ;

x=xn-2, Pn(xn-2)=yn-2=b0+b1(xn-2-xn)+b2(xn-2-xn)(xn-2-xn-1), yn-2-yn+ , b2= . Аналогічно маємо b3= ,…, bn= .

Формула (6) при знайдених коефіцієнтах прийме вигляд Pn(x)=yn+ (7). Це і буде друга інтерполяційна формула Ньютона. Якщо ж ввести нову змінну t, поклавши t= , то з (7) отримаємо інший вигляд другої інтерполяційної формули Ньютона: Pn(x)=Pn(xn+th)=yn+ . (8)

Оцінка останнього члена формули (7): , де Мn+1=max , a x b.

Використовуючи скінчені різниці при додатковому вузлі інтерполяції можна сказати, що .