JTAM (Jurnal Teori dan Aplikasi Matematika) http://journal.ummat.ac.id/index.php/jtam p-ISSN 2597-7512 | e-ISSN 2614-1175 Vol. 3, No. 2, Oktober  2019, Hal. 93-97

## Perbandingan Metode Halley dan Olver dalam Penentuan Akar-akar Penyelesaian Polinomial Wilkinson
1 Randhi Nanang Darmawan, 2 Auda Nuril Zazilah
1,2 Politeknik Negeri Banyuwangi, Indonesia
1 randhi@poliwangi.ac.id , 2 audanuril@poliwangi.ac.id
INFO ARTIKEL ABSTRAK Riwayat Artikel: Diterima: 25-07-2019 Disetujui: 01-10-2019
Abstrak: Root  finding  adalah  salah  satu  topik  dalam  metode  numerik  dalam menentukan  akar  suatu  persamaan ( ) ,  biasanya  persamaan  tersebut  dalam bentuk  rumit  dan  sulit  diselesaikan  secara  analitik.  Dalam  artikel  ini  suatu polinomial  berderajat  tinggi  yaitu  polinomial  Wilkinson  akan  digunakan  untuk menguji perbandingan akurasi metode Halley dan Olver, yang mana metode tersebut jarang digunakan karena kalah populer dengan metode Newton-Raphson, akan tetapi kedua metode tersebut memiliki kinerja yang cukup bagus dan lebih cepat konvergen dengan  iterasi  lebih  sedikit.  Berdasarkan  hasil  simulasi  metode  Halley  pada  iterasi ke-4  mendapatkan  persentase  galat  0,0029%,  Metode  Olver  pada  iterasi  ke-5 mendapatkan  persentase  galat  0,0004%  sedangkan  metode  Newton-Raphson membutuhkan iterasi ke-7 untuk mendapatkan persentase galat 0,0098%.
Abstract:    Root  finding  is  one  of  the  topics  in  numerical  methods  for  determaining roots of an equation ( ) , usually that equation in the form of complicated and it will  be  difficult  to  be  solved  analytically.  In  this  paper,  high  order  polynomial  like Polynomial  Wilkinson  will  be  used  to  test  comparison  the  accuracy  on  Halley  and Olver  methods,  which  is  those  methods  are  rarely  used  for  losing  popular  than Newton-Raphson  method,  but  both  methods  had  powerful  performance  and  faster converging  with  less  iteration.    Based  on  the  simulation,  Halley  method  on  4 th iteration got percentage error  0,0029%, Olver method on 5 th iteration got percentage error  0,0004%, while Newton-Raphson method are need  7 th iteration got percentage error  0,0098%.
Kata Kunci: Metode Halley; Metode Olver; Metode Newton-Raphson; Polinomial Wilkinson; Root Finding.
Keywords: Halley Method; Olver Method; Newton-Raphson Method; Polynomial Wilkinson; Root Finding.
https://doi.org/10.31764/jtam.v3i2.992
This is an open access article under the CC–BY-SA license
——————————  ——————————

