INTERPOLASI PARAMETRIK SEBAGAI PILIHAN LAIN DI ANTARA INTERPOLASI LAGRANGE, SPLAIN-KUBIK DAN NEWBERY-GARRETT M. Bunjamin*
ABSTRAK INTERPOLASI PARAMETRIK SEBAGAI PILIHAN LAIN DI ANTARA INTERPOLASI LAGRANGE, SPLAIN-KUBIK DAN NEWBERY-GARRETT. Berikut akan dibahas tentang interpolasi parametrik di antara beberapa titik yang diketahui di bidang datar, serta akan ditunjukkan beberapa kebaikan sifatnya dibandingkan dengan interpolasi Lagrange, Splain-Kubik dan NewberyGarrett.
ASBTRACT PARAMETRIC INTERPOLATION AS NOTHER ALTERNATIVE AMONG LAGRANGE, CUBIC-SPLINE, AND NEWBERY-GARRETT INTERPOLATIONS. We will discuss how to obtain parametric interpolation between several given points in a plane, and show some of their advantages as compared to the Lagrange, Cubic-spline, and Newbery-Garrett interpolations.
PENDAHULUAN Penulis dalam makalahnya pada tahun 1992 [1] pernah melaporkan tentang kelemahan interpolasi Lagrange jika jumlah titik datanya banyak, misalnya ≥ 5, yang menghasilkan polinom interpolasi derajat ≥ 5 dengan goncangan vertikal demikian besar hingga hasil interpolasi Lagrange dengan interpolasi splain-kubik, yaitu interpolasi orde-tinggi berupa polinom kubik sepotong-sepotong yang di titik-titik data dapat didiferensialkan dua kali secara kontinu, dengan goncangan vertikal sangat minim, meskipun masih ada, sehingga jauh lebih berguna daripada interpolasi Lagrange. Penulis selanjutnya membandingkan kedua interpolasi ini dengan interpolasi orde tinggi yang diusulkan Newbery & Garrett [2], yaitu interpolasi polinom kuintik sepotong-sepotong dengan kelengkungan minimum, yang ternyata bersifat lebih baik lagi daripada interpolasi splain-kubik, karena tidak ada goncangan sama sekali. Namun untuk berbagai aplikasi yang memerlukan kecepatan tinggi, interpolasi splain-kubik dan Newbery & Garrett dianggap terlalu banyak melibatkan komputasi rumit hingga lambat. Karena itu orang masih mencoba mencari metode *
Pensiunan Widyaiswara Utama - BATAN
interpolasi lain yang penampilannya cukup baik, namun komputasinya relatif mudah dan cepat. Backstrom [3] mengusulkan interpolasi Lagrange sepotong-sepotong, yaitu polinom kuadratik untuk setiap tiga titik yang bersebelahan. Meskipun tampilan interpolasi ini cukup baik, dan komputasinya juga cepat, namun derivatif di titik-titik sambungan tidak kontinu, suatu cacat yang untuk banyak aplikasi tidak dapat diterima. Untuk mengatasi hal ini, Akyildiz [4] mengusulkan interpolasi parametrik, yaitu interpolasi polinom kubik sepotong-sepotong yang derivatif pertamanya kontinu di titik-titik data dan komputasinya relatif mudah dan cepat.
INTERPOLASI PARAMETRIK: PEMAHAMAN DASAR Andaikan diketahui N buah titik data berurutan Pi = (xi, ui), i = 1,2,...., N yang akan diinterpolasikan. Untuk menentukan fungsi interpolasi di antara dua titik data sembarang yang bersebelahan, misalnya Pi = (xi, ui) dan Pi+1 = (xi+1, ui+1), ditentukan: a) parabola p(t) yang harus lewat Pi dan Pi+1 dan satu titik sebelumnya, yaitu Pi-1 = (xi-1, ui-1), b) parabola q(t) yang harus lewat Pi dan Pi+1 dan satu titik sesudahnya, yaitu Pi+2 = (xi+2, ui+2), dan c) Kurva interpolasi yang sebenarnya lewat Pi dan Pi+1 ialah polinom kubik hasil kombinasi konvex dari kedua bagian parabola yang berada di interval (xi, xi+1). Persamaan kedua parabola, dan juga persamaan fungsi interpolasi yang sebenarnya, dinyatakan dalam bentuk parametrik dengan parameter t, dan fungsi interpolasi di interval (xi, xi+1) dinyatakan sebagai : r(t) = (1-t)p(t) + tq(t), 0 ≤ t ≤ 1. Dari uraian di atas tampak bahwa fungsi interpolasi parametrik di antara setiap dua titik yang bersebelahan didapat dari empat titik yang bersebelahan, yaitu dua titik tersebut ditambah satu titik sebelumnya dan satu titik sesudahnya. Jika N buah titik yang diinterpolasikan membentuk sebuah kurva tertutup (lihat gambar 5 s/d 8), maka metode ini akan menghubungkan semua titik dan membentuk kurva tertutup. Jika N buah titik ini membentuk sebuah kurva terbuka, maka kita harus menambahkan dua titik fiktif untuk melakukan interpolasi parametrik, yaitu satu di posisi sebelum P1 dan yang lain di posisi sebuah PN. Kedua titik fiktif ini dipilih demikian hingga hasil akhir kurva interpolasi di titik awal P1 dan titik akhir PN mempunyai derivatif kedua = 0, seperti yang biasanya disyaratkan pada interpolasi splain-kubik atau Newberry & Garrett. Sebagai contoh, perhatikan lima titik data sebagai berikut: P1 = (-8,8), P2 = (-1, -1), P3 = (10, 6), P4 = (8, -6), dan P5 = (20, 10), dan bagaimana cara menemukan persamaan parametrik polinom kubik (r(t) yang menghubungkan P2 dan P3 (lihat gambar 1 s/d 3).
Pertama, dicari persamaan parametrik dari parabola yang lewat P1, P2 dan P3, dengan syarat bahwa titik P1 harus sesuai dengan nilai parameter t = -1, titik P2 sesuai dengan nilai t = 0, dan titik P3 sesuai dengan nilai t = 1. Persamaan parabola p(t) yang harus lewat tiga titik tersebut dapat diuraikan dalam komponen Px(t) dan Pu(t), dengan persamaan Px(t) = -1 + 9t + 2t2 dan Pu(t) = -1 – t + 8t2 Kedua, dicari persamaan parametrik dari parabola yang lewat P2, P3 dan P4, dengan syarat bahwa titik P2 harus sesuai dengan nilai parameter t = 0, P3 sesuai dengan t = 1, dan P4 sesuai dengan t = 2. Persamaan parabola q(t) yang harus lewat tiga titik tersebut diuraikan dalam komponen qx(t) dan qu(t), yaitu qx(t) = -1 + 17.5t – 6.5t2 dan qu(t) = -1 + 16.5t – 9.5t2 Jadi intinya ialah, bagi titik P2 dan P3 yang dilalui oleh parabola p(t) dan q(t), daerah (range) nilai parameter t bagi kedua parabola di antara kedua titik ini harus sama, yaitu 0 ≤ t ≤ t 1. Ketiga, dicari persamaan parametrik dari fungsi interpolasi di antara titik P2 dan P3, yaitu r(t) = (1 – t) p(t) + tq(t), terdiri dari rx(t) = (1 – t) px(t) + tqx(t) = -1 + 9t + 10.5t2 – 8.5t3, dan ru(t) = (1 – t) pu(t) + tqu(t) = -1 – t + 25.5t2 – 17.5t3
INTERPOLASI PARAMETRIK: RUMUSAN SECARA RINCI Untuk menentukan fungsi interpolasi di antara dua titik data sebarang yang bersebelahan, misalnya Pi dan Pi+1 , pertama-tama perlu kita cari persamaan parametrik umum dari parabola yang lewat titik Pi-1, Pi , dan Pi+1, dengan syarat bahwa Pi-1 sesuai nilai t = -1, Pi sesuai dengan nilai t = 0, dan Pi+1, sesuai dengan nilai t = 1. Jika persamaan parabola ini mempunyai komponen px(t) = ax + bxt + cxt2 dan pu(t) = au + but + cut2, maka kita memiliki enam persamaan berikut untuk menentukan koefisien kedua parabola ini, yaitu: t = -1 ⇒ px(-1) = xi – 1 = ax + bx + cx dan pu(-1) = ui – 1 = au + bu + cu
t = 0 ⇒ px(0) = xi = ax dan Pu(0) = ui = au t = 1 ⇒ px(1) = xi + 1 = ax + bx + cx dan pu(1) = ui + 1 = au + bu + cu dari persamaan untuk t = 0 didapat ax = xi dan au = ui, dan jika hasil ini dimasukkan ke persamaan pertama dan ketiga akan memberikan bx = (xi + 1 - xi - 1 ) /2, dan bu = (ui + 1 - ui - 1 ) /2, cx = (xi + 1 - xi - 1 – 2xi ) /2, dan cu = (ui + 1 - ui - 1 – 2ui ) /2. Rumus-rumus di atas dapat disingkat sebagai berikut: a = Pi, b = (Pi + 1 - Pi - 1 ) /2, c = (Pi + 1 + Pi - 1 – 2Pi) /2. Selanjutnya kita cari persamaan parametrik parabola yang lewat titik Pi, Pi + 1, dan Pi + 2 , dengan syarat bahwa Pi sesuai dengan nilai t = 0, Pi + 1 sesuai dengan t = 1, dan Pi + 2 sesuai dengan t = 2. Jika persamaan parabola ini memiliki komponen qx(t) = Ax + Bxt + Cxt2 dan qu(t) = AU + But + Cut2, maka ada enam persamaan berikut untuk menentukan koefisien kedua parabola ini, yaitu: t = 0 ⇒ qx(0) = xi = Ax dan qu(0) = ui = Au t = 1 ⇒ qx(1) = xi + 1 = Ax + Bx + Cx dan qu(1) = ui + 1 = Au + Bu + Cu, t = 2 ⇒ qx(2) = xi + 2 = Ax + 2Bx + 4Cx dan qu(2) = ui + 2 = Au + 2Bu + 4Cu. Dari persamaan untuk t = 0 didapat Ax = xi dan Au = ui, Dan jika hasil ini dimasukkan ke persamaan ke-2 dan ke-3 akan memberikan: Bx = (-3xi + 4xi+1 – xi+2)/2, Bu = (-3ui + 4ui+1 – ui+2)/2, Cx = (xi - 2 xi+1 + xi+2) / 2, Cu = (ui - 2 ui+1 + ui+2) / 2, atau disingkat
A = P1, B = (-3Pi + 4Pi+1 – Pi+2)/2, C = (Pi – 2Pi+1 + Pi+2) / 2 Akhirnya kita cari persamaan fungsi interpolasi r(t) di antara titik P1 = (xi, ui) dan Pi+1 = (xi+1 , ui+1) dari persamaan r(t) = (1 – t) p(t) + tq(t) = (1 – t)(a + bt + ct2) + t(A + Bt + Ct2), atau r(t) = a + (b – a + A)t + (c – b + B)t2 + (C – c)t3 = Pi + 0.5(Pi+1 – Pi-1)t + 0.5(2Pi-1 - 5Pi + 4Pi+1 – Pi+2)t2 + 0.5(-Pi-1 + 3Pi - 3Pi+1 + Pi-2)t3 Ini berarti bahwa fungsi r(t) mempunyai komponen: rx(t) = ax + (bx – ax + Ax)t + (cx – bx + Bx)t2 + (Cx – cx)t3 = xi + 0.5(xi+1 – xi-1)t + 0.5(2xi-1 – 5xi + 4xi+1 – xi+2)t2 + 0.5(-xi-1 + 3ui – 3ui+1 + ui-2)t3 untuk nilai r dalam interval 0 ≤ t≤ 1.
MENENTUKAN KOORDINAT TITIK-TITIK FIKTIF Seperti telah disebutkan di atas, jika N buah titik Pi = (xi, ui) membentuk sebuah kurva terbuka, maka kita harus menambahkan dua titik fiktif, yaitu P0 = (x0, u0) di posisi sebelum Pi , dan yang lain PN+1 = (xN+1 , uN+1) di posisi sesudah PN. Kedua titik fiktif ini dipilih demikian hingga hasil akhir kurva interpolasi u(t) di titik awal Pi dan titik akhir PN mempunyai u" = 0, seperti yang biasanya disyaratkan pada interpolasi splain-kubik atau Newbery & Garrett (lihat gambar 4). Dari persamaan umum kurva interpolasi u(t) = a + (b – a + A)t + (c – b + B)t2 + (C – c)t3, didapat u'(t) = (b – a + A) + 2(c – b + B)t + 3(C – c)t2, dan u''(t) = 2(c – b + B) + 6(C – c)t
Untuk interval (xi,,x2), di titik Pi = (xi, ui) nilai t = 0 sehingga syarat u" = 0 berarti c – b + B = 0. Untuk 4 titik pertama (termasuk titik fiktif) P0 = (x0, u0), Pi = (xi, ui),
P2 = (x2, u2) dan P3 = (x3, u3),
kita mempunyai rumus b = (P2 – P0)/ 2, c = (P2 + P0 – 2P1)/2, dan B = (-3P1 + 4P2 – P3)/2, sehingga c – b + B = 0, berarti P2 + P0 – 2P1- P2 + P0 – 3P1 + 4P2 – P3 = 2P0 - 5P1 + 4P2 – P3 = 0 atau atau P0 = 5P1 - 4P2 + P3)/2, Ini berarti bahwa koordinat titik fiktif P0 = (x0, u0) dapat ditentukan dari koordinat tiga titik sesudahnya seperti berikut: x0 = (5x1 – 4x2 + x3)/ 2, dan u0 = (5u1 – 4u2 + u3)/2, Untuk interval (xN-1 , xN), di titik PN = (xN, uN) nilai t = 1, sehingga syarat u" = 0 berarti c – b + B + 3(C – c) = -b – 2c + B + 3C = 0 Untuk empat titik terakhir (termasuk titik fiktif) PN-2 ,= (xN-2, uN-2), PN-1 ,= (xN-1, uN-1), PN, = (xN, uN) dan PN+1 ,= (xN+1, uN+1), kita memiliki b = (PN - PN-2) / 2, c = (PN + PN-2 -2PN-1)/2, B = (-3PN-1 +PN-2)/2 dan C = (PN-1 - 2PN + PN+1)/2, sehingga –b – 2c + B + 3C = 0, berarti -PN/2 + PN-2/2 - PN - PN-2 + 2PN-1 - 3PN-1/2 + 2PN - PN+1/2 + 3PN-1/2 - 3PN + 3PN+1/2 = 0, atau PN+1 = (5PN- 4PN-1 + PN-2)/2 Ini berarti bahwa koordinat titik fiktif PN+1 = (xN+1, uN+1) dapat ditentukan dari koordinat tiga titik sebelumnya sebagai berikut:
xN+1 = (5xN- 4xN-1 + xN-2)/2 dan uN+1 = (5uN- 4uN-1 + uN-2)/2 Sebagai contoh, andaikan digunakan lima titik berikut: P1 = (-8, 8), P2 = (-1, -1), P3 = (10, 6), P4 = (8, -6), dan P5 = (20, 10), maka titik fiktif awal adalah P0 = (-13, 25) dan titik fiktif akhir adalah P6 = (39, 40).
KONTINUITAS DI TITIK-TITIK DATA Dari uraian di atas telah diketahui bahwa persamaan fungsi interpolasi di antara titik Pi = (xi, ui), dan Pi+1 = (xi+1, ui+1) ialah r(t) = Pi + 0.5(Pi+1 – Pi-1)t + 0.5(2Pi-1 – 5Pi + 4Pi+1 – Pi-2)t2 + 0.5(-Pi-1 + 3Pi - 3Pi+1 + Pi-2)t3,
sehingga derivatif pertamanya adalah: r’(t) = 0.5(Pi+1 – Pi-1)t + (2Pi-1 – 5Pi + 4Pi+1 – Pi-2)t2 + 1.5(-Pi-1 + 3Pi - 3Pi+1 + Pi-2)t2, yang berarti bahwa r’(0) = 0.5(Pi+1 – Pi-1). Ini adalah limit kanan. Jika sekarang kita perhatikan interval di antara Pi-1 = (xi-1, ui-1) dan Pi = (xi, ui), maka r’(t) = 0.5(Pi – Pi-2) + (2Pi-2 – 5PI-1 + 4Pi – Pi+1)t + 1.5(-Pi-2 + 3Pi-1 - 3Pi + Pi-1)t2, sehingga r’(1) = 0.5(Pi+1 – Pi-1). Ini adalah limit kiri dari r’(t) di titik Pi, yang ternyata sama dengan limit kanannya, sehingga interpolasi parametrik mempunyai derivatif pertama yang kontinu di titik-titik data, suatu sifat yang cukup ideal untuk suatu fungsi interpolasi. Nilai derivatif di titik Pi = (xi-, ui) adalah
r ' ( Pi =
u i +1 − u i −1 xi +1 − xi −1
Hal lain yang dapat disimpulkan dari sifat ini ialah bahwa garis singgung pada fungsi r(t) di titik Pi sejajar dengan garis yang menghubungkan Pi-1 dengan Pi+1.
MEMBANDINGKAN INTERPOLASI PARAMETRIK DENGAN INTERPOLASI LAIN Pada gambar 9 s/d 12 ditampilkan empat macam interpolasi yang diterapkan pada tigabelas titik yang sama, yaitu interpolasi Lagrange, splain-kubik, Newbery-
Garrett, dan parametrik. Ke-tigabelas titik ini digunakan Newbery-Garrett untuk membandingkan metode interpolasi mereka dengan splain-kubik. Tidak dapat disangkal bahwa hasil interpolasi Lagrange sama sekali tidak dapat diterima, karena goncangan vertikalnya yang demikian besar. Interpolasi splain-kubik menunjukkan ciri jauh lebih baik dari pada lagrange, tetapi masih ada cacat, yaitu adanya goncangan kecil di antara titik-titik 2 dan 3, 3 dan 4, 6 dan 7, 7 dan 8 serta 9 dan 10. Hasil interpolasi Newbery-Garrett jelas paling superior, apalagi jika digunakan algoritma yang baik untuk meminimalkan kelengkungannya. Namun di luar dugaan, hasil interpolasi parametrik yang komputasinya jauh lebih sederhana daripada splain-kubik dan Newbery-Garrett, menunjukkan ciri yang sangat dekat dengan hasil NewberyGarrett, dan jelas lebih baik dari hasil interpolasi splain-kubik. Hal ini sekali lagi tampak dari gambar 13 s/d 15 yang menunjukkan gambar mobil dari hasil interpolasi Newbery-Garrett, interpolasi splain-kubik, dan interpolasi parametrik yang diterapkan pada kumpulan 18 titik yang sama, dengan hasil yang juga cukup mencengangkan, yaitu hasil interpolasi parametrik yang lebih baik dari hasil interpolasi splain-kubik dan tidak jauh berbeda dari hasil interpolasi Newbery-garrett. Sekedar sebagai contoh tambahan, gambar 16 menunjukkan wajah orang yang penulis buat dengan bantuan interpolasi parametrik, suatu hal yang di masa lalu sulit penulis coba lakukan dengan sistem interpolasi yang lain.
KESIMPULAN DAN SARAN Dari pembahasan di atas tampak betapa interpolasi parametrik yang algoritmanya demikian sederhana jika dibandingkan dengan interpolasi splain-kubik, apalagi dibandingkan interpolasi Newbery-Garrett yang algoritmanya demikian kompleks, ternyata mampu memberi hasil tampilan yang mengalahkan hasil splainkubik dan sangat dekat dengan hasil Newbery-Garrett. Dengan kata lain, algoritma interpolasi parametrik adalah sangat efisien dan efektif. Kelebihan lain dari interpolasi parametrik terhadap interpolasi splain-kubik dan Newbery-Garrett ialah sebagai berikut. Jika kedua interpolasi terakhir ini bersifat global, yaitu perubahan satu titik data berakibat berubahnya seluruh komputasi N titik, maka interpolasi parametrik bersifat lokal, yaitu perubahan satu titik data tidak mempengaruhi komputasi data lain, dan hanya titik tetangga terdekatnya yang terpengaruh. Dengan berbagai kelebihan seperti tercantum di atas, penulis menyarankan kepada rekan-rekan peneliti, khususnya di bidang kimia, biologi, kedokteran, pertanian dan sebagainya. Yang biasanya kurang akrab dengan berbagai algoritma komputasi, untuk memanfaatkan interpolasi ini, antara lain untuk membantu proses
pengolahan dan pemodelan data dari hasil eksperimen laboratorium atau kebun percobaan atau rumah sakit.
UCAPAN TERIMA KASIH Penulis mengucapkan terima kasih sebesar-besarnya kepada rekan-rekan dosen di jurusan Fisika FMIPA-UI di Depok, karena telah membantu penulis dengan fasilitas jurnal komputasi, khususnya jurnal Computers in Physics dari American Institute of Physics.
DAFTAR PUSTAKA 1. BUNJAMIN, M., Interpolasi dengan Kelengkungan Minimum, Prosiding Lokakarya Komputasi dalam Sains dan Teknologi Nuklir II, Jakarta, Februari (1992) 9-23. 2. NEWBERY, A.C.R. & GARRETT, T.S., Comput. Math. Appl., 22, 37 (1997). 3. BACKSTROM, G., Computers in Physics, 7, 213 (1993) 4. AKYILDIZ, Y., Computers in Physics, 8, 722 (1994)
DISKUSI
HAYET LAGGOUNE Bagaimana perbandingan hasil antara interpolasi parametrik dengan metode lain ditinjau dari segi hasil akhir dan kompleksitas algoritma?
M. BUNJAMIN 1. Dari segi efisiensi komputasi/kompleksitas algoritma, interpolasi parametrik unggul karena komputasinya hanya ±10% dari komputasi Spline-cubic interpolation, apalagi terhadap metode Newbery-Garrett. 2. Dari segi hasil akhir/efektivitas, interpolasi parametrik setingkat dengan interpolasi Newbery-Garrett, berarti setingkat dengan interpolasi orde tinggi.
M. SYAMSA ARDISASMITA Kalau titik-titik kontrol membentuk suatu kontour (keliling tertutup), dapatkah titiktitik tersebut dihubungkan dengan satu tarikan kurva garis atau harus dilakukan oleh dua kurva garis yang berbeda?
M. BUNJAMIN Interpolasi itu sifatnya sepotong-sepotong (piecewise), jadi keliling tertutup tidak dapat dihubungkan dengan satu tarikan kurva garis sehingga harus dilakukan oleh dua (atau lebih) kurva garis yang berbeda.
DAFTAR RIWAYAT HIDUP
1. Nama
: M. BUNJAMIN
2. Tempat/Tanggal Lahir
: Kediri, 13 Mei 1933
3. Instansi
: -
4. Pekerjaan / Jabatan
: Pensiunan Widyaiswara Utama BATAN
5. Riwayat Pendidikan
: (setelah SMA sampai sekarang)
•
FMIPA-UGM, Jurusan Matematika
6. Pengalaman Kerja
(S1)
: 1986 – 1992 : Kepala PPI - BATAN 1992 - 1998 : Widyaiswara Utama BATAN
7. Organisasi Professional
HOME
: -
KOMPUTASI DALAM SAINS DAN TEKNOLOGI NUKLIR X
