Top Banner
Tim Matematika Diskrit RELASI REKURENSI
38

RELASI REKURENSI

Jan 15, 2016

Download

Documents

eilis

RELASI REKURENSI. Tim Matematika Diskrit. Barisan yang didefinisikan secara rekursif. - PowerPoint PPT Presentation
Welcome message from author
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
Page 1: RELASI REKURENSI

Tim Matematika Diskrit

RELASI REKURENSI

Page 2: RELASI REKURENSI

Sebuah barisan dapat dinyatakan dalam beberapa cara.

- dengan menuliskan beberapa suku pertama barisan itu misalnya: 3, 5, 7, …

- menyatakan barisan dalam rumus eksplisit dalam suku-sukunya misalnya: an = 2n + 1

- menyatakan barisan secara rekursif suatu barisan dinyatakan secara rekursif jika kondisi awal barisan ditentukan, dan suku-suku barisan selanjutnya dinyatakan dalam hubungannya dengan sejumlah suku-suku yang sudah dinyatakan sebelumnya misalnya: ak = ak-1 + 2 (relasi rekurensi) dan a0 = 3 (kondisi awal)

Barisan yang didefinisikan secara rekursif

Page 3: RELASI REKURENSI

Contoh 1.Suatu barisan c0, c1, c2, … didefinisikan secara rekursif sbb:Untuk semua bilangan bulat k ≥ 2, ck = ck-1 + k ck-2 + 1Dengan kondisi awal: c0 = 1 dan c1 = 2. Hitunglah c5.

Penyelesaian:Karena barisan didefinisikan secara rekursif, maka c5 tidak bisa dihitung secara langsung, tetapi harus terlebih dahulu menghitung c2, c3, dan c4.c2 = c1 + 2 c0 + 1 = 2 + 2.1 + 1 = 5c3 = c2 + 3 c1 + 1 = 5 + 3.2 + 1 = 12c4 = c3 + 4 c2 + 1 = 12 + 4.5 + 1 = 33c5 = c4 + 5 c3 + 1 = 33 + 5.12 + 1 = 94Jadi c5 = 94

Page 4: RELASI REKURENSI

Contoh 2.Misalkan a1, a2, …; b1, b2, … dan c1, c2, … adalah 3 barisan yang semuanya memenuhi relasi rekurensi: Nilai suatu suku sama dengan 3 kali nilai suku sebelumnya.Jadi ak = 3 ak-1; bk = 3 bk-1; ck = 3 ck-1

Tetapi kondisi awal ketiga barisan tersebut berbeda:a1 = 0; b1 = 1; c1 = 2Nyatakan barisan-barisan tersebut dengan cara menuliskan beberapa suku awal barisan tersebut! Apakah ketiganya merupakan barisan yang sama?

Penyelesaian:Barisan ai adalah: 0, 0, 0, …Barisan bi adalah: 3, 9, 27, …Barisan ci adalah: 6, 18, 54, …Tampak bahwa ketiga barisan tersebut berbeda

Page 5: RELASI REKURENSI

Contoh 3. (Bilangan Fibonacci)Pada tahun 1202, Leonardo of Pisa yang dikenal dengan Fibonacci mengemukakan masalah sbb: Misalkan mula-mula ada sepasang kelinci (jantan dan betina) yang baru lahir. Setiap bulan, kelinci-kelinci yang sudah berumur 2 bulan akan beranak 2 ekor kelinci (jantan dan betina). Carilah banyaknya kelinci setelah 12 bulan (dan secara umum setelah n bulan)

Penyelesaian:Pada bulan ke-0, ada 1 pasang kelinci (sebut pasangan A)Pada bulan ke-1, tetap masih ada 1 pasang kelinci (A) karena belu cukup umur untuk beranakPada bulan ke-2, pasangan A mempunyai sepasang anak (sebut pasangan B). Jadi total ada 2 pasang kelinci.Pada bulan ke-3, pasangan A mempunyai sepasang anak lagi (sebut pasangan C), tetapi pasangan B belum punya anak krn belum cukup umur. Total 3 pasang.Pada bulan ke-4, pasangan A mempunyai sepasang anak lagi (sebut pasangan D), pasangan B juga mempunyai sepasang anak (sebut pasangan E). Total 5 pasang kelinci). Dan seterusnya …

