Interpolasi

Topics
• Interpolation problems
• Existence of solutions
• Polynomial Interpolations
• Standard basis
• Lagrange
• Newton
• Hermite
• Error
• Piecewise polynomial interpolations (Cubic Splines)
Persoalan interpolasi
• Diberikan data dicari fungsi yang memenuhi – persyaratan in disebut
syarat interpolasi.
• Diasumsikan bahwa berbeda satu sama lain dan berada dalam ruang
fungsi berdimensi n (sesuai dengan jumlah data yang diketahui).
• Contoh
Ekistensi Solusi
• Misalkan di mana C adalah ruang fungsi berdimensi n. Selanjutnya
misalkan juga adalah basis dari C.
• Maka terdapatlah dengan tunggal sedemikian hingga
• Untuk mencari digunakan n syarat interpolasi, yaitu: yang dapat
dinyatakan sebagai persamaan aljabar

di mana adalah matrix berukuran nxn dengan , sementara c dan y adalah

vector yang berturut-turut memuat koefisien dan data interpolasi .
• Karena bebas linear dan distinct, maka nonsingular. Jadi vector c pasti
ada dan unique.
Contoh: Diketahui data {(1,2), (2,0), (3,4)}
• Carilah fungsi f yang menginterpolasi data di atas dari ruang fungsi:
• A1 = Span{
• A2 = Span{1, sin(x), sin(2x)}
•
Polynomial Interpolation
• Ruang polynomial orde-n berdimensi n+1. Jadi untuk menginterpolasi
dengan polynomial orde-n diperlukan n+1 data.
• Misalkan data interpolasi adalah
• Misalkan juga adalah polynomial orde-n yang menginterpolasi data di
atas, yaitu
• Representasi polynomial akan tergantung basis yang digunakan.
• Catatan: Interpolasi polynomial bersifat projective, artinya jika data
yang diberikan merupakan sample dari polynomial oder n atau
kurang, maka akan sama dengan polynomial semula.
Basis Standard
• Dengan basis standard maka representasi polynomial adl sbb:

• Sehingga syarat interpolasi menghasilkan sistem persamaan linear

• - disebut van der Monde system
• diperlukan teknik khusus untuk menyelesaikan SPL di atas.
Contoh
Basis Lagrange
• Dalam hal ini
• Perhatikan bahwa

• Sehingga matrix coefficient pada sistem persamaan linear yang

dihasilkan akan berupa matrix identitas. Jadi diperoleh
Contoh
Basis Newton
• Polynomial disajikan sebagai
• Perhatikan bahwa , sehingga matrix koefisien berupa matrix segitiga
bawah sbb:

• Catatan: entry (i,j) dari matrix di atas adalah

• Sistem persamaan linear di atas dapat diselesaikan dalam O(n2) flops.
Contoh
Octave function untuk menghitung
polynomial dengan basis Newton
• Diperlukan dua fungsi, yaitu fungsi penghitung basis; dan fungsi
penghitung polynomial hasil interpolasi.
• Fungsi penghitung basis
• function N=BasisNewton(x,i,t) % fungsi ini mengitung basis ke-i pada titik t
dengan data interpolation points x.
• if i==1
• N=1
• elese
• N=BasisNewton(x,i-1,t)*(t – x(i-1));
• end
Octave function untuk menghitung
polynomial dengan basis Newton
• Fungsi untuk menghitung polynomial p dengan basis Newton
• function p=PolyNewton(x,y,t) % menghitung polynom yang menginterpolasi data (x,y) di titik t.
• n=length(x); %polynom p memiliki order n-1
• L=zeros(n,n);
• for j=1:n
• for i=j:n
• L(i,j)= BasisNewton(x,j,x(i));
• end
• end
• c=SegitigaBawah(L,y); %Catatan: Agar lebih efisien L dan c dihitung terpisah; karena tidak tergantung pada t.
• p=c(1);
• for i=2:n
• p=p+c(i)*BasisNewton(x,i,t);
• end
Divided Difference Table
• Jika perhitungan c dilakukan secara manual, maka lebih mudah
menggunakan divided difference table sbb:

xi yi
x0 y0
x1 y1 (y1-y0)/(x1-x0)=a
x2 y2 (y2-y1)/(x2-x1)=b (b-a)/(x2-x0)
… … …..

xn yn (yn-yn-1)/(xn-xn-1)
Hermite Interpolation
• Jika f(x) diketahui dan differentiable; polynomial yang menginterpolasi
f(x) dapat digunakan order yang lebih tinggi, dengan memanfaatkan
turunan f(x) sebagai data tambahan. Teknik ini dikenal dengan
interpolasi Hermite
• Untuk memudahkan perhitungan polynomial dengan interpolasi
Hermite, digunakan tabel divided difference, dengan mereplikasi titik
data di mana turunan f akan dijadikan sebagai data tambahan. Jika
turunan pertama saja yg digunakan, maka data di titik tsb. digunakan
dua kali; dan jika turunan kedua juga digunakan maka direplikasi 3 kali
dan seterusnya.
Contoh Interpolasi Hermite utk di titik
x=0,1,4,9
• Kita ketahui bahwa ; yang tedefinisi pada x=1,4 dan 9;
• Maka divided difference table yang dihasilkan adalah sbb:
x
0 0
1 1 1
1 1 1/2 -0,5
4 2 1/3 -0,05556 0,111111
4 2 1/4 -0,02778 0,009259 -0,02546
9 3 1/5 -0,01 0,002222 -0,00088 0,002731
9 3 1/6 -0,00667 0,000667 -0,00019 8,56E-05 -0,00029

• diperoleh polynomial orde-8

Akurasi & Analisa Error
• Misalkan adalah polynomial order n yang mengiterpolasi pada
• Selanjutnya definisikan fungsi error
• Maka

• dengan suatu konstanta yang memenuhi ;

• Tampak bahwa , yang berarti bahwa menginterpolasi di titik
interpolasi ;
• Ternyata meningkatkan n tidak selalu dapat membuat menjadi lebih
kecil.
Fenomena Runge
Misalkan mengiterpolasi pada interval [-1,1]
titik interpolasi dipilih shg tersebar secara
seragam pada (-1, 1).
Jika digunakan n=4 maka diperoleh seperti
gambar di sebelah.
Perhatikan bahwa terjadi error yang cukup
signifikan di kedua ujung interval. Error akan
semakin besar jika n diperbesar.
Splines (Piecewise Polynomial Interpolation)
• Interpolasi dengan polynomial orde tinggi dapat berpotensi
meningkatkan error. Sehingga tidak direkomendasikan. Sementara,
interpolasi dengan polynomial orde rendah pada selang (interval) yang
lebar juga akan tidak akurat.
• Ide selanjutnya adalah menggunakan interpolasi dengan polynomial
orde rendah, tapi pada selang yang kecil.
• Jika misalnya akan dilakukan interpolasi pada data point i=0,1,…, n;
maka dapat dilakukan interpolasi pada masing-masing subinterval ,
dengan menggunakan polynomial orde rendah. Misalkan adalah
polynomial yang terdefinisi pada selang
• Teknik ini disebut splines interpolation
Linear Splines
Misalkan diberikan data points

x 1 2 3 4 5 6 7 8 9 10
y 2 4 3 1 3 6 7 5 4 2

Kemudian dilakukan interpolasi linear yang

menghubungan setiap titik interpolasi.
Maka dipeoleh

Sangat sederhana, tapi kurva yang dihasilkan

patah-patah.

Agar diperoleh kurva lebih mulus, gunakan

cubic splines
Cubic Splines
• Misal diberikan data points
• Selanjutnya definisikan suatu polynomial orde-3 yang
menginterpolasi data dengan ketentuan sbb:
1. menginterpolasi data: ; ada ( n+1 points)
2. kontinyu pada titik interior: - (n-1)
3. Turunan pertama kontinyu: - (n-1)
4. Turunan kedua kontinyu: - (n-1)
• Sehingga total terdapat 4n – 2 data.
• Sementara masing2 memiliki 4 parameter; sehingga perlu 4n data
• diperlukan 2 data tambahan. Natural splines =0
Contoh: Natural cubic splines di x=0,1,4
 𝑘𝑖 3 𝑘𝑖+1 3
𝑆 𝑖 ( 𝑥 )= ( 𝑥 − 𝑥 𝑖+1 ) + ( 𝑥 − 𝑥𝑖 ) + 𝐴𝑖 x +𝐵𝑖
6 ( 𝑥 𝑖 − 𝑥 𝑖+ 1) 6 ( 𝑥𝑖+1 − 𝑥𝑖 )
Konstruksi Cubic Splines
• Karena adalah cubic polynomial (order 3), maka linear.
• Selanjutnya misalkan , maka

• Sehingga dg integral didapat

• Selanjutnya diperoleh
Konstruksi Cubic Splines
• Untuk mencari Ai dan Bi, gunakan syarat interpolasi dan , sehingga

• dan Bi dapat dihitung dari

•
Mencari ki
• Dari syarat kontinyuitas diperoleh

• yang merupakan sistem persamaan linear.

• Untuk natural splines, digunakan , sehingga sistem persamaan linear
di atas dapat diselesaikan dengan mudah (tridiagonal system).
Contoh: Natural cubic splines di x=0,1,4,9
• hanya k0=k3=0;
Octave Code utk konstruksi Natural Splines
• function k = Carik(x,y)
• function Si = MySplines(x,y,k,t)
• n=length(x);
• for i=2:n-1 • n=length(x);
• a(i-1)=2*(x(i-1)-x(i+1));
• b(i-1)=x(i)-x(i+1); • for j=1:n
• c(i)=b(i-1);
• r(i-1)=6*((y(i-1)-y(i))/(x(i-1)-x(i)) – (y(i) – y(i+1))/(x(i) – • if x(j)<=t<x(j+1)
x(i+1)));
• i=j;
• end
• for i=2:n-1
• end
•
•
a(i)=a(i)-c(i)*b(i-1)/a(i-1);
r(i)=r(i)-c(i)*r(i-1)/a(i-1);
• end
• end
• Ai=
• k(n-1)=r(n-1)/a(n-1);
• for i=n-2:-1:1 • Bi=
• k(i)=(r(i) – b(i+1)*k(i+1))/a(i);
• end • Si=