VARIAN METODE HALLEY BEBAS TURUNAN KEDUA DENGAN ORDE KEKONVERGENAN ENAM Siti Mariana1∗ 1
Mahasiswa Program Studi S1 Matematika Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Riau Kampus Binawidya Pekanbaru (28293), Indonesia ∗
[email protected]
ABSTRACT This article discusses the variant of Halley’s method free from second derivative, modified from a combination of Newton’s method and Halley’s method. This new method has six order of convergence. Furthermore, from computational test it shows that the discussed method is better than the Newton’s method, Halley’s method and Noor’s method when seen from the number of iterations to obtain an approximated root of test fuctions. Keywords: Newton method, variant Halley method, order of convergence, nonlinear equation, error equation. ABSTRAK Artikel ini membahas varian metode Halley bebas turunan kedua, yang dimodifikasi dari kombinasi metode Newton dan metode Halley Metode baru ini memiliki orde kekonvergenan enam. Selanjutnya dari uji komputasi terlihat bahwa metode yang didiskusikan lebih baik dari pada metode Newton, metode Halley dan metode Noor jika dilihat dari jumlah iterasi yang diperoleh untuk mendapatkan akar hampiran. Kata kunci: metode Newton, varian metode Halley, orde kekonvergenan, persamaan nonlinear, persamaan tingkat kesalahan. 1. PENDAHULUAN Masalah yang sering ditemui dalam bidang matematika salah satunya adalah bagaimana menemukan solusi dari persamaan nonlinear f (x) = 0. Persamaan nonlinear tersebut dapat diselesaikan secara analitik dan metode numerik. Banyak metode numerik yang dapat digunakan untuk menyelesaikan persamaan nonlinear diantaranya yaitu metode Newton dengan bentuk iterasi xn+1 = xn −
Repository FMIPA
f (xn ) , n = 0, 1, 2, · · · , f 0 (xn )
(1)
1
dengan f 0 (xn ) 6= 0. Metode Newton memiliki orde kekonvergenan kuadratik [1, h. 67]. Pada setiap iterasi, metode Newton memerlukan dua buah fungsi yang dievaluasi (NFE) yaitu f (xn ) dan f 0 (xn ). Dalam perkembangannya, metode Newton banyak mengalami modifikasi. Salah satu metode hasil modifikasi metode Newton adalah metode Halley dengan bentuk iterasi 2 f (xn ) , n = 0, 1, 2, · · · , (2) xn+1 = xn − 2 − Lf (xn ) f 0 (xn ) f 00 (xn )f (xn ) . Metode Halley [7, h. 86] memiliki orde kekonverf 0 (xn )2 genan kubik. Metode Halley memerlukan tiga buah evaluasi fungsi pada setiap iterasinya yaitu f (xn ), f 0 (xn ) dan f 00 (xn ). Apabila metode Newton dan metode Halley dikombinasikan penggunaannya, maka diperoleh bentuk iterasi f (xn ) . yn = x n − 0 f (xn ) (3) 2f 0 (yn )f (yn ) xn+1 = yn − 0 . 2f (yn )2 − f 00 (yn )f (yn ) dengan Lf (xn ) =
Seperti halnya dengan metode Halley, kombinasi metode Newton dan metode Halley ini masih mengandung bentuk turunan kedua yaitu f 00 (yn ) dan ini dianggap sebagai sesuatu kelemahan. Untuk menghindari penggunaan turunan kedua f 00 (yn ) ini, maka Noor [8] melakukan pendekatan lain pada turunan kedua dengan bentuk f 00 (yn ) =
f 0 (yn ) − f 0 (xn ) . y n − xn
(4)
Menggunakan pendekatan ini maka diperoleh iterasi dengan bentuk yn
f (xn ) = xn − 0 . f (xn )
xn+1 = yn −
2f (xn )f (yn )f 0 (yn ) 2f (xn )f 0 (yn )2 − f (yn )f 0 (xn )2 + f (yn )f 0 (xn )f 0 (yn )
.
Metode Noor memiliki orde kekonvergenan lima [8]. Metode Noor memerlukan empat buah evaluasi fungsi pada setiap iterasinya yaitu f (xn ), f 0 (xn ), f (yn ), dan f 0 (yn ). Pada tulisan ini direview artikel yang ditulis oleh Jiaqi Han, Huiqian HE, Aimin XU and Zhongdi Can [4], pembahasan dimulai dibagian dua dengan mengusulkan varian metode Halley bebas turunan kedua dengan orde kekonvergenan enam. Dibagian tiga disajikan analisa kekonvergenan. Kemudian dilanjutkan di bagian empat dengan mendiskusi beberapa contoh uji komputasi.
Repository FMIPA
2
2. VARIAN METODE HALLEY BEBAS TURUNAN KEDUA Berbeda dengan apa yang dilakukan Noor [8], Jiaqi Han, Huiqian HE, Aimin XU and Zhongdi Can [4] menggunakan pendekatan untuk turunan kedua f 00 (yn ) yaitu 2 f (yn ) − f (xn ) 00 0 0 f (yn ) = 2f (yn ) + f (xn ) − 3 = Pf (xn , yn ), (5) y n − xn y n − xn sehingga diperoleh iterasi dengan bentuk yn
f (xn ) = xn − 0 , f (xn )
1 xn+1 = yn − 1 + 2
Hf (xn , yn ) f (yn ) , 0 1 f (yn ) 1 − Hf (xn , yn ) 2
(6)
Pf (xn , yn )f (yn ) . f 0 (yn )2 Persamaan (6) merupakan bentuk iterasi varian metode Halley bebas turunan kedua. Apabila diperhatikan bentuk iterasi varian metode Halley maka terlihat bahwa pada setiap iterasinya varian metode Halley memerlukan 4 buah fungsi yang dievaluasi (NFE) yaitu f (xn ), f 0 (xn ), f (yn ), dan f 0 (yn ). Selanjutnya akan dilakukan analisa kekonvergenan untuk menunjukkan bahwa varian metode Halley memiliki orde kekonvergenan enam. dengan Hf (xn , yn ) =
3. ANALISA KEKONVERGENAN Teorema 1 Misalkan fungsi f dan f (i) dengan i = 1, 2, · · · , 6, kontinu untuk semua x disekitar α dan x0 adalah nilai tebakan awal yang cukup dekat dengan α, maka metode iterasi pada persamaan (6) memiliki orde kekonvergenan enam. Bukti: Misalkan α adalah akar sederhana persamaan nonlinear f (x) = 0, asumsikan bahwa f 0 (α) 6= 0 dan en = xn − α. Kemudian dengan menggunakan ekspansi Taylor f (xn ) disekitar xn = α sampai orde enam [2, h. 189] dan mengabaikan orde yang lebih tinggi diperoleh (xn − α)2 (xn − α)3 (xn − α) + f (2) (α) + f (3) (α) 1! 2! 3! 4 5 (xn − α) (xn − α) + f (4) (α) + f (5) (α) 4! 5! 6 (xn − α) + f (6) (α) + O (xn − α)7 . 6!
f (xn ) = f (α) + f 0 (α)
Repository FMIPA
(7)
3
f (k) (α) , k = 2, 3, · · · , dan karena f (α) = 0 dan en = xn − α, maka k!f 0 (α) persamaan (7) menjadi
Misalkan ck =
f (xn ) = f 0 (α)(en + c2 e2n + c3 e3n + c4 e4n + c5 e5n + c6 e6n + O(e7n )).
(8)
Selanjutnya dengan menggunakan ekspansi Taylor untuk f 0 (xn ) disekitar xn = α, dan setelah dilakukan penyederhanaan maka diperoleh f 0 (xn ) =f 0 (α)(1 + 2c2 en + 3c3 e2n + 4c4 e3n + 5c5 e4n + 6c6 e5n + O(e6n )).
(9)
Kemudian dari persamaan (8) dan (9) diperoleh f (xn ) (c1 en + c2 e2n + c3 e3n + c4 e4n + c5 e5n + c6 e6n + O(e7n )) = . f 0 (xn ) (1 + 2c2 en + 3c3 e2n + 4c4 e3n + 5c5 e4n + 6c6 e5n + O(e6n ))
(10)
1 = 1−r +r2 −r3 +· · · , untuk 1+r r = 2c2 en + 3c3 e2n + 4c4 e3n + 5c5 e4n + 6c6 e5n + O(e7n ), setelah disederhanakan diperoleh hasil dari persamaan (10) sebagai berikut Selanjutnya dengan menggunakan deret geometri
f (xn ) = en + c2 e2n − (2c22 − 2c3 )e3n − (−4c32 − 3c4 + 7c2 c3 )e4n − (10c2 c4 − 4c5 + 8c42 f 0 (xn ) + 6c23 − 20c22 c3 )e5n + (−5c6 − 16c52 + 52c32 c3 + 13c2 c5 − 33c2 c23 + 17c3 c4 − 28c22 c4 )e6n + O(e7n ). (11) Selanjutnya dengan mensubtitusikan persamaan (11) ke persamaan (6) maka diperoleh yn = α + c2 e2n + (−2c22 + 2c3 )e3n + (4c32 − 7c2 c3 + 3c4 )e4n + (−8c42 + 20c22 c3 − 10c2 c4 − 6c23 + 4c5 )e5n + (16c52 − 52c32 c3 + 5c6 + 33c2 c23 + 28c22 c4 − 13c2 c5 − 17c3 c4 + 5c6 )e6n + O(e7n ).
(12)
Kemudian dilakukan ekspansi Taylor dari f (yn ) disekitar xn = α sampai orde enam dan mengabaikan orde yang lebih tinggi, dan dengan menggunakan (12) diperoleh f (yn ) = f 0 (α)(c2 e2n + (−2c22 + 2c3 )e3n + (5c32 − 7c2 c3 + 3c4 )e4n + (−12c42 + 24c22 c3 − 10c2 c4 − 6c23 + 4c5 )e5n + (28c52 − 73c32 c3 + 37c2 c23 + 34c22 c4 − 13c2 c5 − 17c3 c4 + 5c6 )e6n + O(e7n )).
(13)
Selanjutnya dilakukan ekspansi Taylor dari f 0 (yn ) disekitar yn = α, dan dengan menggunakan (13) diperoleh f 0 (yn ) = f 0 (α)(1 + 2c22 e2n + (−4c32 + 4c2 c3 )e3n + (8c42 − 11c22 c3 + 6c2 c4 )e4n + (−16c52 + 28c32 c3 − 20c22 c4 + 8c2 c5 )e5n + (32c62 − 68c42 c3 + 56c32 c4 − 26c22 c5 + 10c2 c6 − 16c2 c3 c4 + 12c33 )e6n + O(e7n )). (14) Repository FMIPA
4
Selanjutnya persamaan (14) dikuadratkan diperoleh f 0 (yn )2 = f 0 (α)2 (1 + 4c22 e2n + (−8c32 + 8c2 c3 )e3n + (20c42 − 22c22 c3 + 12c2 c4 )e4n + (−48c52 + 72c32 c3 + 16c2 c5 − 40c22 c4 )e5n + (16c22 c23 + 136c32 c4 + 112c62 − 32c2 c3 c4 + 20c2 c6 − 52c22 c5 (15) + 24c33 − 212c42 c3 )e6n + (O(e7n )). Selanjutnya persamaan (13) dibagi dengan persamaan (14), dan disederhanakan maka diperoleh f (yn ) = (c2 e2n + (−2c22 + 2c3 )e3n + (3c32 − 7c2 c3 + 3c4 )e4n f 0 (yn ) + (−4c42 + 16c22 c3 − 6c23 − 10c2 c4 + 4c5 )e5n + (6c52 − 32c32 c3 + 29c2 c23 + 22c22 c4 − 17c3 c4 − 13c2 c5 + 5c6 )e6n + O(e7n )). Dengan menggunakan persamaan (5) diperoleh Pf (xn , yn ) = 2c2 + (−2c4 + 6c2 c3 )e2n + (−4c5 + 4c2 c4 + 12c23 − 12c22 c3 )e3n + (−6c6 + 24c32 c3 − 42c2 c23 + 26c3 c4 + 2c22 c4 + 2c2 c5 )e4n + (28c3 c5 + 24c2 c3 c4 + 52c22 c5 − 36c33 − 200c32 c4 + 420c42 c3 − 14c7 − 84c22 c23 − 192c62 + 12c24 )e5n + (−192c72 − 188c22 c3 c4 − 20c4 c5 − 240c2 c33 + 12c22 c6 + 300c32 c23 − 12c3 c6 − 14c7 c2 + 32c32 c5 + 276c52 c3 + 44c2 c24 + 100c23 c4 + 84c2 c3 c5 − 172c42 c4 )e6n + O(e7n ). (16) Pf (xn , yn )f (yn ) dengan menggunakan persamaan, f 0 (yn )2 (13), (14) dan (16) maka diperoleh Selanjutnya hitung Hf (xn , yn ) =
Hf (xn , yn ) = 2c22 e2n + (−4c32 + 4c2 c3 )e3n + (2c42 − 8c22 c3 + 4c2 c4 )e4n + (8c52 − 8c32 c3 + 12c2 c23 − 12c22 c4 − 4c3 c4 + 4c2 c5 )e5n + (−24c62 − 90c22 c23 + 24c33 + 12c32 c4 + 32c2 c3 c4 − 6c24 − 16c22 c5 − 8c3 c5 + 4c2 c6 )e6n + O(e7n ), (17) sehingga 1 1 − Hf (xn , yn ) = 1 − c22 e2n + (−2c2 c3 + 2c32 )e3n + (−2c2 c4 − c42 + 4c22 c3 )e4n 2 + (2c3 c4 − 2c2 c5 − 6c2 c23 + 6c22 c4 − 4c52 + 4c32 c3 )e5n + (−2c2 c6 + 12c62 + 73c32 c3 − 109c42 c3 + 45c22 c23 − 12c33 − 6c32 c4 − 16c2 c3 c4 + 3c24 + 8c22 c5 + 4c3 c5 )e6n + O(e7n ),
Repository FMIPA
(18)
5
dengan menggunakan identitas geometri [5, h. 500], maka diperoleh 1+
1 2
Hf (xn , yn ) = c2 e2n + (−2c22 + 2c3 )e3n + (3c4 − 7c2 c3 + 4c32 )e4n 1 1 − Hf (xn , yn ) 2 + (−8c42 − 6c23 + 20c22 c3 + 4c5 − 10c2 c4 )e5n + (5c6 − 51c32 c3 + 15c52 − 17c3 c4 + 27c22 c4 − 13c2 c5 + 33c2 c23 )e6n + O(e7n ).
(19)
Jika persamaan (19) disubstitusikan ke persamaan (6) maka diperoleh xn+1 = α + (c22 c4 − c32 c3 + c52 )e6n + O(e7n ).
(20)
Karena en+1 = xn+1 − α maka en+1 = (c22 c4 − c32 c3 + c52 )e6n + O(e7n ).
(21)
Persamaan (21) menunjukkan bahwa varian metode Halley memiliki orde kekonvergenan enam [3]. 2 4. UJI KOMPUTASI Selanjutnya akan dilakukan uji komputasi untuk membandingkan kecepatan dalam menemukan akar hampiran dari persamaan nonlinear antara metode Newton (MN), metode Halley (MH), metode Noor (MNR) dan varian metode Halley (VMH). Berikut ini adalah beberapa contoh fungsi [4] dan nilai tebakan awal yang digunakan untuk membandingkan metode-metode tersebut. f1 (x) = x3 + 4x2 − 10 x0 = 1.0 f2 (x) = e−x + cos(x) x0 = 1.0 5x − 1 f3 (x) = x0 = 0.25 4x f4 (x) = ex sin(x) + log(x2 + 1) x0 = 1.2 x f5 (x) = x2 − e − 3x + 2 x0 = 2.2 f6 (x) = sin2 (x) − x2 + 1 x0 = 1.2 f7 (x) = cos(x) − x x0 = 0.1 Untuk melakukan uji komputasi dari ketujuh contoh fungsi nonlinear di atas, digunakan software aplikasi Maple13. Tabel 1 merupakan tabel perbandingan hasil komputasi dari empat metode yang berbeda. Keterangan untuk Tabel 1 adalah, fungsi fi menyatakan fungsi persamaan nonlinear, x0 merupakan tebakan awal iterasi, n merupakan banyaknya iterasi, xn merupakan akar hampiran yang diperoleh dari setiap metode, |f (xn )| merupakan nilai mutlak dari fungsi untuk akar hampiran ke-n dan |xn − xn−1 | merupakan selisih nilai mutlak antara dua akar hampiran yang berdekatan. Sedangkan Tabel 2 merupakan tabel perbandingan NFE atau banyaknya perhitungan fungsi pada setiap iterasi. Repository FMIPA
6
Tabel 1: Perbandingan hasil komputasi dari beberapa metode iterasi Metode n xn |f (xn )| |xn − xn−1 | f1 (x),x0 = 1.0 MN 5 1.365230013414097 3.662513e − 21 2.126976e − 11 MH 3 1.365230013414097 1.502197e − 19 3.698650e − 07 MNR 2 1.365230013414097 4.603558e − 18 4.181575e − 04 VMV 2 1.365230013414097 9.214707e − 25 1.175233e − 04 f2 (x),x0 = 1.0 MN 5 1.746139530408012 1.106865e − 23 7.965566e − 12 MH 4 1.746139530408012 1.459285e − 35 4.489281e − 12 MNR 3 1.746139530408012 2.126089e − 62 1.358919e − 12 VMH 2 1.746139530408012 6.910824e − 45 1.524821e − 07 f3 (x),x0 = 0.25 MN 5 0.200000000000000 6.776264e − 20 4.656613e − 11 MH 4 0.200000000000000 0.000000e + 00 5.000000e − 02 MNR 3 0.200000000000000 6.445481e − 71 1.615403e − 15 VMH 2 0.200000000000000 3.802663e − 22 5.186722e − 05 f4 (x),x0 = 1.2 MN 7 0.000000000000000 9.860395e − 22 2.220405e − 11 MH 5 0.000000000000000 2.876899e − 35 1.987091e − 12 MNR 3 0.000000000000000 2.930639e − 31 6.810641e − 07 VMH 3 0.000000000000000 2.448421e − 36 6.689076e − 07 f5 (x),x0 = 2.2 MN 5 0.257530285439861 3.634193e − 21 1.014458e − 10 MH 4 0.257530285439861 5.297274e − 29 6.619648e − 10 MNR 3 0.257530285439861 1.872043e − 28 9.210162e − 06 VMH 3 0.257530285439861 1.089289e − 100 7.484145e − 17 f6 (x),x0 = 1.2 MN 5 1.404491648215341 8.130251e − 24 2.044422e − 12 MH 3 1.404491648215341 1.220525e − 21 8.775593e − 08 MNR 2 1.404491648215341 3.944218e − 21 1.145160e − 04 VMH 2 1.404491648215341 2.681243e − 28 2.917175e − 05 f7 (x),x0 = 0.1 MN 6 0.7390851332151606 1.000000e − 16 1.030850e − 11 MH 4 0.7390851332151606 3.968365e − 49 1.269707e − 16 MNR 2 0.7390851332151606 6.036409e − 17 1.489574e − 03 VMH 2 0.7390851332151606 1.796714e − 26 4.753816e − 16
Repository FMIPA
7
Tabel 2: Perbandingan nilai NFE dari beberapa metode iterasi f (x) x0 MN MH MNR VMH f1 1.0 10 9 8 8 f2 1.0 10 9 12 8 f3 0.25 10 15 12 8 f4 −0.8 14 15 12 12 f5 2.2 10 12 12 12 f6 1.2 10 9 8 8 f7 0.1 12 12 8 8
Berdasarkan Tabel 1 semua metode yang dibandingkan berhasil menemukan akar yang diharapkan dari semua contoh fungsi yang diberikan. Secara umum dapat dikatakan semua metode yang dibandingkan berhasil menemukan akar hampiran yang diharapkan dari semua fungsi yang diberikan. Jika dilihat dari jumlah iterasi yang diperlukan maka VMH lebih baik dibandingkan dengan metode lainnya. Berdasarkan Tabel 2 dapat disimpulkan bahwa banyak evaluasi fungsi yang dilakukan oleh VMH lebih sedikit dibandingkan dengan metode-metode lain. Untuk menemukan akar hampiran yang diharapkan. UCAPAN TERIMA KASIH Ungkapan terima kasih penulis ucapkan kepada Bapak Supriadi Putra, M.Si. dan Bapak Zulkarnain, M.Si. yang telah meluangkan waktu, pikiran dan tenaga dalam memberikan bimbingan, petunjuk dan pengarahan kepada penulis dalam menyelesaikan artikel ini. DAFTAR PUSTAKA [1] Burden, R. & J. D. Faires. 2011. Numerical Methods, 3th Ed. Brooks Cole, Belmont. [2] Bartle, R. G. & Shebert. R. D. 1999. Introduction to Real Analysis, 4th Ed. Jhon Wiley & Sons, New York. [3] Sharma, J. R. & Guha. R. K. 2011. Some Modified Newton Methods with Fourth-Order Convergence. Advance in Science Research, 2: 240-247. [4] Han, J. Huiqian, He. Aimin, Xu. & Zhongdi. Can. 2011. A Second Derivative Free Variant of Halley’s Method with Sixth Orde Convergence. Journal of Pure and Applied Mathematics: Advances and Applications, 3(2): 195–203. [5] Stewart, J. 2010. Kalkulus Edisi 5 Buku 2. Terjemahan dari Calculus, 5th Ed, Oleh Sungkuno. C. Salemba Teknika, Jakarta.
Repository FMIPA
8
[6] Traub, J. F. 1964. Iterative Methods for the Solution of Equations. Prentice Hall, Englewood Cliffs, New Jersey. [7] Wait, R. 1979. The Numerical Solution of Algebraic Equation. John Wiley & Sons, Chicester. [8] Noor, K. I. & M. A. Noor. 2007. Predictor Corrector Halley Method for Nonlinear Equations. Applied Mathematics and Computation, 188: 1587–1591.
Repository FMIPA
9
