METODE ITERASI OPTIMAL TANPA TURUNAN BERDASARKAN BEDA TERBAGI Amelia Riski1∗ , Putra. Supriadi2 , Agusni2 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 an iterative method free from derivative based on divided difference for solving nonlinear equation. This iterative method has the convergence of order six and for each iteration it requires four function evaluation, so the efficiency index has 1.565. Further more, the computational tes shows that the discussed method superior, both in the number of function evaluations, as well as the number of iterations needed to get a root. Keywords: divided difference, eficiency index, free derivative method, order of convergence. ABSTRAK Kertas kerja ini membahas metode iterasi tanpa turunan berdasarkan beda terbagi untuk menyelesaikan persamaan nonlinear. Metode iterasi ini mempunyai kekonvergenan orde enam dan pada setiap iterasinya melakukan evaluasi fungsi sebanyak empat kali perhitungan, indek efisiensinya adalah 1.565. Selanjutnya dari uji komputasi terlihat bahwa metode iterasi yang digunakan lebih unggul dari metode pembanding, baik dari perhitungan, maupun jumlah iterasi yang diperlukan untuk mendapatkan akar . Kata kunci: beda terbagi, indek efisiensi, metode iterasi tanpa turunan, orde konvergensi. 1. PENDAHULUAN Menemukan teknik untuk mendapat solusi persamaan nonlinear yang berbentuk f (x) = 0,
(1)
adalah suatu topik yang hangat dalam penelitian di bidang analisis numerik. Hal ini dikarenakan tidak semua kasus persamaan (1) dapat diselesaikan secara secara 1
analitik, seperti polinomial berderajat 5 atau lebih, sehingga solusi numerik menjadi alternatif. Metode numerik yang populer digunakan untuk menyelesaikan persamaan (1) adalah Metode Newton dengan bentuk iterasi xn+1 = xn −
f (xn ) , f ′ (xn )
f ′ (xn ) 6= 0 dan n = 0, 1, 2, · · · ,
(2)
yang memiliki keonvergenan orde dua, [3, h. 97-98]. Dalam perkembangannya banyak peneliti berusaha untuk memodifikasi metode Newton dengan menghindari munculnya turunan di formula iterasi (2), diantaranya adalah Metode Steffensen, dengan bentuk iterasinya adalah xn+1 = xn −
f (xn )2 f (xn + f (xn )) − f (xn )
(3)
dengan kekonvergenan orde dua [5, h. 278]. Metode iterasi lain yang menghindari munculnya turunan adalah yang diturunkan dari metode Potra dan Ptak yang dikemukakan oleh Dehghan-Hajarian, dengan kekonvergenan orde tiga [4]. Metode ini memiliki bentuk iterasi f (xn )2 , f (xn + f (xn )) − f (xn ) f (xn )[f (yn+1 − f (xn )] = xn − . f (xn + f (xn )) − f (xn )
yn+1 = xn −
(4)
xn+1
(5)
Selanjutnya metode Jain [6] dengan bentuk sebagai berikut f (xn )2 , f (xn + f (xn )) − f (xn ) f (xn )3 . = xn − f (xn + f (xn )) − (f (xn ))(f (xn ) − f (yn ))
yn = xn − xn+1
(6) (7)
Pada kertas kerja ini di bagian dua dibahas metode iterasi optimal tanpa turunan berdasarkan beda terbagi yang merupakan review dari artikel F. Soleymani [7], dengan judul ”Eficient Sixth-Order Nonlinear Equation Solver Free from Derivative”, kemudian dilanjutkan di bagian tiga dengan melakukan komputasi numerik terhadap lima fungsi uji. 2. METODE ITERASI OPTIMAL Perhatikan Metode Iterasi Tiga Langkah sebagai berikut f (xn ) , yn = xn − ′ f (xn ) f (yn ) z n = yn − ′ , f (yn ) f (zn ) . xn+1 = zn − ′ f (zn ) 2
(8)
Turunan pertama f ′ (xn ) di x dapat ditaksir dengan menggunakan rumus forward difference[8] yaitu f (xn + f (xn )) − f (xn ) f ′ (xn ) ≈ . (9) f (xn ) Untuk memperoleh metode Iterasi Tiga Langkah yaitu dengan menaksir turunan yang ada pada langkah pertama dengan Forward Difference (9) ke persamaan (8) diperoleh yn = xn −
f (xn )2 . f (wn ) − f (xn )
(10)
Turunan pada langkah kedua dan ketiga ditaksir dengan menngunakan interpolasi linear dan interpolasi kuadratik berdasarkan beda terbagi. Sehingga diperoleh Metode Iterasi Tiga Langkah yang berorde dua [7], f (xn )2 yn = xn − , wn = xn + f (xn ) f (wn ) − f (xn ) f (yn ) (11) , z n = yn − ′ f (yn ) f (zn ) xn+1 = zn − ′ . f (zn )
Dengan menggunakan hubungan wn = (xn + f (xn )) dan definisi beda terbagi [1, h. 111-112], maka yn = xn −
f (xn ) . f [wn , xn ]
(12)
Selanjutnya akan dicari bentuk lain dari f ′ (yn ) dan f ′ (zn ) yaitu dengan cara mengaproksimasi bentuk turunan pertama f ′ (yn ) dan f ′ (zn ) pada persamaan (12). Nilai p1 (t) = a0 + a1 (t − xn ) adalah interpolasi polinomial orde satu untuk f (t), yaitu f (t) ≈ p(t) = a0 + a1 (t − xn ),
(13)
dengan nilai p1 (t)|xn = f (xn ) dan p1 (t)|yn = f (yn ). Sehingga diperoleh f (xn ) = p1 (t)|xn = a0 + a1 (xn − xn ) = a0 ,
(14)
f (yn ) = p1 (t)|yn = a0 + a1 (yn − xn ) = a0 ,
(15)
dan
karena a0 = f (xn ) maka f (yn ) − f (xn ) , yn − xn = f [xn , yn ], a1 = f ′ (yn ).
a1 =
3
(16)
Selanjutnya untuk mencari f ′ (zn ), misalkan f (t) = p2 (t) = b(t − xn )2 + c(t − xn ) + d dengan p2 (t)|xn = f (xn ), p2 (t)|yn = f (yn ), p2 (t)|zn = f (zn ). Menggunakan kondisi ini diperoleh f (xn ) = b(xn − xn )2 + c(xn − xn ) + d = d.
(17)
f (yn ) = b(yn − xn )2 + c(yn − xn ) + f (xn ).
(18)
f (zn ) = b(zn − xn )2 + c(zn − xn ) + f (xn ).
(19)
Dengan menggurangkan persamaan (18) dan (19) akan diperoleh nilai b dan c f [yn , xn ] + f [xn , zn ] , yn − z n (xn − zn )f [xn , yn ] + (yn − xn )f [xn , zn ] c= , yn − z n f (zn ) =f [xn , zn ] − f [xn , yn ] + f [yn , zn ]. b=
(20) (21) (22)
Dengan menggunakan hasil ini maka persamaan (20) dapat ditulis dalam bentuk f (xn ) , wn = xn + f (xn ) yn = xn − f [xn , wn ] f (yn ) z n = yn − , (23) f [xn , yn ] f (zn ) , xn+1 = zn − f [xn , zn ] − f [xn , yn ] + f [yn , zn ]
yang disebut dengan metode Iterasi Optimal Tanpa Turunan Berdasarkan Beda Terbagi.
Teorema 1 (Orde Konvergensi) Misalkan α ∈ I akar sederhana dari fungsi f , f : I → R yang terdiferensial secukupnya pada interval terbuka I. Jika x0 cukup dekat dengan α, maka MIO mempunyai konvergensi orde enam sebagai berikut: en+1 = xn+1 − α =
(1 + c1 )2 c32 (c22 − c1 c3 ) 6 en + O(e7n ). c51
dengan ck = f (k) (α), k = 1, 2, 3, · · · . Bukti: Misalkan α adalah akar dari persamaan f (x) = 0, maka f (α) = 0 dan asumsikan f ′ (α) 6= 0. Misalkan juga en = xn −α. Dengan melakukan ekspansi taylor [2, h.184] terhadap f (xn ) disekitar xn = α sampai orde enam dan mengabaikan orde yang lebih tinggi diperoleh 1 f (xn ) = f (α) + f ′ (α)(xn − α) + f ′′ (α)(xn − α)2 2 7 + · · · + O(xn − α) . 4
(24)
Karena f (α) = 0 dan en = xn − α maka f (xn ) = c1 en + · · · + c6 e6n + O(e7n ),
(25)
dengan ck = f (k) (α), k = 1, 2, 3, · · · . Dan dengan menggunakan bentuk f (xn ) ini diperoleh wn = xn + c1 en + c2 e2n + c3 e3n + c4 e4n + c5 e5n + c6 e6n + O(e7n ).
(26)
Melalui cara yang sama, hasil ekspansi Taylor dari f (wn ) disekitar wn = α adalah f (wn ) =(c21 + c1 )en + (c2 + 3c1 c2 + c2 c21 )e2n + · · · + 8c22 c4 + 7c23 c2 + 7c1 c6 + 7c2 c5 + 7c3 c4 + c3 c32 + 15c6 c21 + 20c6 c31 + 15c6 c41 + 6c6 c51 + c6 c61 + 22c2 c1 c5 + 12c4 c1 c22 + 6c4 c21 c22 + 20c5 c31 c2 + 30c5 c21 c2 (27) + 5c5 c41 c2 + 15c3 c21 c4 + 18c3 c1 c4 + 6c23 c1 c2 + 4c4 c31 c3 + c6 )e6n . Dengan menggunakan hasil yang dibentuk oleh persamaan (24) dan (27) dan dengan menggunakan deret geometri yn = α + (1 +
1 (2 + (2 + c1 )c1 )c22 + c1 (c1 + 1)(c1 + 2) )c2 e2n + · · · − . c1 c21
(28)
Cara yang sama, bentuk ekspansi f (yn ) disekitar yn = α sampai orde enam dan mengabaikan orde yang lebih tinggi diperoleh (2 + c1 (2 + c1 ))c22 2 + (1 + c1 )(2 + c1 )c3 e3n f (yn ) =(1 + c1 )c2 en + c1 7 (29) + · · · + O(en ). Dengan menggunakan definisi beda terbagi untuk f [xn , yn ] dan setelah dilakukan penyederhanaan seperti langkah sebelumnya diperoleh 1 2 3 (−3 + c1 (3 + c1 ))c32 + c1 (1 + c1 )(3 + c1 )c2 c3 4 c1 e n + · · · + en c1 c31 + · · · + O(e7n ),
zn =α +
(30)
dan melakukan ekspansi Taylor terhadap f (zn ) disekitar zn = α sehingga diperoleh 1 2 3 (3 + c1 (3 + c1 ))c32 + c1 (1 + c1 )(3 + c1 )c2 c3 4 f (zn ) =(1 + )c2 en + (− en c1 c21 + · · · + O(e7n ).
(31)
Selanjutnya dengan menggunakan hasil-hasil yang telah diperoleh xn , f (xn ) yn , f (yn ), zn dan f (zn ) maka beda terbagi pada persamaan (20) dapat ditulis sebagai berikut (1 + c21 )c2 (2c22 − c − 1c3 ) 3 en c21 + · · · + O(e7n ), (32)
[f (xn ), f (zn )] + [f (zn ), f (yn )] − [f (xn ), f (yn )] =c1 +
5
sehingga dengan membagi persamaan (31) dan persamaan (32) dan menggunakan langkah terakhir dari persamaan (20) diperoleh xn+1 = α −
(1 + c21 )c32 (c22 − c1 c3 ) 6 en + O(e7n ), c51
(33)
karena en+1 = xn+1 − α maka en+1 =
(1 + c21 )c32 (c22 − c1 c3 ) 6 en + O(e7n ). 5 c1
(34)
Dari definisi orde konvergensi diperoleh kekonvergenan orde enam, maka Teorema terbukti. Pada setiap iterasinya MIO melakukan evaluasi fungsi sebanyak empat kali maka indek efisiensinya adalah 1.565 [7]. 3. SIMULASI NUMERIK Pada bagian ini dilakukan simulasi numerik yang bertujuan untuk membandingkan banyak iterasi dari metode Newton (MN) persamaan (2), metode Steffensen (MS) persamaan (3), metode Dehghan-Hajarian (MDH) persamaan (4)-(5) dan metode Iterasi Optimal Tanpa Turunan Berdasarkan Beda Terbagi(MIO) persamaan (20) dalam menemukan akar dari persamaan nonlinear. Dalam melakukan perbandingan ini, persamaan nonlinear yang digunakan adalah: f1 = (sin(x))2 + x α=0 πx α = 0.333333333333333 f2 = (1 + x3 ) cos( ) + 1.85 2 2 2 f3 = (sin(x)) − x + 1 α = 1.404491648215341 −x f4 = e + sin(x) − 1 α = 2.076831274533113 −x f5 = xe − 0.1 α = 0.111832559158963 Perbandingan kelima contoh di atas menggunakan program MATLAB 5.3 dengan kriteria pemberhentian untuk setiap adalah 1. Jika selisih nilai mutlak antara dua iterasi yang berdekatan bernilai lebih kecil dari toleransi yang diberikan. 2. Jika nilai mutlak fungsi lebih kecil dari tolerasnsi yang diberikan. 3. Jika jumlah iterasi mencapai maksimum iterasi.
6
Tabel 1: Perbandingan Komputasi dan TNE untuk MN, MS, MDH, MJ, MLi dan MIO fi x0 Metode n T N E |f (xn )| |xn − xn−1 | MN 11 22 7.2825e − 017 8.5338e − 009 MS 12 24 9.5219e − 026 2.1819e − 013 −2 MDH 6 18 2.0195e − 028 1.5905e − 012 MJ 7 21 5.0487e − 029 1.8805e − 013 f1 MLi 5 15 5.6167e − 027 1.7489e − 007 MIO 4 16 1.5423e − 024 8.5307e − 005 MN 8 16 5.6798e − 028 2.3890e − 014 MS 9 18 1.8292e − 022 9.5635e − 012 2.0 MDH 5 15 7.8593e − 016 5.0786e − 006 MJ 6 18 1.2925e − 026 7.7640e − 011 MLi 7 21 3.6978e − 032 6.2642e − 009 MIO 4 16 0.0000e + 000 8.5585e − 015 MN 6 12 0.0000e + 000 4.4768e − 011 MS 5 10 0.0000e + 000 2.4151e − 010 0.8 MDH 4 12 0.0000e + 000 2.2828e − 012 MJ 4 12 0.0000e + 000 6.2387e − 012 f2 MLi 3 9 0.0000e + 000 4.6727e − 007 MIO 3 12 2.2204e − 016 2.4036e − 014 MN 5 10 2.2204e − 016 9.8342e − 009 MS 4 8 2.2204e − 016 3.9182e − 010 0.15 MDH 3 9 2.2204e − 016 2.5010e − 007 MJ 3 9 2.2204e − 016 4.5933e − 008 MLi 3 9 0.0000e + 000 1.5072e − 011 MIO 2 8 0.0000e + 000 5.1141e − 005 MN 8 16 3.3307e − 016 1.3323e − 015 MS 6 12 4.4409e − 016 3.9080e − 014 0.6 MDH 4 12 3.3307e − 016 5.3946e − 012 MJ 4 12 4.4409e − 016 2.7699e − 007 f3 MLi 3 9 4.4409e − 016 6.2059e − 006 MIO 3 12 3.3307e − 016 5.2223e − 012 MN 5 10 4.4409e − 016 1.1732e − 008 MS 6 12 3.3307e − 016 1.2541e − 008 2.0 MDH 4 12 4.4409e − 016 2.8824e − 009 MJ 5 15 3.3307e − 016 3.1313e − 012 MLi 3 9 3.3307e − 016 1.0575e − 005 MIO 3 12 3.3307e − 016 1.5251e − 005
7
f
f4
f5
Metode n MN 27 MS 6 −1.6 MDH 4 MJ 4 MLi 3 MIO 3 MN 6 MS 5 1.6 MDH 4 MJ 4 MLi 3 MIO 2 MN 5 MS 6 −0.2 MDH 4 MJ 4 MLi 3 MIO 2 MN 4 MS 5 0.2 MDH 3 MJ 3 MLi 3 MIO 2 x0
T NE 54 12 12 12 9 12 12 10 12 12 9 8 10 12 12 12 9 8 8 10 9 9 12 8
|f (xn )| 2.2204e − 016 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 0.0000e + 000 6.9389e − 017 0.0000e + 000 0.0000e + 000 1.3878e − 017 0.0000e + 000 0.0000e + 000
|xn − xn−1 | 2.6213e − 008 4.9458e − 012 1.3899e − 007 8.2020e − 009 5.0974e − 008 2.0294e − 007 2.1245e − 012 7.4776e − 012 6.1721e − 009 1.3767e − 014 1.1868e − 006 3.2062e − 003 1.3411e − 009 1.1313e − 010 4.4766e − 008 1.9719e − 012 2.9082e − 007 7.9880e − 004 8.2757e − 009 4.5060e − 013 8.8268e − 007 8.3294e − 009 4.8017e − 014 1.4021e − 006
Hasil komputasi untuk setiap metode yang dibandingkan diberikan pada Tabel 1. Berdasarkan komputasi numerik, Tabel 1, tidak terlihat perbedaan yang cukup berarti antara MN, MS, MDGH, MJ, MLi dan MIO baik dari segi iterasi maupun dari tingkat kesalahan (error ). Secara keseluruhan untuk semua komputasi yang dilakukan metode Iterasi Bebas Turunan lebih cepat mencapai akar.
DAFTAR PUSTAKA [1] Atkinson, K. E. 1993. Elementary Numerical Analysis, 2nd Ed. John Wiley & Sons, Inc., New York. [2] Bartle, R. G. & D. R. Shebert. 1999. Introduction to Real Analysis, 3rd Ed. John Wiley & Sons, Inc., New York. [3] Cheney, W.and Kincaid, D. 2004. Numerical Methods for Mathematics and Computing, 6th Edition. Brook/Cole Publishing Company, California
8
[4] Deghan, M., & M. Hajarian, 2010. Some derivative free quadratic and cubic convergence iterative formulas for solving nonlinear equation.Applied Mathematics and Computation. 29:19-31. [5] Gautschi, W. 2011. Numerical Analysis, 2nd . West Lafayette, Indiana. [6] Jain, P. 2007. Steffensen type method for solving nonlinear equation.Applied Mathematics and Computation. 209:206-219. [7] Soleymani, F. 2011. Eficient Sixth-Order Nonlinear Equation Solver Free from Derivative. Computational and Applied Mathematics, 12. h. 2503-2508. [8] Samuer, T. Numerical Analysis. Pearson Education, Inc., Boston. [9] Traub, J.F. 1964. Iterative Methods for the Solution of Equations. Prentice Hall Inc. Englewood Cliffs.
9
