Vol. 12, No. 2,  111-119,  Januari  2016
Penurunan Syarat Orde Metode Runge-Kutta dengan Deret Butcher
Muhtar 

## Abstrak
Tulisan  ini  membahas  aplikasi  deret  Butcher  dalam  penurunan  syarat  orde  metode  Runge- Kutta.  Penurunan  deret  Butcher  didasarkan  pada  deret  Taylor  dengan  menggunakan representasi  pohon  berakar  terhadap  turunan  elementer  fungsi.  Dengan  menggunakan  deret Butcher,  kompleksitas  penurunan  metode  Runge-Kutta  dengan  menggunakan  deret  Taylor bisa  dihindari.  Penurunan  metode  Runge-Kutta  orde  lima  dipilih  sebagai  contoh  aplikasi. Sistem  persamaan  non-linear  yang  terbentuk  dari  syarat  orde  diselesaikan  dengan  bantuan software Maple. Hasilnya diberikan dua varian metode Runge-Kutta orde lima.
Kata Kunci : Deret  Taylor,  deret  Butcher,  pohon  berakar,  turunan  elementer, pembobot elementer, syarat orde.

## 1. Pendahuluan
Bentuk  umum  metode  Runge-Kutta  eksplisit  dengan s langkah  untuk  menyelesaikan persamaan differensial biasa yang berbentuk
0 0 ( ) ( , ), ( )
y' x f x y y x y = = , (1)
didefinisikan oleh
0 0 1 ( ) ( ) s i i i y x h y x h b k = + = + å
(2)
dimana 1 0 0 ( , ) k f x y = dan 1 0 0 1 , , 2, 3, , ( ) i i i ij j j k f x c h y a k i s - = = + + = å L . (3)
Umumnya i c memenuhi
1 1 , 2, 3, , i i ij j c a i s - = = = å L . (4)
Suatu metode Runge-Kutta orde p harus memenuhi syarat orde ( order condition ) tertentu yang umumnya membentuk sistem persamaan non-linear. Syarat orde ini ditentukan berdasarkan ekspansi  deret  Taylor  kedua  ruas  persamaan  (2)  yang  melibatkan  persamaan  (3)  sebagai  fungsi dari h . Sebagai contoh, sistem persamaaan yang diberikan berikut merupakan syarat orde untuk metode Runge-Kutta orde 3.
 Jurusan Pendidikan Matematika, FKIP, Universitas Dayanul  Ikhsanuddin, Bau-Bau
( ) ( ) 1 2 3 2 21 3 31 32
2 2 2 2 21 3 31 32 3 32 21
1
1 2 1 3 1 6 b b b
b a b a a
b a b a a
b a a + + = + + = + + = =
.
Penurunan  syarat  orde  dari  metode  Runge-Kutta  dengan  menggunakan  ekspansi  deret Taylor  terkadang  sangat  kompleks  dan  kurang  efesien  karena  banyaknya  turunan  fungsi  yang harus dievaluasi. Untuk mengatasi masalah ini, representasi deret Taylor ke dalam deret Butcher dengan  menggunakan  pohon  berakar  ( rooted  tree )  memegang  peranan  penting  dalam  analisis orde metode Runge-Kutta.

