Interpolasi [PDF]

Citation preview

Nama :Tsania Ismi Fauzia NIM :19301244017 Kelas :Pendidikan Matematika C 2019



Interpolasi



Secara umum, interpolasi adalah suatu metode atau proses menyusun suatu fungsi atau persamaan dengan menggunakan beberapa titik yang diketahui atau beberapa contoh titik untuk memprediksi atau estimasi nilai pada titik lain yang belum diketahui nilainya. Misalnya terdapat beberapa titik (x1, y1), (x2, y2), (x3, y3), dan seterusnya. Dari titik-titik tersebut akan dibentuk suatu fungsi atau persamaan f(x) sehingga untuk nilai x yang lain dapat diprediksi/estimasi nilai dari y. Interpolasi merupakan teknik untuk mencari nilai suatu variabel yang hilang pada rentang data yang diketahui. Interpolasi merupakan teknik mencari harga suatu fungsi pada suatu titik di antara 2 titik yang nilai fungsi pada ke-2 titik tersebut sudah diketahui. Diberikan n titik: (x1 , y1 ), (x2 , y2 ), (x3 , y3 )..., (xn , yn ) dengan x1 ̸= x2 ̸= x3 ̸= ... ̸= xn .



Masalah: untuk menentukan fungsi f, sehingga kurva y=f(x) melalui (interpolasi) n titik.



Masalah interpolasi: untuk menghitung nilai f(x) untuk min(x1 ) ≤ x ≤ max(x1 )



Fungsi umum yang digunakan pada interpolasi adalah polinomial P (x) = a0 + a1 x + a2 x2 + ... + an−1 xn−1



Untuk setiap himpunan n titik dengan absis yang berbeda, terdapat polinomial dengan derajat maksimum (n-1). Memperkirakan polinomial yang menginterpolasi n titik yang diberikan (x1 , y1 ), (x2 , y2 ), (x3 , y3 ), ..., (xn , yn ) dengan x1 ̸= x2 ̸= x3 ̸= ... ̸= xn ,



adalah P (x) = a0 + a1 x + a2 x2 + ... + an−1 xn−1 .



Itu berarti: y1 =



a0 + a1 x1 + a2 x21 + ... + an−1 xn−1 1



y2 = .. .



a0 + a1 x2 + a2 x22 + ... + an−1 xn−1 2



yn = a0 + a1 xn + a2 x2n + ... + an−1 xn−1 n Nilai dari a 0,a 1,a 2,. . . ,a {n-1} dapat diperoleh dengan menyelesaikan SLE. SLE dapat direpresentasikan dalam persamaan matriks: Va=y dengan       1 x1 x21 x31 ... xn−1 y1 a0 1   y2   a1  1 x2 x22 x32 ... xn−1 2        y3  1 x3 x2 x3 ... xn−1    3 3 3 V =  , y =   , a =  a2    .    . . . . . . .. .. .. . . . ..   ..   ..  ..  1



xn



x2n



x3n



...



xn−1 n



SLE selalu memiliki solusi tunggal untuk x1 ̸= x2 ̸= x3 ̸= ... ̸= xn



yn



an−1 .



Karena V itu nantinya akan membentuk matriks non singular dan nilai determinannya tidak sama dengan nol Matriks V disebut matriks Vandermonde. Contoh: Tentukan polinomial interpolasi titik (0,-5), (1,-3), (-1,-15), (2,39), (-2,-9). Jawab:



>x=[0;1;-1;2;-2]; y=[-5;-3;-15;39;-9]; // data titik-titik yang diketahui >V=[x^0,x^1,x^2,x^3,x^4] // matriks Vandermode



1 1 1 1 1



0 1 -1 2 -2



0 1 1 4 4



0 1 -1 8 -8



0 1 1 16 16



>a=V\y // penyelesaian Va=y, hasilnya a_0=a[1], a_1=a[2], a_2=a[3], a_3=a[4], a_4=a[5]



-5 4 -7 2 3



>a[1]+a[2]*x+a[3]*x^2+a[4]*x^3+a[5]*x^4 // menunjukkan bahwa a.x=y=P(x)



-5 -3 -15 39 -9 Jadi, polinomial interpolasinya adalah: P (x) = −5 + 4x − 7x2 + 2x3 + 3x4 ,



−2 ≤ x ≤ 2



>V.a



-5 -3 -15 39 -9



>t=-2:0.1:2; >u=a[1]+a[2]*t+a[3]*t^2+a[4]*t^3+a[5]*t^4; // menggambar kurva y=P(x) >aspect(25,15); plot2d(t,u, grid=5); plot2d(x,y, >points, , >add):



Berikut adalah program EMT untuk menghitung koefisien-koefisien polinomial interpolasi dan menggambar polinomial interpolasinya.



>function polint(x,y) ...



n=length(x); V=zeros(n,n); for k=1:n V[:,k]=x^(k-1); end a=V\y; t0=min(x’); tn=max(x’); t=t0:0.1:tn; u=a[1]; for k=2:n; u=u+a[k]*t^(k-1);



end plot2d(t,u, grid=5); plot2d(x,y, >points, , >add); return a; endfunction



Soal



Tentukan polinomial yang menginterpolasikan titik-titik (0,1), (1,1), (2,2) dan (4,5). Lakukan pengecekan polinomial yang diperoleh dengan menggunakan titik-titik tersebut. Gambar kurva polinomial bersama titik-titik tersebut!



>x=[0;1;2;4]; y=[1;1;2;5]; >a=polint(x,y):



>fraction a



1 -2/3 3/4 -1/12 Jadi, polinomial interpolasinya adalah: 2 3 1 P (x) = 1 − x + x2 − x3 , 3 4 12



0 ≤ x ≤ 4.



Pertanyaan: Jika urutan titik (data) diubah, apakah polinomik interpolasi akan berubah? Mengapa? Jawab:



>x=[4;1;0;2]; y=[5;1;1;2]; >a=polint(x,y):



>fraction a



1 -2/3 3/4 -1/12 Jadi, polinomial interpolasinya adalah: 2 3 1 P (x) = 1 − x + x2 − x3 , 3 4 12



0 ≤ x ≤ 4.



Jadi, jika urutan titik (data) diubah, polinomik interpolasi tidak berubah karena pasangan titik tidak berubah



Latihan Soal



Tentukan polinomial yang menginterpolasikan titik-titik dibawah ini. Lakukan pengecekan polinomial yang diperoleh dengan menggunakan titik (0.1, 0.6204), (0.2, -0.2839), (0.3, 0.0066), (0.4, 0.2484) tersebut.



>x=[0.1;0.2;0.3;0.4]; y=[0.6204;-0.2839;0.0066;0.2484]; >a=polint(x,y):



>fraction a



3963/1000 -3981/80 18409/100 -829/4 Jadi, polinomial interpolasinya adalah: P (x) =



3963 3981 18409 2 829 3 − x+ x − x 1000 80 100 4



Polinomial Interpolasi



Interpolasi adalah proses pencarian dan perhitungan nilai suatu fungsi yang grafiknya melewati sekumpulan titik yang diberikan. Titik-titik tersebut mungkin merupakan hasil eksperimen dalam sebuah percobaa, atau diperoleh dari sebuah fungsi yang diketahui, salah satunya yang sering dipakai yaitu fungsi polinomial. Interpolasi polinomial merupakan teknik interpolasi dengan mengasumsikan pola data yang kita miliki mengikuti pola polinomial baik berderajat satu (linier) maupun berderajat tinggi. Interpolasi dengan metode ini dilakukan dengan terlebih dahulu membentuk persamaan polinomial. Persamaan polinomial yang terbentuk selanjutnya digunakan untuk melakukan interpolasi dari nilai yang diketahui atau ekstrapolasi (prediksi) dari nilai diluar rentang data yang diketahui. Dua alasan penting pemakaian polinomial interpolasi: 1. Polinomial interpolasi digunakan untuk menghitung hampiran nilai suatu fungsi f (x), karena nilai polinomial mudah dihitung, polinomial mudah diturunkan dan diintegralkan. 2. Polinomial digunakan dalam penentuan kurva mulus yang melalui sekumpulan data titik, biasanya diinginkan sebuah kurva yang tidak osilatif. Penyelesaiannya mengarah ke fungsi-fungsi spline. Poli-



