BAB 5 PENDEKATAN FUNGSI DEVIDE DIFFERENCE (SELISIH TERBAGI) A. Tujuan a. Memahami Polinomial Newton (Selisih Terbagi) b. Mampu menentukan koefisien-koefisien Polinomial Newton c. Mampu menentukan koefisien-koefisien Polinomial Newton dengan Matlab B. Perangkat dan Materi a. Software Matlab b. Metode Selisih Terbagi C. Dasar Teori Misalkan akan mencari pollinomial interpolasi P n (x) untuk menghampiri suatu fungsi
f (x) . Untuk ini data yang diberikan ( x1 , f ( x1 )), ( x2 , f ( x2 )),........., ( xn1 , f ( xn1 )) .
adalah
(n
+
1)
titik
,
Misalkan polynomial interpolasinya kita tulis :
Pn ( x) a1 a2 ( x x1 ) a3 ( x x1 )( x x2 ) ...... an1 ( x x1 )( x x2 ).....( x xn )
(1)
dan kit a ingin mencari nilai-nilai koefisien a1 , a2 ,........, an , an1 . Perhatikan bahwa di sini berlaku : Pn ( xk ) f ( xk ) untuk 1 k (n 1) Jika x x1 disubstitusikan ke dalam persamaan 1 di atas, maka semua suku pada sisi kanan kecuali suku pertama bernilai nol, sehingga diperoleh :
f ( x1 ) Pn ( x1 ) a1
(2)
jika x x2 disubstitusikan ke dalam persamaan (1) , maka semua suku pada sisi kanan kecuali dua suku pertama bernilai nol, sehingga diperoleh :
f ( x2 ) Pn ( x2 ) a1 a2 ( x2 x1 )
(3)
atau
1
a2
f ( x2 ) a1 f ( x2 ) f ( x1 ) x2 x1 x2 x1
(4)
Jika P n (x) dihitung pada x x3 , maka akan dperoleh persamaan
f ( x3 ) Pn ( x3 ) a1 a2 ( x x1 ) a3 ( x3 x1 ) a3 ( x3 x1 )(x3 x2 ). (5) sehingga diperoleh :
f ( x3 ) a1 a 2 ( x3 x1 ) ( x3 x1 )( x3 x2 ) f ( x 2 ) f ( x1 ) f ( x3 ) f ( x1 ) ( )( x3 x1 ) x 2 x1 = ( x3 x1 )( x3 x 2 )
a3
f ( x3 ) f ( x1 ) f ( x 2 ) f ( x1 ) x3 x1 x 2 x1 = ( x3 x 2 )
6
dengan cara menyamakan penyebut ( x3 x2 )( x3 x1 )( x3 x1 ) , sehingga persamaan terakhir menjadi :
f ( x3 ) f ( x1 ) f ( x 2 f ( x1 ) x3 x1 x 2 x1 a3 ( x3 x1 )
(6)
Berikut diperkenalkan pengertian selisih-selisih terbagi dari suatu fungsi : 1. Selisih terbagi ke nol terhadap x k
f | xk | f ( xk )
k 1,2,3,....(n 1)
(7)
2. Selisih terbagi pertma terhadap x k dan x k 1
f xk , xk 1
f xk 1 f xk xk 1 x k
k 1,2,3,....n
3. Selisih terbagi kedua terhadap x k , x k 1 dan x k 2
2
(8)
f xk , xk 1 , xk 2
f xk 1 , xk 2 f xk , xk 1
k 1,2,3,....(n 1)
xk 2 xk
(9)
4. …………….. 5. Selisih terbagi ke-j terhadap x k , x k 1 …… x k j didefinisikan secara rekursif.
f xk , xk 1 ,......, xk j
f xk 1 , xk 2 ,....., xk j f xk , xk 1 ,......, xk j 1
xk j xk
untuk k 1,2,3,...., n 1 j;
(10)
j 1,2,3,...., n .
Teorema POLINOMIAL NEWTON Misalkan fungsi f (x) terdefinisi pada interval [a, b], dan misalkan x1 , x2 ,...., xn1 dan
x n 1 bilangan yang berlainan pada interval [a,b], maka terdapat sebuah polynomial tunggal P n (x) berderajat paling tinggi n yang memenuhi : untuk k = 1, 2, 3, , (n+1) f ( xk ) Pn ( xk ) Polinomial Newton adalah :
Pn ( x) a1 a2 ( x x1 ) a3 ( x x1 )( x x2 ) ... an1 ( x x1 )( x x2 ).....( x xn )
(11)
dengan
ak f [ x1 , x2 ,....., xk ]
untuk k 1,2,3,....., (n 1)
Koefisien polynomial Newton merupakan selisih terbagi fungsi yang dihampiri. AKIBAT HAMPIRAN NEWTON Misalkan P n (x) adalah polynomial Newton yang diberikan oleh teorema Polinomial Newton di atas, dan digunakan untuk menghampiri fungsi f (x) , yaitu :
f ( x) Pn ( x) En ( x)
(12)
Jika f mempunyai turunan ke (n+1) pada interval [a,b], maka untuk setiap x [a, b] , terdapat bilangan c c( x) [a, b] , sedemikian sehingga fungsi galat E n (x) berbentuk :
E n ( x)
( x x1 )( x x2 )....( x xn 1 ) f ( n1) (c) (n 1)!
3
(13)
Cara menghitung selisih-selisih terbagi Newton dengan menggunakan tabel: Tabel 1 : Cara menghitung selisih terbagi Newton
x n 1
xn
x n 1
f [ x3 ]
…… . …
f [ xn1 ]
f [ xn ]
f [ xn1 ]
f [ x3 , x 4 ]
…
f [ xn1 , xn ]
f [ xn , xn1 ]
x1
x2
x3
f [ x1 ]
f [ x2 ]
f [ x1 , x2 ]
f [ x 2 , x3 ]
f [ x1 , x2 , x3 ]
f [ x 2 , x3 , x 4 ] f [ x3 , x 4 , x5 ] …
…….
…
… …
f [ x1 , x2 ,....., xn1 ] …
f [ xn1 , xn , xn1 ]
… …
Untuk keperluan komputasi nilai-nilai selisih terbagi Newton pada tabel 1 perlu disimpan ke dalam matriks (array), misalkan D(j,k). Jadi koefisien-koefisien a k pada persamaan 11 menjadi :
D( j, k ) f [ xk , xk 1 ,..., ( xk j ],
(14)
untuk 1 j (n 1) dan 1 k [(n 1) j 1] dengan demikian a j D( j,1)
j = 1,2, …, (n+1)
Algoritma SELISIH TERBAGI NEWTON INPUT
: (( x1 , f ( x1 )), ( x2 , f ( x2 )),..., ( xn1 , f ( xn1 ))
OUTPUT : a1 , a2 , a3 ,...., an1 LANGKAH-LANGKAH : 1. for k = 1,2,…., (n+1) D(1,k) = f ( x k ) 2. a1 D(1,1) 3. For j = 1, 2, …, (n+1) a. For k = 1, 2, …, ((n+1) – j + 1)
D( j, k ) ( D( j 1, k 1) D( j 1, k )) /( xk j 1 xk ) b. a j D( j,1) 4. STOP
4
Implementasi dalam MATLAB:
function D=selisihN(x,y) n=length(x); D(1,1:n)=y; for j=2:n, for k=1:n-j+1, D(j,k)=(D(j-1,k+1)-D(j-1,k))/(x(k+j-1)-x(k)); end end Contoh 1: Hitunglah selisih-selisih terbagi fungsi f sampai tingkat tiga, jika diketahui data titik-titik sebagai berikut: Selanjutnya, tentukan polynomial Newton yang menginterpolasikan titik-titik tersebut. Tabel contoh 1:
xk
0
1
2
4
f ( xk )
1
1
2
5
Penyelesaian : Dari data pada tabel contoh 1 dapat disusun tabel selisih terbagi Newton untuk fungsi f sebagai berikut. Nilai-nilai selisih terbagi Newton membentuk transpose matriks segitiga atas. Dari hasil perhitungan tersebut, elemen-elemen pada kolom pertama matriks D merupakan koefisien-koefisien polynomial Newton yang menginterpolasikan data tersebut.
xk
0
1
2
4
f ( xk )
1
1
2
5
1 0 1/2 -1/12
1 1 1/6 0
2 3/2 0 0
5 0 0 0
D(1, k) D(2, k) D(3, k) D(4, k)
Polinomial Newton yang dicari adalah :
P3 ( x) 1
1 1 x( x 1) x( x 1)( x 2) 2 12
Contoh Cara Mencari Koefisien :
Misal untuk D(2,1), berarti j = 2 , k =1
D(2,1)
5
D(1,2) D(1,1) 1 1 0 x2 x1 1 0
D(2,2)
Misal untuk D(2,2), berarti j = 2 , k = 2
D(1,3) D(1,2) 2 1 1 x3 x 2 20
…dst Bila Contoh 1 di atas dikerjakan dengan implementasi program Matlab di atas, dan dirunning dalam command windows, diproleh: >> x=[0 1 2 4] x= 0
1
2
4
>> y=[1 1 2 5] y= 1
1
2
5
>> D=selisihN(x,y) D= 1.0000 1.0000 2.0000 5.0000 0 1.0000 1.5000 0 0.5000 0.1667 0 0 -0.0833 0 0 0 yang angka (hijau adalah koefisien-koefisien Newton)
Contoh 2: Misalkan f ( x) x 3 4 x . Buatlah tabel selisih terbagi untuk fungsi f tersebut dengan menggunakan titik-titik x1 1, x2 2,.x3 3, x4 4, x5 5, x6 6 Tentukan Polinomial Newton P3 ( x) dengan menggunakan notasi x1 , x2 , x3 dan x 4 Penyelesaian: Tabel contoh 2
xk
x1 1
x2 2
x3 3
x4 4
x5 5
x6 6
f ( xk )
-3
0
15
48
105
192
-3 3 6 1 0
0 15 9 1 0
15 33 12 1 0
48 57 15 0 0
105 87 0 0 0
192 0 0 0 0
D(1,k) D(2,k) D(3,k) D(4,k) D(5,k)
6
D(6,k)
0
0
0
0
0
0
Selanjutnya, diperoleh koefisien-koefisien P3 ( x) adalah pada kolom kedua pada tabel contoh 2 di atas :
P3 ( x) 3 3( x 1) 6( x 1)( x 2) 1( x 1)( x 2)( x 3) Penyelesaian dengan implementasi Matlab: >> x=[1 2 3 4 5 6] x= 1
2
3
4
5
6
>> y=[-3 0 15 48 105 192] y= -3
0
15
48 105 192
>> D=selisihN(x,y) D= -3 0 15 3 15 33 6 9 12 1 1 1 0 0 0 0 0 0
48 57 15 0 0 0
105 192 87 0 0 0 0 0 0 0 0 0
TUGAS: Buatlah tabel selisih terbagi untuk fungsi : f ( x) cos( x) dengan menggunakan 5 titik
x1 0, x2 1, x3 2, x4 3, x4 4, x5 5 . Tentukan Polinomial Newton Pk (x) , untuk k= 1,2,3,4.
7
