FAMILI METODE ITERASI DENGAN KEKONVERGENAN ORDE TIGA Rahmawati Mahasiswa Program Studi S1 Matematika Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Riau Kampus Bina Widya, Pekanbaru 28293
[email protected]
ABSTRACT In this paper, a new iterative method for solving a nonlinear equation is derived. Using Taylor expansion and geometry series, it is shown that the method has a third-order of convergence. Numerical comparisons show that this method can be used as an alternative method for solving a nonlinear equation. Keywords: Nonlinear equation, iterative method, order of convergence ABSTRAK Pada artikel ini diturunkan sebuah metode iterasi dengan satu parameter untuk menyelesaikan persamaan nonlinear. Secara analitik, menggunakan ekspansi Taylor dan deret geometri ditunjukkan bahwa metode iterasi ini memiliki orde konvergensi tiga. Perbandingan numerik dengan metode orde tiga yang sudah dikenal menunjukkan bahwa metode dan dapat dijadikan sebagai metode alternatif dalam menyelesaikan persamaan nonlinear. Kata kunci: Persamaan nonlinear, metode iteratif, orde konvergensi 1. PENDAHULUAN Matematika merupakan ilmu pengetahuan yang mengalami perkembangan secara terus-menerus dari tahun ketahun. Berkembangnya ilmu pengetahuan matematika akan mempermudah dalam menyelesaikan suatu permasalahan pada bidang sains khususnya pada metode numerik. Metode numerik adalah teknik yang digunakan untuk memformulasikan suatu persoalan matematika sehingga dapat dipecahkan dengan menggunakan operasi perhitungan atau aritmatika biasa dan memiliki penerapan dalam semua bidang sains. Penyelesaian secara numerik umumnya melibatkan proses iterasi, perhitungan berulang dari data numerik yang ada. Jika proses iterasi tersebut dilakukan secara manual, akan membutuhkan waktu yang relatif lama dan akan kemungkinan 1
munculnya nilai kesalahan (error). Pada keadaan demikian ini sangat dibutuhkan untuk mengurangi waktu penyelesaian. Atkinson [1, h. 68-69] menjelaskan bahwa salah satu metode numerik yang sering digunakan untuk mencari akar hampiran dari suatu persamaan nonlinear adalah metode Newton dengan orde konvergensi dua, yang bentuk umumnya adalah xn+1 = xn − dengan
f (xn ) , f ′ (xn )
n = 0, 1, 2, . . . ,
f ′ (xn ) ̸= 0.
Selain metode Newton terdapat beberapa metode lain untuk menyelesaikan persamaan nonlinear, diantaranya metode Ostrowski yang dijelaskan oleh Ostrowski [4, h.253] dan metode Traub yang dikembangkan oleh Traub [7, h.183]. Pembahasan ini merupakan review sebagian dari artikel Ermakov dan Kalitkin [3]. Pada artikel ini di bagian dua dibahas metode iterasi dua langkah dengan satu Parameter dan analisis kekonvergenannya. Kemudian uji komputasi yang dilakukan dibahas pada bagian tiga. 2. METODE ITERASI DUA LANGKAH DENGAN SATU PARAMETER Pada bagian ini dibahas sebuah keluarga iterasi dua titik berparameter tunggal untuk menyelesaikan persamaan nonlinear f (x) = 0. Metode yang dibahas menggunakan modifikasi metode Newton pada langkah pertama dan didefinisikan sebagai skema bertipe Newton yang mana mempunyai tiga evaluasi fungsi. Secara khusus skema damped Newton disajikan oleh Emakov dan Kalitkin [3] dengan bentuk iterasinya sebagai berikut: xn+1 = xn − βn
f (xn ) , f ′ (xn )
n = 0, 1, . . . ,
(1)
dengan βn =
|f (xn )|2 2 |f (xn )| + f (xn −
2 .
f (xn ) ) f ′ (xn )
Diketahui skema metode iterasi dua langkah yn xn+1
f (xn ) = xn − α ′ , n = 0, 1, . . . , f (xn ) f (xn )2 f (xn = xn − , 2 2 bf (xn ) + pf (yn ) f ′ (xn )
(2)
dengan α, b dan p adalah parameter. Metode iterasi pada persamaan (2) dinamakan metode parameter (MP). Parameter b, dan p dipilih pada metode parameter akan 2
ditentukan sedemikian hingga metode parameter memiliki konvergensi berorde setinggi mungkin. Teorema 1 (Analisis kekonvergenan) Misalkan f : I ⊆ R → R dinotasikan sebagai interval terbuka yang didefinisikan pada I. Jika x0 adalah nilai awal yang cukup dekat dengan akar sederhana x∗ dari f (x) maka f (x∗ ) = 0 dan f ′ (α) ̸= 0. Asumsikan bahwa f mempunyai turunan secukupnya pada I. Maka metode iterasi pada persamaan (2) mempunyai orde konvergensi tiga, dengan parameter b = 1 − α + 2α2 1 ,p= 2 ,α∈ / {0, 1} dan memenuhi persamaan error 2 2α 2α (α − 1) en+1 = 2c3 e3n + O(e4n ). Bukti: Misalkan en = xn − x∗ adalah error pada iterasi ke-n, x∗ adalah akar sederhana dari persamaan nonlinear f (x) = 0 sehingga f (x∗ ) = 0 dan f ′ (x∗ ) ̸= 0. Dengan melakukan ekspansi Taylor dari f (x) di sekitar x = x∗ sampai orde ketiga dan mengabaikan orde yang lebih tinggi dan mengevaluasi di titik x = xn diperoleh [2, h. 216-217] 1 f (xn ) = f (x∗ ) + f ′ (x∗ )(xn − x∗ ) + f ′′ (x∗ )(xn − x∗ )2 2! 1 ′′′ ∗ (3) + f (x )(xn − x∗ )3 + O((xn − x∗ )4 ). 3! Kemudian dengan menggunakan ekspansi Taylor dari f (xn ) dilakukan di sekitar x = x∗ sampai orde ketiga dan mengabaikan orde yang lebih tinggi dan mengevaluasi di titik x = xn diperoleh [2, h. 216-217] 1 1 f (xn ) = f ′ (x∗ )en + f ′′ (x∗ )e2n + f ′′′ (x∗ )e3n + O(e4n ). (4) 2! 3! Selanjutnya dengan memfaktorkan f ′ (x∗ ) pada persamaan (4) diperoleh ( ) 1 f ′′ (x∗ ) 2 1 f ′′′ (x∗ ) 3 ′ ∗ f (xn ) = f (x ) en + e + e + O(e4n ), 2! f ′ (x∗ ) n 3! f ′ (x∗ ) n atau
dengan C3 = (5) diperoleh
) ( f (xn ) =f ′ (x∗ ) en + C2 e2n + C3 e3n + O(e4n ) , 1 f (j) (x∗ ) , j! f ′ (x∗ )
(5)
j = 2 dan 3. Selanjutnya dengan menggunakan persamaan f (xn )2 = f ′ (x∗ )2 (e2n + 2C2 e3n ) + O(e4n ).
(6)
Dengan menggunakan ekspansi Taylor dari f ′ (x) dilakukan di sekitar x = x∗ sampai orde ketiga dan mengabaikan orde yang lebih tinggi dan mengevaluasi di titik x = xn diperoleh [2, h. 216-217]
3
f ′ (xn ) = f ′ (x∗ ) + f ′′ (x∗ )(xn − x∗ ) + + O(xn − x∗ )4 .
1 1 ′′′ ∗ f (x )(xn − x∗ )2 + f (4) (x∗ )(xn − x∗ )3 2! 3! (7)
Karena en = xn − x∗ , persamaan (7) dapat ditulis menjadi f ′ (xn ) = f ′ (x∗ ) + f ′′ (x∗ )en +
1 ′′′ ∗ 2 1 f (x )en + f (4) (x∗ )e3n + O(e4n ). 2! 3!
(8)
Selanjutnya dengan memfaktorkan f ′ (x∗ ) pada persamaan (8) diperoleh ( ) f ′′ (x∗ ) + 1 f ′′′ (x∗ ) 2 1 f (4) (x∗ ) 3 f (xn ) = f (x ) 1 + ′ ∗ en e + e + O(e4n ), f (x ) 2! f ′ (x∗ ) n 3! f ′ (x∗ ) n ′
atau
′
∗
( ) f ′ (xn ) = f ′ (x∗ ) 1 + 2C2 en + 3C3 e2n + 4C4 e3n + O(e4n ) .
(9)
Jika persamaan (6) dibagi dengan persamaan (9) diperoleh f (xn ) en + C2 e2n + C3 e3n + O(e4n ) = . f ′ (xn ) 1 + 2C2 en + 3C3 e2n + 4C4 e3n + O(e4n )
(10)
Untuk menyederhanakan persamaan (10) digunakan deret geometri dengan r = 2C2 en + 3C3 e2n + 4C4 e3n + O(e4n ), sehingga diperoleh [6, h. 500] 1 f (xn ) = f (xn ) × ′ , ′ f (xn ) f (xn ) 1 = f (xn ) × , 1+r = f (xn ) × (1 − r + r2 − r3 + O(r4 )), f (xn ) = en + C2 e2n − (−2C3 + 2C22 )e3n + O(e4n ). (11) f ′ (xn ) Dengan mengalikan parameter α pada persamaan (11) diperoleh f (xn ) α ′ =αen + C2 αe2n − (−2C3 + 2C22 )αe3n + O(e4n ). f (xn )
(12)
Selanjutnya persamaan (12) disubstitusikan ke langkah pertama dari persamaan (2) dengan xn = en + x∗ sehingga diperoleh yn = x∗ + (1 − α)en + C2 αCn2 + (2αC3 − 2αC22 )e3n + O(e4n ).
(13)
Dengan cara yang sama seperti sebelumnya, dengan melakukan ekspansi Taylor dari f ′ (xn ) dilakukan di sekitar x = x∗ sampai orde ketiga dan dievaluasi pada titik x = yn dan setelah disederhanakan diperoleh [2, h. 216-217]
4
1 1 f (yn ) = f (x∗ ) + f ′ (x∗ )(yn − x∗ ) + f ′′ (x∗ )(yn − x∗ )2 + f ′′′ (x∗ )(yn − x∗ )3 2 6 ∗ 4 + O(yn − x ) . (14) Karena f (x∗ ) = 0, maka persamaan (14) dapat ditulis menjadi ( f (yn ) = f ′ (x∗ ) (1 − α)en + (C2 + C2 α2 − C2 α)e2n + (C3 + 3C 2 ) − C3 α3 − αC3 − 2C22 α2 )e3n + O(en )4 .
(15)
Kemudian dengan menggunakan persamaan (15) diperoleh ( f (yn )2 = f ′ (x∗ )2 (1 − 2α + α2 )e2n + (2C2 − 4C2 α + 4C − 2α2 ) − 2C2 α3 )e3n + O(e4n ).
(16)
Dengan mengalikan parameter b ke persamaan (6) dan p ke persamaan (16), kemudian dengan melakukan penjumlahan diperoleh ( ) ( bf (xn )2 + pf (yn )2 = f ′ (x∗ )2 b + p(1 − 2x∗ + (x∗ )2 ) e2n + 2bC2 + C(2C2 ) − 4C2 x∗ + 4C2 (x∗ )2 − 2C2 (x∗ )3 ) e3n + O(e4n ). (17) Dengan membagi persamaan (6) dengan persamaan (17) menggunakan deret geometri diperoleh [6, h. 500] f (xn )2 bf (xn )2 + pf (yn )2 ( 3 1 = p + b3 − 6b2 pα + 3b3 pα2 + 3bp2 α4 2 4 (b + p − 2pα + pα ) − 12bp2 α + 18bp2 α2 − 12bp2 α3 + 3b2 p + 3bp2 − 6p3 α5 + 15p3 α2 ) − 20p3 α3 + 15p3 α4 + p3 α6 − 6p3 α ( 1 + − 4p2 c2 α2 b − 10p3 c2 α6 + 10p3 c2 α3 2 4 (b − p − 2pα + pα ) − 20p3 c2 α4 + 20p3 c2 α5 + 2pc2 α3 b2 + 4p2 c2 α5 b + 12p2 c2 α3 b ) − 12p2 c2 α4 b − 2pc2 α2 b2 + 2p3 c2 α7 − 2p3 c2 α2 en ( 1 + − 20c22 p3 α7 − 56c22 p3 α5 − 16c22 p2 α5 b 2 4 (b − p − 2pα + pα ) + 28c22 p2 α4 b + 8c22 p2 α2 b − 4c22 pα3 b2 + 4c22 p2 α6 b + 44c22 p3 α6 + 4c22 p3 α8 + 4c22 p3 α2 + 4c22 pα2 b2 + 44c22 p3 α4 − 24c22 p2 α3 b ) − 20c22 p3 α3 e2n
5
( 3 3 7 1 96p c2 α + 144p3 c32 α5 − 8p3 c32 α2 2 4 (b − p − 2pα + pα ) − 40p3 c32 α8 + 40p3 c32 α3 − 96p3 c32 α4 − 144p3 c32 α6 + 8b2 c32 pα3 − 64bc32 p2 α4 − 16bc32 p2 α6 − 8b2 c32 pα2 + 48bcp2 α3 + 48bc32 p2 α5 ) + 8p3 c32 α9 − 16bc32 p2 α2 e3n + O(e4n ). +
(18)
Dengan mengalikan persamaan (11) dan persamaan (18) diperoleh f (xn )2 f (xn ) 2 2 bf (xn ) + pf (yn ) f ′ (xn ) ( ) 1 =− en −b − p + 2pα − pα2 ( 2pc2 c2 + + 2 2 (−b − p + 2pα − pα ) −b − p + 2pα − pα2 4pc2 α 4pc2 α2 + − (−b − p + 2pα − pα2 )2 (−b − p + 2pα − pα2 )2 ) 2pc2 α3 2bc2 − + e2n 2 2 2 2 (−b − p + 2pα − pα ) (−b − p + 2pα − pα ) ( 2c3 16p2 c22 α5 + − − −b − p + 2pα − pα2 (−b − p + 2pα − pα2 )3 32p2 c22 α2 4b2 c22 + + (−b − p + 2pα − pα2 )3 (−b − p + 2pα − pα2 )3 4p2 c22 40p2 c22 α3 + − (−b − p + 2pα − pα2 )3 (−b − p + 2pα − pα2 )3 2c22 b 16bc22 pα + − (−b − p + 2pα − pα2 )3 (−b − p + 2pα − pα2 )2 16bc22 pα2 32p2 c22 α4 + + (−b − p + 2pα − pα2 )3 (−b − p + 2pα − pα2 )3 4p2 c22 α6 4c22 pα2 + + (−b − p + 2pα − pα2 )3 (−b − p + 2pα − pα2 )2 2c22 pα3 16p2 c22 α − − (−b − p + 2pα − pα2 )2 (−b − p + 2pα − pα2 )3 4c22 pα 2c22 p − + (−b − p + 2pα − pα2 )2 (−b − p + 2pα − pα2 )2 ) 8bc22 p 8bc22 pα3 + − e n3 (−b − p + 2pα − pα2 )3 (−b − p + 2pα − pα2 )3 + O(e4n ).
(19)
6
Agar persamaan (19) memiliki orde tiga, dari koefisien en terbukti satu dan e2n terbukti nol sehingga ) ( 1 en = 1 (20) − −b − p + 2pα − pα2 dan 2pc2 c2 4pc2 α2 + + (−b − p + 2pα − pα2 )2 −b − p + 2pα − pα2 (−b − p + 2pα − pα2 )2 4pc2 α 2pc2 α3 − − (−b − p + 2pα − pα2 )2 (−b − p + 2pα − pα2 )2 2bc2 + = 0. (21) (−b − p + 2pα − pα2 )2 Dari persamaan (20) diperoleh ( ) 1 − =1 −b − p + 2pα − pα2 b = −p + 2pα − pα2 + 1.
(22)
Selanjutnya persamaan (22) disubstitusikan ke persamaan (21) dengan diperoleh c2
(
) 1 1 1 α (α − 1) − 2 + − +1 2α (α − 1) α(α − 1) 2(α − 1) c2 − 1 1 1 − 2 + − +1 2α (α − 1) α(α − 1) 2(α − 1) 2c2 ( ) + 1 1 1 (α − 1) − 2 + − +1 2α (α − 1) α(α − 1) 2(α − 1) 2c2 ( ) − 1 1 1 α(α − 1) − 2 + − +1 2α (α − 1) α(α − 1) 2(α − 1) αc2 ( ) + 2c2 = 0. − 1 1 1 (α − 1) − 2 + − +1 2α (α − 1) α(α − 1) 2(α − 1) 2
(23)
1 − α + 2α2 1 dan p = , serta persamaan (20) dan 2 2 2α 2α (α − 1) (22) disubstitusikan ke dalam persamaan (23) sehingga diperoleh
Selanjutnya nilai b =
f (xn )2 f (xn ) = en + 2C3 e3n + O(e4n ). bf (xn )2 + pf (yn )2 f ′ (xn )
(24)
7
Selanjutnya persamaan (24) disubstitusikan ke langkah ke dua dari persamaan (2) dengan xn = en + x∗ sehingga diperoleh xn+1 = en + x∗ − en + 2c3 e3n + O(e4n ). (25) Karena xn+1 − x∗ = en+1 maka persamaan (25) menjadi en+1 = 2c3 e3n + O(e4n ),
(26)
Persamaan (26) merupakan persamaan error dari metode parameter. Berdasarkan definisi orde konvergensi [5], dapat disimpulkan bahwa metode parameter memiliki orde konvergensi tiga.
3. UJI KOMPUTASI Pada bagian ini, uji komputasi dilakukan untuk membandingkan metode-metode yang dibahas dalam menemukan akar persamaan nonlinear f (x) = 0 antara metode Newton (MN), metode Ostrowski (MO), metode Traub (MT) dan metode parameter (MP). Persamaan nonlinear yang digunakan adalah (i) f1 (x) = x3 − 2, (ii) f2 (x) = (sin(x))2 + x, (iii) f3 (x) = cos(x) − x. Untuk mendapatkan solusi numerik dari ketiga contoh fungsi di atas, digunakan toleransi 1.0 × 10−25 serta kriteria pemberhentian jalannya program komputasi yang ditentukan untuk setiap metode yang dibandingkan, yaitu jika nilai |f (xn )| < toleransi, atau |xn −xn−1 | < toleransi atau jika jumlah iterasi mencapai maksimum iterasi. Hasil komputasi dapat dilihat pada Tabel 1.
8
Tabel 1: Perbandingan Uji komputasi untuk MN, MO, MT dan MP fi
x0 1.2
f1
1.4
1.3
1.9
f2
3.4
3.2
1.5
f3
1.0
0.9
Metode MN MO MT MP MN MO MT MP MN MO MT MP MN MO MT MP MN MO MT MP MN MO MT MP MN MO MT MP MN MO MT MP MN MO MT MP
n 5 3 3 3 5 4 4 4 5 3 3 3 13 6 6 5 7 6 5 5 7 4 4 4 5 3 4 3 8 3 3 3 5 3 3 3
|f (xn )| 7.80e − 42 1.58e − 87 4.17e − 31 4.19e − 28 1.71e − 31 3.03e − 266 3.15e − 69 3.05e − 60 3.69e − 48 5.38e − 100 7.17e − 37 7.34e − 34 8.19e − 30 2.08e − 47 6.55e − 36 1.37e − 28 1.36e − 39 1.34e − 28 4.08e − 42 4.97e − 27 1.57e − 40 1.13e − 39 1.09e − 28 8.21e − 45 5.34e − 32 1.74e − 50 6.53e − 72 4.23e − 34 1.87e − 333 6.00e − 74 1.54e − 31 1.25e − 30 1.89e − 47 2.44e − 86 2.26e − 36 3.24e − 35
|xn − xn−1 | 1.44e − 21 1.78e − 22 4.11e − 11 3.45e − 10 2.13e − 16 3.72e − 67 8.07e − 24 6.68e − 21 9.88e − 25 1.36e − 25 4.93e − 13 4.15e − 12 2.86e − 15 2.14e − 12 1.49e − 12 3.48e − 10 3.69e − 20 1.08e − 07 1.27e − 14 1.15e − 09 1.25e − 20 1.83e − 10 3.79e − 10 1.36e − 15 3.80e − 16 7.98e − 13 3.42e − 24 1.27e − 11 7.12e − 167 1.09e − 18 9.81e − 11 1.81e − 10 7.16e − 24 8.69e − 22 2.40e − 12 5.37e − 12
COC 2.00 4.00 3.00 3.00 2.00 4.00 3.00 3.00 2.00 4.00 3.00 3.00 2.00 4.00 3.00 3.00 2.00 4.00 3.00 3.00 2.00 4.00 3.00 3.00 2.00 4.00 3.00 3.00 2.00 4.00 3.00 3.00 3.00 4.00 3.00 3.00
Pada Tabel 1 dapat dilihat bahwa dengan fungsi dan tebakan awal yang berbeda, semua metode yang dibandingkan berhasil mencapai akar hampiran yang diharap-
9
kan. Secara umum dari semua contoh persamaan nonlinear yang diberikan dengan tebakan awal yang berbeda, tidak terdapat perbedaan yang signifikan dari semua metode. Dapat disimpulkan bahwa metode Parameter terlihat lebih unggul dari metode Newton, tetapi metode Parameter sebanding dengan metode Ostrowski dan metode Traub dari segi jumlah iterasi. Jadi metode parameter dapat dijadikan sebagai metode alternatif untuk menyelesaikan persamaan nonlinear berdasarkan simulasi numerik beberapa contoh fungsi nonlinear yang didiskusikan.
4. KESIMPULAN Berdasarkan pembahasan yang telah dikemukakan pada sebelumnya, dapat disimpulkan bahwa proses untuk mendapatkan metode iterasi yang dibahas pada skripsi ini adalah dengan memodifikasi metode Newton. Selanjutnya dengan menggunakan ekspansi Taylor diperoleh sebuah metode baru yang disebut dengan metode parameter (MP). Selanjutnya secara analitik dengan menggunakan ekspansi Taylor ditunjukkan bahwa metode parameter memiliki orde tiga. Pada simulasi numerik dilakukan uji komputasi untuk empat persamaan nonlinear dengan menggunakan program Maple. Metode yang diuji adalah metode parameter dengan metode pembanding yaitu metode Newton, metode Ostrowski, dan metode Traub. Tebakan awal yang diberikan berpengaruh untuk menentukan akar pendekatan yang dicari, sama dengan metode pembanding. Dapat dilihat melalui simulasi numerik untuk membandingkan keempat metode iterasi yang dibahas pada skripsi ini untuk mencari akar pendekatan suatu persamaan nonlinear. Pada bagian ini terlihat bahwa metode parameter sebanding dengan metode Ostrowski dan metode Traub serta lebih unggul dari metode Newton dari segi jumlah iterasi. Jadi metode parameter dapat dijadikan alternatif dalam menyelesaikan persaman nonlinear. Ucapan Terimakasih Penulis mengucapkan terima kasih kepada Dr. Imran M., M.Sc. yang telah memberikan arahan dan bimbingan dalam penulisan artikel ini. DAFTAR PUSTAKA [1] K. E. Atkinson, An Introduction to Numerical Analysis, Second Edition John Wiley & Son, New York, 1989 [2] R. G. Bartle dan R. D. Shebert, Introduction to Real Analysis, Second Edition., Jhon Wiley & Son, New York, 2001. [3] V. V. Ermakov dan N. N. Kalitkin, The optimal step and regularization for newton’s method, USSR Computh. Math. Phys, 2 (1981), 235-242. [4] A. M. Ostrowski, Solution of Equations and Systems of Equations. Academic Press, New York, 1966. 10
[5] J. R. Sharma, R. K. Guha dan R. Sharma, Some modified Newton’s methods with fourth-order convergence, Advances in Applied Science Research, 2 (2011), 240-247. [6] J. Stewart, Kalkulus Edisi 5 Buku 2. Terjemahan dari Calculus, Fifth Edition, oleh C. Sungkono, Salemba Teknika, Jakarta, 2010. [7] J. F. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall Inc, Englewood Cliffs, 1964.
11