nomial Newton dan Metode Selisih terbagi Newton



Polinomial Newton adalah polinomial interpolasi untuk sekumpulan titik data tertentu. Polinomial Newton kadang-kadang disebut polinomial interpolasi perbedaan terbagi Newton karena koefisien polinomial dihitung menggunakan metode perbedaan terbagi Newton. Diberikan satu set k + 1 titik data



(x0 , y0 ), . . . , (xj , yj ), . . . , (xk , yk )(x0 , y0 ), . . . , (xj , yj ), . . . , (xk , yk )



di mana tidak ada dua xj yang sama, polinomial interpolasi Newton adalah kombinasi linier dari polinomial basis Newton



N (x) :=



k X



aj nj (x)N (x) :=



j=0



k X



aj nj (x)



j=0



dengan polinomial basis Newton yang didefinisikan sebagai



nj (x) :=



j−1 Y



j−1 Y



i=0



i=0



(x − xi )nj (x) :=



(x − xi )f orj > 0andn0 (x) ≡ 1n0 (x) ≡ 1.



Koefisien didefinisikan sebagai



aj := [y0 , . . . , yj ]aj := [y0 , . . . , yj ]



dimana



[y0 , . . . , yj ][y0 , . . . , yj ]



adalah notasi untuk selisih terbagi. Dengan demikian polinomial Newton dapat ditulis sebagai



