BAB 2 LANDAS AN TEORI
2.1
Navigasi Udara Navigasi udara merupakan kegiatan untuk mengarahkan alat transportasi udara
(dalam hal ini pesawat) dari satu tempat ke tempat yang lain agar tidak keluar dari jalurnya. Navigation is the process of reading, planning, recording, and controlling the movement of a craft or vehicle from one place to another. [Jacob et al., 1993] Navigasi juga diperlukan untuk mengurangi risiko kecelakaan pesawat yang diakibatkan oleh tabrakan dengan pesawat lainnya maupun benturan dengan bukit dan awan tebal khususnya ketika cuaca buruk atau jarak pandang pilot terbatas. Navigasi ini dilakukan dari darat yang dibantu melalui sinyal yang dipancarkan oleh instrumen terpasang pada menara (ground base) maupun sinyal dari satelit (satellite base). Kemudian dengan sinyal-sinyal yang dipancarkan balik oleh pesawat, orang di darat dapat mengetahui koordinat titik lokasi pesawat tersebut berada yang kemudian digunakan untuk mengarahkan pesawat.
2.2
Posisi dan S istem Koordinat Posisi suatu titik biasanya dinyatakan dengan koordinat (dua-dimensi atau tiga-
dimensi) yang mengacu pada suatu sistem koordinat tertentu. Sistem koordinat itu sendiri didefinisikan dengan menspesifikasikan tiga parameter berikut, yaitu: •
Lokasi titik nol dari sistem koordinat
7
•
Orientasi dari sumbu-sumbu koordinat
•
Satuan yang digunakan untuk mendefinisikan posisi suatu titik dalam sistem koordinat tersebut.
Setiap parameter dari sistem koordinat tersebut dapat dispesifikasikan lebih lanjut, dan bergantung pada spesifikasi parameter yang digunakan. Posisi titik di permukaan bumi diberikan dalam koordinat kartesian tiga-dimensi (X, Y, Z) dalam sistem koordinat. Koordinat kartesian (X, Y, Z) tersebut selanjutnya dapat ditransformasikan menjadi koordinat geodetik ( , ,h).
Gambar 2.1 Posisi titik dalam system koordinat kartesian dan geodetik Hubungan matematis antara koordinat-koordinat kartesian dan geodetik dapat dituliskan sebagai berikut: (1)
8
Pada rumus di atas,
dan
adalah jari-jari kelengkungan vertikal dan eksentrisitas
ellipsoid yang keduanya dapat dihitung sebagai berikut:
, Di mana
dan
(2)
berturut-turut adalah setengah sumbu panjang dan setengah sumbu
pendek dari elipsoid.
2.3
GPS (Global Positioning S ystem) GPS adalah sistem radio navigasi dan penentuan posisi menggunakan satelit.
Nama formalnya adalah NAVSTAR GPS (Navigation Satellite Timing and Ranging Global Positioning System). Sistem yang dapat digunakan oleh banyak orang sekaligus dalam segala cuaca ini, didesain untuk memberikan posisi dan kecepatan tiga dimensi yang teliti, dan juga informasi mengenai waktu, secara kontinyu di seluruh dunia. Pada dasarnya GPS terdiri atas tiga segmen utama, yaitu segmen angkasa (spacial segment) yang terdiri dari satelit-satelit GPS, segmen sistem kontrol (control system segment) yang terdiri dari stasiun-stasiun pemonitor dan pengontrol satelit, dan segmen pemakai (user segment) yang terdiri dari pemakai GPS termasuk alat-alat penerima dan pengolah sinyal dan data GPS. Ketiga segmen ini digambarkan secara skematik di Gambar 2.2.
9
Gambar 2.2 Sistem Penentuan Posisi Global , GPS Ada beberapa hal yang membuat GPS menarik untuk digunakan dalam penentuan posisi, yakni: •
GPS dapat digunakan setiap saat tanpa bergantung waktu dan cuaca. GPS dapat digunakan baik pada siang ataupun malam hari, dalam kondisi cuaca yang buruk sekalipun seperti hujan ataupun kabut. Karena karakteristiknya ini maka penggunaan GPS dapat meningkatkan efisiensi dan fleksibilitas dari pelaksanaan aktivitas-aktivitas yang terkait dengan penentuan posisi.
•
Satelit-satelit GPS mempunyai ketinggian orbit yang cukup tinggi, yaitu sekitar 20.000 km di atas permukaan bumi. Jumlahnya pun relatif cukup banyak, untuk saat ini terdapat 24 satelit. Ini menyebabkan GPS dapat meliput wilayah yang cukup luas, sehingga akan dapat digunakan oleh banyak orang pada saat yang sama, serta pemakaiannya menjadi tidak bergantung pada batas-batas politik dan batas alam, seperti yang diilustrasikan pada Gambar 2.3.
10
Gambar 2.3 Cakupan GPS yang relatif luas
•
Posisi yang ditentukan dengan GPS akan mengacu pada suatu datum global yang dinamakan WG S 1984. WGS 1984 adalah sistem koordinat kartesian terikatbumi. Pusatnya berimpit dengan pusat massa bumi, sumbu-Z nya berimpit dengan sumbu putar bumi yang melalui CTP (Conventional Terrestrial Pole), sumbu-X nya terletak pada bidang meridian nol (Greenwich), sumbu-Y nya tegak lurus sumbu X dan Z dan membentuk sistem tangan kanan.
•
GPS dapat memberikan ketelitian posisi yang spektrumnya cukup luas. Dari yang sangat teliti (orde milimeter) sampai yang biasa-biasa saja (orde puluhan meter). Luasnya spektrum ketelitian yang bisa diberikan ini memungkinkan penggunaan GPS secara efektif dan efisien sesuai dengan ketelitian yang diminta.
•
Selain memberikan informasi posisi, GPS juga dapat memberikan informasi mengenai jarak, kecepatan, percepatan, dan waktu secara teliti.
11
2.3.1
Metode Penentuan Posisi Kinematik Penentuan posisi secara kinematik (kinematic positioning) adalah penentuan
posisi dari titk-titik yang bergerak. Hasil penentuan posisi bisa diperlukan pada saat pengamatan (real-time) ataupun sesudah pengamatan (post-processing). Problem utama dari penentuan posisi kinematik secara teliti adalah penentuan ambiguitas fase secara onthe-fly, yaitu penentuan ambiguitas fase pada saat receiver sedang bergerak dalam waktu sesingkat mungkin.
2.3.2
GPS dan Perhubungan Udara Organisasi Penerbangan Sipil Sedunia, ICAO (International Civil Aviation
Organization) sudah sejak 1966 melakukan investigasi terhadap potensi satelit dalam mendukung navigasi pesawat udara. Pada periode 1969 – 1970, Komisi Penasihat ATC (Air Traffic Control) dari Departemen Transportasi Amerika Serikat juga sudah melakukan investigasi terhadap kemungkinan penggunaan satelit sebagai elemen utama pada ATC ataupun pada pesawat terbang untuk keperluan komunikasi, navigasi, dan pemantauan. Komisi ini menganalisis penggunaan satelit untuk aplikasi penerbangan di atas lautan maupun daratan. Komisi penasehat ATC ini berkesimpulan bahwa meskipun sistem CNS (Comunication, Navigation and Surveillance) berbasis satelit tersebut secara konsepsional memungkinkan dan juga potensinya sangat besar. Pada awal 1980-an RTCA (Radio Technical Commision for Aeronautics) di Amerika Serikat mulai melakukan investigasi yang berkaitan dengan teknologi, keuntungan-keuntungan, serta kebutuhan-kebutuhan pemakai dari sistem-sistem CNS di masa mendatang untuk pengelolaaan lalu lintas udara dan navigasi , dengan penekanan
12
khusus pada aplikasi dari teknologi satelit. Komisi Khusus dari RCTA, setelah melakukan investigasi selama tiga tahun berkesimpulan bahwa penggunaan teknologi satelit tidak hanya memikat, tetapi secara nyata tampaknya akan menjadi satu-satunya metode yang mampu memberikan pelayanan untuk navigasi serta pengelolaan lalu lintas yang memenuhi persyaratan penerbangan di masa mendatang dalam skala global. Selanjutnya pada November 1983, ICAO membentuk kelompok kerja internasional yang bernama FANS (Future Air Navigation Systems) yang terdiri atas negara anggota ICAO dan peninjau dari organisasi internasional sebanyak 32 negara. Secara lebih spesifik, kelompok kerja FANS ini bertujuan melakukan studi, identifikasi, dan konsolidasi dari konsep-konsep dan teknologi baru dalam bidang navigasi udara, termasuk teknologi satelit, serta memformulasikan rekomendasi bagi pengembangan bidang navigasi udara sipil di masa mendatang untuk periode 25 tahun (1990 - 2015). Kelompok kerja FANS ini selama lima tahun masa kerjanya telah mengembangkan konsep dari suatu sistem komunikasi, navigasi, dan pemantauan (CNS) terpadu yang berbasiskan pada teknologi satelit. Untuk komponen komunikasi dan pemantauan, FANS menggunakan GNSS (Global Navigation Satellite System) yang mencakup sistem-sistem satelit GPS. Pada saat ini organisasi-organisasi penerbangan banyak terlibat dengan pengembangan spesifikasi dan standar penerbangan untuk penggunaan GPS dan sistem-sistem yang terkait.
13
2.3.3
Aplikasi dan Manfaat Penggunaan GPS pada Perhubungan Udara Potensi penggunaan GPS dalam bidang perhubungan udara terutama terkait
dengan aspek-aspek navigasi dan pemantauan. Kalau kita mengacu pada fase-fase navigasi yang umum dikenal yaitu en-route/terminal (oceanic, domestic, terminal, remote areas, special helicopter operations) dan approach and landing (non-precision, precision), maka pada dasarnya dapat dikatakan bahwa GPS akan punya manfaat dan peran yang besar untuk setiap fase tersebut. Di samping dapat memberikan informasi tentang posisi tiga-dimensi pesawat (termasuk parameter tinggi) dari waktu ke waktu secara teliti, GPS juga dapat digunakan untuk memberikan informasi tentang kecepatan, arah terbang, serta atitude (pitch, roll) dari pesawat yang bersangkutan.
Gambar 2.4 Automatic Dependent Surveillance Penggunaan GPS dalam bidang perhubungan udara tidak hanya akan memengaruhi sistem kokpit pesawat, tetapi juga sistem ATC (Air Traffic Control), dan ground base systems. Beberapa aplikasi GPS dalam bidang penerbangan yang sedang dikembangkan meliputi: Aplikasi yang segera direalisasikan •
Oceanic en-route navigation and surveillance
14
•
Domestic en-route navigation and surveillance
•
Terminal area navigation and surveillance
•
Non-precision approach guidance
•
Instrument landing guidance
•
Altimetry
•
Runway incrusion detection Aplikasi masa mendatang
•
Precision landing guidance
•
Attitude and heading reference
•
Airport surface guidance Dalam dunia penerbangan, minat terhadap GPS dan kemampuan navigasinya
timbul sebagian karena hasil studi yang menunjukkan bahwa penggunaan GPS mempunyai manfaat yang berdampak ekonomis cukup besar bagi perusahaanperusahaan penerbangan, bisnis penerbangan, dan komunitas penerbangan secara umum.
2.3.4
Kinerja dan Keterbatasan GPS Telah banyak pertanyaan dilontarkan mengenai peran GPS sebagai sistem
navigasi sipil untuk penerbangan. Terutama berkaitan dengan aspek-aspek ketelitian, keandalan, integritas, dan ketersediaannya dalam melayani fase-fase penerbangan. Baik itu en-route/terminal maupun approach and landing. Berikut ini kinerja dan keterbatasan dari GPS akan dibahas dengan mengacu pada aspek-aspek ketelitian, keandalan, integritas, dan ketersediaan.
15
Dari aspek ketelitian, sistem satelit navigasi seperti GPS sebenarnya mempunyai level ketelitian yang lebih tinggi dibandingkan sistem-sistem navigasi lainnya, seperti yang ditunjukkan pada Tabel 2.1 berikut. Tabel 2.1 Ketelitian tipikal dari beberapa sistem navigasi [Jacob et al., 1993; DoD and DoT,1993] Sistem Navigasi GPS (C/A code, L1) DGPS (Carrier Smoothed Code) DGPS (Carrier Phase, Kinematik) GLONASS VOR (jarak = 10 nm, Dc = 4 derajat) DM E (Distance M easuring Equipment) VLF – W INS (Inertial Navigation System) AHRS
Ketelitian tipikal 100 m, 2 D, 95% <3m < 0,5 m 18 m 1200 m < 450 m > 1000 m 1800 m / jam > 18000 m / jam
Kalau hanya memerhatikan masalah ketelitian, sebenarnya GPS dapat melayani semua fase navigasi dari penerbangan. Dari Tabel 2.2 berikut terlihat bahwa secara teoritis dari segi ketelitian dapat dikatakan bahwa GPS dapat melayani semua fase sampai tahap kategori 3. M eskipun dari segi ketelitian GPS lebih baik dibanding sistem lainnya, tetapi sampai saat ini GPS hanya disertifikasi sebagai sistem navigasi suplemen di samping sistem-sistem navigasi yang telah ada. Alasan utamanya adalah masalah integritas dari GPS dan juga adanya degradasi yang sifatnya periodik dari geometri satelit di beberapa tempat di permukaan bumi ini.
16
Tabel 2.2 Persyaratan ketelitian untuk penerbangan sipil [DoD and DoT, 1993] Fase Sub-Fase Ketelitian (Source Accuracy) 2drms (meter) En-Route / Oceanic Domestic 1000 (normal and high traffic density) Terminal 2000 (low traffic density) Terminal 500 Remote 1000 – 4000 Special Helicopter 500 (high traffic density) Operation 1000 - 2000 (low traffic density) Approach Non-Precision 100 CAT I Lateral : 17,1 Vertikal : 4,1 and landing precision CAT II 5,2 1,7 CAT III 4,1 0,6 M engingat pentingnya masalah integritas sistem navigasi dalam dunia penerbangan dan jga mengingat bahwa kelemahan GPS yang utama adalah dalam masalah integritas ini, banyak penelitian yang difokuskan pada cara-cara meningkatkan dan memantau tingkat integritas dari GPS. Perlu dicatat bahwa sistem GPS sendiri sebenarnya sudah dilengkapi dengan karakteristik built-in serta prosedur operasional yang dimaksudkan untuk memantau dan sekaligus menjamin integritas dari GPS. Tetapi meskipun begitu, delay waktu sebesar 15 - 20 menit masih ada antara terjadinya anomali (kesalahan) pada satelit dengan indikasi awalnya yang diamati oleh Segmen Kontrol GPS. Di samping itu waktu tambahan sekitar satu jam biasanya diperlukan untuk meng-update data yang ditransmisikan ke pengguna. Delay waktu yang inhren dalam kemampuan pemantauan dari Segmen Kontrol GPS ini tidak memenuhi syarat integritas yang dituntut baik oleh ICAO maupun FAA untuk semua fase navigasi, seperti yang ditunjukkan pada Tabel 2.3.
17
Tabel 2.3 Persyaratan integritas untuk penerbangan sipil [DoD and DoT, 1993] Fase En-Route / Terminal Approach and Landing
Sub-Fase Oceanic Domestic Terminal Non-Precision Precission
2.4
Interpolasi
2.4.1
Ilustrasi Interpolasi
CAT I CAT II CAT III
Time-toAlarm (detik) 30 30 10 10 6 2 2
Data yang diperoleh dari hasil pengamatan di lapangan dengan GPS selanjutnya akan diproses sehingga menghasilkan titik-titik koordinat pesawat, di mana titik-titik ini digunakan sebagai jalur pendaratan pesawat. Sebagai ilustrasi, sebuah perekaman titik koordinat oleh GPS adalah setiap 400 meter. Permasalahan yang diangkat dengan data tersebut adalah menentukan nilai di antara titik-titik diskrit tersebut (tanpa harus melakukan pengukuran lagi). M isalkan dari pengukuran di atas, diinginkan posisi titik koordinat setiap 100 meter. M aka sebelumnya akan ditentukan fungsi yang menghubungkan peubah-peubah yang ada. Solusinya adalah mencari fungsi yang mencocokkan (fit) titik-titik data tersebut. Pendekatan seperti ini di dalam metode numerik dinamakan pencocokan kurva ( Curve fitting ). Fungsi yang diperoleh dengan pendekatan ini merupakan fungsi hampiran, karena itu nilai fungsinya tidak setepat nilai sesungguhnya. Namun, cara ini dalam prakteknya
18
sudah mencukupi karena rumus yang benar – benar menghubungkan beberapa buah besaran fisik sulit ditemukan
Gambaran perekaman koordinat oleh GPS : 400m kedua
400m pertama
400m keempat
400m ketiga
400m kelima
Ketelitian data koordinat yang diinginkan setiap 100 meter 400m kedua
400m pertama
400m keempat
400m ketiga
400m kelima
Gambar 2.5 Perekaman koordinat oleh GPS Pencocokan kurva tidak hanya bertujuan menghitung nilai fungsi, tetapi ia juga digunakan untuk mempermudah perhitungan numerik yang lain seperti menghitung nilai turunan (derivative) dan menghitung nilai integral (
∫
). M isalnya kita dihadapkan
dengan fungsi yang bentuknya cukup rumit, seperti fungsi berikut :
19
f ( x) =
(
ln 2 x 1 / 2 − 4x 2 1 + 2x 5
)
3
.
(3)
M enghitung turunan fungsi tersebut pada nilai x tertentu, misalnya di x = a , f ' (a ) = ? merupakan pekerjaan yang cukup sulit, apalagi bila turunan yang dibutuhkan semakin tinggi ordenya. Demikian juga dengan menghitung nilai integral fungsi f ( x ) pada selang integrasi [a, b] , misalnya selang [0,1], 1
∫ 0
(
ln 2x 1 / 2 − 4 x 2 1 + 2 x5
).
(4)
Hal ini merupakan pekerjaan yang sulit, bahkan secara analitik pun belum tentu dapat dilakukan. Rumus integrasi untuk fungsi semacam ini tidak tersedia. Satu pendekatan untuk melakukan dua perhitungan ini ialah dengan menyederhanakan fungsi f ( x ) menjadi polinom p n(x) yang berderajat ≤ n. f ( x ) = pn (x ) ,
(5)
yang dalam hal ini, p n ( x ) = a 0 + a1 x + a2 x 2 + ... + an x n .
(6)
M enghitung turunan atau mengintegralkan suku-suku polinom menjadi lebih mudah karena rumus untuk menghitung turunan atau mengintegrasikan polinom sangat sederhana, yaitu (i) Jika f ( x ) = ax n maka f ' ( x ) = nax n −1 , a dan n konstan. (ii)
∫ ax n dx =
a x n +1 + C , a dan n konstan, n ≠ -1. ( n + 1)
20
Untuk membentuk polinom ini, kita mengambil beberapa titik diskrit (yang umumnya berjarak sama) pada kurva fungsi f. Titik-titik tersebut secara alami direpresentasikan dalam bentuk tabel. Selanjutnya titik-titik data ini dicocokkan untuk menentukan polinom p n ( x ) yang menghampiri fungsi aslinya.
y
x
Gambar 2.6 Pencocokan kurva dengan Interpolasi Pencocokan kurva adalah sebuah metode yang mencocokkan titik-titik data dengan sebuah kurva (fitting curve) fungsi.
2.4.2
Metode Interpolasi Bila data diketahui mempunyai ketelitian yang sangat tinggi, maka kurva
cocokannya dibuat melalui setiap titik, persis sama kalau kurva fungsi yang sebenarnya dirajah melalui tiap titik itu. Kita katakan di sini bahwa kita menginterpolasi titik-titik data dengan sebuah fungsi (Gambar 2.6). Bila fungsi cocokan yang digunakan berbentuk polinom, polinom tersebut dinamakan polinom interpolasi. Pekerjaan menginterpolasi titik-titik data dengan sebuah polinom disebut interpolasi (dengan) polinom. Contoh data yang berketelitian tinggi adalah titik-titik yang dihitung dari fungsi yang telah
21
diketahui (seperti dari persamaan 3), atau data tabel yang terdapat di dalam acuan ilmiah (seperti data percepatan gravitasi bumi sebagai fungsi jarak sebuah titik ke pusat bumi). Selain dengan polinom, interpolasi titik-titik data dapat dilakukan dengan fungsi spline, fungsi rasional (pecahan), atau deret Fourier.
2.4.3
Persoalan Interpolasi Polinom Diberikan n+1 buah titik berbeda (x0,y 0),(x1,y 1), … ,(xn,y n). Tentukan polinom
p n(x) yang menginterpolasi (melewati) semua titik-titik tersebut sedemikian rupa sehingga y i = pn (x i ) untuk i = 0,1,2, … ,n Nilai y i dapat berasal dari fungsi matematika f(x) sedemikian sehingga y i = f(xi), sedangkan p n(x) disebut fungsi hampiran terhadap f(x). Atau y i berasal dari nilai empiris yang diperoleh melalui percobaan atau pengamatan.
(y=p n(x))
(x1,y1)
(xn,yn)
(x2,y2) (x3,y3)
(xn‐1,yn‐1)
(a,p n(a))
(b,p n(b))
(x0,y0)
(x = a)
(menginterpolasi)
(x = b)
(mengekstrapolasi)
Gambar 2.7 Interpolasi dan Ekstrapolasi
22
Setelah polinom interpolasi p n(x) ditemukan, p n(x) dapat digunakan untuk menghitung perkiraan nilai y di x = a, yaitu y = p n(a). Bergantung pada letaknya, nilai x=a mungkin terletak di dalam rentang titik-titik data (x0 < a < xn) atau di luar rentang titik-titik data (a < x0 atau a > xn) : (i) Jika x0 < a < xk maka y k = p(xk) disebut nilai interpolasi (interpolated value) (ii) Jika xn < xk atau x0 > xk maka y k = p(xk) disebut nilai ekstrapolasi (extrapolated value) Keduanya, (i) dan (ii), ditunjukkan pada Gambar 2.7. Beberapa metode perhitungan polinom interpolasi telah ditemukan oleh para analis numerik tanpa menggunakan cara pendekatan di atas. Beberapa di antaranya akan diberikan di sini yaitu : a. Polinom Lagrange b. Polinom Newton c. Polinom Newton-Gregory (kasus khusus dari polinom Newton) Untuk sejumlah titik-titik data yang diberikan, metode interpolasi yang berbedabeda ini tetap menghasilkan polinom yang sama (unik), tetapi dalam bentuk yang berbeda satu sama lain, dan berbeda juga dalam jumlah komputasi yang dilibatkan.
2.5
Polinom Newton Pada Polinom Lagrange terdapat beberapa kelemahan yaitu: a. Banyaknya 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.
23
b. Bila jumlah titik-titik data meningkat atau menurun, hasil komputasi sebelumnya tidak dapat digunakan. Hal ini disebabkan oleh tidak adanya hubungan antara pn-1(x) dan pn(x) pada polinom Lagrange. Polinom Newton dibuat untuk mengatasi kelemahan ini. Dengan polinom Newton, polinom yang dibentuk sebelumnya dapat dipakai untuk membuat polinom derajat yang lebih tinggi. Pada polinom lanjar persamaannya: p1 (x ) = y 0 +
( y1 − y 0 ) ( x − x0 ) ( x1 − x 0 )
(7)
Bentuk persamaan ini dapat ditulis sebagai P1(x) = a0+a1(x-x0)
(8)
Di mana a0 = y0 =f(x0)
(9)
dan a1 =
y1 − y0 f (x1 ) − f ( x 0 ) = x1 − x 0 x1 − x 0
(10)
Persamaan (10) ini merupakan bentuk selisih-terbagi (divided-difference) dan dapat disingkat penulisannya menjadi a1 = f[x1, x0]
(11)
Setelah polinom lanjar, polinom kuadratik dapat dinyatakan dalam bentuk p2(x) = a0 + a1(x-x0) + a2(x-x0)(x-x1)
(12)
p2(x) = p1(x) + a2(x-x0)(x-x1)
(13)
atau
24
Persamaan (13) memperlihatkan bahwa p2(x) dapat dibentuk dari polinom sebelumnya, p1(x). Ini mengarahkan kita pada pembentukan polinom Newton untuk derajat yang lebih tinggi. Nilai a2 dapat ditemukan dengan menyulihkan x = x2 untuk memperoleh a2 =
f ( x2 ) − a0 − a1 ( x2 − x 0 ) (x 2 − x0 )( x2 − x1 )
(14)
Nilai a0 dan nilai a1 pada persamaan (9) dan (10) dimasukkan ke dalam persamaan (14) untuk memberikan f ( x2 ) − f (x0 ) f (x1 ) − f ( x0 ) − x2 − x0 x1 − x 0 a2 = x 2 − x1 Dengan melakukan perhitungan aljabar, persamaan terakhir ini lebih disukai ditulis menjadi f (x2 ) − f (x1 ) f (x1 ) − f (x0 ) − f [ x2 , x1 ] − f [ x1 , x0 ] x 2 − x1 x1 − x0 a2 = = x2 − x0 x2 − x0
(15)
Demikian seterusnya, kita dapat membentuk polinom Newton secara bertahap : polinom derajat n dibentuk dari polinom derajat (n-1). Polinom Newton dinyatakan dalam hubungan rekursif sebagai berikut : (i) Rekurens : pn(x) = pn-1(x) + an(x-x0)(x – x1) ... (x – xn-1) (ii) Basis : p0(x) = a0 Jadi, tahapan pembentukan polinom Newton adalah sebagai berikut : p1(x)
= p0(x) + a1(x – x0) = a0 + a1(x – x0)
p2(x)
= p1(x) + a2(x – x0)(x – x1) = a0 + a1(x – x0) + a2(x – x0)(x – x1)
(16)
25
p3(x)
= p2(x) + a3(x – x0)(x – x1)(x – x2) = a0 + a1(x – x0) + a2(x – x0)(x – x1) + a3(x – x0)(x – x1)(x – x2)
... pn(x)
= pn-1(x) + an(x – x0)(x – x1) ... (x – xn-1) = a0 + a1(x – x0) + a2(x – x0)(x – x1) + a3(x – x0)(x – x1)(x – x2) + ... + an(x – x0)(x – x1) ... (x – xn-1)
(17)
Nilai konstanta a0, a1, a2,…an merupakan nilai selisih-terbagi dengan nilai masingmasing : a0=f(x0) a1=f [x1, x0] a2=f [x2, x1,x0] : an = f [xn, xn-1,…,x1,x0] di mana,
[
]
f xi , x j =
[
f (xi ) − f (x j ) xi − x j
]
f xi , x j , x k =
f (xi , x j ) − f (x j , x k ) xi − x k
f [xn , xn −1 ,..., x1 , x 0 ] =
f (xn , x n−1 ,..., x1 ) − f ( xn −1 , x n−2 ,..., x0 ) x n − xo
(18)
(19)
(20)
dengan demikian polinom Newton pada persamaan (16) dapat ditulis dalam hubungan rekursif sebagai berikut (i) Rekurens :
26
p n (x ) = pn −1 (x ) + (x − x0 )( x − x1 )...(x − x n −1 ) f [x n , xn −1 ,..., x1 , x 0 ]
(21)
(ii) Basis : p0(x) = f(x0) atau dalam bentuk polinom yang lengkap sebagai berikut : pn(x)
= f(x0) + (x – x0) f[x1,x0] + (x – x0)(x – x1) f[x2,x1,x0] + (x – x0)(x – x1) … (x – xn-1) f[xn,xn-1, … ,x1,x0]
(22)
Karena tetapan a0, a1, a2,..., an merupakan ini selisih terbagi, maka polinom Newton dinamakan juga polinom interpolasi selisih-terbagi Newton. Nilai selisih terbagi ini dapat dihitung dengan menggunakan tabel yang disebut tabel selisih-terbagi, misalnya tabel selisih terbagi untuk empat buah titik (n = 3 ) berikut : Tabel 2.4 Tabel Selisih Terbagi untuk Empat buah Titik i 0 1 2 3
xi x0 x1 x2 x3
yi = f(x i) f(x0) f(x1) f(x2) f(x3)
ST – 1 f[x1,x0] f[x2,x1] f[x3,x1]
ST – 2 f[x2,x1,x0] f[x3,x2,x1]
ST – 3 f[x3,x2,x1,x0]
Keterangan : ST = Selisih-Terbagi Sekali tabel selisih-terbagi dibentuk, polinom interpolasi yang melewati sekumpulan titik (x1,y1) berbeda (misalnya untuk i = 0,1,2, atau i = 1,2,3) dapat ditulis dengan mudah. Bila bagian tabel yang diarsir dinyatakan di dalam matriks ST [ 0...n, 0...n], maka evaluasi pn(x) untuk x = t dapat dinyatakan sebagai pn(t)
= ST(0,0) + ST[0,1](t-x0) + ST[0,2](t – x0)(t – x1) + ST[0,n](t – x0)(t – x1) … (t – xn-1)
Kelebihan Polinom Newton Alasan mengapa Polinom Newton lebih disukai untuk dibuat program, yaitu
27
a. Karena polinom Newton dibentuk dengan menambahkan satu suku tunggal dengan polinom derajat yang lebih rendah, maka ini memudahkan perhitungan polinom derajat yang lebih tinggi dalam program yang sama. Karena alasan itu, polinom Newton sering digunakan khususnya pada kasus yang derajat polinomnya tidak diketahui terlebih dahulu. b. Penambahan suku-suku polinom secara beruntun dapat dijadikan kriteria untuk menentukan tercapainya titik berhenti, yaitu apakah penambahan suku-suku yang lebih tinggi tidak lagi memperbaiki nilai interpolasi, atau malahan menjadi lebih buruk. c. Tabel selisih terbagi dapat dipakai berulang-ulang untuk memerkirakan nilai fungsi pada nilai x yang berlainan.
2.6
Polinom Newton – Gregory Polinom Newton-Gregory merupakan kasus khusus dari polinom Newton untuk
titik-titik yang berjarak sama. Pada kebanyakan aplikasi nilai-nilai x berjarak sama, misalnya pada tabel nilai fungsi, atau pada pengukuran yang dilakukan pada selang waktu yang teratur. Untuk titik-titik yang berjarak sama, rumus polinom Newton menjadi lebih sederhana. Selain itu, tabel selisih-terbaginya pun lebih mudah dibentuk. Di sini kita menamakan tabel tersebut sebagai tabel selisih saja, karena tidak ada proses pembagian dalam pembentukan elemen tabel. Ada dua macam tabel selisih, yaitu tabel selisih maju (forward difference) dan karena itu, ada dua macam polinom Newton – Gregory, yaitu polinom Newton-Gregory
28
maju dan polinom Newton Gregory mundur. Pada tugas akhir ini yang dibahas adalah polinom Newton-Gregory Maju.
2.7
Polinom Newton-Gregory Maju Polinom Newton-Gregory maju diturunkan dari tabel selisih maju. Sebelum
menurunkan rumusnya, kita bahas terlebih dahulu tabel selisih maju.
2.7.1
Tabel selisih Maju M isal diberikan lima buah titik dengan absis xi, i=0,1,...,4 yang berjarak sama.
Tabel selisih maju yang dibentuk dari kelima titik tersebut adalah Tabel 2.5 Tabel Selisih M aju dari Lima Titik x f(x) Δf Δ2f Δ3f Δ4f 2 3 4 x0 f0 Δf0 Δ f0 Δ f0 Δ f0 2 3 4 x1 f1 Δf1 Δ f1 Δ f1 Δ f1 2 3 4 x2 f2 Δf2 Δ f2 Δ f2 Δ f2 2 3 x3 f3 Δf3 Δ f3 Δ f3 Δ4f3 2 3 4 x4 f4 Δf4 Δ f4 Δ f4 Δ f4 Lambang Δ menyatakan selisih maju. Arti setiap simbol di dalam tabel adalah : f 0 = f (x 0 ) = y0 f 1 = f (x1 ) = y1 ... f 4 = f (x 4 ) = y 4 Notasi : f p = f (x p ) Δf 0 = f1 − f 0 Δf 1 = f 2 − f 1
29
... Δf 3 = f 4 − f 3 Notasi : Δf p = f p +1 − f p Δ2 f 0 = Δf 1 − Δf 0 Δ2 f 1 = Δf 2 − Δf 1 Δ2 f 2 = Δf 3 − Δf 2
Notasi : Δ2 f p = Δf p +1 − Δf p Δ3 f 0 = Δ2 f1 − Δ2 f 0 Δ3 f1 = Δ2 f 2 − Δ2 f 1 Notasi : Δ3 f p = Δ2 f p +1 − Δ2 f p Bentuk umum : Δn +1 f p = Δn f p ,
2.7.2
n = 0, 1, 2, ...
(23)
Penurunan Rumus Polinom Newton-Gregory Maju Sekarang kita mengembangkan polinom Newton-Gregory maju yang didasarkan
pada tabel selisih maju. f [x1 , x 0 ]
=
f (x1 ) − f (x 0 ) x1 − x 0
=
Δ f (x 0 ) h
30
f [x 2 , x 1 , x0 ]
=
Δf0 1!h
=
f [x 2 , x1 ] − f [x1 , x0 ] x2 − x0
(24)
f (x 2 ) − f ( x1 ) f (x1 ) − f (x 0 ) − x 2 − x1 x1 − x 0 = x2 − x0 Δ f1 − Δ f 0 h = 2h
Δ2 f 0 = 2!h 2
(25)
Bentuk umum : f [x n ,..., x1 , x0 ] =
Δn f (x 0 ) Δn f 0 = n!h n n!h n
(26)
Dengan demikian polinom Newton untuk data berjarak sama dapat ditulis sebagai : p n (x )
=
f ( x0 ) + ( x − x0 ) f [x1 , x 0 ] + ( x − x0 )(x − x1 ) f ( x2 , x1 , x 0 ) + ... +
(x − x0 )(x − x1 )...(x − x n −1 ) f [x n , x n−1 ,..., x1 , x 0 ] =
Δf 0 Δ2 f 0 f 0 + (x − x 0 ) + (x − x 0 )( x − x1 ) + ... + 1!h 2!h 2
(x − x0 )(x − x1 )...(x − x n −1 )
Δn f 0 n! hn
(27)
Persamaan (27) ini dinamakan polinom Newton-Gregory maju. Persamaan ini dapat juga ditulis sebagai relasi rekursif :
31
p n (x ) = pn −1 ( x ) + ( x − x0 )(x − x1 )...(x − x n−1 )
Δn f 0 n!h n
(28)
Jika titik-titik berjarak sama dinyatakan sebagai x i = x0 + ih ,
i = 0,1,2,..., n
dan nilai x yang diinterpolasikan adalah x = x0 + sh , s ∈ R maka, persamaan (27) dapat juga ditulis dalam parameter s sebagai p n (x ) = f 0 +
sh s(s − 1)h 2 s(s − 1)(s − 2)...(s − n + 1)h n Δf0 + Δ f 0 + ... + Δ f0 2 1!h 2!h n! hn 2
n
yang menghasilkan s s(s − 1) 2 s(s − 1)(s − 2)...(s − n + 1) n p n (x ) = f 0 + Δf 0 + Δ f 0 + ... + Δ f0 1! 2! n!
(29)
atau dalam bentuk relasi rekursif, (i) Rekurens : p n (x ) = pn −1 ( x ) +
s(s − 1)(s − 2 )...(s − n + 1) n Δ f0 n!
(ii) Basis : p 0 (x ) = f (x0 )
(30)
Seringkali persamaan (29) dinyatakan dalam bentuk binomial : n ⎛s⎞ p n (x ) = ∑ ⎜⎜ ⎟⎟Δk f 0 k =0 ⎝ k ⎠
(31)
yang dalam hal ini, ⎛ s⎞ ⎜⎜ 0 ⎟⎟ = 1, ⎝ ⎠ dan k!= 1.2.....k
⎛ s ⎞ s(s − 1)(s − 2 )...(s − k + 1) ⎜⎜ k ⎟⎟ = k! ⎝ ⎠
(s > 0, bilangan bulat positif)
32
Tahap pembentukan polinom Newton-Gregory maju untuk titik-titik berjarak sama dapat dituliskan sebagai berikut : p 0 (x ) = f 0 p1 ( x ) = p 0 (x ) +
s 1!
p 2 ( x ) = p1 ( x ) +
s(s − 1) 2 Δ f0 2!
s Δf 0 = f 0 + Δf 0 1!
s s(s − 1) 2 = f0 + Δf0 + Δ f0 1! 2! p 3 ( x ) = p 2 (x ) +
s(s − 1)(s − 2) 3 Δ f0 2!
s s(s − 1) 2 s(s − 1)(s − 2) 3 Δ f0 + Δ f0 = f0 + Δf0 + 1! 2! 2!
2.7.3
Taksiran Galat Interpolasi Newton-Gregory Maju Seperti halnya pada polinom Newton, taksiran galat interpolasi Newton-Gregory
dapat dihitung dengan menghampiri turunan fungsi ke (n + 1) dengan nilai pada tabel selisih. Tinjau kembali polinom Newton-Gregory M aju : p n (x ) = pn −1 ( x ) + ( x − x0 )(x − x1 )...(x − x n−1 ) Naikkan suku Δn f 0 (x − x0 )(x − x1 )...(x − x n −1 ) n n! h dari n menjadi n + 1 :
Δn f 0 n!h n
33
(x − x0 )(x − x1 )...(x − x n −1 )( x − x n )
Δn +1 f 0 (n + 1)!h n +1
Bentuk terakhir ini bersesuaian dengan rumus galat interpolasi E ( x ) = (x − x0 )(x − x1 )...(x − x n ) (n+1)
Sehingga, f f
(n +1)
(t )
f (t ) (n + 1) n+1
(t) dapat dihampiri dengan
Δn +1 f 0 h n +1
(32)
Jadi, taksiran galat dalam menginterpolasi f(x) dengan polinom Newton-Gregory maju adalah E ( x ) = (x − x0 )(x − x1 )...(x − x n )
f
n +1
f0 h (n + 1)! n +1
(33)
atau dalam bentuk lain, Δn +1 f 0 E ( x ) = s(s − 1)(s − 2)...(s − n) (n + 1)!
(34)
dengan s = (x − x 0 ) / h
2.7.4
Manfaat Tabel Selisih Maju Pada contoh-contoh perhitungan yang diberikan sebelum ini, derajat polinom
interpolasi ditentukan pada soal. Bila polinom interpolasi derajat n yang diinginkan, maka jumlah titik yang dibutuhkan harus (n + 1) buah. Sebaliknya, bila diberikan (n+1) titik, maka kita dapat menginterpolasi titik-titik itu dengan polinom derajat satu (jadi hanya dua titik yang diperlukan), polinom derajat dua (tiga titik), polinom derajat tiga (empat titik) dan maksimal polinom derajat n (jadi semua titik yang dipakai). Timbul
34
pertanyaan, dengan polinom derajat berapakah sekumpulan titik data sebaiknya diinterpolasi agar memberikan galat interpolasi yang minimum? misalkan kita membentuk tabel selisih untuk fungsi f(x)=x,f(x)=x2 dan f(x)=x3 pada titik-titik x yang berjarak sama yaitu : (i) Tabel 2.6 Selisih fungsi f(x)=x x 0 h 2h 3h
f(x)=x 0 h 2h 3h
Δf h h h
Δ2f 0 0
Δ3f 0
(ii) Tabel 2.7 Selisih fungsi f(x)=x2 x 0 h 2h 3h 4h
2
f(x)=x 0 2 h 2 4h 2 9h 2 16h
Δf h2 2 3h 2 5h 2 7h
Δ2f 2h2 2 2h 2 2h
Δ3f 0 0
(iii) Tabel 2.8 Selisih fungsi f(x)=x3 x 0 h 2h 3h 4h
f(x)=x2 0 3 h 3 8h 3 27h 3 64h
Δf H3 3 7h 3 19h 3 37h
Δ2f 6h3 3 6h
h adalah jarak antara nilai-nilai x. Selisih orde pertama adalah
Δ3f 0
35
Δf ( x )
=
f ( x + h ) − f (x )
=
{a
=
an (x + h) − x n + a n −1 (x + h)
0
}{
+ a1 ( x + h ) + ...an (x + h )n − a0 + a1 x + ... + an x n
[
n
]
[
n −1
}
]
− x n −1 + suku-suku derajat ≤ n-2
[(
]
)
an −1 x n −1 + (n − 1)hx n −2 + (n − 2 )x n −3 h 2 + ... + h n −1 − x n −1 + suku-suku derajat ≤ n-2 =
nhan x n −1 + suku-suku derajat ≤ n-2
Jadi kesimpulan kita benar. Apakah kegunaan kesimpulan ini? Bila di dalam tabel selisih ditemukan Δ k bernilai (hampir) konstan (≠ 0) maka polinom yang tepat mengiterpolasi titik-titik adalah polinom berderajat k. Pada contoh tabel (iii) diatas : Δ 3 konstan, jadi titik – titiknya tepat diinterpolasi dengan polinom derajat tiga (sama dengan fungsi aslinya, f(x) = x3) Bagaimana jika tidak terdapat Δ yang bernilai tetap ? M isalnya diberikan tabel selisih di bawah ini : Tabel 2.9 Δ yang tidak bernilai tetap x 0.10 0.20 0.30 0.40 0.50 0.60
f(x)=1/x 10.00 5.00 3.33 2.50 2.00 1.67
Δf -5.00 -1.67 -0.83 -0.50 -0.33
2
Δf 3.33 0.83 0.33 0.17
Δ3f -2.49 -0.51 -0.16
Δ4f 1.98 0.35
Pada tabel selisih di atas, tidak ada Δ k yang mendekati nilai tetap. Jadi f(x) = 1/x tidak tepat dihampiri dengan polinom derajat 1, 2, 3, atau 4 di dalam selang [0.10, 0.60]. Tetapi jika selang datanya diperkecil dengan penngambilan h yang lebih kecil dan digunakan empat angka benar sebagai berikut :
36
Tabel 2.10 Δ yang bernilai tetap x 0.25 0.26 0.27 0.28 0.29 0.30
f(x)=1/x 4.000 3.846 3.704 3.571 3.448 3.333
Δf -0.154 -0.142 -0.133 -0.123 -0.115
2
Δf 0.012 0.009 0.010 0.008
Δ3f -0.003 0.001 -0.002
M aka dari tabel ini ditemukan Δ 2 mendekati nilai tetap yaitu sekitar 0.010. karena itu f(x) = 1/x dapat dihampiri sebanyak empat angka bena dengan polinom kuadratik di dalam selang [0.25, 0.30].