Page 6: RELASI REKURENSI

Anak kelinci yang lahir pada tiap bulan ke - dinyatakan dalam tabel sbb:

Induk Kelinci

1 2 3 4 5 6

A - B C D F I

B - - - E G J

C - - - - H K

D - - - - - L

E - - - - - M

F - - - - - -

G - - - - - -

Page 7: RELASI REKURENSI

Misalkan Fn menyatakan banyak pasangan kelinci yang hidup pada bulan ke-n (n ≥ 0)Maka: F0 = 1,

F1 = 1, F2 = 2, F3 = 3, F4 = 5, …

Fn terbentuk dari 2 hal yaitu: Fn-1 pasang kelinci dari bulan sebelumnya ditambah dengan jumlah pasangan anak yang dilahirkan. Karena kelinci yang mempunyai anak adalah yang berumur minimal 2 bulan, maka jumlah pasang anak yang diperoleh sama dengan jumlah kelinci pada 2 bulan sebelumnya yaitu Fn-2. Maka didapat relasi Fn = Fn-1 + Fn-2 dengan F0 = 1; F1 = 1. Relasi ini dikenal dengan relasi Fibonacci. Fi yang terbetuk disebut Bilangan Fibonacci.

Page 8: RELASI REKURENSI

Contoh 4. (Menara Hanoi)Pada tahun 1883, seorang ahli matematika Perancis bernama Edouard Lucas mengemukakan suatu teka-teki sbb:Menurut legenda, ada sebuah kuil Budha yang di dalamnya terdapat 3 tiang berdiameter kecil terbuat dari permata. Pada waktu dunia diciptakan, Tuhan menciptakan 64 buah cakram dengan ukuran berbeda-beda pada salah satu tiang. Cakram-cakram tesebut ditumpuk satu di atas yang lain, sedemikian hingga semakin ke atas, diameter cakram semakin mengecil. Biksu-biksu kuil tersebut berusaha memindahkan cakram satu demi satu dari satu tiang ke tiang lain, sehingga semua cakram berpindah dari tiang A ke tiang C. Syaratnya: pemindahan hanya boleh dilakukan satu persatu, dan pada setiap keadaan, cakram dengan diameter yang lebih kecil harus berada di atas cakram dengan diameter yang lebih besar.

Page 9: RELASI REKURENSI

Menurut legenda, setelah pemindahan tersebut selesai, maka tiang, cakram, dan semua yang ada akan hancur menjadi debu. Bersamaan dengan itu, akan terdengar halilintar yang menggelegar dan dunia akan hilang (kiamat). Misalkan biksu-biksu tersebut dapat memindahkan sebuah cakram dalam satu detik, berapa lama dunia akan kiamat sejak diciptakan?

Penyelesaian:

Suatu cara penyelesaian yang efisien adalah secara rekursif.

Misalkan kita tahu tentang memindahkan (k-1) cakram dari tiang ke tiang lain. Maka cara paling efisien untuk memindahkan k cakram dari tiang A ke tiang C adalah sbb:

Page 10: RELASI REKURENSI

Langkah 1. pindahkan (k-1) buah cakram dari tiang A ke tiang B. Jika k > 2, eksekusi langkah ini memerlukan sejumlah proses untuk memindahkan cakram satu per satu.

Langkah 2. pindahkan cakram yang terletak paling bawah dari tiang A ke tiang C.

Langkah 3. pindahkan (k-1) buah cakram dari tiang B ke tiang C. seperti langkah 1, jika k > 2, langkah 3 juga memerlukan sejumlah proses di dalamnya.