N (x) = [y0 ] + [y0 , y1 ](x − x0 ) + · · · + [y0 , . . . , yk ](x − x0 )(x − x1 ) · · · (x − xk−1 ).N (x) = [y0 ]+[y0 , y1 ](x−x0 )+· · ·+[y0 , . . . ,



P (x) = a0 + a1 (x − x1 ) + a2 (x − x1 )(x − x2 ) + ... + an−1 (x − x1 )(x − x2 )...(x − xn−1 )



D(i, 1) = yi , untuk i = 1, 2, 3, ...., n



D(i, j) =



D(i + 1, j − 1) − D(i, j − 1) untuk j = 2, 2, 3, ...., n dan i = 1, 2, ..., (n − j + 1) xi+j−1 − xi



a0 = D(1, 1), a1 = D(1, 2), a2 = D(1, 3), ..., an−1 = D(1, n)



Selain dapat dituliskan dalam bentuk baku P (x) = a0 + a1 x + a2 x2 + ... + an−1 xn−1 ,



polinomial yang menginterpolasikan n titik: (x1 , y1 ), (x2 , y2 ), (x3 , y3 ), . . . , (xn , yn ) dengan x1 ̸= x2 ̸= x3 ̸= . . . ̸= xn .



juga dapat dituliskan dalam bentuk: P (x) = a0 + a1 (x − x1 ) + a2 (x − x1 )(x − x2 ) + ... + an−1 (x − x1 )(x − x2 )...(x − xn−1 ).



Nilai dari



a0 , a1 , a2 , ..., an−1



dapat ditentukan secara rekursif dengan mensubstitusi nilai



(x1 , y1 ), (x2 , y2 ), (x3 , y3 ), ..., dan (xn , yn )



ke dalam polinomial Newton di atas. y1 = P (x1 ) ⇒ a0 = y1 y2 − y1 y2 = P (x2 ) ⇒ a1 = x2 − x1 −y1 1 )(x3 − x1 ) ( y3 −y2 ) − ( xy22 −y y3 − y1 − ( xy22 −x −x1 ) 1 = x3 −x2 y3 = P (x3 ) ⇒ a2 = (x3 − x1 )(x3 − x2 ) x3 − x1 ...



Pn (x) = a1 + a2 (x − x1 ) + a3 (x − x1 )(x − x2 ) + ... + an + 1(x − x1 )(x − x2 )...(x − xn ).



dengan ak = f [x1 , x2 , ..., xk ] untuk k = 1, 2, 3, ..., (n + 1)



Pertanyaan: Dengan menggunakan titik-titik yang diberikan dalam contoh sebelumnya, tentukan interpolasi polinomial Newton, dan kemudian sederhanakan ke dalam bentuk polinomial standar. Mendapatkan apa? Jawaban: I. Urutan titik yang diketahui: (0,1), (1,1), (2,2), (4,5) P (x) = a0 + a1 x + a2 x(x − 1) + a3 x(x − 1)(x − 2)



Using (0, 1) → 1 = a0 Using (1, 1) → 1 = a0 + a1 = 1 + a1 → a1 = 0 (2, 2) → 2 = a0 + a1 (2) + a2 (2)(1) = 1 + 2a2 → a2 = 1/2 (4, 5) → 5 = a0 + a1 (4) + a2 (4)(3) + a3 (4)(3)(2) = 1 + 0 + 6 + 24a3 → a3 = −2/24 = −1/12 1 1 So, P (x) = 1 + x(x − 1) − x(x − 1)(x − 2) 2 12 2 3 1 = 1 − x + x2 − x3 3 4 12 II. Urutan titik yang diketahui: (4, 5), (1,1), (0,1), (2,2) 1 1 4 P (x) = 5 + (x − 4) + (x − 4)(x − 1) − (x − 4)(x − 1)x 3 3 12 2 3 2 1 3 =1− x+ x − x 3 4 12 Ini adalah fakta bahwa interpolasi polinomial Newton ketika disederhanakan akan menjadi polinomial standar sebagai hasil dari SLE yang sesuai. Juga, perhatikan bahwa urutan (x (k,) y k) tidak akan mengubah polinomial yang diperoleh.



Rumus selisih pembagian Newton maju



Polinomial Newton dapat dinyatakan dalam bentuk yang disederhanakan ketika



x0 , x1 , . . . , xk x0 , x1 , . . . , xk



disusun berurutan dengan jarak yang sama. Memperkenalkan notasi



h = xi+1 − xi h = xi+1 −xi f oreachi = 0, 1, . . . , k − 1i = 0, 1, . . . , k−1andx = x0 + shx = x0 +sh, thedif f erencex − xi x−x



Jadi polinomial Newton menjadi



N (x) = [y0 ] + [y0 , y1 ]sh + · · · + [y0 , . . . , yk ]s(s − 1) · · · (s − k + 1)hk N (x) = [y0 ] + [y0 , y1 ]sh + · · · + [y0 , . . . , yk ]s(s − 1) · · · =



=



k X



s(s − 1) · · · (s − i + 1)hi [y0 , . . . , yi ]



=



k X



s(s − 1) · · · (s − i + 1)hi [y0 , . . . , yi ]



i=0



i=0



k   X s



k   X s



i=0



i



i!hi [y0 , . . . , yi ].



=



i=0



i



i!hi [y0 , . . . , yi ].



Ini disebut rumus selisih terbagi Newton



Metode Selisih Terbagi Newton



Selisih terbagi newton suatu fungsi f(x) terhahap xk , xk+1 , ..., xk+j , untuk k = 1, 2, ..., n,



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 mendapatkan koefisien polinomial Newton kita dapat menggunakan metode selisih terbagi Newton: D(1, j) = yj , untuk j = 1, 2, 3, ...., n D(i, j) =



D(i − 1, j + 1) − D(i − 1, j) untuk i = 2, 2, 3, ...., n dan j = 1, 2, ..., (n − i + 1) xi+j−1 − xj



Koefisien polinomial Newton adalah



a0 = D(1, 1), a1 = D(2, 1), a2 = D(3, 1), ..., an−1 = D(n, 1).



(INGAT: a 0, a 1, a 2, ..., a {n-1} bukan koefisien polinomial dalam bentuk baku.) Sifat-sifat selisih terbagi newton sebagai berikut: 1. Jika f(x) dapat diferensialkan pada interval yang memuat x 1 dan x 2, maka terdapat bilangna c sedemikian sehingga f ′ (c) =



f (x2 ) − f (x1 ) = f [x1 , x2 ]. x2 − x − 1



2. Jika diberikan (n+1) titik berlainan, (x k,y k) dengan y k=f(x k) untuk k=1,2,...,(n+1) terhadap simpul x 1,x 2,...,x n+1 dinyatakan sebagai



f [x1 , x2 , ..., xn+1 ] =



n+1 X



yk Qn+1



k=1



j=1j̸=k (xk



− xj



3. Simetris. Dapat dituliskan : f [x1 , x2 , ...xn+1 ] = f [x1 , x2 , ..., xn ]



4. Apabila polinomial f(x) berderajat n, dika diketahui m function stn(x,y) ...



n=length(x); D=zeros(n,n); D[1,:]=y’; for i=2:n; for j=1:(n-i+1); D[i,j]=(D[i-1,j+1]-D[i-1,j])/(x[i+j-1]-x[j]); end; end; return D; endfunction



>D=stn(x,y) // contoh soal sebelumnya



1 0 0.5 -0.0833333



1 1 0.166667 0



2 1.5 0 0



>fraction(D)



1 0 1/2 -1/12



1 1 1/6 0



2 3/2 0 0



5 0 0 0



5 0 0 0



Polinomial Newton yang menginterpolasikan titik-titik yang diketahui adalah: 1 1 P (x) = 1 + 0.x + x(x − 1) − x(x − 1)(x − 2). 2 12 Setelah disederhanakan (lakukan!), hasilnya adalah: 2 3 1 P (x) = 1 − x + x2 − x3 , 3 4 12



0 ≤ x ≤ 4.



>x=[0;1;-1;2;-2]; y=[-5;-3;-15;39;-9]; >D=stn(x,y)



-5 2 -4 8 3



>x=[0;10;30;50;70;90;100]



0 10 30 50 70 90 100



-3 6 12 2 0



-15 18 6 0 0



39 12 0 0 0



-9 0 0 0 0



>y=[1.792;1.308;0.801;0.549;0.406;0.317;0.284] // dari data ini akan ditentukan nilai y untuk x=40



1.792 1.308 0.801 0.549 0.406 0.317 0.284



>largematrices on; D=stn(x,y)



Column 1 to 5: 1.792 1.308 -0.0484 -0.02535 0.000768333 0.00031875 -8.99167e-06 -3.04167e-06 8.5e-08 2.36979e-08 -6.81134e-10 -1.74024e-10 5.0711e-12 0 Column 6 to 7: 0.317 0.284 -0.0033 0 0 0 0 0 0 0 0 0 0 0



0.801 -0.0126 0.00013625 -1.14583e-06 8.03571e-09 0 0



0.549 -0.00715 6.75e-05 -5.83333e-07 0 0 0



0.406 -0.00445 3.83333e-05 0 0 0 0



Berikut adalah fungsi EMT untuk menghitung nilai polinomial interpolasi Newton P(z), berdasarkan data x dan y.



>function politon(x,y,z) ...



D=stn(x,y); n=length(D); Pz=D[1,1]; for i=2:n; suku=D[i,1]; for j=2:i; suku=suku*(z-x[j-1]); end Pz=Pz+suku; end; return Pz; endfunction



>Pz=politon(x,y,40)



0.656535119048 Pertanyaan: Coba gambar polinomial interpolasi yang didapat tersebut beserta titik-titik datanya! Jawab:



>z=0:0.1:100; Pz=zeros(length(z)); >for i=1:length(z), Pz[i]=politon(x,y,z[i]); end >plot2d(z,Pz); plot2d(x,y,>points, ,>add):



Latihan Soal



Gunakan polinomial interpolasi Newton untuk menentukan yat x = 3,5 untuk akurasi terbaik. Hitung terbagi hingga perbedaan seperti pada Gambar 17.5, dan urutan poin Anda untuk mencapai akurasi dan konvergensi yang optimal. Artinya, intinya harus berpusat di sekitar dan sedekat mungkin dengan yang tidak diketahui. x = [0, 1, 2.5, 3, 4.5, 5, 6] y = [2, 5.4375, 7.3516, 7.5625, 8.4453, 9.1875, 12]



>x=[0;1;2.5;3;4.5;5;6]; y=[2;5.4375;7.3516;7.5625;8.4453;9.1875;12]; >D=stn(x,y)



Column 1 to 5: 2 5.4375 3.4375 1.27607 -0.864573 -0.427133 0.145813 0.145857 9.73545e-06 -7.61905e-06 -3.4709e-06 1.26984e-06 7.90123e-07 0 Column 6 to 7: 9.1875 12 2.8125 0 0 0 0 0 0 0 0 0 0 0



7.3516 0.4218 0.0833667 0.145827 -1.26984e-06 0 0



7.5625 0.588533 0.447933 0.145822 0 0 0



8.4453 1.4844 0.8854 0 0 0 0



>fraction(D)



2 87/16 18379/2500 121/16 84453/10000 147/16 55/16 19141/15000 2109/5000 2207/3750 3711/2500 45/16 -64843/75000 -6407/15000 2501/30000 6719/15000 4427/5000 1367/9375 1021/7000 10937/75000 3281/22500 0 0 1/102717 -1/131249 -1/787499 0 0 0 -1/288109 1/787500 0 0 0 0 1/1265625 0 0 0 0 0



12 0 0



0 0 0 0 0



>Pz=politon(x,y,3.5)



7.74216296296



Perkalian Tersarang



Rumus pada metode Newton merupakan bentuk umum yang dapat diterapkan pada sebarang fungsi. Biala fungsi yang akan dicari akarnya berupa polinom, maka perhitungan pada rumus tersebut dapat dibuat efisien, dalam arti lebih singkat dan akurat (proses pembulatan di komputer menjadi lebih sedikit). Hal ini dilakukan dengan mengoptimalkan proses pada perhitungan nilai fungsi dan nilai turunannya. Perhatikan suatu polinom derajat n, p(x) = a0 + a1 x + a2 x2 + . . . + an xn , a0 ̸= 0.



Di dalam komputer/kalkulator, untuk menghitung xˆn setara dengan proses perkalian sebanyak n kali. Misalkan z suatu bilangan real. Bila kita menghitung nilai p(z) dari rumus tersebut secara langsung, yaitu p(z) = a0 + a1 z + a2 z 2 + . . . + an z n



maka banyaknya operasi perkaliannya berorde O(nˆ2). Untuk penerapan metode Newton, kita juga perlu menghitung p’(z) dan jumlah operasi perkaliannya berorde O(nˆ2). Pada pasal ini kita akan membahas metode untuk menghitung nilai tersebut dengan cara yang lebih efisien. CATATAN: Pada perhitungan di tas kita tidak memerdulikan operasi pertambahan karena operasi ini memerlukan waktu komputasi yang jauh lebih kecil dari operasi perkalian. Untuk mengefisienkan perhitungan p(z), kita susun urutan operasi perhitungannya sebagai berikut: p(z) = a0 + a1 + (a2 + (. . . an−3 + (an−2 + (an−1 + an z)z)z . . . )z)z



Dengan cara seperti di atas, maka operasi kali yang diperlukan hanya sebanyak n buah, suatu penurunan yang sangat drastis dari operasi perhitungan langsung. Cara seperti ini dinamakan perkalian tersarang yang ekivalen dengan metode Horner. Dalam bentuk algoritma, proses perkalian tersebut dapat dilakukan sebagai berikut: bn := an



, untuki := n − 1, n − 2, . . . , 0



bi := ai + bi+1 ∗ z



bila algoritma tersebut dijalankan maka ilai p(z) akan tersimpan pada variabel b 0 Misalkan bn , bn−1 , . . . , b1



adalah koefisien-koefisien yang dihasilkan dari algoritma persamaan diatas, sebut q(x) = bn xn−1 + bn−1 xn−2 + . . . + b2 x + b1 ,



maka p(x) = (x − z)q(x) + b0



dari sifat diatas maka p’(x)=q(x)+(x-z)q’(x). Dengan demikian p’(z)=q(z). Keismpulan p′ (z) = bn z n−1 + bn−1 z n−2 + . . . + b2 + b1 .



untuk kembali menerapkan perkalian bersaranng untuk mengitung nilai p’(z). Bila algoritma perhitungan p(z) dan p’(z) ditulis bersamaan maka bentuknya adalah



Bila algoritma diatas dijalankan maka p(z) dan p’(z) akan tersimpan di variabel b 0 dan c 1 Berdasarkan metode perkalian tersarang, maka algoritma penerapan metode Newton untuk polinom akan berbentuk sebagai berikut:



Polinomial Lagrange



Diberikan satu set k + 1 titik data



(x0 , y0 ), . . . , (xj , yj ), . . . , (xk , yk )(x0 , y0 ), . . . , (xj , yj ), . . . , (xk , yk )



di mana tidak ada dua



xj xj



yang sama, polinomial interpolasi dalam bentuk Lagrange adalah kombinasi linier



L(x) :=



k X j=0



yj ℓj (x)L(x) :=



k X



yj ℓj (x)



j=0



polinomial basis Lagrange



ℓj (x) :=



Y 0≤m≤k m̸=j



(x − xj−1 ) (x − xj+1 ) (x − xk ) x − xm (x − x0 ) ··· ··· ,ℓj (x) := = xj − xm (xj − x0 ) (xj − xj−1 ) (xj − xj+1 ) (xj − xk )



Y 0≤m≤k m̸=j



x − xm (x − x0 ) ··· = xj − xm (xj − x0 ) (



dimana 0 ≤ j ≤ k0 ≤ j ≤ k.



Perhatikan caranya, dengan asumsi awal bahwa tidak ada dua



xj xj



yang sama, maka m ̸= jm ̸= jxj − xm ̸= 0xj − xm ̸= 0,



jadi ekspresi ini selalu terdefinisi dengan baik. Alasan berpasangan xi = xj xi = xj dengan yi ̸= yj yi ̸= yj



tidak diperbolehkan adalah tidak ada fungsi interpolasi



LLsuchthatyi = L(xi )yi = L(xi )



akan ada; fungsi hanya bisa mendapatkan satu nilai untuk setiap argumen



xi xi .



Di sisi lain, jika juga yi = yj yi = yj ,



maka kedua titik tersebut sebenarnya akan menjadi satu titik tunggal.



P (x) =



n X



yk



k=1



Y x − xj xk − xj



j̸=k



Nilai P (x) di x = z adalah:



P (z) =



n X k=1



yk



Y z − xj xk − xj



j̸=k



Contoh: Polinomial Lagrange yang menginterpolasikan titik-titik:



(0, 1), (1, 1), (2, 2), (4, 5)



dapat ditulis: (x − 1)(x − 2)(x − 4) (0 − 1)(0 − 2)(0 − 4) (x − 0)(x − 2)(x − 4) +1 (1 − 0)(1 − 2)(1 − 4) (x − 0)(x − 1)(x − 4) +2 (2 − 0)(2 − 1)(2 − 4) (x − 0)(x − 1)(x − 2) +5 . (4 − 0)(4 − 1)(4 − 2)



P (x) =1



Jika disederhanakan (lakukan!),hasilnya 2 3 1 P (x) = 1 − x + x2 − x3 , 3 4 12



0 ≤ x ≤ 4,



sama dengan hasil, baik menggunakan langsung ke polinomial bentuk baku maupun dengan polinomial Newton. Berikut adalah program EMT untuk menghitung nilai polinomial interpolasi di z dengan data x dan y, menggunakan polinomial Lagrange.



>function PL(x,y,z) ...



n=length(x); P=0; for k=1:n; S=y[k]; for j=1:n; if jk then S=S*(z-x[j])/(x[k]-x[j]); endif;



end; P=P+S; end; return P; endfunction



>x // data pada contoh terakhir



0 10 30 50 70 90 100



> y



1.792 1.308 0.801 0.549 0.406 0.317 0.284



>PL(x,y,40)



0.656535119048



>t=0:1:100; >p=PL(x,y,t); >plot2d(t,p); plot2d(x,y,>points, ,>add):



Latihan: Pilih soal-soal interpolasi dari LATIHAN pada buku-buku referensi yang sudah saya sebutakn/berikan dan kerjakan dengan polinomial Lagrange, seperti contoh di atas.



Latihan Soal



(Buku Numerical Analysis 9th) 5a. Gunakan polinomial Lagrange untuk menemukan polinomial interpolasi dan memperkirakan nilai dari f(8.4) jika f(8.1)=16.94410, f(8.3)=17.56492, f(8.6)=18.50515, f(8.7)=18.82091 Penyelesaian:



>x=[8.1;8.3;8.6;8.7]



8.1 8.3 8.6 8.7



>y=[16.94410;17.56492;18.50515;18.82091]



16.9441 17.5649 18.5052 18.8209



>PL(x,y,8.4)



17.8771425 Nilai f(8.4) = 17.8771425 6b. Gunakan polinomial Lagrange untuk menemukan polinomial interpolasi dan memperkirakan nilai dari f(0) jika f(-0.5)=1.93750, f(-0.25)=1.33203, f(0.25)=0.800781, f(0.5)=0.687500 Penyelesaian:



>x=[-0.5;-0.25;0.25;0.5]



-0.5 -0.25 0.25 0.5



>y=[1.93750;1.33202;0.800781;0.687500]



1.9375 1.33202 0.800781 0.6875



>PL(x,y,0)



0.984367333333



Nilai f(0) = 0.984367333333 Carilah fungsi-fungsi kardinalnya dan Polinomial Interpolasi Lagrange yang menginterpolasikan titiktitik: (0, −3), (1, −2), (−1, 5), (2, 10), (−2, 16), (3, −10)



Penyelesaian : Berikut kita hitung fungsi-fungsi L 1, L 2, L 3, L 4, L 5, dan L 6 (x − 1)(x + 1)(x − 2)(x + 2)(x − 3) (x − 1)(x + 1)(x − 2)(x + 2)(x − 3) = (0 − 1)(0 + 1)(0 − 2)(0 + 2)(0 − 3) −12 (x − 0)(x + 1)(x − 2)(x + 2)(x − 3) x(x + 1)(x − 2)(x + 2)(x − 3) L2 (x) = = (1 − 0)(1 + 1)(1 − 2)(1 + 2)(1 − 3) 12 (x − 0)(x − 1)(x − 2)(x + 2)(x − 3) x(x − 1)(x − 2)(x + 2)(x − 3) = L3 (x) = (−1 − 0)(−1 − 1)(−1 − 2)(−1 + 2)(−1 − 3) 24 (x − 0)(x − 1)(x + 1)(x + 2)(x − 3) x(x − 1)(x + 1)(x + 2)(x − 3) L4 (x) = = (2 − 0)(2 − 1)(2 + 1)(2 + 2)(2 − 3) −24 x(x − 1)(x + 1)(x − 2)(x − 3) (x − 0)(x − 1)(x + 1)(x − 2)(x − 3) = L5 (x) = (−2 − 0)(−2 − 1)(−2 + 1)(−2 − 2)(−2 − 3) −120 (x − 0)(x − 1)(x + 1)(x − 2)(x + 2) x(x − 1)(x + 1)(x − 2)(x + 2) L6 (x) = = (3 − 0)(3 − 1)(3 + 1)(3 − 2)(3 + 2) 120 L1 (x) =



Jadi, polinomial Lagrange yang dicari adalah P5 (x) = −3L1 (x) − 2L2 (x) + 5L3 (x) + 10L4 (x) + 16L5 (x) − 10L6 (x).



Catatan : Polinom Lagrange kurang disukai dalam praktek karena : - Jumlah komputasi yang dibutuhkan untuk satu kali interpolasi adalah besar. Interpolasi untuk nilai x yang lain memerlukan jumlah komputasi yang sama karena tidak ada bagian komputasi sebelumnya yang dapat digunakan. - Bila jumlah titik data meningkat atau menurun, hasil komputasi sebelumnya tidak dapat digunakan. Karena tidak ada hubungannya antara p n-1(x) dan p n(x) pada polinom Lagrange Pengertian Spline (Syarat-syarat spline)



Interpolasi spline adalah bentuk interpolasi di mana interpolan adalah jenis khusus polinomial sepotongsepotong yang disebut spline. Interpolasi spline sering lebih digunakan daripada interpolasi polinomial karena kesalahan interpolasi dapat dibuat kecil bahkan ketika menggunakan polinomial derajat rendah untuk spline. Interpolasi spline juga menghindari masalah fenomena Runge, di mana osilasi dapat terjadi antar titik saat interpolasi menggunakan polinomial derajat tinggi. Awalnya, spline adalah istilah untuk penggaris elastis yang ditekuk untuk melewati sejumlah titik yang telah ditentukan, atau simpul. Ini digunakan untuk membuat gambar teknis untuk pembuatan kapal dan konstruksi dengan tangan, seperti yang diilustrasikan pada gambar. Kami ingin memodelkan jenis kurva yang serupa menggunakan satu set persamaan matematika, dengan satu polinomial y = qi (x)y = qi (x)



untuk setiap pasang simpul (xi−1 , yi−1 )(xi−1 , yi−1 )



dan (xi , yi )(xi , yi ),



dimana i = 1, 2, . . . , ni = 1, 2, . . . , n.



Metode Spline adalah salah satu metode Interpolasi yaitu dengan memakai pendekatan fungsi-fungsi Spline sebagai polinom penghubung. Interpolasi Spline merupakan polinom sepotong-sepotong. Suatu fungsi f(x) yang sudah diketahui pada selang a≤x≤b



dihampiri dengan sebuah fungsi lain g(x) dengan cara menyekat selang a≤x≤b



menjadi beberapa anak selang a = x1 < x2 < x3 < ... < xn = b



Fungsi g(x) yang didapat dinamakan spline. Berikut contoh bentuk dari spline.



Di dalam metode numerik, terdapat beberapa spline, diantaranya yakni Spline Linier, Spline Kuadrat, dan Spline Kubik. Syarat-syarat dari masing-masing Spline akan dijelaskan sebagai berikut. 1. SPLINE LINIER



2. SPLINE KUADRAT



3. SPLINE KUBIK



Interpolasi dengan Spline



Untuk interpolasi dengan spline, disyaratkan bahwa n titik yang diketahui:



(x1 , y1 ), (x2 , y2 ), (x3 , y3 ), ..., (xn , yn ),



harus memenuhi:



x1 < x2 < x3 < ... < xn .



Selanjutnya, spline didefinisikan sebagai fungsi



S(x) =



  S1 (x),      S2 (x),     ...  Sk (x),    ..   .    S n−1 (x),



x 1 ≤ x ≤ x2 x 2 ≤ x ≤ x3 .. . xk ≤ x ≤ xk+1 .. . xn−1 ≤ x ≤ xn



dengan syarat: (1) Setiap Sk (x) merupakan polinomial pada interval xk ≤ x ≤ xk+1 , untuk k = 1, 2, 3, ..., (n − 1). (2) Fungsi S(x) dan semua turunannya (yang bukan konstan) bersifat kontinu pada interval [x1 , xn ]. (3) S(xk ) = yk untuk k = 1, 2, 3, ..., n



(Syarat interpolasi).



Interpolasi Linear



Interpolasi linier adalah metode pemasangan kurva menggunakan polinomial linier untuk membangun titik data baru dalam kisaran satu set diskrit titik data yang diketahui. Jika dua titik yang diketahui diberikan oleh koordinat (x0 , y0 )(x0 , y0 )and(x1 , y1 )(x1 , y1 ),



interpolan linier adalah garis lurus antara titik-titik ini. Untuk nilai x dalam interval (x0 , x1 )(x0 , x1 ), thevalueyalongthestraightlineisgivenf romtheequationof slopes



y − y0 y1 − y0 y − y0 y1 − y0 = , = , x − x0 x1 − x0 x − x0 x1 − x0 yang dapat diturunkan secara geometris dari gambar di sebelah kanan. Ini adalah kasus khusus interpolasi polinomial dengan n = 1. Memecahkan persamaan ini untuk y, yang merupakan nilai yang tidak diketahui di x, memberikan



y = y0 + (x − x0 )



y0 (x1 − x) + y1 (x − x0 ) y1 − y0 y0 (x1 − x) + y1 (x − x0 ) y1 − y0 = ,y = y0 + (x − x0 ) = , x1 − x0 x1 − x0 x1 − x0 x1 − x0



Interpolasi Kuadratik



Misal diberi tiga buah titik data (x 0,y 0), (x 1,y 1), (x 2, y 2). Polinom yang menginterpolasi ketiga buah titik itu adalah polinom yang berkuadrat.



Interpolasi Kubik



Misalkan diberikan empat titik data (x 0,y 0), (x 1,y 1), (x 2, y 2), (x 3,y 3). Polinom yang menginterpolasi keempat buah titik berupa polinom kubik yang persamaannya adalah : images: interpolasikubik.png



Spline Linier



Pada spline linier, Sk (x) = ak x + bk untuk xk ≤ x ≤ xk+1 ,



merupakan persamaan garis yang melalui titik



(xk , yk ) dan (xk+1 , yk+1 ).



Jadi,



ak =



(yk+1 − yk ) dan bk = yk − ak xk . (xk+1 − xk )



Jadi, spline linier berbentuk:  (y2 −y1 )  (x2 −x1 ) (x − x1 ) + y1 ,    (y3 −y2 )   (x3 −x2 ) (x − x2 ) + y2 ,     ... S(x) = (yk+1 −yk )   (xk+1 −xk ) (x − xk ) + yk ,    .  ..      (yn −yn−1 ) (xn −xn−1 ) (x − xn−1 + yn−1 ,



x1 ≤ x ≤ x2 x2 ≤ x ≤ x3 .. . xk ≤ x ≤ xk+1 .. . xn−1 ≤ x ≤ xn )



Program EMT untuk menghitung nilai spline linier di z.



>function spliner(x,y,z) ...



{x,i}=sort(x); y=y[i]; n=length(x); m=zeros(n-1); for k=1:n-1; m[k]=(y[k+1]-y[k])/(x[k+1]-x[k]); end p=length(z); s=zeros(p); for i =1:p; for k=1:n-1; if z[i]>=x[k] and z[i]n then s[p]= m[n-1]*(z[p]-x[n-1])+ y[n-1]; endif return {s,m}; endfunction



>x=[0;1;-1;2;-2]; y=[-5;-3;-15;39;-9]; // spline linier yang menginterpolasikan ... >// titik2 (0,-5), (1,-3), (-1,-15), (2,39), (-2,-9) >spliner(x,y,x) // cek apakah program spliner menghasilnya nilai y yang sama dengan data



[-5,



-3,



-15,



39,



-9]



>z=-2:.1:2; >{s,m}=spliner(x,y,z); >m



[-6,



10,



2,



42]



>plot2d(x,y,>points, ); plot2d(z,s,>add):



Jadi, spline linier yang menginterpolasikan titik-titik (0,-5), (1,-3), (-1,-15), (2,39), (-2,-9) adalah:   −6(x + 2) − 9,  10(x + 1) − 15, S(x) = 2x − 5,    42(x − 1) − 3,



−2 ≤ x ≤ −1 −1 ≤ x ≤ 0 0≤x≤1 1 ≤ x ≤ 2.



Contoh 2: Tentukan spline linier yang menginterpolasikan titik-titik (-2,16), (-1,5), (0,-3), (1,-2), (2, 10), dan (3,-10).



>x=[-2;-1;0;1;2;3]



-2 -1 0 1 2 3



>y=[16;5;-3;-2;10;-10]



16 5 -3 -2 10 -10



>spliner(x,y,x)



[16,



5,



-3,



-2,



10,



-10]



>z=-2:0.1:3; >{s,m}=spliner(x,y,z); >m



[-11,



-8,



1,



12,



-20]



>plot2d(x,y,>points, ); plot2d(z,s,>add):



Spline linier yang menginterpolasikan titik-titik (-2,16), (-1,5),(0,-3), (1,-2), (2, 10), dan (3,-10):   −11(x + 2) + 16, −2 ≤ x ≤ −1      −8(x + 1) + 5, −1 ≤ x ≤ 0  S(x) = x − 3, 0≤x≤1    12(x − 1) − 2, 1≤x≤2    −20(x − 2) + 10, 2 ≤ x ≤ 3.



Latihan Soal



Diketahui data titik-titik(0,1), (1,1), (2,5). Tentukan spline linier yang menginterpolasikan titik-titik tersebut.



>x=[0;1;2]



0 1 2



>y=[1;1;5]



1 1 5



>spliner(x,y,x)



[1,



1,



5]



>z=0:.1:2; >{s,m}=spliner(x,y,z); >m



[0,



4]



>plot2d(x,y,>points, ); plot2d(z,s,>add):



Spline linier yang menginterpolasikan titik-titik (0,1), (1,1),(2,5): ( (x + 0) + 1, 0≤x≤1 S(x) = 4(x + 1) + 1, 1≤x≤2



Spline Kuadratik



S(x) =



  a1 x2 + b1 x + c1 ,      a2 x2 + b2 x + c2 ,     ...  ak x2 + bk x + ck ,     ..   .    a 2 n−1 x + bn−1 x + cn−1 ,



x1 ≤ x ≤ x 2 x2 ≤ x ≤ x 3 .. . xk ≤ x ≤ xk+1 .. . xn−1 ≤ x ≤ xn



Dalam spline kuadrat, Sk (x) = ak x2 + bk x + ck for xk ≤ x ≤ xk+1



(k = 1, 2, 3, ..., n − 1).



Nilai a k, b k, c k (k=1, 2, 3, ..., n-1) dapat ditemukan dengan menerapkan kondisi spline: 1) Kondisi interpolasi: S(xk ) = yk



(k = 1, 2, 3, ..., n).



Ini menghasilkan persamaan



yk = ak x2k + bk xk + ck ,



(k = 1, 2, 3, ..., n − 1), and



yn = an−1 x2n + bn−1 xn + cn−1 .



2) S dilanjutkan, artinya: Sk (xk+1 ) = Sk+1 (xk+1 ),



memberikan persamaan



ak x2k+1 + bk xk+1 + ck = ak+1 x2k+1 + bk+1 xk+1 + ck+1



(k = 1, 2, 3, ..., n − 2).



3) S’ dilanjutkan, yaitu: ′ Sk′ (xk+1 ) = Sk+1 (xk+1 ),



yang mengarah ke persamaan 2ak xk+1 + bk = 2ak+1 xk+1 + bk+1



(k = 1, 2, 3, ..., n − 2).



Ada total 3n-4 persamaan linear dalam a k, b k, c k (k=1, 2, 3, ..., n-1). Tidak memiliki satu persamaan linier secara berurutan untuk menemukan a k, b k, c k. Dalam hal ini, biasanya diasumsikan bahwa S’(x 1)=0 atau S’(x n)=0. SPL yang harus diselesaikan:



Dua persamaan terakhir dipilih salah satu, sesuai syarat yang diminta.



Contoh: Temukan spline kuadrat S(x) yang menginterpolasi titik (-2, 16), (-1, 5), (0,-3), (1,-2), (2, 10), dan (3,-10) dengan syarat tambahan S’(3) = 0. Selanjutnya, plot kurva dari spline bersama dengan poin yang diberikan! Solusi: Spline kuadrat adalah  2  a1 x + b1 x + c1 ,    a2 x2 + b2 x + c2 ,  S(x) = a3 x2 + b3 x + c3 ,    a4 x2 + b4 x + c4 ,    a x2 + b x + c , 5 5 5



−2 ≤ x ≤ −1 −1 ≤ x ≤ 0 0≤x≤1 1≤x≤2 2≤x≤3



Kondisi untuk spline kuadrat adalah: 1) Interpolasi S(xk ) = yk ,



