METODE ITERASI KELUARGA CHEBYSHEV-HALLEY UNTUK MENYELESAIKAN PERSAMAAN NONLINEAR Yuli Syafti Purnama1∗ 1
Mahasiswa Program Studi S1 Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Riau Kampus Binawidya Pekanbaru (28293), Indonesia ∗
[email protected]
ABSTRACT This article discusses the family of Chebyshev-Halley iterative method with two parameters obtained through a linear combination of the Newton methods with one parameter. Analytically it is shown that this method of order three for any value of the two parameters. If the value of the first parameter is equal one and the value of the second parameter can be determined appropriately, so that this method is of order four. Furthermore, the computational test shows that the discussed method is better than Chebyshev method, Halley method and Super Halley method in terms of the error produced in obtaining the estimated root. Keywords: Newton method, Chebyshev-Halley method, order of convergence, nonlinear equation. ABSTRAK Artikel ini membahas metode iterasi keluarga Chebyshev-Halley dengan dua parameter yang diperoleh melalui kombinasi linear dari dua metode Newton dengan satu parameter. Secara analitik ditunjukkan bahwa metode ini berorde tiga untuk sebarang nilai dari kedua parameter. Jika dipilih nilai perameter pertama sama dengan satu dan nilai parameter kedua ditentukan dengan tepat, maka metode ini berorde empat. Selanjutnya dari uji komputasi terlihat bahwa metode yang didiskusikan lebih baik dari pada metode Chebyshev, metode Halley dan metode Super Halley jika dilihat dari error metode dalam mendapatkan akar pendekatan. Kata kunci: Metode Newton, metode Chebyshev-Halley, orde konvergensi, persamaan nonlinear. 1. PENDAHULUAN Salah satu persoalan matematika yang sering dijumpai adalah bagaimana menemukan akar dari persamaan nonlinear yang dinyatakan dalam bentuk f (x) = 0. Tidak semua persamaan nonlinear dapat diselesaikan menggunakan metode analitik, oleh sebab itu penyelesaian dilakukan menggunkan metode numerik. Repository FMIPA
1
Banyak metode numerik yang dapat digunakan untuk mencari solusi dari persamaan nonlinear, beberapa diantaranya adalah seperti metode Newton [2, h. 45] yang memiliki orde konvergensi dua dengan bentuk iterasi xn+1 = xn −
f (xn ) , n = 0, 1, 2, ..., f ′ (xn )
metode Chebyshev [7, h.88] yang memiliki orde konvergensi tiga dengan bentuk iterasi ( ) Lf (xn ) f (xn ) xn+1 = xn − ′ 1+ , n = 0, 1, 2, · · · , f (xn ) 2 metode Halley [7, h.86] yang memiliki orde konvergensi tiga dengan bentuk iterasi ( ) f (xn ) 2 xn+1 = xn − ′ , n = 0, 1, 2, · · · , f (xn ) 2 − Lf (xn ) metode Super-Halley [5] yang memiliki orde konvergensi tiga dengan bentuk iterasi ( ) f (xn ) Lf (xn ) xn+1 = xn − ′ 1+ , n = 0, 1, 2, · · · , f (xn ) 2(1 − Lf (xn )) f (xn )f ′′ (xn ) , dan metode Chebyshev-Halley [4]. f ′ (xn )2 Pada artikel ini akan dibahas metode baru dengan memodifikasi metode Chebyshev-Halley dengan kekonvergenan orde tiga yang diperoleh dengan kombinasi linear dari dua metode Newton, yang bergantung pada parameter β dimana β ∈ R dan dapat ditulis sebagai dengan Lf (xn ) =
Gβ (x) = dimana
1 [Nβ (x) − (1 − 2β) N0 (x)] , 2β
f (x) Nβ (x) = x − ′ f (x)
(
dan N0 (x) = x −
1 1 − βLf (x)
(1)
) ,
f (x) . f ′ (x)
Sehingga diperoleh bentuk iterasi dari metode Chebyshev-Halley dengan kekonvergenan orde tiga tersebut adalah ( ) f (xn ) 1 Lf (xn ) xn+1 = xn − ′ 1+ , (2) f (xn ) 2 1 − βLf (xn ) f (xn )f ′′ (xn ) dengan Lf (xn ) = . Apabila dipilih parameter tertentu pada per(f ′ (xn ))2 1 samaan (2), yaitu β = 0, dan 1, akan diperoleh beberapa metode yang 2 Repository FMIPA
2
sudah dikenal sebelumnya. Selanjutnya dengan memodifikasi persamaan (1) untuk mempercepat iterasi menuju akar atau memperkecil tingkat kesalahannya (error ) dengan dua parameter β yang berbeda yaitu β1 dan β2 sehingga diperoleh metode Chebyshev-Halley dua paramater yang memiliki kekonvergenan paling sedikit orde tiga dan jika dipilih nilai β1 dan β2 yang tepat maka metode ini memiliki kekonvergenan orde empat. Artikel ini merupakan review dari artikel yang berjudul ”On the ChebyshevHalley Family of Iteration Function and the n-th Root Computation Problem”[4]. Pembahasan diawali dengan pendahuluan, dibagian kedua pembahasan tentang metode Chebyshev-Halley satu parameter, kemudian dibagian ketiga pembahasan tentang metode Chebyshev-Halley dua parameter beserta analisa kekonvergenannya dan dibagian empat melakukan uji komputasi. 2. METODE CHEBYSHEV-HALLEY SATU PARAMETER Salah satu metode iterasi yang dapat digunakan untuk menyelesaikan persamaan nonlinear f (x) = 0 adalah metode Chebyshev-Halley yang memiliki orde konvergensi tiga. Metode Chebyshev-Halley diperoleh dengan kombinasi linear dari dua metode Newton f (x) N (x) = x − ′ . (3) f (x) Misalkan β ̸= 0 dan diberikan Gβ (x) seperti pada persamaan (1). Selanjutnya ganti f (x) f (x) pada persamaan (3) dengan ′ β dengan β ∈ R, sehingga diperoleh f (x) f (x) f ′ (x)β Nβ (x) = x − ( )′ , f (x) f ′ (x)β kemudian dengan menggunakan turunan (
f (x) f ′ (x)β
)′ =
(4)
u diperoleh v
1 (f ′ (x))β−1
− βf (x)
f ′′ (x) (f ′ (x))β+1
.
(5)
Selanjutnya dengan mensubstitusikan persamaan (5) ke persamaan (4), diperoleh ( ) f (x) 1 Nβ (x) = x − ′ . (6) f (x) 1 − βLf (x) Berdasarkan persamaan (4) dengan mengganti nilai β menjadi 0 diperoleh N0 (x) = x −
Repository FMIPA
f (x) . f ′ (x)
(7)
3
Kemudian dengan mensubstitusikan persamaan (6) dan (7) ke dalam persamaan (1) sehingga diperoleh ( ) f (x) 1 Lf (x) Gβ (x) = x − ′ 1+ . (8) f (x) 2 1 − βLf (x) Berdasarkan persamaan (8) diperoleh bentuk iterasi dari metode Chebyshev-Halley adalah sebagai berikut ( ) f (xn ) 1 Lf (xn ) xn+1 = xn − ′ , (9) 1+ f (xn ) 2 1 − βLf (xn ) f (xn )f ′′ (xn ) . (f ′ (xn ))2 Metode Chebyshev-Halley pada persamaan (9) memiliki orde konvergensi tiga [4]. dengan Lf (xn ) =
Selanjutnya perhatikan kembali persamaan (9). Jika diambil tiga variasi nilai 1 yang berbeda untuk parameter β, misalkan β = 0, β = , dan β = 1 maka akan 2 diperoleh metode iterasi lainnya sebagai berikut: • untuk β = 0, maka akan dipeoleh metode Chebyshev, 1 • untuk β = , maka akan dipeoleh metode metode Halley, 2 • untuk β = 1, maka akan dipeoleh metode metode Super Halley.
3. METODE CHEBYSHEV-HALLEY DUA PARAMETER Selanjutnya perhatikan kembali persamaan (1). Jika diambil dua nilai berbeda dari parameter β, misalkan β1 dan β2 dimana β1 , β2 ∈ R\{0}, β1 ̸= β2 dan berdasarkan kombinasi linear 1 Gβ1 ,β2 (x) = ((1 − 2β1 )Nβ2 (x) − (1 − 2β2 )Nβ1 (x)) (10) 2(β2 − β1 ) dimana Nβ1 dan Nβ2 adalah metode Newton dengan parameter β1 dan β2 seperti pada persamaan (6), yaitu ( ) f (x) 1 Nβ1 (x) = x − ′ , (11) f (x) 1 − β1 Lf (x) dan
f (x) Nβ2 (x) = x − ′ f (x)
(
1 1 − β2 Lf (x)
) .
(12)
Kemudian dengan mensubstitusikan persamaan (11) dan (12) ke persamaan (10) diperoleh ( ) 1 ( 1 − (β1 + β2 ) − Lf (x) ) f (x) 2 Gβ1 ,β2 (x) = x − ′ . (13) f (x) 1 − (β1 + β2 )Lf (x) + β1 β2 L2f (x) Repository FMIPA
4
Persamaan (13) disebut metode Chebyshev-Halley dua parameter. Bentuk iterasi dari persamaan (13) adalah sebagai berikut ( ) 1 ( 1 − (β1 + β2 ) − Lf (xn ) ) f (xn ) 2 xn+1 = xn − ′ , (14) f (xn ) 1 − (β1 + β2 )Lf (xn ) + β1 β2 L2f (xn ) dengan Lf (xn ) =
f (xn )f ′′ (xn ) , β1 , β2 ∈ R\{0}, β1 ̸= β2 . (f ′ (xn ))2
Analisa Kekonvergenan Metode Chebyshev-Halley Dua Parameter Teorema 1 Misalkan α ∈ I adalah akar sederhana dari fungsi f : I → R yang terdiferensialkan secukupnya untuk interval buka I. Jika x0 cukup dekat ke α, maka orde konvergensi dari metode Chebyshev-Halley dua parameter yang didefinisikan oleh persamaan (14) mempunyai orde konvergensi tiga. Apabila dipilih nilai β1 = 1 1 c3 dan β2 = maka metode Chebyshev-Halley dua parameter mempunyai orde 2 c22 konvergensi empat. Bukti: Misalkan α adalah akar sederhana dari f (x) = 0 maka f (α) = 0, dan f ′ (α) ̸= 0. Kemudian dengan melakukan ekspansi Taylor, untuk f (xn ) disekitar xn = α sampai orde ke empat diperoleh (xn − α) (xn − α)2 (xn − α)3 + f ′′ (α) + f ′′′ (α) 1! 2! 3! 4 (xn − α) + f ′′′′ (α) + O(e5n ). 4!
f (xn ) = f (α) + f ′ (α)
(15)
Karena f (α) = 0 dan en = xn − α, maka persamaan (15) dapat ditulis menjadi f (xn ) = f ′ (α)en + f ′′ (α) atau
e2n e3 e4 + f ′′′ (α) n + f ′′′′ (α) n + O(e5n ), 2! 3! 4!
) ( f ′′ (α) 2 f ′′′ (α) 3 f ′′′′ (α) 4 5 f (xn ) = f (α) en + e + e + e + O(en ) , 2!f ′ (α) n 3!f ′ (α) n 4!f ′ (α) n ′
f (k) (α) , k = 2, 3, ..., maka persamaan (16) menjadi k!f ′ (α) ) ( f (xn ) = f ′ (α) en + c2 e2n + c3 e3n + c4 e4n + O(e5n ) .
(16)
dengan memisalkan ck =
(17)
Selanjutnya dengan menggunakan ekspansi Taylor untuk f ′ (xn ) disekitar xn = α, setelah dilakukan penyederhanaan maka diperoleh ) ( (18) f ′ (xn ) = f ′ (α) 1 + 2c2 en + 3c3 e2n + 4c4 e3n + O(e4n ) , Repository FMIPA
5
dan (f ′ (xn )) = (f ′ (α)) 2
2
(
( ) 1 + 4c2 en + 4c22 + 6c3 e2n + (12c2 c3 + 8c4 ) e3n ( ) ) + 16c2 c4 + 9c23 e4n + O(e4n ) .
(19)
Kemudian dengan cara yang sama digunakan ekspansi Taylor untuk f ′′ (xn ) disekitar xn = α, diperoleh ( ) f ′′ (xn ) = f ′ (α) 2c2 + 6c3 en + 12c4 e2n + O(e3n ) . (20) Selanjutnya dari persamaan (17) dan (18) diperoleh en + c2 e2n + c3 e3n + c4 e4n + O(e5n ) f (xn ) = . f ′ (xn ) 1 + 2c2 en + 3c3 e2n + 4c4 e3n + O(e4n )
(21)
Kemudian dengan menggunakan deret geometri, untuk r = 2c2 en + 3c3 e2n + 4c4 e3n + O(e4n ), sehingga setelah disederhanakan persamaan (21) menjadi, ( 2 ) 3 ( ) f (xn ) 2 3 + = e − c e 2 c − c e + −4c + 7c c − 3c + O(e5n ). (22) n 2 3 2 3 4 n 2 n 2 ′ f (xn ) Maka Lf (xn ) yang ditunjukkan oleh persamaan (14) dapat ditulis dalam bentuk ( ) ( ) Lf (xn ) = 2c2 en + 6c3 − 6c22 e2n + 16c32 − 28c2 c3 + 12c4 e3n ( ) + −40c42 + 100c22 c3 − 30c32 − 50c2 c4 e4n + O(e5n ), (23) dan L2f (xn ) = 4c22 e2n + (+24c2 c3 − 24c32 )e3n + (36c23 + 100c42 − 184c22 c3 + 48c2 c4 )e4n + O(e5n ).
(24)
Sehingga ( ) 1 1 − (β1 + β2 ) − Lf (xn ) 2 = 1 + (−2β2 c2 − 2β1 c2 + c2 )en + (6β1 c22 − 6β1 c3 − 6β2 c3 + 6β2 c22 − 3c22 + 28β1 c2 c3 + 3c3 )e2n + (6c4 − 16β1 c32 + 8c32 − 16β2 c32 − 12β2 c4 − 12β1 c4 − 14c2 c3 + 28β2 c2 c3 )e3n + (30β1 c23 + 40β2 c42 + 50β1 c2 c4 − 25c2 c4 + 30β2 c23 − 100β2 c22 c3 + 40β1 c42 + 50β2 c2 c4 − 20c42 − 15c23 − 100β1 c22 c3 + 50c22 c3 )e4n + O(e5n ). (25) Selanjutnya menghitung 1 − (β1 + β2 )Lf (xn ) + β1 β2 L2f (xn ) menggunakan persamaan (23) dan (24), diperoleh 1 − (β1 + β2 )Lf (xn ) + β1 β2 L2f (xn ) = 1 + (−2β2 c2 − 2β1 c2 )en + (6β1 c22 + 6β2 c22 − 6β1 c3 − 6β2 c3 + 4β1 β2 c22 )e2n + (−24β1 β2 c32 − 16β1 c32 − 12β2 c4 − 12β1 c4 − 16β2 c32 + 24β1 β2 c2 c3 + 28β2 c2 c3 + 28β1 c2 c3 )e3n + (30β1 c23 + 40β2 c42 + 50β2 c2 c4 + 50β1 c2 c4 + 40β1 c42 + 36β1 β2 c23 + 100β1 β2 c42 − 100β2 c22 c3 − 100β1 c22 c3 (26) − 184β1 β2 c22 c3 + 48β2 β2 c2 c4 + 30β2 c23 )e4n + O(e5n ). Repository FMIPA
6
Kemudian dari persamaan (25) dan (26), dengan menggunakan deret geometri dan setelah dilakukan penyederhanaan maka diperoleh ( ) 1 1 − (β1 + β2 ) − Lf (xn ) 2 1 − (β1 + β2 )Lf (xn ) + β1 β2 L2f (xn ) = 1 + c2 en + (−3c22 + 2β2 c22 + 2β1 c22 − 4β1 β2 c22 + 3c3 )e2n + (28β1 β2 c32 − 12β2 c32 + 8c32 + 4β12 c32 − 12β2 c32 − 14c2 c3 − 8β12 c32 β2 + 12β1 c2 c3 + 4β22 c32 − 24β1 β2 c2 c3 + 12β2 c2 c3 + 6c4 − 8β22 c32 β1 )e3n + (24β1 c2 c4 − 92β1 c22 c3 + 24β2 c2 c4 − 92β2 c22 c3 − 36β1 β2 c23 − 136β1 β2 c42 + 220β1 β2 c22 c3 − 48β1 β2 c2 c4 + 18β1 c23 + 50β2 c42 + 18β2 c23 + 50β1 c42 − 36β22 c42 − 36β12 c42 + 8β23 c42 + 8β13 c42 − 15c23 − 25c2 c4 − 20c42 + 50c22 c3 − 72β12 c3 β2 c22 − 72β22 c3 β1 c22 + 36β12 c3 c22 + 36β22 c3 c22 + 80β22 c42 β1 + 80β12 c42 β2 − 16β12 β22 c42 − 16β23 c42 β1 − 16β13 c42 β2 )e4n + O(e5n ). (27) Jika persamaan (27) disubstitusikan ke persamaan (14) maka diperoleh xn+1 = α + (−2β2 c22 − c3 − 2β1 c22 + 2c22 + 4β1 β2 c22 )e3n + (−12β2 c2 c3 + 14β1 c32 − 9c32 − 3c4 + 8β12 c32 β2 + 14β2 c32 + 12c2 c3 + 24β1 β2 c2 c3 + 8β22 c32 β1 − 4β12 c32 − 12β1 c2 c3 − 32β1 β2 c32 − 4β22 c32 )e4n + O(e5n ), (28) karena en+1 = xn+1 − α maka en+1 = ( − 2β2 c22 − c3 − 2β1 c22 + 2c22 + 4β1 β2 c22 )e3n + (−12β2 c2 c3 + 14β1 c32 − 9c32 − 3c4 + 8β12 c32 β2 + 14β2 c32 + 12c2 c3 + 24β1 β2 c2 c3 + 8β22 c32 β1 − 4β12 c32 − 12β1 c2 c3 − 32β1 β2 c32 − 4β22 c32 )e4n + O(e5n ). (29) Berdasarkan Definisi orde konvergensi dan persamaan tingkat kesalahan [6] maka pada persamaan (29) menujukkan bahwa metode iterasi Chebyshev-Halley dua parameter memiliki orde konvergensi tiga. Apabila diambil nilai β1 = 1 dan memilih 1 c3 β2 = 2 maka koefisien e3n sama dengan nol sehingga persamaan (29) menjadi 2 c2 ) ( 2 7c3 3 (30) − c2 − 3c4 + 5c2 c3 e4n + O(e5n ). en+1 = c2 Berdasarkan Definisi orde konvergensi dan persamaan tingkat kesalahan [6] maka persamaan (30) menunjukkan bahwa metode iterasi Chebyshev-Halley dua parameter memiliki orde konvergensi empat.
Repository FMIPA
7
4. UJI KOMPUTASI Pada bagian ini dilakukan uji komputasi untuk membandingkan kecepatan dalam menemukan akar hampiran dari persamaan nonlinear antara metode Chebyshev (MC), metode Halley (MH), metode Super-Halley (MSH), metode Chebyshev-Halley (MCH), dan metode Chebyshev-Halley dua parameter (MCHDP). Berikut ini adalah beberapa contoh fungsi [3],[1] dan nilai tebakan awal beserta akar yang digunakan untuk membandingkan metode-metode tersebut. f1 (x) = sin2 (x) − x2 + 1 x0 = 2.3 α = 1.4044916482153412 f2 (x) = x2 − 5x + 6 x0 = 1.0 α = 2.0000000000000000 −x f3 (x) = x − 2 − e x0 = 2.0 α = 2.1200282389876412 Untuk melakukan uji komputasi dari ketiga contoh fungsi persamaan nonlinear di atas, digunakan program Maple13. Untuk mendapatkan solusi numerik dari ketiga contoh fungsi di atas, terlebih dahulu ditentukan kriteria pemberhentian jalannya program komputasi yang sama untuk semua metode, yaitu jika nilai mutlak fungsi lebih kecil dari toleransi yang diberikan, atau jika selisih nilai mutlak antara dua akar hampiran yang berdekatan bernilai lebih kecil dari toleransi yang diberikan, atau jika jumlah iterasi mencapai maksimum iterasi. Tabel 1 merupakan tabel perbandingan hasil komputasi dari lima metode yang berbeda. Fungsi fn menyatakan fungsi persamaan nonlinear, x0 merupa-kan 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. Berdasarkan Tabel 1 semua metode yang dibandingkan berhasil menemukan akar yang diharapkan dari semua contoh fungsi yang diberikan. Pada semua contoh tampak bahwa metode Chebyshev-Halley (MCH), metode Chebyshev-Halley dua parameter dengan konvergensi orde tiga (MCHDP), memerlukan iterasi yang relatif sedikit atau sama jika dibandingkan dengan metode Chebyshev (MC), metode Halley (MH) dan metode Super-Halley (MSH). Oleh karena itu metode Chebyshev-Halley dua parameter dengan konvergensi orde tiga dapat dikatakan sebanding dengan metode berorde tiga lainnya atau dapat dijadikan metode alternatif untuk menyelesaikan persamaan nonlinear berorde tiga.
Repository FMIPA
8
Tabel 1: Perbandingan hasil komputasi dari beberapa metode iterasi Metode n xn |f (xn )| |xn − xn−1 | f1 (x), x0 = 2.3 MC MH MSH MCH MCHDP f2 (x), x0 = 1.0
5 9 6 5 4
1.4044916482153412 1.4044916482153412 1.4044916482153412 1.4044916482153412 1.4044916482153412
1.341011e − 71 2.222147e − 61 5.368109e − 35 8.314178e − 74 1.157327e − 41
1.679494e − 24 1.951391e − 31 7.429238e − 18 3.204809e − 25 5.101564e − 14
MC MH MSH MCH MCHDP f3 (x), x0 = 2.0
5 10 7 5 4
2.0000000000000000 2.0000000000000000 2.0000000000000000 2.0000000000000000 2.0000000000000000
2.497743e − 56 1.656053e − 54 6.002816e − 54 7.547073e − 59 1.337012e − 39
2.320096e − 19 7.429790e − 28 3.464914e − 27 3.474044e − 20 1.883802e − 13
MC MH MSH MCH MCHDP
3 5 4 3 3
2.1200282389876412 2.1200282389876412 2.1200282389876412 2.1200282389876412 2.1200282389876412
2.452184e − 50 3.694783e − 54 8.507592e − 39 4.812443e − 50 4.119228e − 48
1.217931e − 16 4.530093e − 27 5.324657e − 19 1.501499e − 16 5.969782e − 16
Ucapan Terimakasih Penulis mengucapkan terimakasih kepada dosen Pembimbing Bapak Supriadi Putra, M.Si, dan Bapak Khozin Mu’tamar, M.Si yang telah memberikan arahan dan bimbingan dalam penulisan skripsi penulis yang menjadi acuan artikel ini. DAFTAR PUSTAKA [1] Basto, M., Semiao, V., & Calheiros, F. L. 2006. A New Iterative Method to Compute Nonlinear Equations. Applied Mathematics and Computation. 173: 468–483. [2] Burden, R. & Faires, J. D. 2011. Numerical Methods, 3th Ed. Brooks Cole, Belmont. [3] Chun, C. 2007. Some Second-Derivative-Free Variants of Chebyshev-Halley Methods. Applied Mathematics and Computation. 191: 410–414. [4] Dubeau, F. & Gnang, C. 2013. On the Chebyshev-Halley Family of Iteration Functions and the n-th Root Computation Problem. International Journal of Pure and Applied Mathematics. 85: 1051–1059. Repository FMIPA
9
[5] Gutierrez, J. M. & Hernandez, M. A. 1997. A Family of Chebyshev-Halley Type Methods in Banach Spaces. Bull. Austral. Math. Soc. 92: 113–130. [6] Sharma, J. R. & Guha. R.K. 2011. Some Modified Newton Methods with Fourth-Order Convergence. Advance in Science Research. 2: 240–247. [7] Wait, R. 1979. The Numerical Solution of Algebraic Equations. John Wiley & Sons, Inc., Chicester.
Repository FMIPA
10
