KELUARGA METODE LAGUERRE DAN KELAKUAN DINAMIKNYA DALAM MENENTUKAN AKAR GANDA PERSAMAAN NONLINEAR Een Susilawati1∗ 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 Laguerre method to find multiple roots of nonlinear equations with a known multiplicity. Analytically, we show that this iterative method has a convergence of order three. Furthermore, by choosing the value of certain parameter in the Laguerre method, we obtained several well-known iterative methods. Using some test functions, we compare the family of Laguerre methods to obtain a root of nonlinear equation by looking at the number iterations of the methods. In addition, comparisons are also made through Basins of Attraction. Keywords: iterative methods, order of convergence, Laguerre method, Basins of Attraction. ABSTRAK Pada artikel ini dibahas keluarga metode Laguerre untuk menyelesaikan persamaan nonlinear berakar ganda dengan multiplisitas diketahui. Secara analitik dengan menggunakan ekspansi Taylor ditunjukkan bahwa metode iterasi ini memiliki orde kekonvergenan tiga. Selanjutnya, dengan memilih nilai parameter tertentu yang ada di keluarga metode Laguerre diperoleh beberapa metode iterasi orde tiga yang sudah dikenal. Perbandingan kecepatan keluarga metode Laguerre dilakukan dengan melihat jumlah iterasi yang diperlukan untuk mendapatkan akar dari beberapa contoh fungsi nonlinear yang diberikan. Perbandingan juga dilakukan melalui Basins of Attraction dari keluarga metode Laguerre Kata kunci: metode iterasi, orde konvergensi, metode Laguerre, Basin of attraction.
JOM FMIPA Volume 2 No. 1 Februari 2015
58
1. PENDAHULUAN Dalam bidang matematika sering ditemui permasalahan yang berkaitan dengan menemukan solusi dari persamaan nonlinear f (x) = 0. Solusi persamaan tersebut tidak selalu berbentuk akar sederhana, ada juga yang merupakan akar ganda dengan multiplisitas m, dengan m > 1. Banyak metode numerik yang dapat digunakan untuk mencari akar dari persamaan nonlinear, salah satunya adalah metode Laguerre yang memiliki kekonvergenan orde tiga[3], dengan bentuk iterasinya yaitu xn+1 = xn −
νf (xn ) p , f ′ (xn ) ± (ν − 1)2 (f ′ (xn ))2 − ν(ν − 1)f (xn )f ′′ (xn )
(1)
n = 0, 1, 2, . . . , ν 6= 0. Apabila dipilih nilai parameter tertentu pada metode Laguerre untuk akar sederhana yaitu ν = 0, 1, 2 dan ∞, secara berurutan diperoleh metode Newton, metode Euler Cauchy, metode Halley dan metode Ostrowski. Penggunaan metode iterasi untuk akar sederhana untuk menentukan akar ganda menyebabkan konvergensi metode tersebut menjadi berkurang, seperti penerapan metode Newton yang konvergen kuadratik menjadi linear jika diterapkan untuk menemukan akar ganda [4, h.354]. Pada artikel ini persamaan (1) dimodifikasi sehingga dapat digunakan untuk menemukan akar ganda persamaan nonlinear, yang merupakan review dari artikel Beny Neta dan Changbum Chun [2]. Untuk itu pada bagian dua didiskusikan pemodifikasian metode Laguerre Dibagian tiga dibahas kasus khusus dari metode Laguerre hasil modifikasi. Dibagian empat diberikan perbandingan numerik dari metode yang dikemukakan dengan metode iterasi untuk akar ganda yang sudah dikenal. Pembahasan ditutup dengan basin of attraction dari metode yang dikemukakan pada tulisan ini. 2. KELUARGA METODE LAGUERRE UNTUK MENENTUKAN AKAR GANDA PERSAMAAN NONLINEAR Metode Laguerre untuk akar sederhana (1) akan dimodifikasi untuk dapat diterapkan ke persamaan nonlinear dengan akar ganda dengan memisalkan f (x) = g(x)m , atau g(x) = f (x)1/m ,
(2)
sehingga g(x) mempunyai akar sederhana. Selanjutnya dengan menghitung g (x) dan g ′′ (x), dan mensubstitusikan ke persamaan (1), setelah penyederhanaan diperoleh n) λ ff′(x (xn ) r xn+1 = xn − (3) h i, f (xn )f ′′ (xn ) λ−m 1 + sign (λ − m) ( m ) (λ − 1) − λ (f ′ (xn ))2 ′
λ dan λ ∈ R. Rumus iterasi (3) merupakan metode dengan n = 0, 1, 2, . . . , ν = m iterasi Laguerre untuk akar ganda.
JOM FMIPA Volume 2 No. 1 Februari 2015
59
Teorema 1 (Orde Konvergensi) Misalkan fungsi f : I ⊂ R → R, memiliki sebuah akar ganda α ∈ I dengan multiplisitas m. Jika x0 cukup dekat dengan α, maka metode iterasi (3) memiliki orde konvergenan tiga dan memenuhi persamaan error (m+1) 2 1 1 f (α) en+1 = 1− 2m(m + 1)2 (λ − m) f (m) (α) (m+2) 1 f (α) − e3n + O(e4n ). (4) m(m + 1)(m + 2) f (m) Bukti: Misalkan α adalah akar dari persamaan nonlinear f (x) = 0. Jika terdapat bilangan asli m dan fungsi kontinu g(x) dengan g(α) 6= 0, sedemikian hingga f (x) dapat dinyatakan sebagai f (x) = (x − α)m g(x). (5) Jadi α adalah akar ganda dari f (x) dengan multiplisitas m. Asumsikan bahwa en = xn − α, kemudian dengan menggunakan ekspansi Taylor[1, h.189] untuk g(xn ) disekitar xn = α sampai orde tiga dan mengabaikan orde yang lebih tinggi, diperoleh
g ′′ (α) 2 e + O(e3n ). (6) 2! n Kemudian dengan mengaproksimasikan x = xn dikedua ruas persamaan (5), dan mesubstitusikan persamaan (6) ke persamaan yang didapat, diperoleh 2 3 f (xn ) = g(α)em (7) n 1 + c1 en + c2 en + O(en ) . g(xn ) = g(α) + g ′ (α)en +
dengan
g (k) (α) , k = 1, 2. (8) g(α) Kemudian melalui cara yang sama, diperoleh ekspansi Taylor dari f ′ (xn ) dan f ′′ (xn ) disekitar xn = α berturut-turut m+1 m+2 2 ′ m−1 3 1+ f (xn ) =mg(α)en c1 e n + c2 en + O(en ) . (9) m 2m m+2 m+1 2 ′′ m−2 c1 e n + c2 e + O(e3n ). (10) 1+ f (xn ) =m(m − 1)g(α)en m−1 2m(m − 1) n ck =
Jika persamaan (7) dibagi dengan persamaan (9), kemudian dengan menggunakan deret geometri setelah penyederhanaan diperoleh f (xn ) 1 en (m + 1)c21 c2 2 3 1 − c1 e n + e + O(en ) . (11) = − f ′ (xn ) m m m2 m n Melalui strategi yang sama diperoleh (m + 1) m−1 m+2 −m2 − 2m − 1 2 f ′′ (xn ) 1+ = c1 e n + c + c2 e2n 2f ′ (xn ) 2en m(m − 1) m2 (m − 1) 1 m(m − 1) 3 + O(en ) . (12) JOM FMIPA Volume 2 No. 1 Februari 2015
60
Kemudian persamaan (12) dikalikan dengan persamaan (11), diperoleh f ′′ (xn ) f (xn ) 2 m−1 3(m + 1) 2 3 1+ = c1 en + − c1 + c2 e2n 2f ′ (xn ) f ′ (xn ) 2m m(m − 1) 2m3 2m2 3 + O(en ) . (13) Selanjutnya dihitung sign (λ − m)
λ−m m
f ′′ (x) f (xn ) (λ − 1) − 2λ 2f ′ (x) f ′ (x ) n
21
dengan meng-
gunakan persamaan (13) dan memperhatikan persamaan p 1 1 1 2 1 + ax + bx2 + O(x3 ) = 1 + ax + − a + b x2 + O(x3 ), 2 8 2
sehingga diperoleh 21 f ′′ (x) f (xn ) λ−m sign (λ − m) (λ − 1) − 2λ ′ m 2f (x) f ′ (xn ) c1 e n λ 2λ − 3m + 3mλ − 3m2 2 3c2 2 3 1− e + O(en ) . + c1 − = −1 + m m 2m2 (λ − m) 2m n (14) Selanjutnya persamaan (11) dan (14) disubstitusikan ke persamaan (3), dan dengan menggunakan bantuan deret geometri serta mengingat en+1 = xn+1 − α diperoleh 1 1 2 2 (15) (c − c2 ) − c e3 + O(e4n ). en+1 = 2m 1 2m(λ − m) 1 n
Dengan menggunakan persamaan (8), persamaan (15) dapat ditulis menjadi ′ 2 (2) ′ 2 1 1 g (α) g (α) g (α) en+1 = − e3n + O(e4n ). (16) − 2m g(α) g(α) 2m(λ − m) g(α)
Perhatikan bahwa f (m+j) (x) dapat dihitung dengan menggunakan aturan Leibniz, yaitu m+j X m + j m! (m+j) f (x) = (x − α)k−j g (k) (α), j = 0, 1, 2. (17) k (k − j)! k=j Jadi dari persamaan (17) diperoleh g (j) (α) =
j! f (m+j) (α), (m + j)!
j = 0, 1, 2.
(18)
Selanjutnya persamaan (18) disubstitusikan ke persamaan (16), kemudian disederhanakan diperoleh (m+1) 2 1 1 f (α) 1 1− en+1 = − 2 (m) 2m(m + 1) λ−m f (α) m(m + 1)(m + 2) (m+2) f (α) e3n + O(e3n ) (19) (m) f (α) JOM FMIPA Volume 2 No. 1 Februari 2015
61
Persamaan error pada persamaan (19) menunjukkan bahwa metode Laguerre untuk akar ganda memiliki orde konvergensi tiga [5]. 3. BENTUK KHUSUS METODE LAGUERRE AKAR GANDA Pada bagian ini diberikan nilai khusus untuk parameter pada Metode Laguerre untuk akar ganda pada persamaan (3), yang menghasilkan metode iterasi yang sudah dikenal. 1. Kasus khusus parameter λ = 1 Jika parameter λ = 2m disubstitusikan ke persamaan (3), setelah disederhanakan diperoleh xn+1 = xn − m
f (xn ) , f ′ (xn )
n = 0, 1, 2 . . . .
(20)
Metode iterasi (20) adalah metode Newton untuk akar ganda yang memiliki kekonvergenan orde dua [4, h.354-355]. 2. Kasus khusus parameter λ = 2m Jika parameter λ = 2m disubstitusikan ke persamaan (3), diperoleh 2m xn+1 = xn − 1+
f (xn ) f ′ (xn )
,
s
n = 0, 1, 2, . . . .
(21)
f (xn )f ′′ (xn ) (2m − 1) − 2m (f ′ (xn ))2
Metode iterasi (21) adalah metode Euler-Cauchy untuk akar ganda yang memiliki kekonvergenan orde tiga [2]. 3. Kasus khusus parameter λ → 0 Jika parameter λ → 0 disubstitusikan ke persamaan (3) dan dengan menggunakan aturan L’Hospital [1, 181], diperoleh
xn+1 = xn −
m+1 2m
f (xn ) f ′ (xn ) , f (xn )f ′′ (xn ) − 2f ′ (xn )2
n = 0, 1, 2, . . . .
(22)
Metode iterasi (22) adalah metode Halley untuk akar ganda yang memiliki kekonvergenan orde tiga [2]. 4. Kasus khusus parameter λ → ∞ Jika parameter λ → ∞ disubstitusikan ke persamaan (3) dan dengan menggunakan proses limit untuk λ → ∞, diperoleh √
xn+1 = xn − s
m
f (xn ) f ′ (xn )
,
n = 0, 1, 2, . . . .
(23)
f (xn )f ′′ (xn ) 1− (f ′ (xn ))2
JOM FMIPA Volume 2 No. 1 Februari 2015
62
Metode iterasi (23) dinamakan metode Ostrowski untuk akar ganda yang memiliki kekonvergenan orde tiga [2]. 4. PERBANDINGAN KOMPUTASI Pada bagian ini dilakukan perbandingan komputasi yang bertujuan untuk membandingkan jumlah iterasi dari metode metode Euler Cauchy untuk akar ganda (MEC2), metode Halley untuk akar ganda (MH2), metode Ostrowski untuk akar ganda (MOT2) dan metode Newton untuk akar ganda (MN2) dalam menemukan akar pendekatan dari persamaan nonlinear. Persamaan nonlinear yang digunakan dalam perbandingan adalah: f1 (x) = (x3 + 4x2 − 10)3 , f2 (x) = (sin(x) − x2 )2 , f3 (x) = (cos(x) − x)3 , f4 (x) = (x3 − 1)4 , f5 (x) = (x2 − 1)2 . Perbandingan kelima contoh di atas menggunakan program Matlab R2013a dengan kriteria pemberhentian adalah jika |f ′ (xn )| < tol, maka metode gagal diterapkan, jika |f (xn+1 )| ≤ tol atau |xn+1 − xn | < tol, maka program sukses dan jika n > maxit, metode gagal setelah maksimum iterasi. Jumlah iterasi maksimum yang diizinkan adalah 100. Hasil perbandingan jumlah iterasi dari empat metode yang berbeda dapat dilihat pada Tabel 1. Tabel 1: Perbandingan Jumlah Iterasi dari Beberapa Metode Iterasi f (x) f1 (x) f2 (x) f3 (x) f4 (x) f5 (x)
x0 0.5 2.0 -1.0 1.0 -1.0 0.5 0.5 2.0 -3.0 3.0
MEC2 3 2 3 3 3 2 2 3 1 1
MH2 3 3 5 5 4 2 3 3 3 3
MOT2 3 2 4 4 3 2 3 2 3 3
MN2 5 4 13 13 7 3 5 5 5 5
Secara keseluruhan berdasarkan Tabel 1, jumlah iterasi dari keempat metode tidak terlihat perbedaan yang signifikan. Namun, secara umum MEC2 lebih baik dari metode pembanding yang lain. 5. BASINS OF ATTRACTION
JOM FMIPA Volume 2 No. 1 Februari 2015
63
Pada bagian ini dibahas cara lain untuk membandingkan metode-metode dari bentuk khusus metode Laguerre untuk akar ganda. Perbandingan diantara metode dilakukan dengan menggunakan Basins of Attraction yang menghasilkan gambar fraktal yang mempermudah untuk melihat jumlah iterasi yang diperoleh untuk berbagai tebakan awal. Untuk membuat gambar fraktal Basins of Attraction, pertama dibuat persegi yang berukuran [−3, 3] × [−3, 3] pada bidang kompleks dan kemudian persegi tersebut dibagi menjadi grid berukuran 100 × 100. Setiap titik (xk , yj ) pada grid tersebut mewakili sebuah bilangan kompleks z = xk + iyj yang dijadikan sebagai tebakan awal untuk metode iterasi yang digunakan. Kriteria pemberhentian metode iterasi adalah |xn+1 − αr | < toleransi, dengan toleransi = 1.0 × 10−15 , αr adalah akar-akar dari fungsi yang digunakan dan jumlah iterasi maksimum adalah 10. Setiap titik pada grid tersebut diwarnai berdasarkan jumlah iterasi yang diperlukan pada setiap metode. Warna dibedakan berdasarkan jumlah iterasi yang konvergen ke akar-akarnya, yaitu jumlah iterasi yang kecil ditunjukkan dengan intensitas warna yang tinggi dan jumlah iterasi yang besar ditunjukkan dengan intensitas warna yang rendah. Untuk iterasi 1 − 5 digunakan warna yang berbeda dan untuk iterasi 6 − 10 digunakan warna yang sama. Sedangkan untuk titik-titik yang divergen ke akar-akarnya digunakan warna hitam. Gambar Basins of Attraction dari empat metode yang dibandingkan dapat dilihat pada Gambar 1 dan Gambar 2. Pada Gambar 1, fungsi f (x) = (x2 − 1)2 memiliki dua akar yang berbeda, maka digunakan dua warna dasar yang berbeda, yaitu warna merah untuk iterasi yang konvergen ke akar α1 = 1 dan warna hijau untuk iterasi yang konvergen ke akar α2 = −1. Pada Gambar 1 (a) dapat dilihat bahwa warna basin MEC2 dihasilkan intensitas warna yang tinggi. Hal ini berarti bahwa iterasi yang diperlukan untuk konvergen ke akar-akarnya adalah 1 iterasi. Sedangkan pada Gambar 1 (b) dan (c) terdapat perbedaan iterasi yang diperlukan untuk konvergen ke akar-akarnya. Hal ini terlihat dari perbedaan intensitas warna yang dihasilkan. Berbeda dengan Gambar 1 (a)−(c), pada Gambar 1 (d) terdapat warna hitam, hal ini berarti terdapat tititk-titik yang divergen ke akar-akarnya. Secara umum, berdasarkan Gambar 1 basin MEC2 lebih baik dibandingkan dengan tiga metode lainnya. Fungsi yang digunakan pada Gambar 2 memiliki tiga akar, maka digunakan tiga warna dasar yang berbeda yaitu biru, hijau dan merah. Dari keempat gambar tersebut terlihat bahwa MEC2 lebih baik, karena terlihat dari hampir semua daerah memiliki intensitas yang tinggi yang berarti memiliki sedikit iterasi. Selain itu, setiap titik tebakan awal akan konvergen ke akar yang dekat dengan titik-titik tersebut. Seperti pada Gambar 1, pada basin MN2 terdapat warna hitam yang berarti terdapat titik-titik yang divergen ke akar-akarnya. Berdasarkan Gambar 1 dan Gambar 2, secara umum terlihat bahwa MEC2 lebih baik dibandingkan metode lain.
JOM FMIPA Volume 2 No. 1 Februari 2015
64
(a)
(b)
(c)
(d)
Gambar 1: Basins of Attraction f (x) = (x2 − 1)2 . (a) MEC2 (b) MH2, (c) MOT2 dan (d) MN2
(a)
(b)
(c)
(d)
Gambar 2: Basins of Attraction (c) MOT2 dan (d) MN2
f (x) = (x3 + 4x2 − 10)3 . (a) MEC2 (b) MH2,
JOM FMIPA Volume 2 No. 1 Februari 2015
65
UCAPAN TERIMAKASIH Penulis mengucapkan terima kasih kepada Bapak Supriadi Putra, M. Si dan Bapak Zulkarnain, M. Si yang telah memberikan arahan dan bimbingan dalam penulisan artikel ini. DAFTAR PUSTAKA [1] Bartle, R. G. & Shebert, D. R. 2010. Introduction to Real Analysis, 4th Ed . John Wiley & Sons, Inc., New York. [2] Neta, B. & Chun, C. 2013. On a Family of Laguerre Methods to Find Multiple Roots of Nonlinear Equations. Applied Mathematics and Computation, 219: 10987-11004. [3] Simeunovic, D.M. 2010. A Procedure for Obtaining a Family of Iterative Formulas for Finding Zeros of Functions. Mathematica Moravica, 2:1-5. [4] Ralston, A. & Rabinowitz, P. 1978.A First Course in Numerical Analysis. McGraw-Hill Book company, New York. [5] Weerakoon, S. & Fernando, T.G.I. 2000. A Variant of Newton’s Method with Accelerated Third-Order Convergence. Applied Mathematics Letters, 13:87–93.
JOM FMIPA Volume 2 No. 1 Februari 2015
66