memberikan hasil:



4a1 − 2b1 + c1 = 16 a2 − b2 + c2 = 5 c3 = −3 a4 + b4 + c4 = −2 4a5 + 2b5 + c5 = 10 9a5 + 3b5 + c5 = −10



2) S dilanjutkan Sk (xk+1 ) = Sk+1 (xk+1 ) = yk+1 ,



maka:



a1 − b1 + c1 = a2 − b2 + c2 = 5 c2 = c3 = −3 a3 + b3 + c3 = a4 + b4 + c4 = −2 4a4 + 2b4 + c4 = 4a5 + 2b5 + c5 = 10 3) S’ dilanjutkan ′ Sk′ (xk+1 ) = Sk+1 (xk+1 ),



maka:



−2a1 + b1 = −2a2 + b2 b2 = b3 2a3 + b3 = 2a4 + b4 4a4 + b4 = 4a5 + b5



4) Asumsi tambahan, S’(3)=0, artinya 6a5 + b5 = 0.



Dari persamaan turunan, solusinya adalah (silakan periksa!): a1 = 57, a2 = −54, a3 = 63, a4 = −52, a5 = 20,



b1 = 160, b2 = −62, b3 = −62, b4 = 168, b5 = −120,



c1 = 108, c2 = −3, c3 = −3, c4 = −118, c5 = 170



