Interpolasi Polinomial Newton – Script Matlab

Ahmaddahlan.NET – Interpolasi Lagrange yang memenuhi n+1 untuk data {x_i,y_i=f(x_i),i=0,…,n} memenuhi data l_i(x). Polinomial dari Interpolasi Newton dapat ditulis sebagai berikut :

Maka solusi dari interpolasi Polinomialnya adalah :

Jika diturunkan akan ketemu dengan deret :

Jika data (x_n, y_n) berikutna didapatkan, maka persamaan ini bisa digunakna untuk menghitung koefisien c_n. Untuk derajat polinomial n^th maka N_n(x) akan memenuhi n+1 di titik (x_i, y_i), (i = 0, … , n) :

Dalam bentuk matriks dapat ditulis :

Koefisien c₀ , … , c_n dapat diselesaikan dengan sistem persamaan segitiga secara bertahap :

c₀ =

c₁ =

c2 = , dst

secara umum kita tuliskan :

Persamaan dapat dijabarkan ke kth untuk f[x₀,…,x_k] yang dimulai dari k+1 sehingga Interpolasi Polynomial Newton dapat ditulis :

Interpolasi Polinomial Newton sama dengan yang ada pada Lagrange dan Interpolasi Fungsi Berpangkat yakni N_n(x) = L_n(x)=P_n(x). Ketiganya adalah Polinomial berpangkan n^th hanya berasal dari basis dan koefisien yang berbeda.

Kondisi Khusus Interpolasi Polinomial Newton

a. x_n+1, y_n+1

Ketika terdapat titik tambahan x_n+1, y_n+1 yang bisa digunakan maka semua basis polinomial sebelumnya bisa digunakan dengan koefisien tetap, analisinya hanya perlu mencari polinomial basis baru untuk n+1.

pada titik n+1, perbedaanya ditunjukkan c_n+1 = f [ x₀ , … , x_n , x_n+1]. Melalui persamaan ini, Interpolasi Newton yang baru untuk n+1 bisa didapatkan dengan aturan pemjulahan

karena N_n+1 pasti melalui titik (x_n+1, y_n+1) maka :

f(x_n+1) = N_n+1(x_n+1) = N_n+1 + f [ x₀ , … , x_n , x_n+1] l(x)

namun titik x_n+1 adalah titik yang bisa dimana saja maka, maka kita dapat menggantinya dengan x sehingga

f(x) = N_n(x) = N_n+1 + f [ x₀ , … , x_n , x] l(x)

b. n + 1

Misalkan semua titik n + 1 mendekati satu posisi, x_i → x₀, (i = 1,…,n), pada batas diaman semaunya mendekati nilai x₀ yang terulang sebanyak n kali

Maka interpolasi newton dengan basis n+1 menjadi

Dimana suku pertama dari n+1 untuk deret Taylor memiliki kesalahan perpotongan dengan persamaan :

dimana ξ (dibaca xi) adalah titik yang sama untuk x_i dan x₀, maka dari sini kita bisa lihat bahwa deret Taylor adalah kasus khusus untuk interpolasi Polinomial newton.

c. n + 1 pada x₀ = a ≤ x_i ≤ … ≤ x_n-1 ≤ x_n = b

x₀ = a ≤ x_i ≤ … ≤ x_n-1 ≤ x_n = b jaraknya sama dengan :

Interpolasi Newton dapat disederhanakan dengan x ∈ (a,b), misalkan c = (x – x₀) / h, maka x = x₀ + ch dan x – xi = (x₀ + ch) – (x₀ + ih) = (c – i ) h, sehingga Polinomial Newton bisa dituliskan dalam bentuk

dimana

Contoh Kasus :

Sebuah fungsi y = f (x) = x sin (2x + π/4) + 1 dengan derajat polinomial n = 3 dan n + 1 = 4, ditunjukkan pada data berikut ini

Tentukan : Devide Diference untuk suku f [x_i] = f (x_i) untuk i = 0, …, n

Script untuk Analisis Menggunakan Matlab

Untuk menyelesaikan maslaah diatas dengan menggunakan bantuan Peprograman Matlab, koefisien c_i = f[x₀,…,x_n] dimana i = 0,…,n

function [v N]=NI(u,x,y)  % Newton's Interpolation
    % vectors x and y contain n+1 points and the corresponding function values
    % vector u contains all discrete samples of the continuous argument of f(x)
    n=length(x);          % number of interpolating points
    k=length(u);          % number of discrete sample points
    v=zeros(1,k);         % Newton interpolation 
    N=ones(n,k);          % all n Newton's polynomials (each of m elements)
    N(1,:)=y(1);          % first Newton's polynomial
    v=v+N(1,:);    
    for i=2:n             % generate remaining Newton's polynomials
        for j=1:i-1
            N(i,:)=N(i,:).*(u-x(j));   
        end
        c=DividedDifference(x,y,i)  % get the ith coefficient c_i
        v=v+c*N(i,:);     % weighted sum of all Newton's polynomials
    end
end

function dd=DividedDifference(x,y,i) % generate f[x_0,...,x_i] in expanded form
    dd=0;
    for k=1:i             % loop for summation
        de=1;
        for l=1:i         % loop for product
            if k~=l   
                de=de*(x(k)-x(l));               
            end
        end
        dd=dd+y(k)/de;    % ith coefficient c_i
    end
end

function dd=DividedDifferenceMatrix(x,y) % generate divided difference matrix
    n=length(x);                         % the coefficients are along diagonal
    dd=zeros(n);                         % matrix of divided differences
    dd(:,1)=y;
    for i=1:n
        fprintf('%6.3f\t',dd(i,1))
        for j=2:i
            dd(i,j)=(dd(i,j-1)-dd(i-1,j-1))/(x(i)-x(i-j+1));
            fprintf('%6.3f\t',dd(i,j));
        end
        fprintf('\n');
    end
end