## 2. Pohon Berakar
Himpunan dari pohon (berakar) T didefinisikan secara rekursif sebagai berikut, (Hairer et al , 2006):
a) Graf t dengan hanya satu simpul (disebut akar) termuat pada T ;
b) Jika 1 2 , , , m t t t T Î K , maka graf yang ditentukan dengan menghubungkan akar-akar dari
1 2 , , , m t t t K ke  sebuah  simpul  baru  juga  termuat  pada T .  Operasi  ini  dinotasikan  oleh
1 2 [ , , , ] m t t t t = K dan simpul baru tersebut merupakan akar dari t .
Berikut  beberapa  definisi  penting  dari  pohon  berakar  yang  akan  digunakan  dalam  pembahasan selanjutnya.
Definisi 1 . (Rattenburry, 2005) Orde dari pohon berakar t, ( ) r t didefinisikan oleh
1 1 2 1 jika ( ) 1 ( ) ( ) jika [ , , , ] m m t r t r t r t t t t t t ìï = ï = íï + + + = ïî L K
Sebagai contoh, pohon berakar di bawah ini memiliki orde ( ) 8 r t = . a g b c d  e f h
Definisi 2 . (Rattenburry, 2005)
Kepadatan dari pohon berakar
1 2 [ , , , ] m t t t t = K , ( ) t g didefinisikan oleh
1 2 1 2
1 jika ( ) ( ) ( ) ( )
( ) jika [ , , , ] m m t t r t t t t t t t t t g g g g ìï = ï = íï = ïî L K
Sebagai contoh, pohon berakar
memiliki kepadatan ( ) 1 1 1 1 1 4 3 8 96 t g = ´ ´ ´ ´ ´ ´ ´ = .
Definisi 3 . (Rattenburry, 2005)
Simetri  dari  pohon  berakar 1 2 1 2 [ , , , ] m n n n m t t t t = L , ( ) t s dimana 1 2 , , , k t t t K semuanya  berbeda, didefinisikan oleh
1 2
1 2 1 2 1 2 1 2 1
jika
( )
! ! ! ( ) ( ) ( ) jika [ , , , ] m m n n n n n n m m m t t n n n t t t t t t t t s s s s ìï = ïï = íï = ïïî L L L
Sebagai contoh, simetri pohon berakar
adalah ( ) 3! 3! 2! 72 t s = ´ ´ = .
Secara  ringkas,  orde,  kepadatan  dan  simetri  dari  pohon  berakar  sampai  orde  lima diberikan dalam tabel di bawah ini.
Tabel 1. Orde, Kepadatan dan Simetri dari Pohon Berakar sampai Orde 5. t 1 2 3 4 5 6 7 8 9 10  11  12  13  14  15  16 17 ( ) r t 1 2 3 3 4 4 4 4 5 5 5 5 5 5 5 5 5 ( ) t g 1 2 3 6 4 8 12  24 5 10  15  30  20  20  40  60  120 ( ) t s 1 1 2 1 6 1 2 1 24 2 2 1 2 6 1 2 1 3! 3! 2! 8 1 4 3 1  1 1
1