Jadi, spline kuadrat adalah:  2  57x + 160x + 108,    −54x2 − 62x − 3,  S(x) = 63x2 − 62x − 3,    −52x2 + 168x − 118,    20x2 − 120x + 170,



−2 ≤ x ≤ −1 −1 ≤ x ≤ 0 0≤x≤1 1≤x≤2 2 ≤ x ≤ 3.



Berikut adalah program EMT untuk menghitung nilai spline kuadratik di z. Perhatikan, program ini memerlukan input selain x dan y, juga a, b, c, yang diperoleh dengan menyelesaikan SPL terkait seperti di atas. Silakan Anda buat program EMT untuk mendapatkan nilai-nilai a, b, c. Jika berhasil, program EMT berikut tidak perlu input a, b, c, namun a, b, c dapat dihitung di dalam program tersebut dengan menggunakan program yang Anda buat.



>function spline2a(x,y,a,b,c,z)



{x,i}=sort(x); y=y[i]; n=length(x); m=length(z); s=zeros(m); for i =1:m; for k=1:n-1; if z[i]>=x[k] and z[i]n then s[m]= a[n-1]*z[m]^2+b[n-1]*z[m]+c[n-1]; endif return s; endfunction



>x=-2:3; y=[16,5,-3,-2,10,-10]; >a=[57;-54;63;-52;20]



