RELASI REKURENSI LINIER BERKOEFISIEN KONSTAN DESKRIT
RELASI REKURENSI LINIER BERKOEFISIEN KONSTAN
Sebuah relasi rekurensi linier berkoefisien konstan dari sebuah fungsi numerik a, secara umum ditulis sebagai berikut
C0 an + C1 an-1 + C2 an-2 + … + Ck an-k = f(n)
dimana Ci , untuk i = 0,1,2,…,k adalah konstan dan f(n) adalah sebuah fungsi numerik dengan variabel n.
Relasi rekurensi tersebut dikatakan relasi rekurensi linier berderajat k , jika C0 dan Ck keduanya tidak bernilai 0 (nol).
Contoh 5.1.
2 an + 2 an-1 = 3n adalah sebuah relasi rekurensi linier berderajat 1
tn = 7 tn-1 adalah sebuah relasi rekurensi linier berderajat 1
an – an-1 – an-2 = 0 adalah sebuah relasi rekurensi linier berderajat 2
bn-3 – 3bn = n+3 adalah sebuah relasi rekurensi linier berderajat 3 ð
Untuk sebuah relasi rekurensi dengan koefisien konstan derajat k, jika diberikan k buah harga aj yang berurutan am-k , am-k+1 , … , am-1 untuk suatu nilai m tertentu, maka setiap nilai am yang lain dapat dicari dengan rumus
am = 
( C1 am-1 + C2 am-2 + … + Ck am-k - f(m) )
( C1 am-1 + C2 am-2 + … + Ck am-k - f(m) )dan selanjutnya, harga am+1 juga dapat dicari dengan cara
am+1 = ( C1 am + C2 am-1 + … + Ck am-k+1 - f(m+1) )
( C1 am + C2 am-1 + … + Ck am-k+1 - f(m+1) )demikian pula untuk nilai am+2 , am+3 dan seterusnya. Di lain pihak, harga am-k-1 dapat pula dihitung dengan
am-k-1 = 
( C1 am-1 + C2 am-2 + … + Ck-1 am-k - f(m-1) )
( C1 am-1 + C2 am-2 + … + Ck-1 am-k - f(m-1) )dan am-k-2 dapat dicari dengan
am-k-2 = 
( C1 am-2 + C2 am-3 + … + Ck-1 am-k-1 - f(m-2) ).
( C1 am-2 + C2 am-3 + … + Ck-1 am-k-1 - f(m-2) ).Harga am-k-3 dan seterusnya dapat dicari dengan cara yang sama. Jadi, untuk sebuah relasi rekurensi linier berkoefisien konstan derajat k , bila harga k buah aj yang berurutan diketahui, maka harga aj yang lainnya dapat ditentukan secara unik. Dengan kata lain, k buah harga aj yang diberikan merupakan himpunan syarat batas (kondisi batas) yang harus dipenuhi oleh relasi rekurensi tersebut untuk dpat memperoleh harga yang unik.
5.1. SOLUSI DARI RELASI REKURENSI
Seperti telah disebutkan pada bagian sebelumnya, sebuah relasi rekurensi linier berkoefisien konstan dapat dinyatakan dalam bentuk C0 an + C1 an-1 + … + Ck an-k = f(n). Bila nilai f(n) = 0, maka diperoleh relasi rekurensi yang memenuhi
C0 an + C1 an-1 + C2 an-2 + … + Ck an-k = 0.
Relasi rekurensi demikian disebut dengan relasi rekurensi homogen dan solusi dari relasi rekurensi homogen ini dinamakan solusi homogen atau jawab homogen.
Dalam usaha mencari solusi dari sebuah relasi rekurensi perlu dicari dua macam solusi, yaitu :
1. Solusi homogen (jawab homogen) yang diperoleh dari relasi rekurensi linier dengan mengambil harga f(n) = 0.
2. Solusi khusus/partikuler (jawab khusus) yang memenuhi relasi rekurensi sebenarnya.
Solusi total atau jawab keseluruhan dari sebuah relasi rekurensi adalah jumlah dari solusi homogen dan solusi partikuler. Misalkan an(h) = (a0(h), a1(h), … ) adalah solusi homogen yang diperoleh dan misalkan an(p) = (a0(p), a1(p), … ) adalah solusi partikuler yang diperoleh, maka solusi total dari relasi rekurensi yang dimaksud adalah
an = a(h) + a(p)
Soal Latihan 5.1.
1. Tentukan lima nilai pertama dari an = an-1 + 3 an-2 jika diketahui a0 = 1 dan a1 = 2.
2. Misalkan {an} sebuah barisan bilangan yang memenuhi relasi rekurensi
an = an-1 – an-2 untuk n = 2, 3, 4,... dimana a0 = 3 dan a1 = 5. Tentukan a2 dan a3 .
3. Diketahui gn = gn-1 + 2 gn-2 dimana g6 = 11 dan g4 = 3. Tentukan g7 dan g9 .
4. Tentukan relasi rekurensi untuk menghitung jumlah langkah yang diperlukan untuk memindahkan n cakram pada permainan menara Hanoi.
5. Sebuah bola dijatuhkan dari ketinggian 15 meter. Bola tersebut selalu memantul dan mencapai ketinggian sepertiga dari ketinggian sebelumnya. Nyatakan relasi rekurensi untuk menghitung tinggi bola pada pantulan ke t.
0 komentar :
Post a Comment
Silahkan Berkomentar Sesuai Dengan Topik, Jangan Menggunakan Kata-Kata Kasar, Komentar Dengan Link Aktif Tidak Akan Dipublikasikan
ttd
Admin Blog