## 3. Turunan Elementer dan Deret Butcher
Analisis  keakuratan  (orde) dari  metode  Runge-Kutta dilakukan  dengan  membandingkan ekspansi  deret  Taylor  dari  solusi  eksak  dengan  solusi  numeriknya.  Untuk  keperluan  analisis tersebut, perhatikan persamaan differensial autonomous,
( ) ( ( )) y' x f y x = (5)
Ekspansi deret Taylor dari solusi eksak persamaan (5) diberikan oleh
2 3 ( ) ( ) ( ) ( ) ( ) 2! 3! h h y x h y x hy' x y'' x y''' x + = + + + + L
Dengan menggunakan aturan rantai, diperoleh
2 3 ( ) ( ) ( ( ))
( ( ))( ( ( ))) 2 ! ( ( ( ))( ( ( )), ( ( ))) ( ( ))( ( ( ))( ( ( ))))) 3 ! h y x h y x hf y x f' y x f y x h f'' y x f y x f y x f' y x f' y x f y x + = + + + + + L
atau
2 3 ( ) ( ) ( ( , ) ) 2! 3! h h y x h y x h ' '' ' ' ' + = + + + + + f f f f f f f f f L (6)
Di sini digunakan notasi f , ' f dan '' f untuk menyatakan secara singkat ( ( )) f y x , ( ( )) f' y x dan ( ( )) f'' y x secara berturut-turut.
Ekspresi-ekspresi pada persamaan (6) yang muncul pada setiap suku dari i h dinamakan turunan elementer ( elementary differential ). Turunan-turunan elementer tersebut selanjutnya akan direpresentasikan  secara  sederhana  dengan  menggunakan  graf  pohon  berakar.  Setiap f menyatakan sebuah simpul, turunan pertama ' f menyatakan sebuah simpul dengan satu sisi dan turunan  ke- n , ( ) n f menyatakan  sebuah  simpul  dengan n buah  sisi.  Secara  formal,  turunan elementer ( )( ) F t y dinyatakan oleh definisi berikut.
Definisi 4 . (Turunan Elementer, Hairer et al , 2006) Untuk  suatu  pohon  berakar t T Î ,  turunan  elementer  adalah  sebuah  pemetaan ( ) : n n F t ® ¡ ¡ yang didefinisikan
( ) 1 2 1 2 ( )
jika ( )( ) ( )( ( )( ), ( )( ), , ( )( )) jika [ , , , ] m m m f y
t F t y f y F t y F t y F t y t t t t t ìï = ïï = íï = ïïî
K K
Sebagai contoh, turunan elementer dari pohon berakar di bawah ini adalah
( )( ) ( ( , , ), ( , )) F t y '' ''' ' '' = f f f f f f f f f .
f  f  f
f f

## Muhtar
Turunan  fungsi  ke- n dari ( ) y x dari  orde  tertentu  dapat  dinyatakan  secara  unik  sebagai kombinasi linear dari turunan-turunan elementer. Hal ini dinyatakan oleh teorema berikut.
Teorema 1 . (Hairer et al , 2006)
Turunan ke-n dari solusi eksak persamaan (5) diberikan oleh
( ) ( ) ( ) ( ) ( )( ( )) n r t n y x t F t y x a = = å
dimana ( ) t a adalah koefesien bulat positif.
Teorema di atas menyatakan ekspresi deret Taylor ke dalam deret formal yang melibatan turunan- turunan elementer dari fungsi ( ) y x .
Definisi 5 . (Deret Butcher , Hairer et al , 2006)
Untuk pemetaan : {Ø} a T È ® ¡ , deret formal yang dinyatakan oleh
( ) ( ) ( ( ), ( )) (Ø) ( ) ( )( ( )) ( ) r t t T a t B a t y x a y x h F t y x t s Î = + å
disebut deret Butcher ( deret-B ) .

## 4. Pembobot Elementer
Koefisien  dari  ekspansi  deret  Taylor  pada  metode  Runge-Kutta  yang  diberikan  oleh persamaan  (2)  dan  (3)  disebut  pembobot  elementer  ( elementary  weight ) ( ) t F ,  yang  dapat ditentukan  dari  pohon t untuk  semua t T Î sampai  orde  tertentu.  Berikut  contoh  menentukan pembobot elementer dari sebuah pohon berakar dengan tujuh simpul.
Pertama,  dengan  memulai  dari  akar,  setiap  cabang  yang  mengarah  keluar  dilabelkan  dengan , , , i j k L ,  kecuali  simpul  terminal.  Kedua,  akar  diberi  nama i b dan  simpul  lain  dengan ** a kecuali  simpul  terminal.  Subindeks  pertama  pada ** a menyatakan  simpul  orangtua  ( parent ) sedangkan  subindeks  kedua  menyatakan  simpul  yang  bersesuaian.  Terakhir,  simpul  terminal diberi  nama * c ,  dimana  subindeks  pada * c menyatakan  simpul  orangtua.  Pembobot  elementer merupakan  jumlah  dari  semua  hasil  kali  kuantitas-kuantitas  ini.  Dengan  demikian  pembobot elementer yang dimaksud pada pohon berakar di atas adalah
i j k
2 , , 1 , , 1 ( ) s s i ij j i ik k k i ij j i ik k i j k i j k t ba c c a c c ba c c a c = = F = = å å Definisi 5 . (Lee, 2004)
Untuk metode Runge-Kutta dengan s langkah, pembobot elementer, ( ) t F didefinisikan oleh
1 1 2 1 2 1 jika ( )
( ) ( ) ( ) jika [ , , , ] s i i s i i i i m m i b t t b t t t t t t t t = = ìïï = ïïï F = íï ï F F F = ïï ïî å å L K
dimana ( ) i t F adalah pembobot elementer langkah ke-i dan didefinisikan oleh
1 1 2 1 2 1
jika ( )
( ) ( ) ( ) jika [ , , , ] s ij i i s i ij j j j m m i a c t t
a t t t t t t t t = = ìïï = = ïïï F = íï ï F F F = ïï ïî å å L K
Pembobot elementer pohon berakar sampai orde lima tersaji pada Tabel 2.

## 5. Syarat Orde
Syarat orde metode Runge-Kutta merupakan himpunan persamaan yang diperoleh dengan membandingkan  koefesien  ekspansi  deret  Taylor  dari  solusi  eksak  dengan  solusi  numeriknya.
Solusi  eksak  ini  merupakan  ekspansi deret Taylor  ruas  kanan  persamaan  (2)  di  sekitar  titik 0 x , yaitu
2
1
0 0 0 0 0 ( ) 1 0 0 1 ( )
( ) ( ) ( ) ( ) ( ) 2 ! ! ( ) ( ) ( ) ! p p k p k p k h h y x h y hy' x x x O h x p h y x y x O h k + + = + = + + + + + = + + å L (7)
yang dapat dinyatakan sebagai
( ) 1 0 0 0 1 ( ) ( ) ( )( ( )) ( ).
( ) ( ) r t p t T y x h y x h
F t y x O h t t s g + Î + = + + å (8)
menurut Teorema 1.
Selanjutnya,  dengan  menggunakan  deret  Butcher,  solusi  numerik  di  titik 0 x dapat ditentukan dengan menggunakan pembobot elementer ( ) t F untuk setiap pohon t T Î , yaitu
( ) 1 0 0 0 1
( ) ( ) ( )( ( )) ( ). ( ) r t p t T y x h y x h
t y x O h t s +
Î + = + F + å (9)
Dengan membandingkan persamaan (8) dan (9), diperoleh
1 ( ) ( ) t t g F = (10)
Hasil penting ini, secara formal dinyatakan oleh teorema berikut ini.
Teorema 2 .  (Hairer et al , 2006)
Metode Runge-Kutta memiliki orde p jika dan hanya jika
1 ( ) ( ) t t g F = untuk ( ) r t p £ .

## 6. Metode Runge-Kutta Orde Lima
Berdasarkan  Teorema  2  dan  hasil-hasil  sebelumnya,  syarat  orde  metode  Runge-Kutta orde lima tersaji secara lengkap pada Tabel 2. Dengan demikian terdapat sebanyak 17 persamaan non-linear.  Untuk  menjamin  konsistensi  penyelesaian  sistem  persamaan  tersebut,  maka banyaknya langkah ( s ) yang dipilih adalah 6.
Dengan  terlebih  dahulu  melakukan  penyederhaan  dan  dengan  bantuan software Maple untuk menyelesaian secara serentak sistem persamaan tersebut, diperoleh dua varian dari metode Runge-Kutta eksplisit orde lima berikut:
0 0 1 3 4 5 6 1 0 0 2 0 0 1 3 0 0 1 2 4 0 0 2 3 5 0 0 1 4 6 0 0 1 2 3 4 5 1 ( ) ( ) 7 32 12 32 7 90 ,
1 1 , 4 4 1 1 1 , 4 8 8 1 1 , 2 2 3 3 9 , 4 16 16 3 2 12 12 8 , 7 7 7 7 7
( ) ( ) ( )
( )
( ) ( ) ( ) y x h y x h k k k k k k f x y k f x h y k k f x h y k k k f x h y k k k f x h y k k k f x h y k k k k k
+ = + + + + + = = + + = + + +
= + - +
= + + + = + - + + - +
0 0 1 3 4 5 6 1 0 0 2 0 0 1 3 0 0 1 2
4 0 0 1 2 5 0 0 1 2 3 4 6 0 0 1 2 3 4 1 ( ) ( ) 11 81 64 81 11 120 ,
1 1 , 3 3 1 1 1 , 3 6 6 1 1 3 , 2 8 8 2 2 1 1 4 , 3 27 9 3 27 1 3 27 2 , 4 22 22 11 ( ) ( ) ( ) ( )
( ) ( ) ( y x h y x h k k k k k k f x y k f x h y k k f x h y k k k f x h y k k k f x h y k k k k k f x h y k k k k + = + + - + + = = + + = + + + = + + + = + + + + + = + - + + - + 5 7 11 ) k
Tabel 2. Pembobot Elementer dari Pohon Berakar sampai Orde 5.
t ( ) r t ( )( )
F t y ( ) t F 1
( ) t g 1 1 ( ) f 1 s i i b = å 1 2 2
( ) ' f f 1 s i i i b c = å 1 2 3
3 ( , ) '' f f f 2 1 s i i i b c = å 1 3 4
3 ( ) ' ' f f f , 1 s i ij j i j ba c = å 1 6 5
4 ( , , ) ''' f f f f 3 1 s i i i b c = å 1 4 6
4 ( , ) '' ' f f f f , 1 s i i ij j i j b c a c = å 1 8 7
4 ( , ) ' '' f f f f 2 , 1 s i ij j i j ba c = å 1 12 8
4 ( ) ' ' ' f f f f , , 1 s i ij jk k i j k b a a c = å 1 24 9
5 (4) ( , , , ) f f f f f
4 1 s i i i b c = å 1 5 10
5 ( , , ) ''' ' f f f f f 2 , 1 s i i ij j i j b c a c = å 1 10 11
5 ( , ( , )) '' '' f f f f f 2 , 1 s i i ij j i j bc a c = å 1 15 12
5 ( , ) '' ' ' f f f f f , , 1 s i i ij jk k i j k b c a a c = å 1 30
13 5 ( , ) '' ' ' f f f f f 2 1 1 ( ) s s i ij j i j b a c = = å å 1 20 14 5
( ( , , )) ' ''' f f f f f 3 , 1 s i ij j i j b a c = å 1 20 15
5 ( , ) ' '' ' f f f f f , , 1 s i ij j jk k i j k b a c a c = å 1 40 16 5
( , ) ' ' '' f f f f f 2 , , 1 s i ij jk k i j k b a a c = å 1 60 17
5 ( )
' ' ' ' f f f f f , , 1 s i ij jk kl l i j k ba a a c = å 1
120

