METODE ORDE-TINGGI UNTUK MENENTUKAN AKAR DARI PERSAMAAN NONLINEAR I. P. Edwar1∗ , M. Imran2 , L. Deswita2 1
Mahasiswa Program Studi S1 Matematika Laboratorium Matematika Terapan, Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Riau Kampus Binawidya Pekanbaru (28293), Indonesia 2
∗
[email protected]
ABSTRACT We discuss a derivation of a high-order iterative method based on Taylor expansion of a nonlinear function. The method is a special case of the method derived by Germani, A., et al. in Journal of Optimization Theory and Applications. 131 (2006). 347-364. We show analytically with a different technique from those of Germani that the method is of four order. The numerical simulation using four nonlinear functions shows that the performance of the method is better than those of Newton method, Traub method, Halley method, and Chebyshev method. Keywords: high-order method, iterative method, Newton method, nonlinear equation ABSTRAK Skripsi ini membahas metode orde-tinggi yang diturunkan berdasarkan ekspansi Taylor dan merupakan hal khusus dari artikel Germani, A., et al., Journal of Optimization Theory and Applications. 131 (2006). 347-364. Secara analitik dengan teknik yang berbeda dengan teknik yang digunakan Germani ditunjukkan bahwa metode orde-tinggi yang diperoleh berorde empat. Hasil simulasi menggunakan empat fungsi nonlinear menunjukkan bahwa metode orde tinggi unggul dari metode Newton, metode Traub, metode Halley, dan metode Chebyshev. Kata kunci: metode iterasi, metode Newton, metode orde-tinggi, persamaan nonlinear 1. PENDAHULUAN Dalam bidang matematika sering ditemui permasalahan yang berkaitan dengan menemukan solusi dari persamaan nonlinear f (x) = 0.
1
(1)
Salah satu metode yang dapat digunakan untuk menyelesaikan persamaan (1) adalah metode numerik, yang menghasilkan solusi hampiran. Metode Newton [3, h.55] merupakan salah satu dari metode numerik yang sering digunakan untuk menyelesaian persamaan nonlinear, yang bentuk iterasinya diberikan oleh f (xk ) xk+1 = xk − (1) , k = 0, 1, 2, . . . . (2) f (xk ) Bila tebakan awal yang diberikan cukup dekat ke akar α, metode Newton konvergen kuadratik [3, h.57]. Metode Newton dapat dinyatakan dalam metode dua langkah juga sering disebut dengan metode Traub [6, h.184], f (xk ) , f (1) (xk ) f (yk ) untuk k ≥ 0. = yk − (1) f (xk )
yk = xk − xk+1
(3) (4)
Metode ini memerlukan 2 perhitungan fungsi dan satu perhitungan derivatif periterasinya. Bila ekspansi Taylor untuk f (x) di sekitar x = xn dilakukan sampai suku ke tiga, maka diperoleh metode Halley [7, h.86] xk+1 = xk −
2f (xk )f (1) (xk ) , 2(f (1) (xk ))2 − f (2) (xk )f (xk )
k = 0, 1, 2, . . . , n,
(5)
dan metode Chebyshev [7, h.88] , xk+1
f (xk ) − = xk − (1) f (xk )
f 2 (xk )f (2) (xk ) 2(f (1) (xk ))3
.
(6)
Metode iterasi (5) dan (6), sama-sama memiliki orde konvergensi tiga. Untuk orde yang lebih tinggi dari tiga, strategi penemuan metode iterasi menggunakan ekspansi Taylor secara langsung mengalami aljabar yang rumit. Untuk mengatasi ini A. Germani, C. Manes, P. Palumbo, dan M. Sciandrone memberikan teknik yang disajikannya dalam artikel ” Higher-Order Method for the Solution of a Nonlinear Scalar Equation ” [4]. Teknis yang dikemukakan Germani inilah yang menjadi bahasan artikel ini yang dibatasi untuk kasus ekspansi Taylor sampai suku ke empat. 2. METODE ORDE-TINGGI Germani [4] menyarankan untuk menyelesaikan persamaan nonlinear (1), dengan menyelesaikan sistem f i (x) = 0, i = 1, . . . , n. (7)
2
Bila n = 3, maka ekspansi Taylor [2, h.184] untuk (7) disekitar x = xk adalah f (3) (xk )(x−xk )3 f (2) (xk )(x−xk )2 + 2! 3! (f 2 )(2) (xk )(x−xk )2 (f 2 )(3) (xk )(x−xk )3 + 2! 3! 3 (2) 2 (f 3 )(3) (xk )(x−xk )3 (f ) (xk )(x−xk ) + 2! 3!
f (xk ) + f (1) (xk )(x − xk ) + f 2 (xk ) + (f 2 )(1) (xk )(x − xk ) + f 3 (xk ) + (f 3 )(1) (xk )(x − xk ) +
=0 =0
(8)
= 0.
Sistem persamaan (8) diubah ke dalam bentuk matriks f (2) (xk ) f (3) (xk ) f (1) (xk ) 0 y1,k f (xk ) 2! 3! (f 2 )(2) (xk ) (f 2 )(3) (xk ) 2 (1) f 2 (xk ) + (f ) (xk ) y2,k = 0 , 2! 3! 3 (2) 3 (3) 0 y3,k f 3 (xk ) (f 3 )(1) (xk ) (f ) 2! (xk ) (f ) 3! (xk )
(9)
dengan
yi,k = (x − xk )i ,
i = 1, 2, 3.
(10)
Sistem persamaan (9) dapat ditulis dalam bentuk 1 1 y1,k 0 Q3 (f (xk )) y2,k = 0 , y3,k 0
(11)
dengan
Q3 (f (xk )) =
1 0 (1) f (xk ) f (xk ) f 2 (xk ) (f 2 )(1) (xk ) f 3 (xk ) (f 3 )(1) (xk )
0
0
f (2) (xk ) 2! (f 2 )(2) (xk ) 2! (f 3 )(2) (xk ) 2!
f (3) (xk ) 3! (f 2 )(3) (xk ) 3! (f 3 )(3) (xk ) 3!
.
(12)
Karena semua subdeterminan dari Q3 (f (xk )) tidak sama dengan nol, maka faktorisasi LU ([1, h.104]) dari (12) ada, yaitu Q3 (f (xk )) = LU,
(13)
dengan
dan
1 0 0 f (xk ) 1 0 L= f 2 (xk ) 2f (xk ) 1 3 2 f (xk ) 3f (xk ) 3f (xk )
0 0 , 0 1
1 0 0 0 f (2) (xk ) f (3) (xk ) 0 f (1) (xk ) . 2! 3! U = 0 0 (f (1) (xk ))2 f (1) (xk )f (2) (xk ) 0 0 0 (f (1) (xk ))3
3
(14)
(15)
Selanjutnya persamaan (11) ditulis menjadi 1 y1,k LU y2,k = y3,k
1 0 . 0 0
(16)
Kemudian persamaan (16) akan diselesaikan dengan forward substitution dan backward substitution sehingga diperoleh f 3 (xk ) , (f (1) (xk ))3 f 2 (xk ) f (2) (xk )f 3 (xk ) = (1) + , (f (xk ))2 (f (1) (xk ))4 2 f (xk ) f (xk ) 1 f (2) (xk ) = − (1) − f (xk ) 2 f (1) (xk ) f (1) (xk ) ! 2 3 1 f (2) (xk ) 1 f (3) (xk ) f (xk ) − − . 2 f (1) (xk ) 6 f (1) (xk ) f (1) (xk )
y3,k = − y2,k y1,k
(17)
Pada persamaan (10) diketahui bahwa y1,k = (x − xk ), maka x = xk + y1,k .
(18)
Bila x dinyatakan dengan xk+1 , maka persamaan (18) menjadi xk+1 = xk + y1,k ,
(19)
dan dengan mensubstitusikan nilai y1,k pada persamaan (17) ke persamaan (19), diperoleh 2 f (xk ) 1 f (2) (xk ) f (xk ) xk+1 = xk − (1) − f (xk ) 2 f (1) (xk ) f (1) (xk ) ! 2 3 1 f (3) (xk ) f (xk ) 1 f (2) (xk ) − − , f (1) (xk ) 6= 0. (20) 2 f (1) (xk ) 6 f (1) (xk ) f (1) (xk ) Persamaan (20) merupakan bentuk iterasi dari metode orde-tinggi. Berikut ini ditunjukkan orde konvergensi metode iterasi (20) sebagaimana disaji Teorema 1. Teorema 1 (Orde Konvergensi) Misalkan f : D → R, dengan D ⊂ R. Misalkan α ∈ D adalah akar sederhana f (x) = 0. Misalkan juga f mempunyai turunan pertama, ke dua, ke tiga, dan ke empat yang kontinu pada D. Jika x0 cukup dekat ke α maka metode iterasi pada persamaan ((20)) mempunyai orde kekonvergenan empat dengan persamaan tingkat error, yaitu F4 5F23 5F2 F3 4 ek+1 = + − ek , 24F1 8F13 12F12 dengan Fj = f (j) (α), j ≥ 1.
4
Bukti Misalkan α adalah akar dari persamaan f (x) = 0 maka f (α) = 0. Asumsikan f (1) (α) 6= 0 dan ek = xk − α. Ekspansi Taylor dari f (xk ) di sekitar xk = α sampai suku ke lima dan mengabaikan suku yang lebih tinggi, diperoleh f (xk ) = f (α) + f (1) (α)(xk − α) + +
f (2) (α)(xk − α)2 f (3) (α)(xk − α)3 + 2! 3!
f (4) (α)(xk − α)4 . 4!
(21)
Karena α adalah akar, maka f (α) = 0 dan persamaan (21) menjadi f (xk ) = F1 ek +
F2 e2k F3 e3k F4 e4k + + , 2 6 24
(22)
dimana Fj = f (j) (α), j ≥ 1. Melalui cara yang sama, ekspansi Taylor dari f (1) (xk ), f (2) (xk ), dan f (3) (xk ) di sekitar xk = α dengan mengabaikan suku ke enam dan seterusnya, didapat F2 ek F3 e2k F4 e3k F5 e4k (1) f (xk ) = F1 1 + , (23) + + + F1 2F1 6F1 24F1 F4 e2k F5 e3k F6 e4k + + , (24) f (2) (xk ) = F2 + F3 ek + 2 6 24 F5 e2k F6 e3k F7 e4k f (3) (xk ) = F3 + F4 ek + + + . (25) 2 6 24 Dari persamaan (23) didapat 1 f (1) (x
k)
=
1
F1 1 +
F2 ek F1
+
F3 e2k 2F1
+
F4 e3k 6F1
+
F5 e4k 24F1
.
(26)
Selanjutnya dengan bantuan deret geometri, persamaan (26) dapat ditulis menjadi 1 1 F3 F22 2 F4 F2 F3 F23 3 F2 ek = − 4 ek − 2 + − 2 + 3 ek + − 2 + f (1) (xk ) F1 F1 2F1 F1 6F1 F13 F1 2 2 4 F2 F4 3F2 F3 F F F5 + − + 33 + 25 − e4k . (27) 3 4 2 3F1 2F1 4F1 F1 24F1 Selanjutnya persamaan (27) dikalikan dengan persamaan (22) dan disederhanakan, sehingga diperoleh e2k F2 F22 F23 7F2 F3 4 f (xk ) F3 F4 3 = ek − + + − e + + ek . (28) f (1) (xk ) 2F1 3F1 2F12 k 8F1 2F13 12F12 Kemudian dihitung
f (2) (xk ) f (1) (xk )
dengan menggunakan persamaan (24) dan persamaan
5
(27) kemudian disederhanakan, diperoleh f (2) (xk ) F2 F22 F3 F4 F23 2 3F2 F3 = + − 2+ + + e ek + − f (1) (xk ) F1 F1 F1 2F12 2F1 F13 k F32 2F22 F4 2F2 F4 3 F24 F4 ek + − 2− 4+ + − 2F1 F1 6F1 F13 3F12 F F F25 5F2 F32 F6 5F22 F4 F2 F4 2 5 + + + + + − 24F12 F15 4F13 24F1 6F13 6F12 5F3 F4 5F23 F3 4 − ek . − 12F12 2F14
(29)
(3)
k) Selanjutnya dihitung ff (1) (x dengan menggunakan persamaan (25) dan persamaan (xk ) (27) kemudian disederhanakan, diperoleh
f (3) (xk ) F3 = + f (1) (xk ) F1
F 2F F32 F2 F4 F5 2 F4 F2 F3 2 3 − e + − − + e k F1 F12 F13 2F12 F12 2F1 k F 2F F2 F32 F23 F3 2F3 F4 F6 F2 F5 3 2 4 + + − − + − e F13 F13 F14 3F12 6F1 2F12 k F F 3 7F F 3F32 F22 F3 F24 F7 F5 F22 3 5 4 2 − − − + + + − F14 24F12 2F14 F15 24F1 2F13 F3 F2 F6 F2 4F3 F2 F4 4 + 33 − 42 − + ek . 4F1 6F1 6F12 3F13
(30)
Bila persamaan (28), (29), (30), disubstitusikan ke persamaan (20), maka setelah penyederhanaan diperoleh 5F23 5F2 F3 4 F4 + xk+1 = xk − ek + − ek , 24F1 8F13 12F12 atau ek+1 =
F4 5F23 5F2 F3 + − 24F1 8F13 12F12
e4k ,
dengan ek+1 = xk+1 − α. Bila diambil nilai mutlak kedua ruas pada persamaan (31), maka didapat |ek+1 | F4 5F23 5F2 F3 = . + − |e4k | 24F1 8F13 12F12
(31)
Dari Definisi Orde Konvergensi [5, h.75] diperoleh kekonvergenan orde empat, maka Teorema terbukti. ✷
6
3. SIMULASI NUMERIK Pada bagian ini dilakukan simulasi numerik yang bertujuan untuk membandingkan banyak iterasi dari metode Newton (MN) (2), metode Traub (MT) (3) dan (4), metode Halley (MH) (5), Metode Chebyshev (MC) (6) dan metode Orde-Tinggi (MOT) (20) dalam menemukan akar dari persamaan nonlinear. Dalam melakukan perbandingan ini, persamaan nonlinear yang digunakan adalah: 1. f (x) = x3 − x + 3,
α = −1.67169988165716
2. f (x) = x3 − 3x2 + 2x + 0.4,
α = −0.15970485276486
3. f (x) = x7 + 2x5 + 3x3 + x2 + x + 1, α = −0.58411442246840 4. f (x) = sin(x2 ) − x2 + 1,
α = −0.58411442246840
Perbandingan ke empat contoh di atas menggunakan program Matlab 7.0.1, dengan menggunakan kriteria pemberhentian program komputasi yang sama untuk setiap metode, yaitu: 1. Jika |f (1) (xk )| = 0, 2. Jika |f (xn+1 )| ≤ T ol, 3. Jika |xk − xk−1 | ≤ T ol. dengan T ol adalah toleransi sebesar 10−10 dan maksimum iterasi 100. Tabel 1 merupakan Tabel perbandingan dari lima metode yang berbeda. Pada Tabel 1 kolom pertama merupakan fungsi, kolom ke dua merupakan tebakan awal yang dinotasikan dengan x0 , kolom ke tiga sampai kolom ke tujuh merupakan metode yang dibandingkan, dan kolom terakhir merupakan nilai dari akar real yang dinotasikan dengan α. Tanda ∗ pada jumlah iterasi menyatakan bahwa metode konvergen ke akar yang lain (tidak sama dengan nilai akar yang tertera pada kolom terakhir). Jumlah iterasi 100+ merupakan jumlah iterasi dari metode melebihi maksimum iterasi sedangkan Div (Divergen) menyatakan bahwa iterasi yang dihasilkan tidak menuju ke satu akar. Berdasarkan jumlah iterasi, maka dari Tabel 1 terlihat bahwa terdapat perbedaan yang signifikan antara MN, MT, MH, MC, dan MOT. Masing-masing metode mempunyai keunggulan jumlah iterasi pada setiap tebakan awal yang berbeda. Secara umum MOT lebih unggul dari metode pembanding yang lain.
7
Tabel 1: Perbandingan dari beberapa metode iterasi f (x)
f1
f2
f3
f4
x0 -3.0 -1.0 0.0 1.5 3.0 -0.5 0.0 0.3 1.0 2.0 -1.5 -1.0 0.0 1.0 1.5 -1.2 -1.8 -2.0 -2.9 -3.2
MN 6 6* 100+ 11 100+ 5 4* 7* 60* 19* 8* 6* 7* 10 8* 5 5 5 7* 26
Jumlah MT 4 100+ 57 21 40* 3* 3* 35* 78 100+ 6 4* 12 27 23 4 3* 3* 4* 4*
iterasi metode MH MC MOT 4 4 3* 4 8* 7 7 30 16 5 24 57 6 29 5 3 3* 3 3 3* 3 4* 26 11 47 100+ 19 8 13* 34 5 6 5 4 4* 4 Div 8 5 19 59* 6 11 9 8 3 4 3 4 4 3 4 4 4 100+ 5 4* 13 Div 4
α
-1.67169988165716
-0.15970485276486
-0.58411442246840
-1.39088576481033
DAFTAR PUSTAKA [1] Allaire, G. & S. M. Kaber. 2008. Numerical Linear Algebra. Springer, New York. [2] Bartle, R. G. & D. R. Shebert. 1999. Introduction to Real Analysis, 2nd Ed. John Wiley & Sons, Inc., New York. [3] Faires, J. D & R. L. Burden. 2002. Numerical Methods, 3rd Ed, Brooks Cole, Belmont [4] Germani, A., C. Manes., P. Palumbo., & M. Sciandrone. 2006. Higher-Order Method for the Solution of a Nonlinear Scalar Equation. Journal of Optimization Theory and Applications, 131: 347-364. [5] Mathews, J. H. & K. D. Fink. 1999. Numerical Methods Using MATLAB, 3rd Ed. Prentice Hall, New Jersey. [6] Traub, J. F. 1964. Iterative Methods for Solution of Equations. Prentice Hall.Englewood Cliffs, New Jersey. [7] Wait, R. 1979. The Numerical Solution of Algebraic Equations. John Wiley & Sons, Inc., Chicester.
8