Misalkan mn = jumlah langkah minimal untuk memindahkan n buah cakram dari satu tiang ke tiang lain. Perhatikan bahwa mn tidak dipengaruhi oleh asal dan tujuan tiang. mn juga tidak tergantung dari banyaknya cakram yang terletak di bawah n buah cakram yang dipindah tersebut.

Page 11: RELASI REKURENSI

Langkah 1 memerlukan mk-1 kali perpindahan. Langkah 2 memerlukan 1 kali perpindahan. Langkah 3 memerlukan mk-1 kali perpindahan. Jadi jumlah keseluruhan perpindahan minimal adalah: mk = mk-1 + 1 + mk-1 = 2mk-1 + 1

Kondisi awal terjadi jika k = 1

Diperoleh persamaan rekursif m1, m2, …, sbb:

mk = 2 mk-1 + 1 (relasi rekurensi)

m1 = 1 (kondisi awal)

Maka untuk memindahkan:

2 cakram, dibutuhkan m2 = 2 m1 + 1 = 2.1 + 1 = 3 langkah

3 cakram, dibutuhkan m3 = 2 m2 + 1 = 2.3 + 1 = 7 langkah

4 cakram, dibutuhkan m4 = 2 m3 + 1 = 2.7 + 1 = 15 langkah, dst

64 cakram, dibutuhkan m64 = … = 1,844674.1019 detik ≈ 5.84542.1011 tahun

Page 12: RELASI REKURENSI

Contoh 5. (Perhitungan bunga bank)Jika kita menyimpan uang di bank, biasanya bank memberikan bunga yang dihitung per tahun, misal i. Jika bunga diberikan per periode tertentu dan dalam satu tahun ada m kali periode, maka besarnya bunga per periode = i/m. Sebagai contoh, suatu bank memberikan bunga 12% = 0,12 per tahun dan bunga diberikan secara bulanan. Maka besarnya bunga per bulan = 0,12/12 = 0,01.Untuk tiap bilangan positif k ≥ 1, misalkan:Pk = jumlah tabungan pada akhir periode ke-k (tanpa ada transaksi).Nyatakan Pk sehingga relasi rekurensi suku-suku sebelumnya!

Page 13: RELASI REKURENSI

Penyelesaian:

Besarnya bunga selama periode ke-k adalah jumlah tabungan pada akhir periode ke (k-1) dikalikan dengan bunga untuk periode tersebut.

Jadi, bunga selama periode ke-k adalah (Pk-1) (i/m).

Jumlah uang tabungan pada akhir periode ke-k (=Pk) didapat dengan cara menjumlahkan uang tabungan pada akhir periode ke(k-1) (=Pk-1) dengan bungan yang didapat selama periode ke-k tersebut.

Maka jumlah uang tabungan pada akhir periode ke-k adalah:

Pk = Pk-1 + Pk-1 (i/m)

= Pk-1 (1 + i/m)

Kondisi awal (P0) adalah jumlah uang tabungan mula-mula.

Page 14: RELASI REKURENSI

Prinsipnya: dihitung suku-suku barisan secara berurutan terus menerus sehingga diperoleh suatu pola tertentu.

Misalnya:

Penyelesaian Relasi Rekurensi dengan Iterasi

1,1

1...1