## A. LATAR BELAKANG
Sepintas  yang  terpikir  dalam  benak  setiap pembaca  terkait  penentuan  akar-akar  suatu persamaan ( ) adalah metode grafik, pemfaktoran, melengkapi kuadrat sempurna dan jika metode-metode  tersebut  tidak  dapat  digunakan maka  menggunakan  rumus  Al-Kharizmi  atau  lebih dikenal  dengan  rumus  ABC.  Lebih  jelas  lihat  (Putri, Syamsudhuha, & Hasbiyati, 2016), (Gani, 2014).
Penyelesaian  dengan  metode-metode  tersebut masih  dalam  lingkup  yang  kecil  dan  persamaan- persamaan  yang  digunakan  hanya  persamaan kuadrat  (polinom  derajat  2),  jika  melibatkan polinom  berderajat  yang  lebih  tinggi  maka  metode horner yang akan digunakan sebagaimana dijelaskan
dan dipelajari dalam Sekolah Menengah Atas (SMA) (Hidayah, Riski, Kumalasari, & Astutiningtyas, 2018). Seiring perkembangan teknologi saat ini, penentuan akar-akar  penyelesaian ( ) ( root finding) lebih melibatkan  persamaan/model  matematika  yang rumit, dan melibatkan polinom dengan derajat yang tinggi  dan  bahkan  dalam  bentuk  tidak  wajar  dan sulit untuk ditentukan akar/solusi sejatinya (eksak). Sehingga  pada  kasus  seperti  ini  metode  numerik bekerja  untuk  menghampiri  akar/solusi  sejati  dari persamaan/model  matematika  yang  rumit  tersebut (Darmawan, 2016), (Wigati, 2017), (Batarius, 2018).
Salah  satu  metode  numerik  yang  populer  dan powerful dalam menentukan akar-akar penyelesaian adalan  metode  Newon-Raphson  (NR),  metode  NR
94 | JTAM (Jurnal Teori dan Aplikasi Matematika) | Vol. 3, No. 2, Oktober 2019, Hal. 93-97
banyak  diterapkan  dalam  beberapa  disiplin  ilmu seperti bidang estimasi, informatika dan elektronika. Konsep  metode  NR  adalah  dengan  menggunakan turunan  untuk  mempercepat  kekonvergenan,  akan tetapi  metode  NR  bisa  juga  mengalami  divergen (menjauhi  akar)  (Wulan,  Sukarti,  &  Zulkarnaen, 2017), (Batarius, 2018).
Sedangkan  metode  Halley  dan  Olver  diklaim memiliki  tingkat  kekonvergenan  lebih  cepat  dari metode  NR  (Malek,  2010),  dan  sama-sama menerapkan konsep turunan pada proses perhitungan  iterasinya.  Akan  tetapi  kedua  metode melalui proses perhitungan yang rumit dan panjang jika dibanding dengan metode NR.
Oleh karena itu metode numerik tidak bisa lepas dari  peranan  komputasi  dalam  melakukan perhitungan  iterasi  yang  rumit  dan  panjang terutama  dalam  penentuan  akar-akar  polinomial. Lebih  jelas  lihat  (Stor  &  Slapnicar,  2017),  (Le  Thi, Ouanes, & Zidna, 2014).
Pada  artikel  ini  akan  dikaji  kinerja  dari  kedua metode  dengan  acuan  pada  metode  NR,  yang dicobakan  untuk  menentukan  salah  satu  akar penyelesaian polinom derajat tinggi yaitu polinomial Wilkinson  (polinom  derajat  20).  Masing-masing metode  akan  dibandingkan  berdasarkan  kecepatan iterasi  untuk  mencapai  kekonvergenan  dengan melihat  persentase  galat  terkecil,  dengan  demikian akan  terlihat  metode  mana  yang  terbaik  dalam menyelesaiakan  permasalahan root  finding dalam kasus  polinomial  derajat  tinggi.  Lebih  jelas  lihat (Winkler, Lao, & Hasan, 2012).