57 -54 63 -52 20



>b=[160; -62; -62; 168; -120]



160 -62 -62 168 -120



>c=[108; -3; -3; -118; 170]



108 -3 -3 -118 170



>z=-2:0.1:3; >s=spline2a(x,y,a,b,c,z); >plot2d(z,s); plot2d(x,y,>points, , >add):



Latihan Soal



Tunjukkan bahwa fungsi yang didefinisikan sebagai berikut merupakan spline kubik dengan cara menunjukkan bahwa S1(2)=S2(2), S1’(2)=S1’(2), dan S1”(2)=S2”(2)



b. Tentukan spline kuadratik yang menginterpolasikan titik-titik



tersebut. ( f (x) =



S1 (x) = S2 (x) =



−13 3 81 19 2 4 x + 15x − 4 x − 2 , 11 3 207 77 2 4 x − 21x + 4 x − 2 , ,



>x=1:3; y=[-19/2,77/2,-77/2]; >a=[-13/4;11/4]



-3.25 2.75



>b=[15;-21]



15 -21



>c=[-81/4;207/4]



-20.25 51.75



>z=1:.1:3; >s=spline2a(x,y,a,b,c,z); >plot2d(z,s); plot2d(x,y,>points, , >add):



1≤x≤2 2≤x≤3



Terbukti dari plot siatas bahwa S1(2)=S2(2), S1’(2)=S1’(2), dan S1”(2)=S2”(2)



Spline Kuadratik (Bentuk Lain)



Berikut adalah alternatif untuk mencari spline kuadratik dengan menyelesaikan SPL yang memuat lebih sedikit variabel. Misalkan mk = S ′ (xk ), untuk k = 1, 2, 3, ..., n.



Anggap seolah-olah kita memunyai n titik (x k,m k), untuk k=1, 2, 3, ...,n. Dalam hal ini S’(x) merupakan spline linier (karena S’(x) kontinu) dengan persamaan: S ′ (x) = Sk′ (x) =



mk+1 − mk (x − xk ) + mk , untuk xk ≤ x ≤ xk+1 . xk+1 − xk



Jadi (jelaskan dari mana diperoleh), S(x) = Sk (x) =



(mk+1 − mk ) (x − xk )2 + mk (x − xk ) + Ck , untuk xk ≤ x ≤ xk+1 . 2(xk+1 − xk )



Karena S(x k)=y k, maka C k=y k, sehingga S(x) = Sk (x) =



(mk+1 − mk ) (x−xk )2 +mk (x−xk )+yk , untuk xk ≤ x ≤ xk+1 , dan k = 1, 2, ..., (n−1). 2(xk+1 − xk )



Selanjutnya, untuk mendapatkan nilai-nilai m k digunakan syarat S kontinu, yakni Sk (xk+ 1) = Sk+1 (xk+1 ) = yk+1 , untuk k = 1, 2, 3, ..., n − 2, dan Sn−1 (xn ) = yn



sehingga didapatkan: (mk+1 − mk ) + mk (xk+1 − xk ) = yk+1 − yk , 2(xk+1 − xk ) atau (jelaskan mengapa): mk + mk+1 =



2(yk+1 − yk ) , k = 1, 2, 3, ..., n − 1, (xk+1 − xk )



yang merupakan SPL yang terdiri atas (n-1) equation dalam n variabel. Agar dapat diselesaikan, seperti biasanya digunakan satu asumsi tambahan, yakni m 1=0 atau m n=0. (Tahukah Anda, apa arti asumsi ini?) Contoh: Untuk contoh spline kuadratik di atas dapat diselesaikan dengan menggunakan SPL: m1 + m2 = −22 m2 + m3 = 16 m3 + m4 = 2 m4 + m5 = 24 m5 + m6 = −40 m6 = 0 yakni: m6 = 0, m5 = −40, m4 = 64, m3 = −62, m2 = 46, m1 = −68.



Jadi spline kuadratiknya adalah  1 2   2 (114)(x + 2) − 68(x + 2) + 16,     12 (−108)(x + 1)2 + 46(x + 1) + 5,  S(x) = 21 (126)x2 − 62x − 3,   1 2   2 (−104)(x − 1) + 64(x − 1) − 2,    1 (40)(x − 2)2 − 40(x − 2) + 10, 2



−2 ≤ x ≤ −1 −1 ≤ x ≤ 0 0≤x≤1 1≤x≤2 2 ≤ x ≤ 3.



dan jika disederhanakan (silakan periksa!) persamaan spline tersebut sama dengan persamaan spline kuadratik sebelumnya. Berikut adalah program EMT untuk mendapatkan spline kuadratik dengan menggunakan metode alternatif tersebut. Input ini t adalah untuk memilih syarat tambahan yang digunakan. Perhatikan, program ini akan menghasilkan nilai-nilai spline s (untuk menggambar splinenya) dan nilai m (untuk menyusun persamaan splinenya).



>function spline2(x,y,t,z) ...



{x,i}=sort(x); y=y[i]; n=length(x); m=zeros(n); if t==1 then m[1]=0; for k=1 to n-1; m[k+1]= 2*(y[k+1]-y[k])/(x[k+1]-x[k]) - m[k]; end endif if t==2 then m[n]=0; for k=1 to n-1; m[n-k]= 2*(y[n-k+1]-y[n-k])/(x[n-k+1]-x[n-k]) - m[n-k+1]; end endif p=length(z); s=zeros(p); for i =1:p; for k=1:n-1; if z[i]>=x[k] and z[i]n then s[p]=1/2*(m[n]-m[n-1])/(x[n]-x[n-1])*(z[p]-x[n-1])^2+m[n-1]*(z[p]-x[n-1])+y[n-1]; endif return {s, m}; endfunction



>x=-2:3; y=[16,5,-3,-2,10,-10]; >z=-2:0.1:3; >{s,m}=spline2(x,y,2,z); // menggunakan syarat tambahan untuk ujung kanan >m



[-68,



46,



-62,



64,



-40,



0]



Jadi, spline kuadratiknya adalah:  1 46+68 2   2 −1+2 (x + 2) − 68(x + 2) + 16,   1 −62−46 2    2 0+1 (x + 1) + 46(x + 1) + 5, 2 S(x) = 21 64+62 1−0 (x − 0) − 62(x − 0) − 3,   1 −40−64 2   2 2−1 (x − 1) + 64(x − 1) − 2,    1 0+40 (x − 2)2 − 40(x − 2) + 10, 2 3−2



>plot2d(z,s); plot2d(x,y,>points, , >add):



−2 ≤ x ≤ −1 −1 ≤ x ≤ 0 0≤x≤1 1≤x≤2 2≤x≤3



Bandingkan dengan hasil sebelumnya.



>{s,m}=spline2(x,y,1,z); // menggunakan syarat di ujung kiri. >m



[0,



-22,



6,



-4,



28,



-68]



>plot2d(z,s); plot2d(x,y,>points, , >add):



Perhatikan persamaan dan perbedaan kedua spline tersebut.



Spline Kubik



 a1 x3 + b1 x2 + c1 x + d1 , x 1 ≤ x ≤ x2     a2 x3 + b2 x2 + c2 x + d2 , x 2 ≤ x ≤ x3 S(x) = . ..      an−1 x3 + bn−1 x2 + cn−1 x + dn−1 , xn−1 ≤ x ≤ xn



Syarat-syarat yang harus dipenuhi: S(xk ) = yk ,



k = 1, 2, ..., n



Sk (xk+1 ) = Sk+1 (xk+1 ) = yk+1 , Sk′ (xk+1 ) Sk′′ (xk+1 )



= =



′ Sk+1 (xk+1 ), ′′ Sk+1 (xk+1 ),



k = 1, 2, ..., n − 2



k = 1, 2, ..., n − 2 k = 1, 2, ..., n − 2



Dari keempat syarat diperoleh 4n-6 persamaan linier, padahal koefisien yang harus dicari sebanyak 4n-4. Agar dapat diselesaikan digunakan dua asumsi, seperti biasanya menyangkut nilai-nilai S’(x) atau S”(x) di kedua titik ujung. Cara alternatif: Misalkan mk = S ′′ (xk ),



k = 1 , 2, ..., n.



Anggap seolah-olah kita memunyai n titik (x k,m k), untuk k = 1, 2, 3, ..., n. Dalam hal ini S”(x) merupakan spline linier dengan persamaan: S ′′ (x) = Sk′′ (x) =



(mk+1 − mk ) (x − xk ) + mk , untuk xk ≤ x ≤ xk+1 . (xk+1 − xk )



Turunan pertama spline kubiknya adalah: S ′ (x) = Sk′ (x) =



(mk+1 − mk ) (x − xk )2 + mk (x − xk ) + Ck , untuk xk ≤ x ≤ xk+1 . 2(xk+1 − xk )



dan spline kubiknya adalah: S(x) = Sk (x) =



(mk+1 − mk ) 1 (x − xk )3 + mk (x − xk )2 + Ck (x − xk ) + Dk , untuk xk ≤ x ≤ xk+1 . 6(xk+1 − xk ) 2



Karena S(x k)=y k, maka D k=y k. Selanjutnya, untuk mendapatkan nilai-nilai m k dan C k digunakan syarat S dan S’ kontinu, yakni: ′ Sk (xk+1 ) = Sk+1 (xk+1 ) = yk+1 dan Sk′ (xk+1 ) = Sk+1) (xk+1 ) = Ck+1 untuk k = 1, 2, 3, ..., n−2, dan Sn−1 (xn ) = yn



