Поліноми Ньютона

Іноді корисно знайти кілька поліномів P ₁(x), P ₂(x), …, P_N (x), які є наближенням функції і потім вибрати з них той, котрий задовольняє необхідні вимоги. При використанні поліномів Лаґранжа не існує чітко вираженого співвідношення між P_{N -1}(x) і P_N (x) – кожний поліном будується індивідуально, та обчислення полінома високого ступеня вимагає виконання безлічі операцій.

Поліном Ньютона, на відміну від полінома Лагранжа, має рекурентну властивість [8]:

(4.10)

(4.11)

(4.12)

Поліном (4.12) являє собою поліном Ньютона з N центрами і складається із P_{N -1}(x) за допомогою рекурентного співвідношення:

(4.13)

Задача інтерполяції полягає в знаходженні коефіцієнтів a_k для всіх поліномів P ₁(x), P ₂(x), …, P_N (x), які є наближенням заданої функції f (x).

P_k (x) будуються за центрами і мають вузли Коефіцієнти a_k полінома P_N (x) залежать від значень f (x_j), і обчислюються з використанням різницевих відношень функції f (x):

. (4.14)

Різницеві відношення для функції f (x):

(4.15)

Рекурентне правило побудови різницевих відносин високого порядку:

(4.16)

Таблиця різницевих відношень (табл. 4.1) будується з використанням (4.16).

Таблиця 4.1 – Різницеві відношення для

Для значень на інтервалі для функції f (x) можна побудувати єдиний поліном Ньютона зі степенем , для якого є правдивим:

. (4.17)

Поліном Ньютона має вигляд:

, (4.18)

де - коефіцієнти полінома Ньютона; .

Наближення Паде

Уведемо поняття раціонального наближення функції. Основна задача такого наближення – зведення максимальної помилки наближення до мінімуму.

Раціональне наближення функції f (x) на інтервалі – це відношення двох поліномів степенів N і M відповідно:

, (4.19)

де ; – поліноми степенів N і M відповідно.

Для наближення Паде необхідно, щоб функція f (x) та її похідні були безперервні у точці . Поліноми P_N (x) і Q_M (x) побудовані таким чином, що функції f (x) і R_N,M (x) збігаються у точці і їх похідні до N + М порядку також збігаються у в точці .

У випадку точним наближенням функції f (x) є розкладання у ряд Маклорена. При фіксованому значенні N + M помилка буде найменша, коли поліноми P_N (x) і Q_M (x) мають однаковий степінь або коли степінь полінома P_N (x) більше, ніж степінь Q_M (x).

Для аналітичної функції f (x), що має розкладання Маклорена правдивою є різниця :

, (4.20)

де – невідомі коефіцієнти наближення Паде.

Якщо перемножити суми в лівій частині (4.20) і коефіцієнти при степенях дорівняти нулю для , то в результаті отримаємо системи з N +1 і М лінійних рівнянь відповідно:

(4.21)

(4.22)

Першими знаходяться невідомі системи (4.22), потім рівняння в системі (4.21) послідовно використовуються для знаходження . Для пошуку розв’язку систем (4.21), (4.22) можна використовувати матричні методи розв’язання лінійних систем (метод виключення Гаусса, ітераційні методи Якобі, Гаусса-Зейделя та ін.) [5].

У табл. 4.2 наведено приклади програм для інтерполяції функцій поліномами Лаґранжа і Ньютона, написаних мовою пакета Matlab.

Таблиця 4.2 – Програми для інтерполяції функцій поліномами Лаґранжа і Ньютона

Інтерполяція поліномом Лаґранжа

Function [C, L]=lagran(X,Y) % вхідні параметри: X – вектор абсцис; Y – вектор ординат; % вихідні параметри: С, L – матриці коефіцієнтів поліномів Лагранжа; w=length(X); n=w-1; L=zeros(w, w); for k=1:n+1 V=1; for j=1:n+1 if k~=j V=conv(V,poly(X(j)))/(X(k)-X(j)); end end L(k,:)=V; end С=Y*L;

Інтерполяція поліномом Ньютона

Function [C, D]=newpoly(X,Y) % вхідні параметри: X – вектор абсцис; Y – вектор ординат; % вихідні параметри: С – вектор коефіцієнтів полінома Ньютона; D – таблиця % різницевих відношень; n=length(X); D=zeros(n, n); D(:,1)=Y’; for j=2:n for k=j:n D(k, j)=(D(k,j-1)-D(k-1,j-1))/(X(k)-X(k-j+1)); end end С=D(n,n); for k=(n-1):-1:1 C=conv(C,poly(X(k))); m=length(C); C(m)=C(m)+D(k, k); end