## B. METODE PENELITIAN
Jenis penelitian ini adalah comparative research yaitu  penelitian  bersifat  membandingkan  antara metode  yang  satu  dengan  metode  yang  lain  untuk mengetahui  metode  mana  yang  menghasilkan  hasil penelitian  yang  lebih  baik  berdasarkan  kriteria- kriteria yang telah ditentukan.
Data  yang  digunakan  untuk  bahan  uji  adalah polinomial  Wilkinson  ( (     ) )  dengan  titik  akar yang dicari adalah satu titik dengan nilai awal .
Dengan  menggunakan  bantuan software Maple 15,  adapun  langkah-langkah  penelitian  yang dilakukan adalah sebagai berikut:
1. Studi  literatur  dari  buku  dan  jurnal online terkait  metode  NR,  Halley,  Olver  dan  juga polinomial Wilkinson.
2. Mendefinisikan  polinomial  Wilkinson  dengan perintah:
product(W(x),i=1..20); kemudian expand(product(W(x),i=1..20)); sehingga  didapatkan  polinomial  Wilkinson yang siap ditentukan akar penyelesaiannya.
3. Pembuatan program iteratif metode NR, Halley, dan  Olver.  Kemudian  dengan  masing-masing program  yang  sudah  jadi  dilakukan  proses penentuan  akar  penyelesaian  dengan  masing- masing  metode  dengan  menggunakan  nilai awal .
4. Menentukan  nilai  persentase  galat  dari masing-masing  metode  berdasarkan  nilai hampiran yang didapat dengan nilai eksaknya.
5. Membandingkan hasil pada langkah 4 dengan menganalisis  berapa  banyak  iterasi  yang dibutuhkan  dan  seberapa  kecil  persentase galat dari masing-masing metode.
6. Membuat  kesimpulan,  yang  merupakan jawaban singkat dari permasalahan yang telah dijabarkan  tentang  klaim  bahwa  metode Halley  dan  Olver  lebih  baik  dari  metode  NR, serta  metode  mana  yang  lebih  baik  antara metode Halley dan Olver.

## 1. Metode Newton-Raphson (NR)
Metode  Newton-Raphson  (NR)  diturunkan  dari deret  Taylor  untuk  menentukan  turunan  suatu fungsi di titik ,
( ) ( ) (1)
Persamaan 1 dapat dituliskan untuk perhitungan iteratif  menjadi Persamaan 2,
( ) ( ) (2)
Persamaan  2  lebih  popular  disebut  metode Newton-Raphson  (NR)  (Chapra  &  Canale,  2015), (Amat, Ezquerro, & Hernandez-Veron, 2015).

## 2. Metode Halley
Metode  Halley  adalah  salah  satu  algoritma pencarian  akar  untuk  menyelesaikan  persamaan
Randhi Nanang Darmawan, Perbandingan Metode Halley... 95 nonlinear ( ) ,  namanya  diambil  dari  astronot Edmund  Halley  (1656-1742).  Tidak  seperti  metode NR,  yang  mana  biasanya  memiliki  tingkat kekonvergenan  kuadratik,  untuk  beberapa  kasus metode Halley dapat mencapai
tingkat kekonvergenan kubik (Plate, Papadopoulos, & Müller, 2010).
Formula iteratif metode Halley didapatkan dari penurunan  deret  Taylor  orde-2,  dengan  sedikit manipulasi  aljabar  dan  substitusi  metode  NR  pada persamaan 2, maka didapatkan persamaan 3:
( ) ( ) ( ) ( ) ( ) (3)
Pada  metode  Halley  tersebut  melibatkan turunan  kedua  fungsi,  berbeda  dengan  metode  NR yang hanya melibatkan turunan pertama fungsi.

## 3. Metode Olver
Metode  Olver  mirip  dengan  metode  Halley tingkat  kekonvergenannya  kubik  dan  lebih  cepat dari  metode  NR  yang  tingkat  kekonvergenannya kuadratik,  Persamaan  4  merupakan  formula  iteritif dari metode Olver :
( ) ( ) ( ( ) ( ) ( ) ) (4)
(Malek, 2010).
Sekilas  metede  Olver  mirip  dengan  metede Halley  akan  tetapi  metode  ini  melibatkan perhitungan  sedikit  lebih  rumit  karena  terdapat pembagi berpangkat tiga yaitu ( ) .

## 4. Polinomial Wilkinson
Polinomial  Wilkinson  adalah    suatu  polinomial derajat tinggi yang namanya diambil dari nama ahli matematika  bidang  analisis  numerik  James  H. Wilkinson (1919-1986), yang didefinisikan dengan:
(    ) =
(    ) =
(    ) = (     )(     ) (    ) = (     )(     )(     )
(    ) = (     ) (        ) (5) Persamaan 5 dengan nilai
adalah kondisi khusus  yang  biasa  disebut  polinomial  Wilkinson yang dapat diekspansi menjadi:

## (     )
(6)
(McKee, 2012)
Gambar 1 . Grafik Polinomial Wilkinson

## C. HASIL DAN PEMBAHASAN
1. Akar-akar Polinomial Wilkinson
Polinomial  Wilkinson seperti pada persamaan 5 dan  terlihat  grafik  seperti  ada  Gambar  1  memiliki himpunan  akar-akar  eksak { } . Pada penelitian ini akan diambil satu titik akar eksak yaitu
maka  diambil  nilai  awal sehingga  jika  grafik  polinomial  Wilkinson  dipotong kecil  sesuai  dengan  keperluan  penelitian  ini  adalah sebagai berikut,
96 | JTAM (Jurnal Teori dan Aplikasi Matematika) | Vol. 3, No. 2, Oktober 2019, Hal. 93-97

## 2. Akar Hampiran Polinomial Wilkinson
Dengan  menerapkan  metode  NR  sebagai  acuan dan  metode  Halley  dan  Olver  sebagai  metode  yang akan dibandingkan dengan menggunakan nilai awal maka  didapatkan  nilai  iterasi  dari  seluruh metode sesuai Tabel 1 berikut:
Tabel 1. Hasil Iterasi Akar Hampiran Polinomial Wilkinson dengan Metode Halley dan Olver
Halley Olver NR 1 0.4948783 0.3997905 0.2779522 2 0.8334448 0.7109933 0.5179945 3 0.9835814 0.9148845 0.7160116 4 0.9999708 0.9937950 0.8654045 5 0.9999998 0.9999955 0.9581488 6 0.9999999 0.9999998 0.9946754 7 0.9999998 0.9999999 0.9946754 8 0.9999999 0.9999999 0.9999998 9 0.9999999 0.9999999 0.9999999 10  0.9999999 0.9999999 0.9999999
Berdasarkan  Tabel  1  masing-masing  metode menggunakan 10 iterasi dan terlihat seluruh metode mendekati  nilai  eksak  ( )  hal  ini menunjukkan  seluruh  metode  cukup  bagus  untuk mengestimasi akar eksaknya.