sehingga diperoleh: 1 1 (mk+1 − mk )(xk+1 − xk )2 + mk (xk+1 − xk )2 + Ck (xk+1 − xk ) = yk+1 − yk , untuk k = 1, 2, 3, ..., n − 1, 6 2 dan 1 (mk+1 − mk )(xk+1 − xk ) + mk (xk+1 − xk ) + Ck = Ck+1 , untuk k = 1, 2, 3, ..., n − 2, 2 atau (xk+1 − xk )(2mk + mk+1 ) + 6Ck =



6(yk+1 − yk ) , (xk+1 − xk )



(xk+1 − xk )(mk + mk+1 ) + 2(Ck − Ck+1 ) = 0,



k = 1, 2, 3, ..., n − 1,



k = 1, 2, 3, ..., n − 2,



yang merupakan SPL yang terdiri atas (2n-3) persamaan dalam (2n-1) variabel m 1, m 2, ..., m n, C 1, C 2, ..., C {n-1}. Agar dapat diselesaikan, biasanya digunakan dua asumsi tambahan yang berkaitan dengan nilai-nilai m 1 dan m n. Tugas Anda: 1. Tentukan spline kubik S(x) yang menginterpolasikan titik-titik (0,1), (1,1), (2,2) dan (4,5), dengan dengan syarat S”(0)=S”(4)=0 dengan kedua cara seperti di atas! Jawab: 1) Interpolasi S(xk ) = yk ,



