PERBANDINGAN METODE RUNGE-KUTTA ORDE EMPAT DAN METODE ADAMS-BASHFORTH ORDE EMPAT DALAM PENYELESAIAN MASALAH NILAI AWAL ORDE SATU Lilik Prasetiyo Pratama Jurusan Matematika, FMIPA UNS
1. LATAR BELAKANG Tidak semua persamaan diferensial biasa dapat ditentukan penyelesaian eksaknya. Oleh karena itu, diperlukan suatu metode untuk menjelaskan penyelesaian tersebut. Salah satu metode tersebut adalah metode numerik. Metode numerik yang digunakan untuk memperoleh penyelesaian masalah nilai awal dapat berupa metode satu step maupun multistep. Dikatakan metode satu step jika penyelesaian di titik x = xn diperoleh berdasarkan penyelasaian di titik sebelumnya, x = xn−1 . Jika dibutuhkan penyelesaian di beberapa titik sebelumnya, disebut metode multistep. Salah satu metode satu step adalah metode Runge-Kutta dam salah satu metode multistep adalah Adams-Bashforth. Karena penyelesaian yang diperoleh dengan metode numerik adalah penyelesaian pendekatan serta dalam proses mendapatkan penyelesaian pendekatan membutuhkan waktu, maka terdapat eror dan lama waktu proses. Oleh karena itu, perlu diteliti keakuratan dan efisiensi metode Runge-Kutta dan Adams-Bashforth, khususnya orde 4. 2. PERUMUSAN MASALAH Dari latar belakang dapat dirumuskan tiga masalah, yaitu (1) bagaimana menurunkan ulang algoritma Runge-Kutta orde empat dan Adams-Bashforth orde empat, (2) bagaimana menerapkan algoritma Runge-Kutta orde empat dan Adams-Bashforth orde empat pada suatu kasus, dan (3) bagaimana keakuratan dan efisiensi metode Runge-Kutta orde empat dan Adams-Bashforth orde empat.
3. TUJUAN Tujuan penulisan artikel ini adalah (1) dapat menurunkan ulang algoritma Runge-Kutta orde empat dan Adams-Bashforth orde empat, (2) dapat menerapkan algoritma Runge-Kutta orde empat dan Adams-Bashforth orde empat pada suatu kasus, dan (3) dapat mengetahui keakuratan dan efisiensi metode Runge-Kutta orde empat dan AdamsBashforth orde empat. 4. PEMBAHASAN Dalam penulisan ini, penurunan algoritma Runge-Kutta orde empat mengacu pada Gear [3]. Sedangkan penurunan algoritma Adams-Bashforth orde empta mengacu pada Burden dan Faires [2] dan Gear [3]. 4.1. Metode Runge-Kutta Orde Empat. Bentuk umum metode Runge-Kutta orde empat adalah: yn+1 = yn + h(c1 k1 + c2 k2 + c3 k3 + c4 k4 )
for n = 0, 1, 2, . . .
k1 = f (xn , yn ) k2 = f xn + µh, yn + hµk1 k3 = f (xn + λh, yn + ρhk2 + (λ − ρ)hk1 ) k4 = f (xn + νh, yn + σhk3 + τ hk2 + (ν − σ − τ )hk1 ). Terdapat sepuluh konstanta c1 , c2 , c3 , c4 , µ, λ, ρ, ν, σ dan τ yang harus ditentukan sehingga eror pemotongan lokalnya O(h4 ) dan eror globalnya O(h5 ). Dalam kasus ini diperoleh delapan persamaan dengan sepuluh variabel: c1 + c2 + c3 + c4 = 1, 1 , 3 1 µ3 c2 + λ3 c3 + ν 3 c4 = , 4 1 σµρc4 = , 24 µ2 c2 + λ2 c3 + ν 2 c4 =
µc2 + λc3 + νc4 =
1 , 2
µρc3 + (λσ + µτ )c4 =
1 , 6
1 , 12 1 µλρc3 + (λσ + µτ )νc4 = . 8 µ2 ρc3 + (λ2 σ + µ2 τ )c4 =
Karena ada delapan persamaan dan sepuluh variabel, maka terdapat banyak sekali penyelesaian. Jika setiap variabel dinyatakan dalam µ dan λ dan dipilih µ = λ = 21 , maka diperoleh ρ=
1 , 6c3
τ = 1 − 3c3 ,
ν = 1, c1 =
1 , 6
c2 =
2 − c3 , 3
c4 =
1 . 6
Jika nilai c3 = 31 , diperoleh metode Runge-Kutta orde empat: yn+1 = yn +
h (k1 + 2k2 + 2k3 + k4 ) 6
for n = 0, 1, 2, . . .
k1 = f (xn , yn ) h , yn + 2 h k3 = f (xn + , yn + 2 k2 = f (xn +
h k1 ) 2 h k2 ) 2
k4 = f (xn + h, yn + hk3 ) 4.2. Metode Adams-Bashforth Orde Empat. Metode Adams-Bashforth diturunkan dengan mengintegralkan persamaan diferensial biasa, y 0 = f (x, y) = f (x, y(x)) pada interval [xn−1 , xn ], diperoleh Z
xn
y(xn ) = y(xn−1 ) +
f (x, y(x))dx.
(4.1)
xn−1
Diperhatikan polinomial berderajat k − 1, pk−1 (x), yang menginterpolasi fungsi f (x, y(x)) pada persamaan (4.1) melalui titik-titik xn−1 , xn−2 , . . ., dan xn−k . Dengan menggunakan bentuk selisih mundur Newton diperoleh polinomial interpolasi pk−1 (x) =
k−1 X i=0
i−1 ∇i fn−1 Y (x − xn−1−j ). i!hi j=0
(4.2)
Dari polinomial interpolasi (4.2), terdapat suatu bilangan ξn−1 pada (xn−k , xn−1 ) dengan f (x, y(x)) = pk−1 (x) +
k−1 f (k) (ξn−1 , y(ξn−1 )) Y (x − xn−1−j ). k! j=0
(4.3)
Dimisalkan x = xn +sh, dengan dx = hds, dan dengan menggunakan definisi fungsi binomial i−1 i−1 Y s+j 1 Y i −s (x − xn−1−j ) = = (−1) , i!hi j=0 i! i j=0 polinomial interpolasi (4.2) menjadi k−1 X
−s pk−1 (x) = (−1) ∇i fn−1 . i i=0 i
(4.5)
Dengan memperhatikan persamaan (4.3) dan (4.5), persamaan (4.1) menjadi "Z
! # Z xn k−1 f (k) (ξn−1 , y(ξn−1 )) Y −s i y(xn ) = y(xn−1 ) + (−1) ∇ fn−1 dx + (x − xn−1−j )dx i k! xn−1 i=0 xn−1 j=0 ! Z 1 Z k−1 k−1 X −s hk+1 1 Y i i = y(xn−1 ) + h (−1) ∇ fn−1 ds + (x − xn−1−j )f (k) (ξn−1 , y(ξn−1 ))ds. i k! 0 0 j=0 i=0 xn
k−1 X
i
Jika (−1)i
R1 0
−s i
ds dievaluasi dengan i = 0, 1, 2, . . . , k − 1 dan y(xn ) ≈ yn serta y(xn−1 ) = yn−1 ,
diperoleh 5 2 3 3 1 ∇ + ∇ + . . . + (−1)i yn = yn−1 + h 1 + ∇ + 2 12 8
Z
1
0
! ! −s k−1 ds∇ fn−1 , i
(4.6)
dengan eror lokal Tn =
hk+1 k!
1 k−1 Y
Z 0
(x − xn−1−j )f (k) (ξn−1 , y(ξn−1 ))ds.
j=0
Ambil i = 3, maka persamaan (4.6) menjadi yn = yn−1 + h(1 +
5 2 3 3 1 ∇+ ∇ + ∇ )fn−1 . 2 12 8
(4.7)
Menurut Gear [3], selisih mundur dapat diekspresikan sebagai nilai fungsi di titik-titik sebelumnya, yaitu q
∇ fn−1
! q X j q fn−1−j . = (−1) j j=0
Akibatnya persamaan (4.7) menjadi yn = yn−1 +
h (55fn−1 − 57fn−2 + 37fn−3 − 9fn−4 ), 24
n = 4, 5, 6, . . .
yang merupakan metode Adams-Bashforth orde empat.
4.3. Estimasi Eror. Jika penyelesaian eksak masalah nilai awal tidak diketahui, maka eror perlu diestimasi dan digunakan ide ekstrapolasi Richardson untuk mengestimasi eror (Apsley, [1]). Ide dari ekstrapolasi RIchardson adalah menghitung eror global pada iterasi ke-n dengan mengambil ukuran step h, y(x) − yn (h), dan 2h, y(x) − yn (2h). Selanjutnya kedua eror tersebut digunakan untuk mengestimasi eror penyelesaian dengan ukuran step h. Jika orde dari algorita yang diterapkan adalah k maka berlaku y(x) − yn (h) ≈ O(hk )
(4.8)
y(x) − yn (2h) ≈ 2k O(hk ).
(4.9)
dan
Persamaan (4.8) dikalikan dengan 2k dan dikurangi dengan (4.9), diperoleh y(x) − yn (h) ≈
1 (yn (h) − yn (2h)). 2k − 1
(4.10)
Dari persamaan (4.10), maka estimasi eror penyelesaian dengan ukuran step h menggunakan algoritma berorde k adalah
1 (yn (h) 2k −1
− yn (2h)).
5. PENERAPAN KASUS Kasus 5.1. Diberikan masalah nilai awal y0 =
2 y + x2 ex , x
1 ≤ x ≤ 2,
y(1) = 0.
(5.1)
Masalah nilai awal (5.1) memiliki penyelesaian eksak y(x) = (−e + ex )x2 . Masalah nilai awal (5.1) diselesaikan dengan metode Runge-Kutta dan Adams-Bashforth orde empat dengan ukuran step h = 0.05, 0.025, 0.0125, dan 0.00625. Karena penyelesaian eksaknya diketahui, maka eror dapat ditentukan dengan mudah. Eror mutlak penyelsaian yang terjadi ditunjukkan pada Tabel 1 dan 2. Tabel 1. Eror mutlak yang terjadi di lima titik, jika digunakan metode Runge-Kutta orde empat untuk masalah nilai awal (5.1) x
h = 0.05
h = 0.025 −6
h = 0.0125 −8
h = 0.00625
−9
3.96844 × 10−10
1.2
1.46608 × 10
9.72005 × 10
6.25675 × 10
1.4
3.36821 × 10−6
2.22485 × 10−7
1.42949 × 10−8
9.05837 × 10−10
1.6
5.70824 × 10−6
3.76061 × 10−7
2.41308 × 10−8
1.5281 × 10−9
1.8
8.49846 × 10−6
5.58772 × 10−7
3.58197 × 10−8
2.26714 × 10−9
2.0
1.17557 × 10−5
7.71724 × 10−7
4.94326 × 10−8
3.12744 × 10−9
Tabel 2. Eror mutlak yang terjadi di lima titik, jika digunakan metode Adams-Bashforth orde empat untuk masalah nilai awal (5.1) x
h = 0.05
h = 0.025
h = 0.0125
h = 0.00625
1.2
1.05098 × 10−5
1.83039 × 10−6
1.54097 × 10−7
1.09364 × 10−8
1.4
7.27928 × 10−5
6.31205 × 10−6
4.54933 × 10−7
3.04141 × 10−8
1.6
1.69735 × 10−4
1.31604 × 10−5
9.09597 × 10−7
5.96966 × 10−8
1.8
3.11111 × 10−4
2.29936 × 10−5
1.55769 × 10−6
1.0129 × 10−7
2.0
5.08352 × 10−4
3.65617 × 10−5
2.44726 × 10−6
1.58234 × 10−7
erorh dengan Orde dari kedua metode dapat ditunjukkan dengan menghitung rasio eror mutlak eror h/2 h = 0.05, 0.025, dan 0.0125 untuk masing-masing metode di titik yang sama. Hasil perhitungan dapat dilihat pada Gambar 1, dengan garis hitam untuk h = 0.05, hitam tebal untuk h = 0.025, dan hitam putus-putus untuk h = 0.0125. RasioErorAB4
RasioErorRK4
14 15.5
12 10 8
15 6
1.2
1.4
1.6
1.8
2.
x
1.2
1.4
1.6
1.8
2.
x
Gambar 1. Rasio eror mutlak h dan h/2 di lima titik, berturut-turut dengan metode Runge-Kutta (kiri) dan Adams-Bashforth (kanan) orde empat.
Dari Gambar 1 terlihat bahwa untuk pengambilan h = 0.05, 0.025, dan 0.0125, rasio eror mutlak erorh ≈ 16. Hal ini menunjukkan bahwa orde dari algoritma yang diterapkan adalah empat. erorh/2 Tabel 1 dan 2 menunjukkan bahwa pada ukuran step h yang sama, eror mutlak penyelesaian dengan metode Runge-Kutta orde empat lebih kecil dibandingkan dengan metode Adams-Bashforth orde erorAB4 empat. Keakuratan kedua metode dapat dibandingkan dengan menghitung rasio eror mutlak eror RK4 pada setiap pengambilan h di titik yang sama. Hasil perhitungan rasio ini dapat dilihat pada Gambar 2, dengan garis hitam untuk h = 0.05, hitam tebal untuk h = 0.025, hitam putus-putus untuk h = 0.0125, dan hitam tebal putus-putus untuk h = 0.00625. RasioRK4_AB4 50
30
10
x 1.2
1.4
1.6
1.8
2.
Gambar 2. Rasio eror mutlak Runge-Kutta dan Adams-Bashforth orde empat untuk berbagai nilai h.
Gambar 2 menunjukkan bahwa untuk pengambilan h = 0.05, 0.025, 0.0125, dan 0.00625, semakin erorAB4 ≈ 50. Hal ini menunjukkan bahwa pada orde kecil ukuran step h maka rasio eror mutlak eror RK4 empat, keakuratan Runge-Kutta adalah 50 kali metode Adams-Bashforth. Dapat disimpulkan, pada orde empat, metode Runge-Kutta lebih akurat daripada metode Adams-Bashforth. Efisiensi dapat dibandingkan dengan menghitung lama waktu program berjalan hingga diperoleh penyelesaian pendekatan. Hasil perhitungan lama waktu dapat dilihat pada Tabel 3.
Tabel 3. Lama waktu proses dengan menggunakan metode Runge-Kutta dan metode Adams-Bashforth orde empat dengan ukuran step h = 0.05, 0.025, 0.0125, dan 0.00625 h
0.05
0.025
0.0125
0.00625
Runge-Kutta orde 4
0.
0.
0.016
0.016
Adams-Bashforth orde 4
0.
0.
0.
0.015
Tabel 3 menunjukkan bahwa pada ukuran step h yang sama, dengan h = 0.05, 0.025, 0.0125, dan 0.00625, lama waktu proses program Adams-Bashforth orde empat lebih cepat daripada Runge-Kutta orde empat. Dapat disimpulkan, pada orde empat, metode Adams-Bashforth lebih efisien daripada metode Runge-Kutta. Kasus 5.2. Diberikan masalah nilai awal, y 0 = 2yx2 + 4,
0 ≤ x ≤ 1,
y(0) = 1
(5.2)
dengan penyelesaian eksak tidak diketahui. Masalah nilai awal (5.2) diselesaikan menggunakan metode Runge-Kutta dan Adams-Bashforth orde empat dengan pengambilan h = 0.01, 0.005, 0.0025, dan 0.00125. Karena penyelsaian eksak tidak diketahui, maka dihitung estimasi eror penyelesaian pendekatan masalh nilai awal (5.1) menggunakan persamaan (4.10) dengan k = 4. Hasil dapat dilihat pada Tabel 4 dan 5. Tabel 4. Estimasi eror mutlak yang terjadi di lima titik, jika digunakan metode Runge-Kutta orde empat untuk masalah nilai awal (5.2) x
h = 0.01
h = 0.005
h = 0.0025 3.5838 × 10
2.25005 × 10−15
7.31522 × 10−11
4.44749 × 10−12
2.74033 × 10−13
1.68458 × 10−14
0.6
2.34259 × 10−10
1.43221 × 10−11
8.84981 × 10−13
5.45934 × 10−14
0.8
6.45591 × 10−10
3.93365 × 10−11
2.42496 × 10−12
1.4951 × 10−13
1.0
3.26739 × 10−9
2.0118 × 10−10
1.24677 × 10−11
7.7307 × 10−13
1.00909 × 10
0.4
−13
−14
h = 0.00125
5.92548 × 10
0.2
−11
Tabel 5. Estimasi eror mutlak yang terjadi di lima titik, jika digunakan metode Adams-Bashforth orde empat untuk masalah nilai awal (5.2) x
h = 0.01
h = 0.005 −6
h = 0.0025 −7
h = 0.00125
−8
6.22673 × 10
7.55733 × 10−9
0.2
4.67395 × 10
5.26968 × 10
0.4
4.9679 × 10−6
5.55097 × 10−7
6.51684 × 10−8
7.87897 × 10−9
0.6
5.8923 × 10−6
6.41212 × 10−7
7.38759 × 10−8
8.83151 × 10−9
0.8
8.41693 × 10−5
8.65814 × 10−7
9.55323 × 10−8
1.11123 × 10−8
1.0
1.59121 × 10−5
1.49251 × 10−6
1.51566 × 10−7
1.6622 × 10−8
esterorh Orde dari kedua metode dapat ditunjukkan dengan menghitung rasio estimasi eror mutlak esteror h/2 dengan h = 0.01, 0.005, dan 0.0025 untuk masing-masing metode di titik yang sama. Hasil perhitungan dapat dilihat pada Gambar 3, dengan garis hitam untuk h = 0.01, hitam tebal untuk h = 0.005, hitam putus-putus untuk h = 0.0025. RasioEstErorAB4
RasioEstErorRK4 17.
10.5 10.
16.5
16. 9.
0.2
0.4
0.6
0.8
1.
x 0.2
0.4
0.6
0.8
1.
x
Gambar 3. Rasio estimasi eror mutlak h dan h/2 di limat titik, berturut-turut dengan metode RungeKutta (kiri) dan Adams-Bashforth (kanan) orde empat.
Dari Gambar 3 terlihat bahwa untuk pengambilan h = 0.01, 0.005, dan 0.0025 rasio estimasi eror esterorh ≈ 16. Hal ini menunjukkan bahwa orde dari algoritma yang diterapkan adalah mutlak esteror h/2 empat. Tabel 4 dan 5 menunjukkan bahwa pada ukuran step h yang sama, estimasi eror mutlak penyelesaian dengan metode Runge-Kutta orde empat lebih kecil dibandingkan dengan metode Adams-Bashforth orde empat. Hal ini menunjukkan bahwa pada orde empat, pada orde empat, metode Runge-Kutta lebih akurat daripada metode Adams-Bashforth. Efisiensi dapat dibandingkan dengan menghitung lama waktu program berjalan hingga diperoleh penyelesaian pendekatan. Hasil perhitungan lama waktu dapat dilihat pada Tabel 3. Tabel 6. Lama waktu proses dengan menggunakan metode Runge-Kutta dan metode Adams-Bashforth orde empat dengan ukuran step h = 0.01, 0.005, 0.0025, dan 0.00125 h
0.01
0.005
0.0025
0.00125
Runge-Kutta orde 4
0.
0.
0.015
0.031
Adams-Bashforth orde 4
0.
0.
0.
0.015
Tabel 6 menunjukkan bahwa pada ukuran step h yang sama, dengan h = 0.01, 0.005, 0.0025, dan 0.00125, lama waktu proses program Adams-Bashforth orde empat lebih cepat daripada Runge-Kutta orde empat. Dapat disimpulkan, pada orde empat, metode Adams-Bashforth lebih efisien daripada metode Runge-Kutta.
6. KESIMPULAN Dari pembahasan dan penerapan kasus, diperoleh kesimpulan (1) Algoritma Runge-Kutta orde empat adalah yn+1 = yn +
h (k1 + 2k2 + 2k3 + k4 ) 6
for n = 0, 1, 2, . . .
k1 = f (xn , yn ) h , yn + 2 h k3 = f (xn + , yn + 2 k2 = f (xn +
h k1 ) 2 h k2 ) 2
k4 = f (xn + h, yn + hk3 ) dan algoritma Adams-Bashforth orde empat adalah yn = yn−1 +
h (55fn−1 − 57fn−2 + 37fn−3 − 9fn−4 ), 24
n = 4, 5, 6, . . . ,
(2) pada orde empat, metode Runge-Kutta lebih akurat dibandingkan metode Adams-Bashforth, (3) pada orde empat, metode Adams-Bashforth lebih efisien daripada metode Runge-Kutta. Pustaka [1] Apsley, D., Initial Value Problem, http://personalpages.umist.ac.uk/staff/david.d.apsley/lectures/numeric/initialvalue.pdf [2] Burden, R. L. and Faires, J. D., Numerical Analysis, Brooks/Cole, California, 2001. [3] Gear, J. A., Numerical Solution of Ordinary Differential Equation, Royal Melbourne Institute of Technology Ltd, Melbourne, 1992.
Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, UNS, Jl. Ir. Sutami 36A, Kentingan, Surakarta, 57126 E-mail :
[email protected]