## 3. Perbandingan Metode Halley dan Olver
Sepintas  metode  Halley  dan  Olver  tidak  jauh beda  dengan  metode  NR  dalam  mengestimasi dengan  nilai  awal
,  akan  tetapi  jika
dilihat  secara  seksama  dan  teliti  pada  iterasi  ke-1 didapatkan,
dan juga
bahkan saat iterasi ke-3 juga
terlihat  jelas  bahwa  Metode  Halley  lebih  cepat konvergen  dibandingkan  metode  Olver  dan  NR, meskipun  juga  metode  Olver  lebih  cepat  dari  pada metode NR. Untuk memperkuat kesimpulan tersebut maka  Tabel  2  akan  memaparkan  persentase  galat dari masing-masing metode.
Tabel 2. Persentase Galat Metode Halley dan Olver
Halley Olver NR 1 50,5121% 60,0209% 72,2048 % 2 16,6555% 28,9007% 48,2005% 3 1,6418% 8,5115% 28,3989% 4 0,0029% 0,6205% 13,4595% 5 1,463E-05% 0,0004% 4,1851% 6 7,23E-06% 1,131E-05% 0,5324% 7 3,91E-06% 0,0098% 8 1,579E-05% 9 5,1E-06
Berdasarkan  Tabel  2  terlihat  bahwa  metode Halley  hanya  membutuhkan  empat  iterasi  untuk mendapatkan  persentase  galat  yang  cukup  kecil yaitu  0,0029%  dan  sangat  dekat  dengan dibandingkan  metode  Olver  dan  NR  yang  masing- masing  pada  iterasi  ke-4  dengan  persentase  galat 0,6205%  dan  13,4595%,  dari  hasil  penelitian  ini terlihat  metode  Halley  dan  Olver  lebih  cepat konvergen  dari  pada  metode  NR  yang  lebih  dulu populer digunakan untuk masalah root finding.
Secara keseluruhan penulis sengaja pada Tabel 2 memberikan pewarnaan khusus ( grey ) yang berbeda pada  masing-masing  nilai  agar  lebih  jelas  dalam membacanya, bahwa metode Halley butuh iterasi ke- 4  untuk  mendapatkan  persentase  galat  yang  cukup kecil,  metode  Olver  iterasi  ke-5,  sedangkan  metode NR  iterasi  ke-7.  Untuk  pewarnaan  ( yellow )  terlihat bahwa  metode  Halley  butuh  iterasi  ke-6  untuk mendapatkan  persentase  galat  yang  sangat  kecil (7,23E-06%), metode Olver iterasi ke-7 (3,91E-06%) sedangkan metode NR iterasi ke-9 (5,1E-06).
Berdasarkan hasil penelitian yang telah dilakukan ternyata  klaim  bahwa  metode  Halley  dan  Olver memiliki  tingkat  kekonvergenan  secara  kubik  lebih cepat  dibanding  tingkat  kekonvergenan  metode  NR yaitu  kuadratik  adalah  benar,  akan  tetapi  kedua metode kalah popular dibanding metode NR karena memang  metode  ini  jarang  digunakan  dan melibatkan    formula  iteratif  yang  cukup  rumit dibandingkan  NR  karena  kedua  metode  melibatkan turunan  kedua  dari  polinom  yang  akan  ditentukan akar  penyelesaiannya.  Dari  penelitian  juga  terlihat bahwa  metode  Halley  pada  kasus  polinomial Wilkinson  memiliki  tingkat  kekonvergenan  yang lebih  cepat  dibandingkan  metode  Olver  dengan persentase  galat  yang  sangat  kecil  pada  tiap iterasinya.

## D. SIMPULAN DAN SARAN
Berdasarkan  hasil  penelitian  dan  pembahasan yang  telah  dipaparkan  maka  dapat  ditarik kesimpulan  bahwa  metode  Halley  dan  Olver memiliki  tingkat  kekonvergenan  lebih  cepat  dari pada  metode  NR,  pada  kasus  polinomial  Wilkinson dan metode Halley lebih cepat konvergen dari pada metode    Olver  dengan  nilai  persentase  galat  cukup kecil  0,0029%  pada  iterasi  ke-4,  lebih  jauh  metode Halley  mendapatkan  nilai  hampiran  lebih  baik  dari pada  metode    Olver  dengan  nilai  persentase  galat sangat  kecil  7,23E-06%  pada  iterasi  ke-6.  Metode Halley  dan  Olver  sangat  direkomendasikan  untuk menentukan  akar-akar  penyelesaian  polinomial dengan derajat tinggi.
Penelitian  ini  masih  dapat  dikembangkan dengan polinomial uji yang lebih rumit, atau bahkan menggunakan  persamaan  yang  bukan  suatu polinomial  dan  juga  melibatkan  bilangan  kompleks, di samping itu masih terdapat beberapa metode root finding yang mungkin lebih cepat konvergen seperti metode Graeffe dan Maehly.

## UCAPAN TERIMA KASIH
Penulis  mengucapkan  terima  kasih  kepada  Prof. Massoud  Malek  dari  Department  Mathematics Califrnia  State  University,  East  Bay  yang menginspirasi penulis untuk melakukan comparison research bidang root  finding yang  mana  konsep materi  tersebut  berasal  dari homepage beliau  di http://www.mcs.csueastbay.edu/~malek/Class/ .

