UJI KOMPUTASI ALGORITME MODIFIKASI NEWTONLIKE UNTUK MENYELESAIKAN OPTIMASI NONLINEAR TANPA KENDALA
RAHMAH LAILA
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2016
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa tesis berjudul Uji Komputasi Algoritme Modifikasi Newton-Like untuk Menyelesaikan Optimasi Nonlinear Tanpa Kendala adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor.
Bogor, September 2016
Rahmah Laila NIM G651140211
RINGKASAN RAHMAH LAILA. Uji Komputasi Algoritme Modifikasi Newton-Like untuk Menyelesaikan Optimasi Nonlinear Tanpa Kendala. Dibimbing oleh BIB PARUHUM SILALAHI dan IMAS SUKAESIH SITANGGANG. Dalam perkembangan kehidupan saat ini banyak dijumpai kegiatan yang berhubungan dengan optimasi dan diimplementasikan dalam berbagai bidang seperti ekonomi, pertanian, keteknikan, sains, industri dan berbagai bidang lainnya. Pengoptimasian yang baik akan mempertimbangkan metode yang digunakan serta pemrograman dalam aspek komputasi. Komputasi dapat didefinisikan sebagai cara untuk menemukan pemecahan permasalahan dari data input dengan menggunakan suatu algoritme. Sebuah algoritme yang baik dapat meminimumkan kebutuhan waktu dan ruang dalam menyelesaikan sebuah fungsi. Banyak metode pengoptimasian yang bentuknya sederhana akan tetapi membutuhkan waktu yang lama dalam proses komputasinya. Oleh karena itu diperlukan suatu perbaikan dari metode pengoptimasian baik dari segi kompleksitas ruang maupun waktunya. Salah satu metode terbaik untuk menentukan solusi dari persamaan nonlinear menggunakan metode Newton. Tujuan dari penelitian ini adalah mengkombinasikan algoritme Newton, Invers Newton dengan algoritme Halley untuk melihat efesiensi algoritme serta membandingkan hasil uji komputasi dari modifikasi algoritme baru dengan metode Newton untuk menyelesaikan persamaan optimasi nonlinear tanpa kendala. Hasil penelitian menunjukkan bahwa dengan menggunakan kombinasi algoritme metode Newton, Invers Newton dan Halley (NIH) dan kombinasi algoritme metode Newton, Harmonik, Invers dan Secant (NHIS), kedua algoritme dapat digunakan untuk mencari solusi akar dari fungsi-fungsi nonlinear yang diberikan. Berdasarkan hasil percobaan uji komputasi, secara umum metode NIH mempunyai kinerja yang lebih unggul dari aspek jumlah iterasi dan running time, akan tetapi tidak untuk metode NHIS dari aspek running time. Namun untuk beberapa kasus fungsi metode NIH memperoleh nilai running time yang besar. Hal ini disebabkan karena dalam proses iterasi metode NIH melakukan evaluasi fungsi sebanyak tiga kali dan NHIS sebanyak empat kali evaluasi fungsi, sehingga waktu proses penyelesaian masalahnya meningkat. Walaupun begitu, secara umum dapat disimpulkan bahwa rata-rata running time metode NIH dapat menyeimbangi bahkan lebih kecil dari metode N, H, NH dan IH yang secara garis besar mempunyai running time yang kecil. Dari segi akurasi atau ketepatan, metode NIH dan metode NHIS dalam mencari solusi akar khususnya pada fungsifungsi nonlinear yang cukup sulit memperoleh hasil yang lebih mendekati pada nilai akar yang diinginkan. Metode Halley yang digunakan untuk kombinasi algoritme NIH sangat berpengaruh terhadap besarnya banyak iterasi dan running time. Dengan menggunakan kombinasi metode Halley, maka iterasi yang diperoleh dalam pencarian solusi akar sebuah fungsi menjadi lebih sedikit, hanya saja metode Halley memuat turunan kedua dari sehingga membutuhkan cost yang lebih banyak untuk eksekusi program. Kata kunci: Invers newton, iterasi, metode Halley, metode Newton, optimasi, running time.
SUMMARY RAHMAH LAILA. Computational Test Modified Newton-Like Algorithm for Solving Non-Linear Optimization Without Constraint. Supervised by BIB PARUHUM SILALAHI and IMAS SUKAESIH SITANGGANG. In the present life, activities related to optimization are often found and implemented in various fields such as an economy, agriculture, engineering, science, industry and other areas. A good optimization will consider the methods employed as well as programming in computational aspects. Computation can be defined as a way to find a solution the problem of input data with an algorithm. A suitable algorithm can minimize the needs of time and space to complete a function. Many methods of optimizing that are simple but requires a long time in computation process. Therefore, we need an improvement of methods of optimization in terms space and time complexity. One of the best methods to determine the solution of nonlinear equations is Newton's method. The purpose of this study to combine the Newton algorithm, the Inverse Newton with Halley algorithm to see the efficiency of algorithms and computational comparing test results from modification of the new algorithm with Newton's method to solve nonlinear equations optimization without constraints. These results showed that using a combination of algorithmic methods of Newton, Inverse Newton and Halley (NIH) and the combination algorithm method of Newton, Harmonic, Inverse and secant (NHIS), can be used to find solutions root of nonlinear functions are given. Based on the test results of computational experiments, the general method of NIH has a superior performance concerning the number of iterations and running time. But, for some cases of a function of NIH and obtained the increased value of running time. This is because the process of iterative NIH method to evaluate the three times of function and NHIS method to evaluate the three times of function so that the solution of processing time the problem increases. However, in generally it can be concluded that the average of running time NIH method be able to balance out the even smaller than N,H, NH and IH methods that have a short of running time value. Concerning accuracy or precision, NIH methods and NHIS methods in finding a solution to the root especially nonlinear functions are quite difficult to obtain a closer result of desirable value. Halley method is used for a combination of very influential on many iterations and the amount of running time. By using a combination of Halley methods, then iterations obtained in search of the roots of a function solutions becoming fewer, but the Halley method containing of the second derivative of f thus requiring more cost for program execution. Keywords: Halley method, Invers Newton, optimization, running time.
iteration,
Newton
method,
© Hak Cipta Milik IPB, Tahun 2016 Hak Cipta Dilindungi Undang-Undang Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumbernya. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah; dan pengutipan tersebut tidak merugikan kepentingan IPB Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis ini dalam bentuk apa pun tanpa izin IPB
UJI KOMPUTASI ALGORITME MODIFIKASI NEWTONLIKE UNTUK MENYELESAIKAN OPTIMASI NONLINEAR TANPA KENDALA
RAHMAH LAILA
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Program Studi Ilmu Komputer
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2016
Penguji Luar Komisi pada Ujian Tesis: Dr Eng Wisnu Ananta Kusuma ST MT
PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala rahmat dan karunia-Nya sehingga penulis berhasil menyelesaikan tugas akhir ini. Tugas akhir ini disusun sebagai laporan penelitian yang telah dilakukan penulis sejak bulan januari 2016 dengan judul Uji Komputasi Algoritme Modifikasi Newton-Like untuk Menyelesaikan Optimasi Nonlinear Tanpa Kendala Alhamdulillah atas bimbingan dan petunjuk dari Allah Subhana wa ta'ala serta bimbingan dari semua pihak, penyusunan tugas akhir ini dapat diselesaikan. Tugas akhir ini tidak mungkin dapat diselesaikan tanpa adanya bantuan dari berbagai pihak. Oleh karena itu, penulis ingin mengucapkan terimakasih dan penghargaan yang setinggi-tingginya kepada: 1.
2.
3. 4.
5.
Ayah, Ibu serta adik-adik yang selalu mendoakan, memberi nasihat, kasih sayang, semangat, dan dukungan sehingga penelitian ini bisa diselesaikan dengan baik. Bapak Dr Ir Bib Paruhum Silalahi, MKom dan Ibu Dr Imas Sukaesih Sitanggang, SSi MKom selaku dosen pembimbing I dan II yang selalu bersedia membantu, memberi saran, masukan dan ide-ide dalam penelitian ini. Bapak Dr Eng Wisnu Ananta Kusuma ST MT selaku dosen penguji atas kesediannya sebagai penguji pada tugas akhir. Teman-teman mahasiswa Magister Ilmu Komputer angkatan 2014 yang dua tahun ini telah bersedia berbagi ilmunya selama masa perkuliahan dan pelaksanaan penelitian. Departemen Ilmu Komputer IPB, staf dan dosen yang telah banyak membantu selama masa perkuliahan hingga penelitian. Semoga tesis ini dapat bermanfaat.
Bogor, September 2016 Rahmah Laila
DAFTAR ISI DAFTAR TABEL
vi
DAFTAR GAMBAR
vi
DAFTAR LAMPIRAN
vi
1 PENDAHULUAN Latar Belakang Perumusan Masalah Tujuan Penelitian Ruang Lingkup Penelitian Manfaat Penelitian
1 1 2 3 3 3
2 TINJAUAN PUSTAKA Algoritme Optimasi Matematik Deret Konvergen dan Deret Divergen Metode Harmonik Newton Metode Secant Metode Iterasi Newton Metode Iterasi Newton Invers Secant (NIS) Metode Iterasi Jain Metode Halley Metode Iterasi Newton Halley (NH) Metode Iterasi Invers Halley (IH) Iterasi
3 3 4 4 4 4 5 6 6 7 7 7 8
3 METODE Tempat dan Waktu Penelitian Perangkat Penelitian Tahapan Penelitian
8 8 8 8
4 HASIL DAN PEMBAHASAN 10 Kombinasi dan Formulasi Metode Newton, Invers Newton dengan Metode Halley 11 Kombinasi dan Formulasi Metode Newton, Harmonik, Invers dan Metode Secant 12 Pembuatan Algoritme 13 Implementasi Algoritme 14 Pengujian Komputasi 15 5 SIMPULAN DAN SARAN Simpulan Saran
23 23 23
DAFTAR PUSTAKA
24
LAMPIRAN
26
RIWAYAT HIDUP
41
DAFTAR TABEL 1 Perbandingan jumlah iterasi masing-masing metode untuk toleransi 16 2 Perbandingan running time masing-masing metode untuk toleransi 18 3 Perbandingan rata-rata running time masing-masing metode untuk tiga kali uji komputasi 4 Perbandingan nilai akar masing-masing metode untuk toleransi -
18 20
DAFTAR GAMBAR 1 2 3 4 5 6 7 8
Interpretasi metode Newton Tahapan penelitian metode NIH Tahapan Penelitian metode NHIS Perbandingan banyak iterasi dan running time (a) dengan dan (b) dengan toleransi toleransi Perbandingan banyak iterasi dan running time (a) dengan toleransi dan (b) dengan toleransi Perbandingan banyak iterasi dan running time (a) dengan toleransi dan (b) dengan toleransi Perbandingan banyak iterasi dan running time (a) dengan toleransi dan (b) dengan toleransi Perbandingan banyak iterasi dan running time dengan toleransi
6 9 10 20 20 21 21 21
DAFTAR LAMPIRAN 1 Sintaks dari setiap metode menggunakan program Matlab 2 Perbandingan jumlah iterasi masing-masing metode untuk toleransi
27 33
3 Perbandingan running time masing-masing metode untuk toleransi 34 4 Perbandingan nilai akar untuk masing-masing metode dengan toleransi -
5 Perbandingan selisih nilai akar sebenarnya dan akar pendekatan untuk masing-masing metode dengan toleransi 6 Perbandingan jumlah iterasi untuk masing-masing metode dengan tiga kali uji komputasi 7 Perbandingan running time untuk masing-masing metode dengan tiga kali uji komputasi 8 Perbandingan jumlah iterasi dan running time masing-masing untuk toleransi -
35 36 37 38 39
1 PENDAHULUAN Latar Belakang Dalam perkembangan kehidupan saat ini banyak dijumpai kegiatan yang berhubungan dengan optimasi. Tujuan dari optimasi untuk memaksimumkan atau meminimumkan fungsi yang diberikan. Pengoptimasian biasa dijumpai atau diimplementasikan dalam berbagai bidang seperti ekonomi, pertanian, keteknikan, sains, industri dan berbagai bidang lainnya. Penggunaan optimasi tersebut tidak terlepas dari ilmu eksakta yang erat dengan rumus dan perhitungan yang dapat dijadikan sebagai alat untuk menyederhanakan pembahasan masalah. Menurut fungsinya optimasi terbagi menjadi dua yaitu optimasi linear dan optimasi nonlinear. Adapun dari segi bentuknya optimasi dibedakan menjadi optimasi berkendala dan optimasi tanpa kendala. Optimasi berkendala adalah optimasi yang memperhatikan faktor-faktor pembatas dalam penyelesaian optimasi. Adapun optimasi tanpa kendala adalah optimasi yang tidak dipengaruhi oleh faktor-faktor pembatas pada proses perhitungan sampai optimasi tercapai. Kegiatan optimasi erat kaitannya dengan mencari nilai terbaik dari suatu fungsi. Akan tetapi, pengoptimasian yang baik akan mempertimbangkan metode digunakan serta pemrograman dalam aspek komputasi. Komputasi erat kaitannya dengan kompleksitas waktu. Komputasi dapat didefinisikan sebagai cara untuk menemukan pemecahan permasalahan dari data input dengan menggunakan suatu algoritme. Sebuah algoritme dikatakan baik jika dapat meminimumkan kebutuhan waktu dan ruang dalam menyelesaikan sebuah fungsi. Pada kenyataannya banyak metode pengoptimasian yang bentuknya sederhana akan tetapi membutuhkan waktu yang lama dalam proses komputasinya. Dua aspek penting dalam merekonstruksi sebuah algoritme adalah orde kekonvergenan serta komputasi yang efesien (Sharma et al. 2011). Oleh karena itu diperlukan suatu perbaikan dari metode pengoptimasian baik dari segi kompleksitas ruang maupun waktunya. Metode optimasi pada umumnya dapat dilakukan secara analitik maupun numerik. Namun untuk kasus optimasi tanpa kendala khususnya dengan persamaan nonlinear, terdapat masalah persamaan nonlinear yang tidak dapat diselesaikan secara analitik. Dengan demikian, diperlukan teori khusus untuk memudahkan penyelesaian masalah tersebut. Salah satu teori yang biasa digunakan yaitu metode numerik. Metode numerik yang digunakan dalam masalah optimasi biasanya bersifat iteratif yang secara matematis dapat dibentuk suatu hubungan antar variabel atau parameter. Hal ini akan menjadi lebih baik jika pola hubungan yang dibentuk dapat dijabarkan dalam bentuk fungsi. Metode numerik dapat disajikan dalam bentuk algoritme-algoritme yang dapat dihitung secara cepat dan mudah. Ada suatu cara efektif yang dapat digunakan dalam menyelesaikan persamaan optimasi nonlinear, yaitu dengan metode Newton (Rochmad 2013). Tujuan utama optimasi ialah mencari nilai maksimum atau minimum sebuah persamaan. Akan tetapi, dalam pencarian nilai maksimum dan minimum persamaan nonlinear diperlukan turunan pertama fungsi yang
2
membuat fungsi tersebut menjadi nol ( ) (Homeier 2005). Dalam hal ini nilai ialah akar dari fungsi . Metode Newton merupakan salah satu metode terbaik untuk menentukan solusi akar dari persamaan nonlinear (Sánchez 2009). Pada perkembangannya metode ini telah mengalami banyak kemajuan, tidak hanya mencari akar dari suatu fungsi, namun metode ini juga digunakan untuk mencari titik optimal dari suatu persamaan dalam optimasi nonlinear. Metode Newton merupakan satu dari teknik terbaik untuk menyelesaikan persamaan nonlinear dan meminimumkan fungsi. Metode ini sangat mudah untuk diimplementasikan dan sering konvergen dengan cepat menurut Kumar et al. (2013), bila iterasi dimulai cukup dekat dengan akar yang diinginkan. Beberapa peneliti mencari metode yang paling efektif dan efesien sehingga metode Newton banyak mengalami modifikasi, seperti yang telah di kembangkan oleh beberapa peneliti diantaranya Werakoon dan Fernando (2000). Mereka memodifikasi metode Newton menggunakan aturan trapesium sehingga menghasilkan metode Trapesium Newton yang memiliki orde kekonvergenan kubik di mana metode tersebut lebih baik dari metode Newton. Hasil dari metode WF telah memicu banyak penelitian terhadap metode Newton. Penelitian tersebut dilakukan untuk mendapatkan algoritme pencarian nilai akar fungsi nonlinear dan memungkinkan untuk meningkatkan orde kekonvergenannya kesuatu nilai. Peneliti berikutnya Frontini (2003) dan Ozban (2004) dengan mengaproksimasikan integral Newton menggunakan aturan midpoint yang hasilnya mendapatkan metode midpoint Newton, rata-rata Aritmatik Newton untuk metode Aritmatik Newton dan rata-rata Harmonik Newton untuk metode Harmonik Newton, seluruh metode ini juga menghasilkan orde kekonvergenan kubik yang sama dengan metode WF. Penelitian selanjutnya dilakukan oleh Homeier (2005) memodifikasi metode Newton dengan menggunakan fungsi Invers dan juga menghasilkan orde kekonvergenan kubik. Kemudian Noor (2006) memodifikasi metode Halley dengan konsep dasar metode Newton dan menghasilkan beberapa pengembangan baru dari metode Halley sehingga menghasilkan performa yang lebih baik. Berdasarkan penelitian-penelitian yang telah dilakukan, maka penelitian ini akan menggunakan metode Newton, Invers Newton yang dikombinasikan dengan metode Halley untuk memperoleh iterasi yang cepat namun konvergen mendekati nilai eksak. Modifikasi yang dilakukan diharapkan dapat memperkecil kompleksitas ruang dan waktu yang dibutuhkan algoritme serta dapat memperoleh solusi berupa nilai akar dari suatu fungsi optimasi. Perumusan Masalah Berdasarkan latar belakang yang telah dijabarkan maka rumusan masalah yang akan dikaji pada penelitian ini adalah : 1. Bagaimana mengkombinasi algoritme Newton, Invers Newton dengan algoritme Halley untuk melihat efesiensi algoritme ? 2. Bagaimana perbandingan hasil uji komputasi dari modifikasi algoritme baru dengan metode Newton untuk menyelesaikan fungsi optimasi nonlinear tanpa kendala ?
3
Tujuan Penelitian 1. 2.
Tujuan dari penelitian ini adalah : Mengkombinasikan algoritme Newton, Invers Newton dengan algoritme Halley untuk melihat efesiensi algoritme Membandingkan hasil uji komputasi dari modifikasi algoritme baru dengan metode Newton untuk menyelesaikan fungsi optimasi nonlinear tanpa kendala. Ruang Lingkup Penelitian
Ruang lingkup penelitian yang dilakukan meliputi: 1. Data uji komputasi yang digunakan merupakan data yang diperoleh dari penelitian sebelumnya oleh (Werakoon dan Fernando 2000) yaitu sembilan fungsi nonlinear 2. Fungsi nonlinear yang digunakan pada uji komputasi mewakili fungsifungsi yang sulit seperti fungsi polinomial, logaritmik, trigonometri, dan eksponensial. Manfaat Penelitian Kombinasi metode yang diperoleh dari penelitian dapat dijadikan sebagai referensi terbaru untuk membantu penyelesaian masalah-masalah khususnya mencari akar dari fungsi yang cukup sulit seperti fungsi nonlinear dan fungsi derivative (turunan).
2 TINJAUAN PUSTAKA Algoritme Secara umum algoritme adalah prosedur komputasi yang terdefenisi secara baik dengan mengambil beberapa nilai, atau himpunan dari nilai-nilai yang dijadikan sebagai input dan menghasilkan beberapa nilai atau himpunan nilai-nilai sebagai output. Dengan demikian sebuah algoritme adalah urutan langkah yang mentransformasikan input ke output (Cormen et al. 2009). Sebuah algoritme dapat dijadikan sebagai alat untuk memecahkan masalah komputasi yang lebih spesifik. Secara umum terdapat hubungan antara input dan output yang diinginkan. Algoritme dapat menggambarkan prosedur komputasi khusus untuk mencapai hubungan input dan output (Cormen et al. 2009). Optimasi Matematik Optimasi matematika sering disebut dengan nonlinear programing, pemrograman matematika atau optimasi numerik. Istilah optimasi matematik dapat dijelaskan sebagai suatu ilmu untuk menentukan solusi terbaik secara
4
matematik pada suatu permasalahan. Pada umumnya optimasi matematik menurut (Snyman 2005) adalah proses dari : (i) Formulasi (ii) Solusi dari masalah optimasi dibatasi dari bentuk umum matematik : Meminimumkan ( ) harus memenuhi kendala : (1) di mana ( ) ( ) dan ( ) adalah fungsi skalar. pada komponen disebut dengan desain variabel, ( ) adalah fungsi tujuan, ( ) disebut fungsi kendala dan ( ) disebut dengan fungsi kendala kesetaraan. Defenisi Orde Konvergensi Misalkan adalah akar dari persamaan nonlinear dan adalah barisan yang konvergen ke , defenisikan nilai error sebagai berikut (Chasnov 2012): (2) Untuk besar memiliki hubungan penaksiran : | | | | (3) Nilai disebut orde konvergensi, dengan adalah konstanta positif. Deret Konvergen dan Deret Divergen Deret konvergen yaitu suatu deret di mana jumlah ( ) dari n suku dari deret tersebut cenderung mendekati suatu nilai tertentu, yaitu ketika . Jika ( ) tidak mendekati satu nilai tertentu ketika , maka deret ini disebut dengan deret divergen (Stroud 2003). Metode Harmonik Newton Metode Harmonik Newton adalah varian dari metode Newton. Pada penelitian Ozban (2004) mengaproksimasi integral dengan aturan titik tengah (midpoint) yang dianalogkan dengan rata-rata Harmonik, maka menghasilkan metode Harmonik Newton. Untuk menghitung metode Harmonik Newton menggunakan persamaan 4 berikut (Ozban 2004) : ̅
( )
( (
)
( )
) ( )
(4)
di mana adalah tebakan awal fungsi, ( ) adalah fungsi awal yang diberikan, ( ) adalah turunan pertama fungsi, dan ( ) menyatakan turunan pertama fungsi dengan adalah nilai tebakan awal berikutnya. Metode Secant Metode Secant merupakan metode terbaik kedua setelah metode Newton yang digunakan untuk memperoleh konvergensi yang cepat (Chavnov 2012). Untuk menghitung metode newton menggunakan persamaan 5 (Chavnov 2012) sebagai berikut :
5
(
) ( (
)
(
) )
(5)
di mana merupakan nilai tebakan awal fungsi. Karena metode Secant adalah salah satu metode iteratif yang mana proses perhitungannya menyatakan nilai yang menghasilkan urutan atau rentetan solusi, maka diperoleh dari solusi perhitungan sebelumnya. Sedangkan ( ) menyatakan fungsi dengan nilai substitusi dan ( ) menyatakan fungsi dengan nilai substitusi . Metode Iterasi Newton Metode iterasi Newton adalah salah satu metode yang dipandang sebagai metode untuk mencari akar dari suatu fungsi. Metode ini banyak dikembangkan untuk memecahkan masalah optimasi multivariabel. Metode iterasi Newton diinterpretasikan sebagai pendekatan kuadratik dari suatu fungsi tujuan . di mana merupakan Misalkan untuk mencari akan-akar persamaan ( ) penyelesaian dari persamaan tersebut. Pada solusi eksak nilai fungsi yang dapat dinyatakan sebagai ( ) dan nilai dari turunan fungsi pertama adalah ( ). Nilai merupakan solusi yang diperoleh pada iterasi ke-k. Andaikan adalah . berubah dari menjadi maka perubahan Selanjutnya, metode Newton dapat ditinjau dari tiga suku pertama dari suatu deret Taylor disekitar pada iterasi k, yaitu (Luenberger dan Ye 2008) : ( ) ( ) ) ( )( ( )( ) (6) Syarat perlu untuk mencari titik optimum dari pers (6) adalah ( ) ( ) ( )( ) (7) sehingga (Luenberger dan Ye 2008) : ( ) (8) ( ) Pada setiap iterasi k, titik optimum dari pendekatan kuadratik menjadi titik yang akan digunakan untuk membuat fungsi pendekatan kuadratik yang selanjutnya. Jadi nilai dibuat sama dengan dalam persamaan (8) untuk mendapatkan rumus iterasi Newton sebagai berikut (Luenberger dan Ye 2008) : ( ) (7) ( ) Proses ini diilustrasikan pada Gambar 1 (Luenberger dan Ye 2008) :
Gambar 1 Interpretasi metode Newton
6
Metode Iterasi Newton Invers Secant (NIS) Kombinasi metode NIS diperoleh dari penelitian Jain (2013), yang mana sebelumnya modifikasi metode Invers Newton diperoleh dari penelitian Homeier (2005), kemudian Jain mengkombinasikan dengan metode Secant. Berikut adalah modifikasi metode Newton Invers Secant (Jain 2013) : (
̅ ̅
(
)
(
) )
(9)
(
̅ ( ̅ )
(
)
(
)
(10)
)
( ̅ )
( ̅ )
(11)
Tahapan perhitungan dengan Metode NIS adalah, menghitung metode Newton terlebih dahulu. Kemudian hasil perhitungan dari metode Newton persamaan 9 berupa titik disubstitusikan pada metode Invers persamaan 10. Selanjutnya hasil perhitungan dari persamaan 10 berupa titik ̅ menjadi inputan dengan mensubstitusikan nilai ̅ pada metode Secant persamaan 11. Metode Iterasi Jain Jain (2013) pada penelitiannya menggunakan kombinasi metode Secant dengan modifikasi metode Newton yang telah dikembangkan oleh Weerakoon dan Fernando (2000) yaitu aturan trapesium dan Homeier (2005) yaitu fungsi Invers. Jain mendapatkan formula yang disebut dengan metode secant trapesium Newton dan metode secant Invers Newton. Adapun bentuk dari hasil penurunan metode secant trapesium Newton (Jain 2013): ̅ ( ̅ ) ̅ (12) ( ̅ ) (
di mana
(
̅ dengan
(
)
(
)
(
)
)
)
(
(13)
)
(14)
Berikutnya dengan cara yang sama untuk menurunkan metode secant Invers Newton dimulai dengan modifikasi metode Newton yang telah dikembangkan oleh Homeier (2005) yang selanjutnya dikombinasikan dengan bentuk alternatif metode Secant. Adapun bentuk dari hasil penurunan metode secant Invers Newton (Jain 2013): (
)
(
)
(15)
dengan ̅
(
)
(
(
)
(
)
)
dengan cara yang sama, pada metode (12) di mana (Jain 2013) : ̅ ( ̅ ) ̅ ( ) ̅
(
)
(16)
(17)
7
Metode Halley Metode Halley adalah metode yang memilki algoritme orde ketiga. Algoritme tersebut konvergen kubik, yang mana jumlah signifikan digit akhirnya sejauh tiga kali lipat untuk masing-masing iterasi. Metode halley tidak hanya melakukan turunan pertama dari orde ketiga iterasi fungsi, tetapi terus berlanjut sampai turunan kedua (Scavo dan Thoo 1994). Seperti yang kita ketahui bahwa metode Newton merupakan metode iteratif untuk menghitung pendekatan dari akar (root) dengan menggunakan persamaan 18 (Scavo dan Thoo 1994) : (
)
(
)
,
(18)
berdasarkan persamaan 18 yang diturunkan menggunakan deret taylor polynomial tingkat pertama sebagai berikut (Scavo dan Thoo 1994) : (
)
( ) ( ) ( )( ) ( ) (19) maka di peroleh rumus metode Halley dengan menggunakan turunan dari deret taylor polynomial tingkat dua seperti pada persamaan 20 berikut (Scavo dan Thoo 1994) ( ̅ ) ( ̅ ) ̅ (20) ( ( ̅ )) ( ̅ ) ( ̅ ) Metode Iterasi Newton Halley (NH) Beberapa penelitian tentang modifikasi maupun kombinasi metode iteratif telah banyak dilakukan. Diantaranya adalah penelitian Noor et al (2006) yang mengembangkan salah satu dari metode iteratif yaitu metode Halley menggunakan metode Newton. Berikut adalah kombinasi metode Newton Halley (Noor et al. 2006) : (
)
(
)
̅
(21) ( ̅ ) ( ̅ )
( ( ̅ ))
( ̅ )
( ̅ )
(22)
Tahapan perhitungan dengan Metode NH adalah, menghitung metode Newton terlebih dahulu. Kemudian hasil perhitungan dari metode Newton persamaan 21 berupa titik akan menjadi inputan pada metode Halley persamaan 22. Dengan mengganti nilai ̅ pada persamaan 22 dan mensubstitusikan nilai ̅ . Metode Iterasi Invers Halley (IH) Metode Halley adalah metode konvergen kubik untuk akar sederhana dan memerlukan turunan kedua dari fungsi yang terkadang memerlukkan cost yang besar untuk memperolehnya (Putra et al. 2012). Bedasarkan hal tersebut maka kombinasi dari metode IH dengan menghitung metode Invers pada persamaan 23 (Homeier 2005) : ̅
(
)
(
(
)
(
)
)
(23)
8
dan metode Halley pada persamaan 24 (Noor et al. 2006) : ( ̅ ) ( ̅ ) ̅ ( ( ̅ )) ( ̅ ) ( ̅ )
(24)
Tahapan perhitungan dengan Metode IH adalah, menghitung metode Invers terlebih dahulu. Kemudian hasil perhitungan dari metode Invers persamaan 23 berupa titik ̅ akan menjadi inputan pada metode Halley persamaan 24, yaitu dengan mensubstitusikan nilai ̅ . Iterasi Iterasi adalah sifat tertentu dari algoritme atau program computer di mana suatu urutan atau lebih dari langkah algoritmik yang dilakukan pada loop program. Iterasi merupakan proses yang dilakukan secara berulang dalam menyelesaikan permasalahan numerik (Chapman 2008).
3 METODE Tempat dan Waktu Penelitian Lokasi penelitian bertempat di Lab CI (computer intelligence) Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengethuan Alam (FMIPA), Institut Pertanian Bogor (IPB). Penelitian ini dilaksanakan pada bulan Januari 2016 – Mei 2016. Perangkat Penelitian Penelitian ini dilakukan dengan menggunakan perangkat keras dan perangkat lunak sebagai berikut : Perangkat keras berupa komputer personal dengan spesifikasi sebagai berikut : Processor Intel (R) Pentium (R) CPU
[email protected] RAM 2 GB Mouse dan keyboard Perangkat lunak yang digunakan adalah sebagai berikut : Sistem operasi windows 7 Ultimate 32-bit Microsoft Excel 2013 untuk pegolahan data Matlab R2010b ver. 7.11.0 untuk pengujian komputasi Tahapan Penelitian Langkah awal yang dilakukan pada penelitian ini melalui kajian literatur. Selanjutnya akan mengkombinasikan serta menformulasikan metode Newton, Invers Newton dengan metode Halley. Kemudian membuat algoritme dari metode yang telah diusulkan. Penelitian dilanjutkan dengan melakukan implementasi algoritme yang telah dibuat program komputer. Kemudian tahap pengujian komputasi dilakukan untuk membandingkan metode yang diusulkan
9
dengan metode Newton tanpa modifikasi. Tahapan penelitian metode kombinasi metode Newton Invers Halley (NIH) dapat dilihat pada Gambar 2. Mulai
Studi literatur
Kombinasi dan formulasi metode Newton, invers Newton dengan metode Halley
Selesai
Hasil formulasi
Pengujian Komputasi
Pembuatan algoritme Newton,invers Newton dan metode Halley
Implementasi algoritme
Gambar 2 Tahapan penelitian metode NIH Studi Literatur Pada tahap ini peneliti mengumpulkan semua bahan berupa buku dan jurnal yang berhubungan dengan metode Newton dan metode Halley. Kombinasi dan Formulasi Metode Newton, Invers Newton dengan Metode Halley Pada tahap ini dikombinasikan metode Newton, Invers Newton dengan metode Halley. Dalam proses ini akan dicoba kombinasi metode yang sejenis dan masih dalam satu kategori metode iteratif sehingga metode tersebut dapat menyelesaikan suatu masalah yang diberikan berupa pencarian titik untuk solusi sebuah fungsi. Setelah diperoleh hasil kombinasi metode Newton, Invers Newton dengan metode Halley kemudian metode-metode tersebut akan diformulasikan sehingga dapat diketahui proses evaluasi fungsi dalam satu kali iterasi. Proses formulasi metode yaitu dengan mensubstitusikan hasil perhitungan satu formula ke formula berikutnya dalam setiap satu kali terasi. Pembuatan Algoritme Pada tahap ini dibuat algoritme berdasarkan hasil dari kombinasi metode yang diusulkan. Tahapan ini dilakukan dengan menyesuaikan langkah-langkah iterasi pada metode yang diusulkan dengan algoritme yang dibuat. Implementasi Algoritme Hasil analisis yang diperoleh kemudian diimplementasikan menggunakan sebuah aplikasi Matlab. Hasil implementasi kemudian digunakan untuk mempermudah tahap pengujian komputasi. Pengujian Komputasi Pada tahap ini akan dilakukan uji komputasi untuk membandingkan kemampuan metode yang diusulkan dengan metode Newton tanpa modifikasi dengan menggunakan beberapa contoh fungsi nonlinear tanpa kendala dari aspek jumlah iterasi. Hasil uji komputasi ini juga digunakan untuk melihat waktu tempuh (running time) yang dibutuhkan algoritme untuk menyelesaikan beberapa fungsi yang telah diberikan. Berikut adalah persamaan yang digunakan untuk
10
data uji komputasi dengan dan Fernando 2000) : ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (
adalah root dari masing-masing fungsi (Weerakoon
( ) ( )
( ) ( )
)
Tahapan penelitian metode NHIS sama dengan metode NIH, yaitu mengkombinasikan serta menformulasikan metode Newton, Harmonik, Invers Newton dan Secant. Kemudian membuat algoritme dari metode yang telah diusulkan. Penelitian dilanjutkan dengan melakukan implementasi algoritme yang telah dibuat program komputer. Kemudian tahap pengujian komputasi dilakukan untuk membandingkan metode yang diusulkan dengan metode Newton tanpa modifikasi menggunakan fungsi-fungsi nonlinear berdasarkan penelitian Werakoon dan Fernando (2000). Tahapan penelitian metode kombinasi metode Newton Harmonik Invers Secant (NHIS) dapat dilihat pada Gambar 3.
Mulai
Kombinasi dan formulasi metode Newton, Harmonik, invers, Secant
Selesai
Hasil formulasi
Pembuatan algoritme Newton, Harmonik, invers, Secant
Pengujian Komputasi
Implementasi algoritme
Gambar 3 Tahapan penelitian metode NHIS
4 HASIL DAN PEMBAHASAN Kombinasi dan Formulasi Metode Newton, Invers Newton dengan Metode Halley Kombinasi metode yang digunakan pada penelitian ini adalah metode Newton, metode Invers Newton dan metode Halley yang mana ketiga metode tersebut mempunyai karateristik sama yaitu tergolong dalam metode iteratif. Metode Newton merupakan metode pencarian akar yang penerapannya memerlukan satu titik tebakan awal . Pemberian tebakan awal ini merupakan kriteria dari suatu metode iteratif. Metode Newton juga tidak memerlukan cost yang besar dalam pencarian akar fungsi, sehingga pada proses kombinasi formula metode Newton diletakan pada langkah pertama. Secara umum formula
11
metode Newton untuk mencari nilai akar sebuah fungsi adalah seperti pada persamaan 25 (Luenberger dan Ye 2008). ( ) (25) ( )
dengan adalah titik tebakan awal, ( ) menyatakan fungsi dengan substitusi nilai titik tebakan awal, dan ( ) menyatakan turunan pertama fungsi dengan substitusi nilai titik tebakan awal. Setelah ditentukan metode awal, maka tahap selanjutnya yaitu dengan menambahkan formula metode Invers Newton yang berada pada langkah kedua dalam proses pencarian akar fungsi. Metode Invers Newton yang dikembangkan oleh (Homeier 2005) merupakan pengembangan dari metode Newton dengan menggunakan fungsi Invers. Penggunaan metode Invers Newton pada langkah kedua menghasilkan jumlah iterasi yang lebih sedikit dalam pencarian akar suatu fungsi berdasarkan penelitian (Homeier 2005). Selanjutnya hasil perhitungan dari persamaan 25 berupa titik digunakan sebagai nilai yang disubstitusikan untuk menemukan nilai akar pada langkah kedua menggunakan formula Invers Newton pada persamaan 26 (Homeier 2005). ( ) ̅ ( ( ) ) (26) ( ) dengan ( ) menyatakan turunan pertama fungsi ( ) dengan dari hasil perhitungan langkah pertama pada persamaan 25. Metode Halley merupakan salah satu metode iteratif dengan kekonvergenan tiga. Artinya, setiap iterasi mendapatkan digit angka yang tepat kira-kira sebanyak tiga. Formula metode Halley memuat turunan kedua sehingga membutuhkan cost dan time yang cukup banyak dalam proses perhitungan. Oleh karena itu, metode ini diletakkan pada langkah ketiga untuk mencari solusi pendekatan dari sebuah fungsi yang diberikan. Bentuk umum dari formula metode Halley adalah sebagai berikut (Noor et al. 2006) ( ̅ ) ( ̅ ) ̅ (27) ̅ ( ( )) ( ̅ ) ( ̅ ) dengan mengganti setiap nilai pada formula metode Halley dengan nilai ̅ dari hasil pencarian akar sebelumnya, maka ( ̅ ) menyatakan sebuah fungsi dengan substitusi nilai ̅ , ( ̅ ) menyatakan fungsi turunan pertama dengan substitusi nilai ̅ , dan ( ̅ ) menyatakan fungsi turunan kedua dengan substitusi nilai ̅ . Perhitungan ini dilakukan untuk setiap proses iterasi dengan tiga formula metode yang berbeda. Kombinasi dan Formulasi Metode Newton, Harmonik, Invers dan Metode Secant Kombinasi metode yang digunakan berikut ini adalah metode Newton, metode Harmonik, Invers dan metode Secant, yang mana keempat metode tersebut mempunyai karateristik sama yaitu tergolong dalam metode iteratif. Metode Newton adalah prosedur untuk menemukan akar dari suatu persamaan yang paling dikenal. Metode ini telah banyak digunakan untuk mencari solusi dari masalah yang cukup sulit seperti persamaan nonolinear, persamaan diferensial, dan nonlinear integral (Atkinson 1988). Metode ini tidak selalu baik dalam pemecahan masalah, namun sering digunakan karena kesederhanaannya
12
dan kecepatan konvergensi dalam memecahkan masalah nonlinear (Atkinson 1988). Metode Newton penerapannya memerlukan satu titik tebakan awal . Pemberian tebakan awal ini merupakan kriteria dari suatu metode iteratif. Metode Newton juga tidak memerlukan cost yang besar dalam pencarian akar fungsi, sehingga pada proses kombinasi formula metode Newton diletakan pada langkah pertama. Secara umum formula metode Newton untuk mencari nilai akar sebuah fungsi seperti pada persamaan 28 (Luenberger dan Ye 2008): ( ) (28) ( ) dengan adalah titik tebakan awal, ( ) menyatakan fungsi dengan substitusi nilai titik tebakan awal, dan ( ) menyatakan turunan pertama fungsi dengan substitusi nilai titik tebakan awal. Tahap selanjutnya yaitu dengan menambahkan formula metode Harmonik Newton yang berada pada langkah kedua dalam proses pencarian akar fungsi. Metode Harmonik Newton yang dikembangkan oleh Ozban (2004) merupakan varian dari metode Newton dengan menggunakan pendekatan integral dengan aturan trapesium. Kemudian hasil perhitungan dari persamaan 28 berupa titik disubstitusikan pada persamaan 29 untuk menemukan nilai akar pada langkah kedua menggunakan formula Harmonik Newton (Putra 2013): ̅
( )
( (
)
( )
(29)
) ( )
dengan ( ) menyatakan turunan pertama fungsi ( ) di mana adalah hasil perhitungan langkah pertama pada persamaan 28. Langkah selanjutnya yaitu dengan menambahkan formula metode Invers Newton yang berada pada langkah ketiga dalam proses pencarian akar fungsi. Setelah dilakukan perhitungan metode Harmonik Newton, kemudian hasil perhitungan dari persamaan 29 berupa titik ̅ digunakan sebagai nilai yang disubstitusikan pada persamaan 30 untuk menemukan nilai akar pada langkah ketiga menggunakan formula Invers Newton (Homeier 2005): ( ) ( ( ) ) (30) ( ̅ ) dengan ( ̅ ) menyatakan turunan pertama fungsi ( ). Nilai ̅ adalah nilai yang disubstitusi dari hasil perhitungan langkah kedua metode Harmonik Newton pada persamaan 29. Setelah menghitung formula metode Invers Newton, maka langkah keempat yaitu menghitung metode Secant. Metode Secant merupakan salah satu metode iteratif yang memiliki orde kekonvergenan linear (Putra 2013). Metode ini diletakkan pada langkah keempat untuk mencari solusi pendekatan dari sebuah fungsi yang diberikan. Bentuk umum dari formula metode Secant adalah sebagai berikut (Chavnov 2012) : (
) (
(
)
(
) )
(31)
dengan merupakan titik tebakan awal, kemudian mengganti setiap nilai pada formula metode Secant dengan nilai dari hasil perhitungan sebelumnya persamaan 30, maka ( ) menyatakan sebuah fungsi dengan substitusi nilai . Perhitungan diatas dilakukan untuk setiap proses iterasi dengan empat formula metode yang berbeda.
13
Pembuatan Algoritme Hasil kombinasi dan fomulasi metode selanjutnya digunakan untuk membuat algoritme yang mana setiap langkah penyelesaian untuk mengeksekusi sebuah fungsi disesuaikan dengan langkah-langkah formulasi metode. Adapun algoritme NIH dan Algoritme NHIS dituliskan dalam tahap-tahap sebagai berikut: Algoritme NIH (Newton Invers Halley) Langkah 1. Diberikan fungsi awal ( ) Langkah 2. Diberikan titik tebakan awal
dan batas toleransi
Langkah 3. Diberikan batas maksimum iterasi (
Langkah 4. Hitung Hitung ̅
(
Hitung
)
(
) )
̅
(
(
)
) ( ) ( ̅ ) ( ̅ )
( ( ̅ ))
( ̅ )
( ̅ )
Langkah 5. Hitung atau iterasi mencapai titik maksimum, kembali ke Langkah 6.Jika langkah 4 Langkah terpenting dalam proses kombinasi metode NIH berada pada langkah 4 yaitu penentuan urutan formula untuk mengeksekusi sebuah fungsi nonlinear yang diberikan. Urutan pertama ditempati oleh formula metode Newton yang memiliki cost paling rendah. Hasil perhitungan dari metode Newton berupa sebuah titik digunakan sebagai input dalam proses formula metode Invers Newton. Kemudian urutan terakhir menggunakan formula metode Halley yang mana proses inputan titiknya diperoleh dari hasil perhitungan formula metode Invers Newton sehingga akan diperoleh titik yang baru. Proses ini akan terus berlangsung sampai kriteria berhenti terpenuhi. Meskipun secara teoritis metode-metode yang digunakan dapat terbukti konvergen, tetapi dalam prakteknya tidak dapat secara efektif konvergen untuk semua penyelesaian fungsi. Hal ini tergantung pada nilai tebakan awal yang diberikan, jika tebakan awal yang diberikan terlalu jauh dari akar sebenarnya maka hasil yang diperoleh tidak terpenuhi atau hasilnya akan divergen. Berikut adalah tahap-tahap dari algoritme metode NHIS : Algoritme NHIS (Newton Harmonik Invers Secant) Langkah 1. Diberikan fungsi awal ( ) Langkah 2. Diberikan titik tebakan awal dan batas toleransi Langkah 3. Diberikan batas maksimum iterasi Langkah 4. Hitung Hitung ̅ Hitung
(
)
( (
) )
( (
(
)
)
(
) (
)
(
(
)
)
)
( ̅ )
14
Hitung
(
) ( (
)
(
) )
Langkah 5. Hitung Langkah 6.Jika atau iterasi mencapai titik maksimum, kembali ke langkah 4 Langkah terpenting dalam proses kombinasi metode NHIS berada pada langkah 4 yaitu penentuan urutan formula untuk mengeksekusi sebuah fungsi nonlinear yang diberikan. Urutan pertama ditempati oleh formula metode Newton yang memiliki cost paling rendah. Hasil perhitungan dari metode Newton berupa sebuah titik yang digunakan sebagai input dalam proses formula metode Harmonik Newton. Urutan berikutnya yaitu melakukan proses perhitungan menggunakan metode Invers Newton dengan inputan dari hasil perhitungan metode Harmonik. Kemudian proses perhitungan terakhir menggunakan formula metode Secant yang mana proses inputan titiknya diperoleh dari hasil perhitungan formula metode Invers Newton sehingga akan diperoleh titik yang baru. Proses ini akan terus berlangsung sampai kriteria berhenti terpenuhi. Pada algoritme metode Newton Invers Halley (NIH) dan metode Newton Harmonik Invers Secant (NHIS) memerlukan sembarang nilai tebakan awal yaitu . Selanjutnya metode ini memerlukan batas toleransi sebesar yang digunakan untuk pemberhentian dari proses iterasi. Pembatasan ini dilakukan untuk menentukan tingkat ketelitian dari solusi yang didapatkan. Semakin kecil tolerensi yang diberikan maka solusi dari permasalahan akan semakin mendekati ke nilai yang sebenarnya. Pada dasarnya untuk menentukan solusi numerik mempunyai kriteria pemberhentian adalah sama untuk semua metode. Salah satu kriteria untuk pembatasan proses iterasi program komputasi atau uji konvergesi adalah selisih dua nilai atau titik terakhir yang disimbolkan dengan | | selain itu, dapat menggunakan nilai fungsi yaitu | ( )| (Sharma 2011). Ketika salah satu kriteria terpenuhi maka proses iterasi komputasi akan berhenti. Implementasi Algoritme Dari hasil pembuatan algoritme sebelumnya, algoritme tersebut diimplementasikan kedalam sebuah program. Hal ini dilakukan untuk mempermudah proses uji komputasinya. Hasil dari kedua implementasi algoritme tersebut kemudian dibandingkan algoritme mana yang lebih baik dalam hal ketepatan mencari solusi sebuah fungsi. 1. Implementasi algoritme NIH Implementasi dengan algortime NIH pada program diawali dengan mendefinisikan inputan untuk fungsi awal. Dalam formula metode Newton dan Invers memuat turunan pertama fungsi serta metode Halley memuat turunan kedua fungsi. Maka pada implementasi program perlu didefinisikan turunan pertama dan turunan kedua ketika fungsi diinputkan. Setelah pendefinisian turunan fungsi, maka dilakukan pendefenisian terhadap fungsi dengan substitusi nilai untuk masing-masing variabel yang ada pada turunan pertama dan turunan kedua fungsi. Selanjutnya mendefinisikan titik tebakan awal, besar toleransi dan maksimum iterasi. Kemudian tahap berikutnya
15
yaitu memasukkan formula metode Newton, Invers dan Halley pada program. Ketiga metode tersebut yang menghitung proses pencarian akar dari fungsi yang diinputkan pada program. Akar yang diperoleh dari hasil perhitungan metode NIH tersebut menjadi solusi akhir yang diperoleh saat eksekusi program. Tahap terakhir dari implementasi algoritme NIH adalah menghitung selisih dari nilai akar terakhir dan nilai akar sebelumnya yang dijadikan sebagai syarat pemberhentian iterasi pada saat eksekusi program. Jika selisih nilai akar yang diperoleh kurang dari toleransi yang diberikan, maka proses eksekusi program akan berhenti. Sebaliknya jika tidak memenuhi kriteria pemberhentian, maka proses eksekusi program akan terus berjalan. Untuk implementasi lengkap algoritme NIH pada program dapat dilihat di Lampiran 1. 2.
Implementasi Algoritme NHIS Secara umum, langkah-langkah implementasi algoritme NHIS sama dengan metode NHIS. Perbedaannya hanya pada implementasi program untuk turunan fungsi dan proses implementasi formula metode NHIS. Pada metode Newton, Harmonik, Invers dan Secant tidak memuat turunan kedua fungsi, sehingga tidak perlu mendefinisikan turunan kedua fungsi. Setelah pendefinisian turunan fungsi pertama, maka dilakukan pendefinisian terhadap fungsi dengan substitusi nilai untuk masing-masing variabel yang ada pada turunan fungsi dalam hal ini hanya fungsi dengan turunan pertama. Tahap berikutnya yaitu memasukkan formula metode Newton, Harmonik, Invers dan Secant pada program. Ketiga metode tersebut yang menghitung proses pencarian solusi dari fungsi yang diinputkan pada program dan menghasilkan sebuah akar. Akar yang diperoleh dari hasil perhitungan metode NHIS tersebut menjadi solusi akhir yang diperoleh saat eksekusi program. Tahap terakhir dari implementasi algoritme NHIS adalah menghitung selisih dari nilai akar terakhir dan nilai akar sebelumnya yang dijadikan sebagai syarat pemberhentian iterasi pada saat eksekusi program. Jika selisih nilai akar yang diperoleh kurang dari toleransi yang diberikan, maka proses eksekusi program akan berhenti. Sebaliknya jika tidak memenuhi kriteria pemberhentian, maka proses eksekusi program akan terus berjalan. Untuk implementasi lengkap algoritme NHIS pada program dapat dilihat di Lampiran 1. Pengujian Komputasi
Pada bagian ini pengujian komputasi dilakukan dengan cara membandingkan hasil numerik dari setiap metode yang telah dijelaskan sebelumnya dengan tujuan untuk melihat kelebihan dan kekurangan dari masingmasing metode. Adapun beberapa metode yaitu, Newton, NIS (Newton Invers Secant), Halley, NH (Newton Halley), IH (Invers Halley), NHIS (Newton harmonik Invers secant), NIH (Newton Invers Halley). Uji komputasi dilakukan untuk kasus fungsi nonlinear dengan akar tunggal. Untuk masing-masing fungsi nonlinear pada uji komputasi ini memiliki nilai tebakan awal yang berbeda-beda. dengan selanjutnya dengan ; Fungsi dengan ; dengan dengan ; dengan
16
; dengan ; dengan ; dengan . Kemudian untuk toleransi yang digunakan sebesar dan toleransi . Adapun perbandingan jumlah iterasi dari masing-masing kombinasi metode untuk toleransi ditunjukkan pada Tabel 1. Tabel 1 Perbandingan jumlah iterasi masing-masing metode untuk toleransi
( )
Total
Jumlah iterasi H NH IH 7 74 8 4 3 3 4 3 3 53 25 24 5 3 3 5 4 3 2 2 2 4 4 3 44 3 2 4 3 2 5 4 3 4 4 3 4 4 3 4 3 3 5 4 3 7 5 4 5 4 4
-0.5 1 2 -0.3 1 3 2 3 1 1.7 -0.3 3.5 2.5 1.5 -2 5 3.5
N 130 4 4 53 5 5 2 5 3 4 5 6 5 5 7 8 11
NIS 14* 2* 3 39 3 3 3 3 2* 3 3 4 3 3 4 15 6
NHIS 12 3 3 4 3 5 3 4 2 3 3 4 3 3 3 14 4
NIH
3.25
7
4
4
4
4
3
4
269
99
237
90
79
79
69
7 3 3 11 3 3 2 3 3 3 3 3 3 3 4 4 4
* nilai epsilon belum terpenuhi sehingga proses iterasi berhenti
Berdasarkan hasil uji komputasi dari aspek banyak iterasi menggunakan Sembilan jenis fungsi nonlinear yang berbeda pada Tabel 1, beberapa metode yang menunjukkan bahwa kombinasi metode yang diusulkan yaitu formula metode NIH lebih unggul dibandingkan metode N, NIS, H, NH, IH dan NHIS dengan total jumlah terasi yang lebih sedikit sebanyak 69. Untuk beberapa kasus fungsi nonlinear pada metode NIS dan NHIS terdapat tanda bintang (*) pada iterasinya yaitu pada fungsi dengan tebakan awal dan , selanjutnya pada fungsi dengan tebakan awal . Hal ini menyatakan bahwa iterasi tersebut berhenti di titik itu disebabkan karena pada saat proses pencarian solusi terjadi kesalahan perhitungan atau nilai epsilonnya belum terpenuhi dalam proses komputasi. Sehingga iterasi berhenti dan untuk iterasi berikutnya tidak mendapatkan nilai input untuk proses penyelesaian. Selanjutnya jika metode NIH dibandingkan dengan kombinasi metode H, NH dan IH untuk beberapa kasus fungsi, banyak iterasi yang diperoleh tidak jauh berbeda nyata
17
namun kombinasi metode NIH bisa dikatakan masih lebih baik dari segi iterasinya. Titik awal dan toleransi juga berpengaruh pada banyak iterasi. Jika menggunakan titik awal atau tebakan awal yang cukup dekat dengan nilai akar, maka proses iterasi menjadi lebih cepat. Untuk besar toleransi yang diberikan juga berpengaruh terhadap jalannya proses komputasi. Jika kriteria | maka proses pemberhentian proses iterasi terpenuhi yaitu | komputasi akan berhenti (Sharma 2011). Pada penelitian ini juga dilakukan uji komputasi menggunakan toleransi . Perbandingan jumlah iterasi menggunakan toleransi untuk toleransi masing-masing metode disajikan pada Lampiran 2. Dari Lampiran 2, diketahui bahwa metode NIH memperoleh jumlah iterasi yang lebih sedikit sebanyak 58, disusul oleh metode NHIS sebanyak 77. Besar toleransi juga berpengaruh terhadap banyaknya jumlah iterasi. Jika dibandingkan antara toleransi dan toleransi berdasarkan aspek jumlah iterasi, maka jumlah iterasi dari metode N, NIS, H, NH, IH, NHIS, dan NIH yang diperoleh menggunakan toleransi lebih sedikit. Adapun yang dimaksud dengan iterasi pada kombinasi metode NIH dan NHIS adalah perhitungan sebanyak tiga kali pada metode NIH dan empat kali pada metode NHIS untuk memperoleh nilai akar pendekatan dari fungsi yang diberikan. Berdasarkan hasil uji komputasi dari aspek running time menggunakan pada tabel 2, dapat dilihat beberapa kombinasi metode untuk toleransi bahwa metode NIH memperoleh total nilai running time yang cukup besar yaitu (0.2671 ms) dibandingkan dengan metode NH (0.2307 ms) dan IH (0.2296 ms) pada saat eksekusi program. Hal ini terjadi karena dalam satu kali proses iterasi metode NIH melakukan tiga kali evaluasi fungsi sehingga running time pogram menjadi lebih besar daripada metode lainnya. Akan tetapi, jika dibandingkan jumlah nilai running time metode N (0.2748 ms), NIS (0.664 ms), H (0.3273 ms) dan NHIS (0.5492 ms), metode NIH memperoleh nilai running time yang lebih kecil yaitu (0.2671 ms). Dari tabel 2 juga dapat dilihat metode NIH dibandingkan metode NHIS memperoleh running time yang terbilang kecil. Untuk besar cost setiap kombinasi metode juga berpengaruh terhadap eksekusi running time. Semakin besar cost suatu formula metode, maka running time yang dihasilkan suatu kombinasi metode akan meningkat. Contohnya kombinasi metode NHIS yang memiliki running time terbesar jika dibandingkan dengan metode lainnya. Hal ini disebabkan karena metode NHIS melakukan empat kali evaluasi fungsi dalam satu kali iterasinya. Untuk membandingkan running time masing-masing metode juga menggunakan toleransi yang disajikan pada Lampiran 3. Dari Lampiran 3, dapat diketahui jumlah nilai running time metode NIH lebih besar yaitu (0.3265 ms) dibandingkan dengan metode N (0.2745 ms), NH (0.2773 ms) dan IH (0.2931 ms). Namun metode NIH memperoleh jumlah nilai running time yang lebih kecil dibandingkan metode H (0.3370 ms), NIS (1.6539 ms) dan NHIS (2.3912 ms). Tabel 2 menunjukkan perbandingan running time dari masingmasing kombinasi metode untuk toleransi .
18
Tabel 2 Perbandingan running time masing-masing metode untuk toleransi ( )
N -0.5 1 2 -0.3 1 3 2 3 1 1.7 -0.3 3.5 2.5 1.5 -2 5 3.5 3.25
Total
0.1204 0.0049 0.0049 0.0438 0.0063 0.0064 0.0031 0.0070 0.0013 0.0044 0.0053 0.0066 0.0055 0.0054 0.0108 0.0149 0.0146 0.0092 0.2748
NIS 0.1203 0.0463 0.0118 0.0674 0.0151 0.0120 0.1249 0.0141 0.0888 0.0088 0.0099 0.0135 0.0102 0.0104 0.0203 0.0522 0.0209 0.0171 0.6640
Running time (ms) IH H NH 0.0822 0.0280 0.0271 0.0072 0.0096 0.0063 0.0059 0.0100 0.0079 0.0705 0.0193 0.0563 0.0107 0.0110 0.0090 0.0108 0.0098 0.0090 0.0064 0.0073 0.0103 0.0122 0.0123 0.0101 0.0067 0.0062 0.0040 0.0087 0.0061 0.0059 0.0087 0.0089 0.0108 0.0089 0.0093 0.0061 0.0088 0.0093 0.0072 0.0074 0.0090 0.0078 0.0143 0.0144 0.0111 0.0246 0.0299 0.0129 0.0182 0.0137 0.0172 0.0151 0.0166 0.0106 0.3273 0.2307 0.2296
NHIS 0.0503 0.0185 0.0168 0.0220 0.0187 0.0423 0.0567 0.0283 0.0888 0.0088 0.0099 0.0213 0.0152 0.0158 0.0254 0.0667 0.0235 0.0202 0.5492
NIH 0.0280 0.0096 0.0100 0.0193 0.0107 0.0160 0.0117 0.0172 0.0088 0.0094 0.0128 0.0131 0.0090 0.0088 0.0208 0.0242 0.0207 0.0170 0.2671
Pada penelitian ini juga dilakukan uji komputasi sebanyak tiga kali untuk melihat rata-rata running time yang dihasilkan oleh masing-masing kombinasi metode. Berdasarkan Tabel 3 total rata-rata running time metode NIH lebih kecil dibandingkan dengan metode NIS (0.5016 ms), H (0.1749) dan NHIS (0.2645 ms). Apabila dibandingkan dengan metode N (0.1327 ms), NH (0.1303 ms) dan IH (0.1255 ms), total rata-rata running time metode NIH (0.1348 ms) masih lebih besar, akan tetapi dapat menyeimbangi ketiga metode tersebut. Kemudian total rata-rata running time untuk metode NHIS (0.2645 ms) lebih kecil dibandingkan metode NIS (0.5016 ms). Secara umum metode NHIS masih memperoleh nilai running time yang cukup besar dibandingkan metode N,H,NH,IH dan NIH. Hasil lengkap dari total rata-rata running time untuk semua metode disajikan pada Lampiran 7. Tabel 3 menunjukkan perbandingan rata-rata running time masing-masing metode untuk tiga kali uji komputasi. Tabel 3 Perbandingan rata-rata running time masing-masing metode untuk tiga kali uji komputasi ( ) -0.5 1 2
N 0.0575 0.0025 0.0024
rata-rata running time (ms) NIS H NH IH 0.0842 0.0507 0.0131 0.0132 0.0565 0.0035 0.0047 0.0038 0.0087 0.0032 0.0049 0.0044
NHIS 0.0281 0.0089 0.0083
NIH 0.0138 0.0046 0.0047
19
( ) -0.3 1 3 2 3 1 1.7 -0.3 3.5 2.5 1.5 -2 5 3.5 3.25 Total
N 0.0218 0.0031 0.0030 0.0019 0.0033 0.0008 0.0021 0.0025 0.0031 0.0026 0.0025 0.0052 0.0070 0.0069 0.0044 0.1327
NIS 0.0523 0.0110 0.0090 0.0843 0.0105 0.0598 0.0066 0.0074 0.0102 0.0077 0.0078 0.0151 0.0418 0.0160 0.0127 0.5016
rata-rata running time (ms) H NH IH 0.0396 0.0272 0.0312 0.0048 0.0054 0.0050 0.0053 0.0049 0.0049 0.0037 0.0040 0.0052 0.0056 0.0058 0.0052 0.0032 0.0031 0.0024 0.0040 0.0031 0.0031 0.0042 0.0043 0.0052 0.0043 0.0046 0.0036 0.0040 0.0045 0.0040 0.0035 0.0045 0.0042 0.0070 0.0071 0.0063 0.0119 0.0141 0.0089 0.0096 0.0075 0.0093 0.0069 0.0075 0.0058 0.1749 0.1303 0.1255
NHIS 0.0108 0.0093 0.0188 0.0220 0.0124 0.0312 0.0053 0.0060 0.0104 0.0076 0.0078 0.0123 0.0434 0.0119 0.0099 0.2645
NIH 0.0136 0.0053 0.0078 0.0061 0.0078 0.0043 0.0045 0.0062 0.0063 0.0043 0.0043 0.0103 0.0122 0.0102 0.0085 0.1348
Berdasarkan hasil uji komputasi pada Tabel 4 menunjukan bahwa hampir semua kombinasi metode yang dibandingkan menemukan nilai akar yang diharapkan dari semua fungsi yang diberikan. Selanjutnya nilai akar yang diperoleh dari hasil uji komputasi pada Tabel 4 menggunakan toleransi tidak terdapat perbedaan nyata jika dibandingkan dengan nilai akar sebesar yang diperoleh dari penelitian (Weerakoon dan Fernando 2000. Akan tetapi, pada dengan nilai akar sebesar berdasarkan (Werakoon dan Fernando 2000), terdapat perbedaan nilai akar dengan masing-masing metode N (3.4374), NIS (3.4374), H (3.4374), NH (3.4374) dan IH (3.4374). Sedangkan untuk metode NHIS (4.7667) dan metode NIH (4.6221) memperoleh nilai akar yang mendekati dengan nilai akar pada penelitian sebelumnya. Oleh karena itu dapat disimpulkan bahwa metode NHIS dan NIH merupakan metode yang lebih baik dalam hal pencarian solusi untuk fungsi-fungsi yang sulit seperti pada . Hal ini disebabkan karena metode NHIS dan NIH lebih banyak melakukan evaluasi fungsi dalam setiap satu kali iterasi. Di mana metode NHIS melakukan evaluasi fungsi sebanyak empat kali dan metode NIH melakukan tiga kali evaluasi fungsi. Jika dibandingan dari solusi yang diperoleh dari metode NHIS dan NIH, maka terlihat bahwa metode NHIS memperoleh nilai akar yang lebih mendekati dengan nilai akar pada penelitian Werakoon dan Fernando (2000). Bedasarkan nilai akar tersebut, maka dapat dikatakan bahwa ketelitian dari metode NHIS dan metode NIH untuk memperoleh solusi lebih baik jika dibandingkan dengan metode lainnya yang hanya melakukan satu kali atau dua kali evaluasi fungsi. Selanjutnya uji komputasi perbandingan nilai akar masing-masing metode untuk toleransi disajikan pada Lampiran 4. Dari Lampiran 4 dan Lampiran 5 dapat dilihat nilai akar dan selisih antara nilai akar yang diperoleh menggunakan formula metode N, NIS, H, NH, IH, NHIS dan NIH pada penelitian ini dengan nilai akar penelitian Werakoon dan Frontini (2000).
20
Adapun nilai akar dari
untuk semua titik untuk semua titik
,
,
untuk semua titik , untuk semua titik ,
untuk semua titik , untuk semua titik , untuk semua titik , untuk semua titik , untuk semua titik . Selisih nilai akar yang diperoleh dari hasil komputasi beberapa kombinasi formula metode tidak terlalu jauh berbeda untuk setiap fungsi menggunakan , bahkan untuk fungsi dan memperoleh nilai error 0. toleransi Akan tetapi, pada fungsi diperoleh nilai error yang cukup significant untuk metode NHIS dan metode NIH, yang mana nilai akar metode NHIS (4.76676506130314) dan NIH (4.62210416355283) lebih mendekati nilai akar pembanding yaitu . Hal ini disebabkan karena metode NHIS dan metode NIH melakukan evaluasi fungsi yang lebih banyak dibandingkan dengan metode lainnya. Sehingga dapat dikatakan bahwa ketelitian dari metode NHIS dan metode NIH untuk memperoleh solusi menggunakan lebih baik jika dibandingkan dengan metode N, NIS, H, NH dan toleransi IH. Tabel 4 menunjukkan nilai akar yang diperoleh dari hasil uji komputasi . masing-masing kombinasi metode untuk toleransi Tabel 4 Perbandingan nilai akar masing-masing metode untuk toleransi ( )
N 1.3652 1.3652 1.3652 1.3652 1.4044 1.4044
NIS 1.3652 1.3652 1.3652 1.3652 1.4044 1.4044
H 1.3652 1.3652 1.3652 1.3652 1.4044 1.4044
0.7391 0.7391 0.7391 2.0000 2.0000
0.7391 0.7391 0.7391 2.0000 2.0000
0.7391 0.7391 0.7391 2.0000 2.0000
1.5
2.1544
2.1544
-2
1.2076
5 3.5 3.25
-0.5 1 2 -0.3 1 3 2 3 1 1.7 -0.3 3.5 2.5
Nilai akar NH 1.3652 1.3652 1.3652 1.3652 1.4044 1.4044
IH 1.3652 1.3652 1.3652 1.3652 1.4044 1.4044
NHIS 1.3652 1.3652 1.3652 1.3652 1.4044 1.4044
NIH 1.3652 1.3652 1.3652 1.3652 1.4044 1.4044
0.7391 0.7391 0.7391 2.0000 2.0000
0.7391 0.7391 0.7391 2.0000 2.0000
0.7391 0.7391 0.7391 2.0000 2.0000
0.7391 0.7391 0.7391 2.0000 2.0000
2.1544
2.1544
2.1544
2.1544
2.1544
-1.2076
-1.2076
-1.2076
3.4374
3.4374
3.4374
3.4374
3.4374
4.7667
4.6221
3.0000 3.0000
3.0000 3.0000
3.0000 3.0000
3.0000 3.0000
3.0000 3.0000
3.0000 3.0000
3.0000 3.0000
-1.2076 -1.2076 -1.2076
21
Berdasarkan hasil uji komputasi yang dilakukan, dapat dilihat hubungan antara jumlah iterasi dan running time program yang dieksekusi. Gambar 2 sampai dengan Gambar 6 menunjukkan perbandingan running time dan jumlah iterasi dari masing-masing kombinasi metode yang mewakili satu fungsi nonlinear dan satu tebakan awal fungsi. NIS
0.0400
Running time (ms)
Running time (ms)
0.0500
0.0300 0.0200
NHIS
0.0100
NIH H IH N
0.0000 0
2
4
0.0450 0.0400 0.0350 0.0300 0.0250 0.0200 0.0150 0.0100 0.0050 0.0000
NHIS
NIH NIS IH NH
0
6
2
Jumlah iterasi
Running time (ms)
Running time (ms)
0.0250 0.0200 NIH NIS NH H IH
0.0100
N
0.0050 0.0000 2
(b) dengan
NHIS NIS
0.0800 0.0600 0.0400
NIH
0.0200
4
0
6
N
H NH
0.0000 0
20
NHIS NIS
Running time (ms)
Running time (ms)
(a) Gambar 5 Perbandingan banyak iterasi dan running time (a) toleransi dan (b) dengan toleransi
NIH
NH H
IH N
0
2
4
Jumlah iterasi
6
H 40
60
Jumlah iterasi
Jumlah iterasi
0.0160 0.0140 0.0120 0.0100 0.0080 0.0060 0.0040 0.0020 0.0000
6
0.1000
NHIS
0.0150
4
Jumlah iterasi
(a) Gambar 4 Perbandingan banyak iterasi dan running time (a) toleransi dan (b) dengan toleransi 0.0300
H N
0.0180 0.0160 0.0140 0.0120 0.0100 0.0080 0.0060 0.0040 0.0020 0.0000
(b) dengan
NHIS
NIH
NIS NH IH
H N
0
2
4
Jumlah iterasi
(a) (b) Gambar 6 Perbandingan banyak iterasi dan running time (a) dengan toleransi dan (b) dengan toleransi
6
22
NHIS
0.0250
Running time (ms)
Running time (ms)
0.0300 NIHNIS
0.0200 0.0150
NH H IH
0.0100
N
0.0050 0.0000 0
5
0.0800 0.0700 0.0600 0.0500 0.0400 0.0300 0.0200 0.0100 0.0000
10
NHIS NIS NH NIH H
0
10
Jumlah iterasi
20
Jumlah iterasi
(a)
(b)
Gambar 7 Perbandingan banyak iterasi dan running time (a) dan (b) dengan toleransi toleransi
Running time (ms)
N
IH
dengan
0.0250 NHIS NIH NH H
0.0200 0.0150
IH
0.0100
N
0.0050 0.0000 0
2
4
6
8
Jumlah iterasi
Gambar 8 Perbandingan banyak iterasi dan running time toleransi
dengan
Untuk toleransi berdasarkan Gambar 4 sampai dengan Gambar 8 menggunakan sembilan fungsi nonlinear yang berbeda dan hanya menggunakan satu nilai tebakan awal, dapat dilihat bahwa banyaknya iterasi tidak berbanding lurus terhadap jalannya running time. Semakin kecil jumlah iterasi maka tidak menjamin bahwa semakin kecil running time. Sebaliknya jika jumlah iterasi besar, tidak menjamin akan semakin besar pula running time. Namun ada beberapa hal yang dapat mempengaruhi besarnya iterasi yaitu kombinasi metode yang digunakan untuk menyelesaikan suatu fungsi dan tebakan awal fungsi serta jenis fungsi yang diselesaikan. Pada Gambar 4a menggunakan dengan dan Gambar 4b menggunakan dengan , terlihat bahwa jumlah iterasi metode Newton lebih banyak dibandingkan dengan metode NIH, namun dari segi running time metode Newton memperoleh running time yang lebih kecil dari pada metode NIH. Sedangkan metode NIH memperoleh iterasi lebih sedikit namun menghasilkan running time yang lebih besar. Pada fungsi sampai dengan dengan titik awal yang berbeda-beda untuk setiap fungsi menunjukkan bahwa metode NIH merupakan metode yang unggul dari segi banyak iterasi dibandingkan dengan metode N, NIS, H, NH, IH dan NHIS. Meskipun demikian, pada beberapa kasus fungsi tertentu running time metode NIH masih terbilang kecil, sebagai contoh ditunjukkan pada Gambar 4a menggunakan dengan
23
, 5b menggunakan dengan , 6a menggunakan dengan , 6b menggunakan dengan dan 7b menggunakan dengan . Kombinasi metode yang digunakan juga dapat mempengaruhi besarnya running time pada saat eksekusi program. Gambar lengkap perbandingan jumlah iterasi dan running time untuk toleransi disajikan pada Lampiran 8. Untuk beberapa kasus fungsi , dengan , nonlinear khususnya menggunakan fungsi dengan dengan , dengan , dengan , dengan , dengan , dengan dan dengan , dari grafik pada Lampiran 8 dapat disimpulkan bahwa metode NIH memperoleh nilai running time yang kecil dibandingkan dengan metode N,H,NH dan IH. Sedangkan metode NHIS berada pada posisi yang paling tinggi dari aspek running time dibandingkan dengan semua metode.
5 SIMPULAN DAN SARAN Simpulan Hasil penelitian menunjukkan bahwa dengan menggunakan kombinasi algoritme metode Newton, Invers Newton dan Halley (NIH) dan kombinasi algoritme metode Newton, Harmonik, Invers dan Secant (NHIS), kedua algoritme dapat digunakan untuk mencari solusi akar dari fungsi-fungsi nonlinear yang diberikan. Berdasarkan hasil percobaan uji komputasi, secara umum metode NIH mempunyai kinerja yang lebih unggul dari aspek jumlah iterasi dan running time, akan tetapi tidak untuk metode NHIS dari aspek running time. Namun untuk beberapa kasus fungsi metode NIH memperoleh nilai running time yang besar. Hal ini disebabkan karena dalam proses iterasi metode NIH melakukan evaluasi fungsi sebanyak tiga kali dan NHIS sebanyak empat kali evaluasi fungsi, sehingga waktu proses penyelesaian masalahnya meningkat. Walaupun begitu, secara umum dapat disimpulkan bahwa rata-rata running time metode NIH dapat menyeimbangi metode N, H, NH dan IH yang secara garis besar mempunyai running time yang kecil. Dari segi akurasi atau ketepatan, metode NIH dan metode NHIS dalam mencari solusi akar khususnya pada fungsi-fungsi yang cukup sulit memperoleh hasil yang lebih mendekati pada nilai akar yang diinginkan daripada metode lainnya. Metode Halley yang digunakan untuk kombinasi algoritme NIH sangat berpengaruh terhadap besarnya banyak iterasi dan running time. Dengan menggunakan kombinasi metode Halley, maka iterasi yang diperoleh dalam pencarian solusi akar sebuah fungsi menjadi lebih sedikit, hanya saja metode Halley memuat turunan kedua dari sehingga membutuhkan cost yang lebih banyak untuk eksekusi program. Saran Untuk penelitian selanjutnya, perlu dilakukan modifikasi pada metode Halley sebelum dikombinasikan dengan metode iterasi lainnya karena metode Halley masih memuat turunan kedua sehingga dapat mempengaruhi besarnya
24
running time saat eksekusi program. Perlu dilakukan analisis lebih lanjut tentang pencarian akar pada fungsi delapan serta uji komputasi dengan fungsi-fungsi nonlinear lain yang tingkatnya lebih sulit untuk melihat sejauh mana kinerja dari metode yang dikombinasikan.
DAFTAR PUSTAKA Atkinson KE. 1988. An Introduction to Numerical Analysis Second Edition. Canada : John Wiley & Sons, Inc. Chapman SJ. 2008. Matlab Programming for Engineers. 4th ed. Ontario (CA): Thomson Learning. Chavnov JR. 2012. Introduction to Numerical Method. The Hongkong University of Science and Technology, Hogkong : Creative Commons Attribution 3.0 Hong Kong. Cormen TH, Leiserson CE, Rivest RL, Stein C. 2009. Introduction to Algorithm Third Edition. London, England : The MIT Press. Frontini M, Sormain E. 2003. Some Variant of Newton’s Method with ThirdOrder Corvergence. Applied Mathematic and Computation 140: 419-426. Homeier HHH. 2005. On Newton-type Methods with Cubic Convergence. Journal of Computational and Applied Mathematic 176: 425-432. Jain D. 2013. Families of Newton-Like Methods with Fourth-Order Convergence. International Journal of Computer Mathematic 90(5): 1072-1082. Kumar M, Singh AK, Srivastava A. 2012. Various Newton-type Iterative Methods for Solving Nonlinear Equations. Journal of the Egyptian Mathematic Society 21,334-339. Luenberger DG, Ye Y. 2008. Linear and Nonlinear Programing Third Edition. Stanford, California: Springer. Noor MA, Khan WA, Hussain A. 2006. A new modified Halley method without second derivatives for nonlinear equation. Applied Mathematics and Computation. 189: 1268–1273 Ozban AY. 2004. Some New Variants of Newton’s Methods. Applied Mathematic Letters 17: 677-682. Putra S, Agusni, Restu YP. 2012. Kombinasi Metode Newton dengan Metode Iterasi yang Diturunkan Berdasarkan Kombinasi Linear Beberapa Kuadratur untuk Menyelesaikan Persamaan Nonlinear. Jurnal Sains, teknologi Industri. 10 (1): 85-89 Putra S. 2013. Modifikasi Sederhana dari Varian Metode Newton untuk Menyelesaikan Persamaan Nonlinear. Jurnal Ilmiah Edu Research. 2(2): 111-118 Rochmad . 2013. Aplikasi Metode Newton-Raphson untuk Menghampiri Solusi Persamaan Nonlinear. Jurnal MIPA 36(2): 193-200. Sánchez MG. 2009. Improving Order and Efficiency: Composition with a Modified Newton’s Method. Journal of Computational and Applied Mathematics 231, 592-597. Scavo TR, Thoo JB. 1994. American Mathematical Monthly
25
Sharma JR, Guha RK, Sharma R. 2011. Some Modified Newton’s Methods with Four-order Convergence. Advance in Applied science Research 2(1):240247. Skiena SS. 2008. The Algorithm Design Manual. Second Edition. Department of Computer Science. State University of New York at Stony Brook. New York, USA : Springer. Snyman JA. 2005. Practical Mathematical Optimization. An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms. University of Pretoria, South Africa : Springer. Stroud KA. 2003. Matematika Teknik. Edisi Kelima Jilid 2. Penerbit Elangga. Utami NNR, Widan IN, Asih ND. 2013. Perbandingan Solusi Sistem Persamaan Nonlinear Menggunakan Metode Newton-Raphson dan Metode Jacobian. Ejurnal Matematika 2(2): 11-17 Weerakoon S, Fernando T.G.I. 2000. A Variant of Newton’s Method With Accelerated Third-Order Convergence. Applied Mathematic Letters 13: 87-93.
LAMPIRAN
27
Lampiran 1 Sintaks dari setiap metode menggunakan program Matlab Sintaks untuk metode Newton clear; clc; syms x; fun = input ('input f(x): '); f=inline(fun); z=diff(f(x)); %turunan pertama fungsi f1=inline(z); x0=input('input nilai X:'); toleransi = input ('input nilai toleransi:'); max_iterasi = input ('input max iterasi:'); tic; %Mulai menghitung waktu eksekusi program y=x0; for i=1:max_iterasi %Metode Newton x_new= y - [f(y)/f1(y)]; n(i)= x_new; y = n(i); if i==1 else b = n(i)-n(i-1); c = abs(b); if (c <= toleransi) break; end end end %menghitung waktu eksekusi program selesai execution_time = toc
Sintaks untuk metode Newton Invers Secant (NIS) clear; clc; syms x; fun = input ('input f(x): '); f=inline(fun); z=diff(f(x));%turunan pertama fungsi f1=inline(z); x0=input('input nilai X:'); toleransi = input ('input nilai toleransi:'); max_iterasi = input ('input max iterasi:'); tic; %Mulai menghitung waktu eksekusi program
28
Lampiran 1 Lanjutan Sintaks dari setiap metode menggunakan program Matlab y=x0; for i=1:max_iterasi x_new= y - [f(y)/f1(y)]; x_inv=y-(f(y)./2) * ((1./f1(y)) + (1./f1(x_new))); x_sec=x_inv-[(x_inv-y)/(f(x_inv)-y))]*[f(x_inv)]; n(i)= x_sec; y = n(i); if i==1 else b = n(i)-n(i-1); c = abs(b); if (c <= toleransi) break; end end end %menghitung waktu eksekusi program selesai execution_time = toc
Sintaks untuk metode Halley (H) syms x; % fun = input ('input f(x): '); f=inline(fun); z=diff(f(x)); %turunan pertama fungsi k=diff(z); %turunan kedua fungsi f1=inline(z); f2=inline(k); x0=input('input nilai X:'); toleransi = input ('input nilai toleransi:'); max_iterasi = input ('input max iterasi:'); tic; %Mulai menghitung waktu eksekusi program y=x0; for i=1:max_iterasi x_hall=y-[2*f(y)*f1(y)]/[2*(f1(y))^2-2(y)*f(y)]; n(i)= x_hall; y = n(i); if i==1 else b = n(i)-n(i-1); c = abs(b);
29
Lampiran 1 Lanjutan Sintaks dari setiap metode menggunakan program Matlab if (c <= toleransi) break; end end end %menghitung waktu eksekusi program selesai execution_time = toc
Sintaks untuk metode Newton Halley (NH) syms x; % fun = input ('input f(x): '); f=inline(fun); z=diff(f(x)); %turunan pertama fungsi k=diff(z); %turunan kedua fungsi f1=inline(z); f2=inline(k); x0=input('input nilai X:'); toleransi = input ('input nilai toleransi:'); max_iterasi = input ('input max iterasi:'); tic; %Mulai menghitung waktu eksekusi program y=x0; for i=1:max_iterasi x_new= y - [f(y)/f1(y)]; x_hall=x_new2*f(x_new)*f1(x_new)]/[2*(f1(x_new))^2f2(x_new)*f(x_new)]; n(i)= x_hall; y = n(i); if i==1 else b = n(i)-n(i-1); c = abs(b); if (c <= toleransi) break; end end end %menghitung waktu eksekusi program selesai execution_time = toc
30
Lampiran 1 Lanjutan Sintaks dari setiap metode menggunakan program Matlab Sintaks untuk metode Invers Halley (IH) syms x; % fun = input ('input f(x): '); f=inline(fun); z=diff(f(x)); %turunan pertama fungsi k=diff(z); %turunan kedua fungsi f1=inline(z); f2=inline(k); x0=input('input nilai X0:'); toleransi = input ('input nilai toleransi:'); max_iterasi = input ('input max iterasi:'); tic; %Mulai menghitung waktu eksekusi program y=x0; for i=1:max_iterasi x_inv= y - ([f(y)]/2) * [(1/f1(y)) + (1/f1(y))]; x_hall=x_inv2*f(x_inv)*f1(x_inv)]/[2*(f1(x_inv))^2f2(x_inv)*f(x_inv)]; n(i)= x_hall; y = n(i); if i==1 else b = n(i)-n(i-1); c = abs(b); if (c <= toleransi) break; end end end %menghitung waktu eksekusi program selesai execution_time = toc
Sintaks untuk metode Newton Harmonik Invers Secant (NHIS) syms x; % fun = input ('input f(x): '); f=inline(fun); z=diff(f(x)); %turunan pertama fungsi f1=inline(z); x0=input('input nilai X:');
31
toleransi = input ('input nilai toleransi:'); max_iterasi = input ('input max iterasi:'); tic; %Mulai menghitung waktu eksekusi program y=x0; for i=1:max_iterasi x_new=y- [f(y)/f1(y)]; x_har=y-[f(y)*(f1(x_new)+f1(y))]/ [2*f1(x_new)*f1(y)]; x_inv=y([f(y)]/2) * [(1/f1(y)) (1/f1(x_har))]; x_sec=x_inv-[(x_inv-y)/(f(x_inv)-f(y))]* [f(x_inv)]; n(i)= x_sec; y = n(i); if i==1 else b = n(i)-n(i-1); c = abs(b); if (c <= toleransi) break; end end end %menghitung waktu eksekusi program selesai execution_time = toc
Sintaks untuk metode Newton Invers Halley (NIH) syms x; % fun = input ('input f(x): '); f=inline(fun); z=diff(f(x)); %turunan pertama fungsi k=diff(z); %turunan kedua fungsi f1=inline(z); f2=inline(k); x0=input('input nilai X0:'); toleransi = input ('input nilai toleransi:'); max_iterasi = input ('input max iterasi:');
+
32
Lampiran 1 Lanjutan Sintaks dari setiap metode menggunakan program Matlab tic; %Mulai menghitung waktu eksekusi program y=x0; for i=1:max_iterasi x_new= y - [f(y)/f1(y)]; x_inv=y-([f(y)]/2) * [(1/f1(y)) + (1/f1(x_new))]; x_hall=x_inv-2*f(x_inv)*f1(x_inv)]/ [2*(f1(x_inv))^2-f2(x_inv)*f(x_inv)];n(i)= x_hall; y = n(i); if i==1 else b = n(i)-n(i-1); c = abs(b); if (c <= toleransi) break; end end end %menghitung waktu eksekusi program selesai execution_time = toc
33
Lampiran 2 Perbandingan jumlah iterasi masing-masing metode untuk toleransi
( ) -0.5 1 2 -0.3 1 3 2 3 1 1.7 -0.3 3.5 2.5 1.5 -2 5 3.5 3.25 Total
Jumlah iterasi H NH IH 73 7 4 3 3 3 3 3 3
N 132 6 6
NIS 14* 2* 3*
NHIS 14* 2* 3*
54 7 7 2 7 5 5 6 8 7 7 9 10 13 9
div 4 4 div 3* 2* 3* 3* 4 3* 3* 5 15* 6* 4*
52 4 4 2 4 3 4 4 4 4 4 4 6 6 4
25 3 3 2 3 2 2 3 3 3 3 3 4 4 4
24 3 4 2 2 3 3 4 4 3 3 4 5 5 3
div 4 4 div 3* 2* 3* 3* 4 3* 3* 5 15* 6* 3*
300
78
188
80
82
77
NIH 6 2 2 1 0 2 3 2 3 2 2 3 3 2 2 3 4 4 3 5 8
34
Lampiran 3 Perbandingan running time masing-masing metode untuk toleransi
( )
Tol -0.5 1 2 -0.3 1 3 2 3 1 1.7 -0.3 3.5 2.5 1.5 -2 5 3.5 3.25
Total
N
NIS
0.0930 0.0071 0.0071 0.0387 0.0087 0.0087 0.0030 0.0092 0.0053 0.0026 0.0062 0.0086 0.0076 0.0073 0.0138 0.0188 0.0169 0.0119 0.2745
0.1261 0.1035 0.1304 0.1187 0.0161 0.0156 0.1296 0.0141 0.0974 0.1062 0.1006 0.0138 0.1026 0.1330 0.0308 0.1760 0.1212 0.1182 1.6539
Running time (ms) H NH IH 0.0743 0.0097 0.0097 0.0524 0.0132 0.0134 0.0060 0.0146 0.0070 0.0087 0.0111 0.0111 0.0112 0.0085 0.0179 0.0296 0.0207 0.0179 0.3370
0.0295 0.0144 0.0138 0.0455 0.0113 0.0146 0.0082 0.0098 0.0091 0.0092 0.0118 0.0121 0.0122 0.0089 0.0197 0.0207 0.0202 0.0063 0.2773
0.0143 0.0122 0.0057 0.0682 0.0069 0.0090 0.0095 0.0040 0.0050 0.0056 0.0149 0.0100 0.0550 0.0047 0.0141 0.0284 0.0174 0.0082 0.2931
NHIS
NIH
0.1469 0.1521 0.1498 0.1592 0.0197 0.0218 0.1850 0.1791 0.1438 0.1397 0.1393 0.0200 0.1446 0.1330 0.0332 0.2568 0.1726 0.1946 2.3912
0.0295 0.0144 0.0138 0.0455 0.0162 0.0159 0.0118 0.0136 0.0128 0.0135 0.0129 0.0131 0.0108 0.0130 0.0186 0.0282 0.0237 0.0192 0.3265
( )
3.43747174342176 3.00000000000000
3.00000000000000
5 3.5
3.25
3.5 2.5
2.15443469003188 -1.20764782713091
0.739085133215161
1.5 -2
0.2575302854397710
3 1
0.739085133215161 0.739085133215161 2.00000000000000 2.00000000000000
0.739085133215161
1.40449164821534 0.2575302854397710
3 2
1.7 -0.3
1.40449164821534 0.2575302854397710
1.36523001341409 1.40449164821534
-0.3 1
3.00000000000000
3.00000000000000 3.00000000000000
3.43747174342176
3.43747174342176
3.00000000000000
2.15443469003188 -1.20764782713091
2.15443469003188 -1.20764782713091
2.15443469003188 -1.20764782713091
3.00000000000000
3.00000000000000
3.43747174342176
2.00000000000000 2.00000000000000
2.00000000000000 2.00000000000000
0.739085133215161
0.2575302854397710
1.40449164821534 0.2575302854397710
1.36523001341409 1.40449164821534
1.36523001341409 1.36523001341409
NH 1.36523001341409
0.739085133215161 0.739085133215161
0.739085133215161
0.2575302854397710
1.40449164821534 0.2575302854397710
1.36523001341409 1.40449164821534
1.36523001341409 1.36523001341409
H 1.36523001341409
0.739085133215161 0.739085133215161
0.739085133215161 0.739085133215161 2.00000000000000 2.00000000000000
1.40449164821534
1.36523001341409 1.36523001341409
1.36523001341409 1.36523001341409
1 2
NIS 1.36523001341409
N 1.36523001341409
-0.5
Nilai akar
Lampiran 4 Perbandingan nilai akar untuk masing-masing metode dengan toleransi
3.00000000000000
3.00000000000000
3.43747174342176
2.15443469003188 -1.20764782713091
2.00000000000000 2.00000000000000
0.739085133215161 0.739085133215161
0.739085133215161
0.2575302854397710
1.40449164821534 0.2575302854397710
1.36523001341409 1.40449164821534
1.36523001341409 1.36523001341409
IH 1.36523001341409
3.00000000000000
4.76676506130314 3.00000000000000
2.15443469003188 -1.20764782713091
2.00000000000000 2.00000000000000
0.739085133215161 0.739085133215161
0.739085133215161
1.40449164821534 0.2575302854397710
1.40449164821534
1.36523001341409 1.36523001341409
NHIS 1.36523001341409
3.00000000000000
4.62210416355283 3.00000000000000
2.15443469003188 -1.20764782713091
2.00000000000000 2.00000000000000
0.739085133215161 0.739085133215161
0.739085133215161
0.2575302854397710
1.40449164821534 0.2575302854397710
1.36523001341409 1.40449164821534
1.36523001341409 1.36523001341409
NIH 1.36523001341409
35
( )
-0.5 1 2 -0.3 1 3 2 3 1 1.7 -0.3 3.5 2.5 1.5 -2 5 3.5 3.25
N 0.0000000000003899 0.0000000000003899 0.0000000000003899 0.0000000000003899 0.0000000000008700 0.0000000000008700 0 0 -0.0000000000004030 -0.0000000000004030 -0.0000000000004030 0 0 0.0000000000017901 0.0000000000007798 1.3871175738935000 0 0 0.0000000000008700 0.0000000000008700 0 0 -0.0000000000004030 -0.0000000000004030 -0.0000000000004030 0 0 0.0000000000017901
H 0.0000000000003899 0.0000000000003899 0.0000000000003899 0.0000000000003899 0.0000000000008700 0.0000000000008700 0 0 -0.0000000000004030 -0.0000000000004030 -0.0000000000004030 0 0 0.0000000000017901 0.0000000000007798 1.3871175738935000 0 0
NIS 0.0000000000003899 0.0000000000003899 0.0000000000003899 0.0000000000003899 0.0000000000008700 0.0000000000008700 0 0 -0.0000000000004030 -0.0000000000004030 -0.0000000000004030 0 0 0.0000000000017901
0.0000000000007798 1.3871175738935000 0 0
0.0000000000007798 1.3871175738935000 0 0
Nilai akar NH 0.0000000000003899 0.0000000000003899 0.0000000000003899 0.0000000000003899
0.0000000000007798 1.3871175738935000 0 0
0.0000000000008700 0.0000000000008700 0 0 -0.0000000000004030 -0.0000000000004030 -0.0000000000004030 0 0 0.0000000000017901
IH 0.0000000000003899 0.0000000000003899 0.0000000000003899 0.0000000000003899
0.0000000000007798 0.0578242560121200 0 0
0.0000000000008700 0.0000000000008700 0 0 -0.0000000000004030 -0.0000000000004030 -0.0000000000004030 0 0 0.0000000000017901
NHIS 0.0000000000003899 0.0000000000003899 0.0000000000003899 0.0000000000003899
Lampiran 5 Perbandingan selisih nilai akar sebenarnya dan akar pendekatan untuk masing-masing metode dengan toleransi
0.0000000000007798 0.2024851537624300 0 0
0.0000000000008700 0.0000000000008700 0 0 -0.0000000000004030 -0.0000000000004030 -0.0000000000004030 0 0 0.0000000000017901
NIH 0.0000000000003899 0.0000000000003899 0.0000000000003899 0.0000000000003899
36
Total
( )
3
4
5
6
5
5
7
1
1.7
-0.3
3.5
2.5
1.5
-2
7
5
3
3.25
2
2
8
5
3
11
5
1
5
4
53
-0.3
3.5
3
4
2
7
11
8
7
5
5
6
5
5
4
5
5
53
4
4
4
130
130
1
Uji ke-2
-0.5
Uji ke-1
N
7
11
8
7
5
5
6
5
4
3
5
4
5
5
53
4
5
130
Uji ke-3
270.7
7
11
8
7
5
5
6
5
4
3
5
3
5
5
53
4
4
130
Ratarata
4
6
15
4
3
3
4
3
3
2*
3
3
3
3
39
3
2*
14*
Uji ke-1
4
6
15
4
3
3
4
3
3
2
3
3
3
3
28
3
2*
14
Uji ke-2
NIS
4
6
15
4
3
3
4
3
3
2
3
3
3
3
28
3
2*
14
Uji ke-3
110
4.0
6.0
15.0
4.0
3.0
3.0
4.0
3.0
3.0
2.0
3.0
3.0
3.0
3.0
31.7
3.0
2.0
14.0
Ratarata
4
5
7
5
4
4
4
5
4
44
4
2
5
5
53
4
4
74
Uji ke-1
4
6
5
4
3
3
4
4
3
3
4
4
4
3
52
3
3
72
Uji ke-2
H
4
6
5
4
3
3
4
4
3
3
4
4
4
3
52
3
3
73
Uji ke-3
202
4.0
5.7
5.7
4.3
3.3
3.3
4.0
4.3
3.3
16.7
4.0
3.3
4.3
3.7
52.3
3.3
3.3
73.0
Ratarata
4
4
5
4
3
4
4
4
3
3
4
2
4
3
25
3
3
8
Uji ke-1
3
5
4
3
3
3
3
3
2
2
3
3
3
3
25
3
3
7
Uji ke-2
NH
3
5
4
3
3
3
3
3
2
2
3
3
3
3
25
3
3
7
Uji ke-3
Jumlah iterasi
84
3.3
4.7
4.3
3.3
3.0
3.3
3.3
3.3
2.3
2.3
3.3
2.7
3.3
3.0
25.0
3.0
3.0
7.3
Ratarata
4
4
4
3
3
3
3
3
2
2
3
2
3
3
24
3
3
7
Uji ke-1
3
5
4
3
3
3
3
3
2
2
3
3
3
3
24
3
3
7
Uji ke-2
IH
3
5
4
3
3
3
3
3
2
2
3
3
3
3
24
3
3
7
Uji ke-3
Lampiran 6 Perbandingan jumlah iterasi untuk masing-masing metode dengan tiga kali uji komputasi
79.7
3.3
4.7
4.0
3.0
3.0
3.0
3.0
3.0
2.0
2.0
3.0
2.7
3.0
3.0
24.0
3.0
3.0
7.0
Ratarata
3
4
14
3
3
3
4
3
3
2
4
3
5
3
4
3
3
12
Uji ke-1
3
4
14
3
3
3
4
3
3
2
3
3
5
3
4
3
3
13
Uji ke-2
NHIS
3
4
14
3
3
3
4
3
3
2
3
3
5
3
4
3
3
13
Uji ke-3
79.0
3.0
4.0
14.0
3.0
3.0
3.0
4.0
3.0
3.0
2.0
3.3
3.0
5.0
3.0
4.0
3.0
3.0
12.7
Ratarata
4
4
4
4
3
3
3
3
3
3
3
2
3
3
11
3
3
7
Uji ke-1
4
4
3
3
2
2
3
3
2
2
3
3
3
2
10
2
2
6
Uji ke-2
NIH
4
4
3
3
2
2
3
3
2
3
3
3
3
2
10
2
2
6
Uji ke-3
62.7
4.0
4.0
3.3
3.3
2.3
2.3
3.0
3.0
2.3
2.7
3.0
2.7
3.0
2.3
10.3
2.3
2.3
6.3
Ratarata
37
Total
( )
0.0011
0.003
0.0033
0.0049
0.0438
0.0063
0.0064
0.0031
0.007
0.0013
0.0044
0.0053
0.0066
0.0055
0.0054
0.0108
0.0149
0.0146
0.0092
2
-0.3
1
3
2
3
1
1.7
-0.3
3.5
2.5
1.5
-2
5
3.5
3.25
0.002
0.0023
0.0011
0.0012
0.0014
0.0011
0.0015
0.0007
0.0013
0.0011
0.0013
0.0014
0.0109
0.0011
0.0049
0.0263
0.1204
1
Uji ke-2
-0.5
Uji ke-1
N
0.0019
0.0029
0.0032
0.0024
0.0011
0.0011
0.0014
0.0011
0.0005
0.0005
0.0016
0.0014
0.0014
0.0015
0.0108
0.0011
0.0014
0.0259
Uji ke-3
0.1327
0.0044
0.0069
0.0070
0.0052
0.0025
0.0026
0.0031
0.0025
0.0021
0.0008
0.0033
0.0019
0.0030
0.0031
0.0218
0.0024
0.0025
0.0575
Ratarata
0.0171
0.0209
0.0522
0.0203
0.0104
0.0102
0.0135
0.0099
0.0088
0.0888
0.0141
0.1249
0.012
0.0151
0.0674
0.0118
0.0463
0.1203
Uji ke-1
0.0171
0.0209
0.0522
0.0203
0.0104
0.0102
0.0135
0.0099
0.0088
0.0888
0.0141
0.1249
0.012
0.0151
0.0674
0.0118
0.0463
0.1203
Uji ke-2
NIS
0.004
0.0061
0.0211
0.0047
0.0025
0.0027
0.0036
0.0023
0.0023
0.0018
0.0032
0.003
0.003
0.0028
0.0222
0.0026
0.077
0.0119
Uji ke-3
0.5016
0.0127
0.0160
0.0418
0.0151
0.0078
0.0077
0.0102
0.0074
0.0066
0.0598
0.0105
0.0843
0.0090
0.0110
0.0523
0.0087
0.0565
0.0842
Ratarata
0.0151
0.0182
0.0246
0.0143
0.0074
0.0088
0.0089
0.0087
0.0087
0.0067
0.0122
0.0064
0.0108
0.0107
0.0705
0.0059
0.0072
0.0822
Uji ke-1
0.0028
0.0063
0.0055
0.0036
0.0015
0.0015
0.002
0.0019
0.0017
0.0015
0.0023
0.0023
0.0026
0.0019
0.0243
0.0019
0.0016
0.0357
Uji ke-2
H
0.0029
0.0043
0.0055
0.0032
0.0015
0.0016
0.002
0.0019
0.0015
0.0015
0.0023
0.0023
0.0024
0.0019
0.024
0.0017
0.0017
0.0342
Uji ke-3
0.1749
0.0069
0.0096
0.0119
0.0070
0.0035
0.0040
0.0043
0.0042
0.0040
0.0032
0.0056
0.0037
0.0053
0.0048
0.0396
0.0032
0.0035
0.0507
Ratarata
0.0166
0.0137
0.0299
0.0144
0.009
0.0093
0.0093
0.0089
0.0061
0.0062
0.0123
0.0073
0.0098
0.011
0.0193
0.01
0.0096
0.028
Uji ke-1
0.0028
0.0044
0.0064
0.0032
0.0024
0.0022
0.0023
0.0021
0.0016
0.0014
0.0024
0.0024
0.0025
0.0026
0.0453
0.0023
0.0023
0.0058
Uji ke-2
NH
0.0031
0.0045
0.0061
0.0036
0.002
0.0021
0.0022
0.002
0.0016
0.0016
0.0026
0.0023
0.0025
0.0026
0.0169
0.0023
0.0023
0.0056
Uji ke-3
Running time(ms)
0.1303
0.0075
0.0075
0.0141
0.0071
0.0045
0.0045
0.0046
0.0043
0.0031
0.0031
0.0058
0.0040
0.0049
0.0054
0.0272
0.0049
0.0047
0.0131
Ratarata
0.0106
0.0172
0.0129
0.0111
0.0078
0.0072
0.0061
0.0108
0.0059
0.004
0.0101
0.0103
0.009
0.009
0.0563
0.0079
0.0063
0.0271
Uji ke-1
0.0033
0.0053
0.007
0.0037
0.0026
0.0024
0.0023
0.0024
0.0017
0.0016
0.0027
0.0026
0.0028
0.003
0.0188
0.0026
0.0025
0.0061
Uji ke-2
IH
0.0034
0.0053
0.0067
0.004
0.0023
0.0023
0.0023
0.0023
0.0017
0.0017
0.0028
0.0027
0.003
0.0029
0.0184
0.0026
0.0026
0.0064
Uji ke-3
Lampiran 7 Perbandingan running time untuk masing-masing metode dengan tiga kali uji komputasi
0.1255
0.0058
0.0093
0.0089
0.0063
0.0042
0.0040
0.0036
0.0052
0.0031
0.0024
0.0052
0.0052
0.0049
0.0050
0.0312
0.0044
0.0038
0.0132
Ratarata
0.0202
0.0235
0.0667
0.0254
0.0158
0.0152
0.0213
0.0099
0.0088
0.0888
0.0283
0.0567
0.0423
0.0187
0.022
0.0168
0.0185
0.0503
Uji ke-1
0.0045
0.0062
0.0311
0.0055
0.0035
0.0036
0.005
0.004
0.0035
0.0024
0.0043
0.0047
0.0068
0.0045
0.0052
0.0042
0.004
0.0167
Uji ke-2
NHIS
0.005
0.0061
0.0324
0.006
0.004
0.0041
0.0049
0.0041
0.0036
0.0025
0.0047
0.0045
0.0073
0.0047
0.0053
0.004
0.0041
0.0174
Uji ke-3
0.2645
0.0099
0.0119
0.0434
0.0123
0.0078
0.0076
0.0104
0.0060
0.0053
0.0312
0.0124
0.0220
0.0188
0.0093
0.0108
0.0083
0.0089
0.0281
Ratarata
0.017
0.0207
0.0242
0.0208
0.0088
0.009
0.0131
0.0128
0.0094
0.0088
0.0172
0.0117
0.016
0.0107
0.0193
0.01
0.0096
0.028
Uji ke-1
0.0048
0.0048
0.0061
0.0049
0.0019
0.0019
0.003
0.003
0.002
0.002
0.0031
0.0031
0.0035
0.0025
0.0106
0.0021
0.0021
0.0059
Uji ke-2
NIH
0.0038
0.0051
0.0062
0.0053
0.0022
0.0021
0.0029
0.0027
0.002
0.002
0.0032
0.0034
0.0039
0.0027
0.0109
0.0021
0.0022
0.0074
Uji ke-3
38 0.1348
0.0085
0.0102
0.0122
0.0103
0.0043
0.0043
0.0063
0.0062
0.0045
0.0043
0.0078
0.0061
0.0078
0.0053
0.0136
0.0047
0.0046
0.0138
Ratarata
39
Lampiran 8 Perbandingan jumlah iterasi dan running time masing-masing metode untuk toleransi 0.1600
NHIS
0.0200
0.1200
Running time
Running time
0.0250
NHIS
0.1400
NIS
0.1000 0.0800 0.0600
IH
0.0400 0.0200
NH 0
0.0100
IH
0.0000
5
0
10
Running time
Running time
NHIS
NH IH
NIH NIS H
0
N
5
0.1600 0.1400 0.1200 0.1000 0.0800 0.0600 0.0400 0.0200 0.0000
0.1400 NHIS
Running time
Running time
0.0800 0.0600
IH
0.0400 0.0200
NIHNH H
0.0000 0
5
Jumlah iterasi
N
5
10
0.0800 0.0600 0.0400 NIHNH H IH
0.0000 10
NIHNHH
0.1000
0.0200 N
IH
NIS NHIS
0.1200
NIS
0.1000
NIS
Jumlah iterasi
0.1600 0.1200
10
NHIS
0
10
Jumlah iterasi
0.1400
5
Jumlah iterasi
Jumlah iterasi
0.2000 0.1800 0.1600 0.1400 0.1200 0.1000 0.0800 0.0600 0.0400 0.0200 0.0000
N
0.0050
NIH H N
0.0000
NIHNIS NH H
0.0150
0
5
Jumlah iterasi
N 10
40
0.0350
0.0250 0.0200
NH NIH H IH
0.0150
NHIS
0.2500
Running time
0.0300
N
0.0100
0.2000 NIS 0.1500 0.1000 NIH NHIHH
0.0500
0.0050 0.0000
0.0000 0
5
0
10
5
N 10
0.2500 0.2000
NHIS
0.1500 NIS
0.1000 0.0500
NIH H IH NH
0.0000 0
2
15
Jumlah iterasi
Jumlah iterasi
Running time
Running time
0.3000
NHIS NIS
4
N 6
Jumlah iterasi
8
10
20
41
RIWAYAT HIDUP Penulis dilahirkan pada tanggal 3 Juli 1991 di Palu, Sulawesi Tengah. Penulis merupakan anak kedua dari pasangan Bapak Syahar Mahunju dan Ibu Siti Nurbaya. Pada tahun 2009, penulis lulus dari SMA Negeri 2 Palu dan diterima sebagai mahasiswa Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA), Universitas Tadulako Palu. Penulis lulus dari program sarjana matematika Universitas Tadulako pada tahun 2013. Pada tahun 2014, penulis terdaftar sebagai mahasiswa Magister Ilmu Komputer di Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor (IPB).