## 7. Kesimpulan
Syarat  orde  suatu  metode  Runge-Kutta  orde  tertentu  dapat  ditentukan  dengan  hanya mencari  semua  kombinasi  pohon  berakar  sampai  orde  yang  bersesuaian.  Dengan  demikian, kompleksitas  penurunan  metode  Runge-Kutta  yang  melibatkan  evaluasi  turunan-turunan  fungsi pada ekspansi deret Taylor bisa dihindari.

## Daftar Pustaka
[1] Hairer  E.,  Norsett  S.P.,  Wanner  G.,  1987, Solving  Ordinary  Differential  Equations  I , Springer.
[2] Hairer  E.,  Lubich  C.,  Wanner  G.,  2006 ,  Geometric  Numerical  Integration,  Structure- Preserving Algorithms for Ordinary Differential Equations , Springer.
[3] Lee, J.H.J., 2004, Numerical methods for ordinary differential equations , MSc Thesis, The University of Auckland.
[4] Muhtar,  2001, Solusi  numerik  persamaan  differensial  biasa  dengan  metode  Runge-Kutta orde lima , Skripsi S 1 , Universitas Hasanuddin.
[5] Rattenbury, N., 2005, Almost Runge-Kutta methods for stiff and non-stiff problem , PhD Thesis, The University of Auckland.