## REFERENSI
Amat, S., Ezquerro, J., & Hernandez-Veron, M. (2015). On a new  family  of  high-order  iterative  methods  for the  matrixpth  root. Numer.  Linear  Algebra  Appl. DOI: 10.1002/nla.1974 , 585–595. Batarius, P. (2018). Nilai Awal Pada Metode Newton- Raphson Yang Dimodifikasi Dalam Penentuan Akar Persamaan. Pi: Mathematics Education Journal , 1 (3), 108–115.
https://doi.org/10.21067/pmej.v1i3.2784 Chapra, S. C., & Canale, R. P. (2015). Numerical Methods for Engineers  Seventh  Edition. New  York:  McGraw- Hill Education. Darmawan,  R.  N.  (2016).  Perbandingan  Metode  Gauss- Legendre,  Gauss-Lobatto  dan  Gauss-Kronrod pada  Integrasi  Numerik  Fungsi  Eksponensial. JMPM Vol 1, No 2. , 99-108. Gani, U. A. (2014). Aktivitas Metakognisi Mahasiswa Calon Guru  Matematika  dalam  Pemecahan  Masalah Terbuka. Didaktik Matematika Vol. 1, No. 2 , 21-29.
Hidayah,  N.  I.,  Riski,  V.  D.,  Kumalasari,  L.,  & Astutiningtyas,  E.  L.  (2018).  Pengaruh Penggabungan  Metode  Outdoor  Dengan Indoor Learning Menggunakan Sistem Sepur Selam. Jurnal  Math  Educator  Nusantara: Wahana  Publikasi  Karya  Tulis  Ilmiah  Di Bidang  Pendidikan  Matematika , 4 (2),  168- 176
Le  Thi,  H.  A.,  Ouanes,  M.,  &  Zidna,  A.  (2014).  Computing Real Zeros of A Polynomial By Branch and Bound and  Branch  and  Reduce  Algorithms. Yugoslav Journal of Operations Research 24 Number 1 ,  53- 69. Malek,  M.  (2010). Cal  State  East  Bay  Rising  The  East.
Retrieved from
http://www.mcs.csueastbay.edu/~malek/Class/
root.pdf
McKee,  B.  (2012).  Wilkinson  Polynomials. Parabola Volume 48, Issue 3 , 15.
Plate,  C.,  Papadopoulos,  P.,  &  Müller,  R.  (2010).  Use  of Halley’s  Method  in  the  Nonlinear  Finite  Element Analysis. PAMM · Proc. Appl. Math. Mech. 10 , 569 – 570.
Putri, I. P., Syamsudhuha, & Hasbiyati, I. (2016). Alternatif Menentukan Akar-Akar Persamaan Kuadrat Yang Bukan  Bilangan  Bulat. Jurnal  Sains  Matematika dan Statistika, Vol. 2 No. 2 , 81-86.
Stor,  N.  J.,  &  Slapnicar,  I.  (2017).  Forward  Stable Computation  of  Roots  of  Real  Polynomials  with Real  Simple  Roots. Appl. Math. Inf.  Sci. 11, No. 1 , 33-41.
Wigati,  J.  (2017).  Solusi  Numerik  Persamaan  Non- Linier  Dengan  Metode  Bisection  dan  Regula Falsi. G-Tech : Jurnal Teknologi Terapan , 1 (1), 5–17. Retrieved from http://ejournal.uniramalang.ac.id/index.php /g-tech/article/view/262 Winkler,  J.  R.,  Lao,  W.,  &  Hasan,  M.  (2012).  The computation  of  multiple  roots  of  a  polynomial. Journal of Computational and Applied Mathematics 236 , 3478–3497. Wulan, E. R., Sukarti, S. M., & Zulkarnaen, D. (2017). Perbandingan Tingkat Kecepatan
Konvergensi  dari  Metode  Newton  Raphson dan  Metode  Secant Setelah  Mengaplikasikan Metode  Aiken’s  dalam  Perhitungan  Akar Pangkat  Tiga. Jurnal  Matematika  Integratif ,
12 (1), 35-42. https://doi.org/10.24198/jmi.v12.n1.10282. 35-42