3

)2)(1()1(...4.33.22.1

6

)12)(1(...321

2

)1(...321

12

222

rr

rrrr

nnnnn

nnnn

nnn

nn

Page 15: RELASI REKURENSI

Contoh 6.Misalkan a0, a1, a2, …, barisan yang didefinisikan secara rekursif sbb:Untuk semua bilangan bulat k ≥ 1,ak = ak-1 + 2 (relasi rekurensi), a0 = 1 (kondisi awal)Carilah rumus eksplisit barisan tersebut dengan metode iterasi.

Penyelesaian:ak = ak-1 + 2 = (ak-2) + 2 = ak-2 + 2.2

= (ak-3) + 2.2 = ak-3 + 3.2= (ak-4) + 3.2 = ak-4 + 4.2

Sesuai pola, terlihat bahwa ak = ak-k + k.2 = a0 + 2.kKarena a0 = 1 maka penyelesaian persamaan rekursif adalah ak = 1 + 2k.Jika diselesaikan dengan cara menaik:a1 = a0 + 2a2 = a1 + 2 = (a0 + 2) + 2 = a0 + 2.2a3 = a2 + 2 = (a0 + 2 + 2) + 2 = a0 + 3.2 …ak = a0 + k.2 = 1 + 2k

Page 16: RELASI REKURENSI

Contoh 7.Carilah rumus eksplisit barisan m1, m2, … yang menyatakan masalah menara Hanoi.mk = 2 mk-1 + 1 untuk bilangan bulat k ≥ 2m1 = 1

Penyelesaian:mk = 2 mk-1 + 1

= 2 (2mk-2 + 1) + 1 = 22 mk-2 + 2.1 + 1= 22 (2mk-3 + 1) + 2.1 + 1 = 23 mk-3 + 22.1 + 2.1 + 1= 23 (2mk-4 + 1) + 22.1 + 2.1 + 1 = 24 mk-4 + 23.1 + 22.1 + 2.1 + 1= …= 2k-1 mk-(k-1) + 2k-2.1 + … + 23.1 + 22.1 + 21 + 1= 2k-1 m1 + 2k-2 + … + 23 + 22 + 21 + 1

Karena m1 = 1 maka: mk = 2k-1 + 2k-2 + 2k-3 + … + 23 + 22 + 21 + 1mk merupakan deret geometri dengan r = 2 yang besarnya = 2k -1 Jadi mk = 2k -1 untuk bilangan bulat k ≥ 1

Page 17: RELASI REKURENSI

Contoh 8.Misalkan Kn adalah graf dengan n buah titik dan setiap pasang titik dihubungkan dengan sebuah garis (Graf Lengkap).Jika Sn menyatakan jumlah garis dalam Kn, maka:a. Buktikan bahwa Sn memenuhi relasi rekurensi Sn = Sn-1 + (n-1) dan kondisi awal S1 = 0b. Selesaikan relasi rekurensi Sn tersebut.

Penyelesaian:a. Kn untuk n = 1, 2, 3, 4, dan 5

K1 K2 K3 K4 K5

Page 18: RELASI REKURENSI

Banyaknya garis dalam K4 adalah banyaknya garis K3 ditambah dengan banyaknya garis baru yang harus dibuat akibat penambahan satu buah titik.Banyaknya garis baru yang ditambahkan pada K4 sama dengan banyaknya titik pada K3. Jadi S4 = S3 + 3.Secara umum: Sn = Sn-1 + (n-1)Kondisi awal S1 = 0 jelas benar karena tidak mungkin membuat garis dari satu buah titik.

b. Sn = Sn-1 + (n-1)= (Sn-2 + (n-2)) + (n-1) = Sn-2 + (n-2) + (n-1)= (Sn-3 + (n-3)) + (n-2) + (n-1) = Sn-3 + (n-3) + (n-2) + (n-1)= …= Sn-(n-1) + (n-(n-1)) + …+ (n-3) + (n-2) + (n-1)= S1 + 1 + 2 + … + (n-2) + (n-1)

Karena S1 = 0 makaSn = 1 + 2 + … + (n-2) + (n-1) = ½ n (n-1)

Page 19: RELASI REKURENSI

Contoh 9.Buktikan bahwa rumus eksplisit yang didapat pada contoh 8 merupakan rumus yang benar.

Penyelesaian:Dari contoh 8 didapat Sn = ½ n (n-1)Akan dibuktikan kebenaran rumus tersebut dengan induksi matematika.

Basis:Akan dibuktikan kebenaran rumus untuk n = 1.Menurut rumus, untuk n = 1, S1 = ½ 1 (1-1) = 0Menurut kondisi awal, S1 = 0. jadi terbukti rumus benar untuk n = 0.Induksi:Misalkan rumus benar untuk n = k. Jadi Sk = ½ k (k-1)Menurut persamaan rekurensi untuk n = k + 1, Sk+1 = S(k+1)-1 + ((k+1) -1) = Sk + (k) = ½ k (k-1) + k (hipotesa induk) = ½ k (k+1) = ½ (k+1) ((k+1)-1)Terbukti rumus benar untuk n = k + 1Jadi rumus eksplisit untuk Sn benar untuk n ≥ 1.

Page 20: RELASI REKURENSI

Suatu cara penyelesaian relasi rekurensi yang dapat menentukan rumus eksplisit dengan pasti adalah melalui persamaan karakteristik.

a. Relasi Rekurensi Linier dengan Koefisien Konstan

Misalkan n dan k adalah bilangan-bilangan bulat tidak negatif dengan n ≥ k. Relasi rekurensi linier derajat k adalah relasi berbentuk: c0(n) an + c1(n) an-1 + … + ck(n) an-k = f(n), c0(n) dan ck(n) ≠ 0 Jika c0(n), c1(n), …, ck(n) semuanya konstanta, maka relasi rekurensi disebut relasi rekurensi linier dengan koefisien konstan. Jadi relasi rekurensi linier dengan koefisien konstan adalah: c0 an + c1 an-1 + … + ck an-k = f(n) Apabila dalam persamaan tersebut, f(n) = 0, maka disebut relasi rekurensi homogen linier dengan koefisien konstan.

Penyelesaian Relasi Rekurensi lewat Persamaan Karakteristik

Page 21: RELASI REKURENSI

Contoh 10.Tentukan apakah persamaan di bawah ini merupakan relasi rekurensi linier, linier dengan koefisien konstan atau homogen linier dengan koefisien konstan. Jika demikian tentukan derajatnya!

a. an – 7 an-1 + 10 an-2 = 0b. bk = bk-1 + bk-2 + bk-3

c. ck = 2 ck-2

d. dk = dk-12 + dk-2

e. ek = ek-1.ek-2 f. fk – 2 fk-1 + 1 =0 g. hk = -hk-1 + (k-1) hk-2

Page 22: RELASI REKURENSI

Penyelesaian:

a. Relasi rekurensi homogen linier dengan koefisien konstan derajat 2.b. Relasi (b) dapat dinyatakan dengan bk – bk-1 – bk-2 – bk-3 = 0, yang merupakan relasi rekurensi homogen linier dengan koefisien konstan derajat 3.c. Relasi rekurensi homogen linier dengan koefisien konstan derajat 2.d. Bukan relasi rekurensi linier karena memuat suku kuadratis dk-1

2.e. Bukan relasi rekurensi linier karena memuat pergandaan suku (ek-1.ek-2)f. Relasi rekurensi linier dengan koefisien konstan derajat 1 (f(n) = -1)g. Relasi rekurensi linier dengan derajat 2 (koefisien tidak konstan)

Page 23: RELASI REKURENSI

Misalkan diberikan suatu relasi rekurensi homogen linier dengan koefisien konstan: an + c1 an-1 + … + ck an-k = 0, ck ≠ 0 dan n ≥ kPersamaan karakteristik yang sesuai dengan relasi rekurensi tsb adalah:tk + c1 tk-1 + … + ck = 0

Misalkan α1, α2, …, αk adalah akar-akar persamaan karakteristik di atas. Ada 2 kemungkinan akar:1. Semua akar berbeda Jika semua akar persamaan karakteristik berbeda, maka relasi rekurensi mempunyai penyelesaian: an = c1 α1

n + c2 α2n + … + ck αk

n, dengan c1, c2, … , ck adalah konstanta yang nilainya ditentukan berdasarkan kondisi awal.2. Ada akar yang kembar. Misalkan persamaan karakteristik tsb mempunyai p buah akar yang sama. Jadi akar-akarnya adalah: α1 = α2 = … = αp, αp+1, …, αk. Maka penyelesaian relasi rekurensi tsb: an = (c1 + c2n +…+ cpnp-1) α1

n + cp+1 αp+1n + … + ckαk

n , c1, c2, … , ck konstanta yang nilainya ditentukan berdasarkan kondisi awal.

b. Relasi Rekurensi Homogen Linier dengan Koefisien Konstan

Page 24: RELASI REKURENSI

Contoh 11.Selesaikan relasi rekurensi di bawah ini lewat persamaan karakteristiknya:a. an = 3 an-1 + 4 an-2 untuk n ≥ 2 dengan kondisi awal a0 = 1 dan a1 = 3.b. an – 3 an-1 + 3 an-2 – an-3 = 0 untuk n ≥ 3 dengan kondisi awal a0 = 1; a1 = 2 dan a2 = 4c. an – 7 an-1 + 16 an-2 – 12 an-3 = 0 untuk n ≥ 3 dengan kondisi awal a0 = 1; a1 = 4 dan a2 = 8

Page 25: RELASI REKURENSI

Penyelesaian:

a. Relasi rekurensi an - 3 an-1 + 4 an-2 = 0, merupakan relasi rekurensi homogen linier dengan koefisien konstan. Persamaan karakteristik yang sesuai adalah t2 – 3t – 4 = (t-4)(t+1) = 0 yang mempunyai akar-akar karakteristik α1 = 4 dan α2 = -1. karena semua akar-akarnya berbeda, maka penyelesaiannya adalah:

an = c1 4n + c2 (-1)n

Untuk menentukan c1 dan c2, digunakan kondisi awal:

a0 = 1 sehingga 1 = c1 (4)0 + c2 (-1)0 = c1 + c2

a1 = 3 sehingga 3 = c1 (4)1 + c2 (-1)1 = 4 c1 – c2

Didapat sistem persamaan linier c1 + c2 = 1 dan 4c1 – c2 = 3 yang mempunyai penyelesaian c1 = 4/5 dan c2 = 1/5

Maka penyelesaian relasi rekurensi an - 3 an-1 + 4 an-2 = 0 adalah

an = 4/5 (4)n + 1/5 (-1)n

Page 26: RELASI REKURENSI

Contoh 12.

Suatu taruhan dilakukan dengan cara melempar koin seimbang. Seorang penjudi mempertaruhkan Rp 1.000,- dalam setiap kali permainan. Jika yang muncul adalah gambar maka ia menang Rp 1.000,- dan sebaliknya, ia akan kalah Rp 1.000,- jika yang muncul adalah angka. Penjudi tersebut akan berhenti bermain jika ia kehabisan uang, atau ia menang Rp M (dalam ribuan). M adalah bilangan bulat positif yang besarnya ditentukan sebelum ia mulai berjudi. Misalkan Pn adalah probabilitas penjudi akan kehabisan uang jika sebelum berjudi ia membawa uang sebanyak Rp n (dalam ribuan)

a. Carilah rumus eksplisit untuk Pn

b. Bagaimana penjudi harus menentukan M untuk meminimumkan

kemungkinan kehabisan uang?

Page 27: RELASI REKURENSI

Penyelesaian:

a. Jika suatu koin seimbang dilemparkan, maka kemungkinan munculnya angka sama dengan kemungkinan munculnya gambar P(angka) = P(gambar) = ½

Ini berarti bahwa kemungkinan menang (gambar) dan kalah (angka) juga sama. Jika penjudi mempunyai (k-1) ribu, maka setelah 1 kali permainan, ada 2 kemungkinan jumlah uang yang dimiliki penjudi tersebut:

1. Uang yang dimiliki = (k) ribu. Ini terjadi kalau penjudi tersebut menang/muncul gambar. Jika demikian, maka kemungkinan ia kehabisan uang = Pk.

2. Uang yang dimiliki = (k-2) ribu. Ini terjadi kalau penjudi tersebut kalah/muncul angka. Jika demikian maka kemungkinan ia kehabisan uang adalah Pk-2.

Page 28: RELASI REKURENSI

Untuk kedua kasus tsb, kemungkinan terjadinya sama, yaitu = ½.

Didapat relasi rekurensi Pk-1 = ½ Pk + ½ Pk-2; 2 ≤ k ≤ M.

Didapat Pk – 2Pk-1 + Pk-2 = 0

Persamaan karakteristik yang sesuai t2 – 2t + 1 = 0 yang mempunyai akar kembar α1 = α2 = 1.

Penyelesaian relasi rekurensi adalah Pn = (c1 + c2n) 1n = c1 + c2n

Kondisi awal:

Untuk n = 0, probabilitas ia akan kehabisan uang = 1. Jadi P0 = 1.

Untuk n = M, probabilitas ia akan kehabisan uang = 0

karena jika uangnya = M, ia akan berhenti berjudi sehingga tidak akan kehabisan uang. Jadi PM = 0.

Page 29: RELASI REKURENSI

Dengan memasukkan kondisi-kondisi awal in ke relasi rekurensi, didapat: 1 = c1 + c2(0) atau c1 = 1

0 = c1 + c2 M = 1 + c2 M sehingga c2 = -1/M

Relasi rekurensi yang sesuai adalah: Pn = 1 – n/M untuk sembarang bilangan bulat n dengan 0 ≤ n ≤ M. selanjutnya dibuktikan dengan induksi matematika.

b. Agar penjudi kehabisan uang (Pn = 1), maka n/M haruslah = 0. ini terjadi kalau M sangat besar. Semakin besar target kemenangan yang dicapai supaya ia berhenti berjudi (M), semakin besar kemungkinannya ia akan kehabisan uang (Pn = 1). Jadi untuk meminimumkan kemungkinan kehabisan uang, M harus dibuat sedekat-dekatnya dengan n (uang yang dimiliki sebelum ia mulai berjudi).

Page 30: RELASI REKURENSI

Penyelesaian total relasi rekurensi linier (tidak homogen) dengan koefisien konstan adalah gabungan dari penyelesaian homogen dan penyelesaian khusus. Kesulitan utama mencari penyelesaian khusus adalah tidak adanya metode yang pasti untuk menentukannya. Yang dapat dilakukan hanyalah memperkirakan bentuk umumnya. Metode perkiraan tersebut dikenal dengan nama koefisien tak tentu (Undetermined Coefficients).

Misalkan an + c1 an-1 + … + ck an-k = f(n) adalah relasi rekurensi linier dengan koefisien konstan. Misalkan juga c(t) = tk + c1 tk-1 + … + ck adalah persamaan karakteristik yang sesuai. Untuk beberapa jenis fungsi f(n), pola perkiraan penyelesaian khusus yang sesuai dapat dilihat dalam tabel sbb: (P, P0, P1, …, Ps adalah koefisien yang harus dicari)

c. Penyelesaian Total

Page 31: RELASI REKURENSI

f(n)(D,a: konstan) Sifat Persamaan Karakteristik C(t)

Bentuk Penyelesaian Khusus

D an a bukan akar persamaan karakteristik c(t) (c(a) ≠ 0)

P an

D an a adalah akar persamaan karakteristik c(t)kelipatan m

P nm an

D ns an a bukan akar persamaan karakteristik c(t)(c(a) ≠ 0)

(P0+P1n+…+Psns) an

D ns an a adalah akar persamaan karakteristik c(t)kelipatan m

(P0+P1n+…+Psns) nman

D ns 1 bukan akar persamaan karakteristik c(t)(c(1) ≠ 0)

P0+P1n+…+Psns

D ns 1 adalah akar persamaan karakteristik c(t)kelipatan m

(P0+P1n+…+Psns) nm

Page 32: RELASI REKURENSI

Contoh 13.

Carilah penyelesaian total relasi rekurensi di bawah ini:

a. an – 7 an-1 + 10 an-2 = 4n untuk n ≥ 2 dengan kondisi awal

a0 = 8 dan a1 = 36

b. an – 7 an-1 + 10 an-2 = 7.3n + 4n untuk n ≥ 2

c. an – 4 an-1 + 4 an-2 = 2n untuk n ≥ 2

d. an – 5 an-1 + 6 an-2 = n2 4n untuk n ≥ 2

e. an – 2 an-1 + an-2 = 5 + 3n untuk n ≥ 2

Page 33: RELASI REKURENSI

a. Relasi rekurensi homogennya adalah an – 7 an-1 + 10 an-2 = 0

Persamaan karakteristiknya t2 – 7t + 10 = 0 dengan akar-akar karakteristiknya adalah α1 = 2, α2 = 5.

Penyelesaian homogen an = c1 2n + c5 5n

Karena f(n) = 4n dan 4 bukan akar karakteristik, maka untuk mencari penyelesaian khusus dicoba bentuk an

k = P (4)n.

Penyelesaian khusus ini disubstitusikan ke relasi rekurensi awal.

Didapat: P 4n – 7 (P 4n-1) + 10 (P 4n-2) = 4n

P 4n-2 (42 – 7.4 + 10) = 4n P = -8

Penyelesaian khusus ank = -8 (4)n

Penyelesaian total = penyelesaian homgen + penyelesaian khusus

an = c1.2n + c2.5n – 8(4)n

Page 34: RELASI REKURENSI

Untuk mencari harga c1 dan c2, digunakan kondisi awal yang diberikan:

a0 = 8 sehingga c1(2)0 + c2(5)0 – 8(4)0

8 = c1 + c2 – 8

16 = c1 + c2

a1 = 36 sehingga 36 = c1(2)1 + c2(5)1 – 8(4)1

36 = 2c1 + 5c2 – 32

68 = 2c1 + 5c2

Didapat sistem persamaan linier c1 + c2 = 16 dan 2c1 + 5c2 = 68

Yang bila diselesaikan akan menghasilkan c1 = 4 dan c2 = 12.

Jadi penyelesaian relasi rekurensi mula-mula adalah

an = 4(2)n + 12(5)n – 8(4)n

Page 35: RELASI REKURENSI

Dalam pemrograman komputer, relasi rekurensi dapat diselesaikan dengan 3 cara:

1. Mengubah relasi rekurensi menjadi rumus eksplisit. Nilai suku barisan ke-n (an) dapat dihitung secara langsung. Contoh: ak = ak-1 + 2 dengan a0 = 1 Rumus eksplisit yang bersesuaian dengan relasi tsb adalah ak = 1 + 2k. Untuk mencari suku barisan ke-n (an), yang harus dilakukan adalah membaca harga n dan membuat statemen penugasan an = 1 + 2n

Relasi Rekursif dalam Ilmu Komputer

Page 36: RELASI REKURENSI

2. Menggunakan struktur perulangan (looping). Contoh: untuk menghitung suku ke-n barisan Fibonacci yang memenuhi relasi Fn = Fn-1 + Fn-2 dengan F0 = 1 dan F1 = 1, maka dibuat struktur program sbb:

Depan := 1 Tengah := 1 For i := 2 to n Akhir := Depan + Tengah Depan := Tengah Tengah := Akhir {end For} Write (Akhir)

Page 37: RELASI REKURENSI

3. Menggunakan prosedur atau fungsi yang dipanggil secara rekursif. Merupakan implementasi proses rekursif yang sesungguhnya dalam komputer. Relasi rekursif an dibuat dalam suatu prosedur/fungsi dengan n sebagai salah satu parameternya. Fungsi/prosedur ini secara rekursif memanggil dirinya sendiri dengan nilai parameter yang menurun.

Jika barisan Fibonacci diselesaikan dengan cara ini, maka programnya adalah (dalam struktur pascal) sbb:

Function Fib (n : Integer) : Integer; Begin If ((n=0) or (n=1)) Then Fib := 1 Else Fib := Fib (n-1) + Fib (n-2) End;

Page 38: RELASI REKURENSI

LATIHAN

Dari buku