sehingga : d1 = 1 a2 + b2 + c2 + d2 = 1 8a3 + 4b3 + 2c3 + d3 = 2 64a3 + 16b3 + 4c3 + d3 = 5 2) S adalah continue Sk (xk+1 ) = Sk+1 (xk+1 ) = yk+1 ,



maka: a1 + b1 + c1 + d1 = a2 + b2 + c2 + d2 = 1 8a2 + 4b2 + 2c2 + d2 = 8a3 + 4b3 + 2c3 + d3 = 2



3) S’ adalah continue ′ Sk′ (xk+1 ) = Sk+1 (xk+1 ),



sehingga: 3a1 + 2b1 + c1 = 3a2 + 2b2 + c2 12a2 + 4b2 + c2 = 12a3 + 4b3 + c3 4) S” adalah continue Sk ”(xk+1 ) = Sk+1 ”(xk+1 ),



sehingga: 6a1 + 2b1 = 6a2 + 2b2 12a2 + 2b2 = 12a3 + 2b3 5) Asumsi tambahan, S”(4)=0, artinya 24a3 + 2b3 = 0.



Dari persamaan turunan, solusinya adalah:  1 1 3 2  0≤x≤1  6 (m2 − m1 )x + 2 m1 x + C1 x + 1, 3 1 S(x) = 6 (m3 − m2 )(x − 1) + 21 m1 (x − 1)2 + C1 (x − 1) + 1, 1 ≤ x ≤ 2  1 3 2 1 6 (m4 − m3 )(x − 2) + 2 m1 (x − 2) + C1 (x − 2) + 1, 2 ≤ x ≤ 4.



Kemudian menggunakan syarat S dan S’ kontinu diperoleh SPL 2m1 + m2 + 6C1 = 0 2m2 + m3 + 6C2 = 0 4m3 + 2m4 + 6C3 = 0



m1 + m2 + 2(C1 − C2 ) = 0 m2 + m3 + 2(C2 − C3 ) = 0 2m3 + 2m4 + 2(C3 − C4 ) = 0



Diketahui S”(0) = S”(4) =0 maka m1 = 0 dan m3 = 2m4



Sehingga diperoleh m1 = 0 13 9 2 m3 = 9 1 m4 = 9



m2 =



2. Gambarlah kurva spline tersebut. Jawab:



>xp=1:4; yp=intrandom(1,4,4); s=spline(xp,yp); >plot2d("splineval(x,xp,yp,s)",0,5):



>plot2d(xp,yp,>points,>add):



3. Tulis program EMT untuk spline kubik seperti contoh pada spline kuadratik. Gunakan program tersebut untuk melakukan perhitungan dan menggambar spline kubik. Jawab:



>function spline3 (x,y,z,st,b1,bn) ...



n=lenghth(x); h=x(2:n)-x(1:n-1); d=(y(2:n)-y(1:n-1))./h; u=2*(h(1:n-2)+h(2:n-1)); v=6*(d(2:n-1)-d(2:n-1)); V=v’; dia=h(2:n-2);dib=dia; if st==1, u(1)=3/2*h(1)+2*h(2);V(1)=V(1)-3*(d(1)-b1); u(n-2)=2*h(n-2)+3/2*h(n-1);V(n-2)=V(n-2)-3*(bn-d(n-1));



A=diag(u)+ddiag(dib,-1)+diag(dia,1) m=A\V;m=[0;m;0]; m(1)=3/h(1)*d(1)-b1)-m(2)/2; V m end if st==2, A=diag(u)+diag(dib,-1)+diag(dia,1) V m=A\V;m[0;m;0] end if st==3, u(1)=3*h+2*h(2)+h(1)^2/h(2); dia(1)=h(2)-h(1)^2/h(2); dib(n-3)=h(n-2)-h(n-1)^2/h(n-2); u(n-2)=2*h(n-2)+3*h(n-1)+h(n-1)^2/h(n-2); A=diag(u)+diag(dib,-1)+diag(dia,1) m=A\V;m=[0;m;0]; m(1)=m(2)-h(1)*(m(3)-m(2))/h(2); m(n)=m(n-1)+h(n-1)*(m(n-1)-m(n-2))/h(n-2); V m end if st==4, u(1)=3*h(1)+2*h(2); u(n-2)=2*h(n-2)+3*h(n-1); A=diag(u)+diag(dib,-1)+diag(dia,1) m=A\V;m=[0;m;0]; m(1)=m(2);m(n)=m(n-1); V m end if st==5, V(1)=V(1)-h(1)*b1; V(n-2)=V(n-2)-h(n-1)*bn;



A=diag(u)+diag(dib,-1)+diag(dia,1) V m=A\V;m=[b1;m;bn] end C=y(2:n)./h-h.*m(2:n)’/6 D=y(1:n-1)./h-h.*m(1:n-1)’6 for j=1:lenghth(z), for k=1:n-1, if z(j)