87191966-relasi-rekursif-oke

8/2/2019 87191966-RELASI-REKURSIF-oke

1/12

RELASIREKURSIF

1.Pendahuluan

Relasirekursifseringjugadisebutrelasiberulang.Relasiinimendefinisikansebuahbarisandenganmemberikannilaike-nyangdikaitkandengansukusukusebelumnya.untukmendefinisikansebuahbarisan,relasiberulangmemerlukannilaiawalyangsudahditentukan.Secaraformalrelasiberulanginididefinisikansebagaisebuahrelasiberulanguntukbarisana0,a1,a2,...merupakansebuahpersamaanyangmengkaitkanandengana0,a1,a2,...,an-1.Syaratawaluntukbarisana0,a1,a2,...adalahnilai-nilaiyangdiberikansecaraeksplisitpadabeberapasukudaribarisantersebut.

Banyakpermasalahandalammatematikayangdapatdimodelkandalambentukrelasirekursif,kombinatorikmerupakansalahsatunya.MisalPnmenyatakanbanyaknyapermutasidarinobjekberbeda,makaP1=1karenahanyaadasatupermutasidari1objek.

Untukn=2terdapatnkemungkinanposisidarisatuobjekdansetiapkemungkinanposisidarisatuobjekakandiikutiolehpermutasidarin1objek.Karenabanyaknyapermutasidarin1objekiniadalahPn1makaterdapathubunganPn=Pn1dengandemikian

P1=1;Pn=Pn1,n=2(2.1.1)

BentukdiatasdisebutrelasirekursifuntukPn,banyaknyapermutasidarinobjek.P1=1disebutkondisiawalsedangkanPn=Pn1disebutbagianrekusifdarirelasirekursiftersebut.

Contoh

barisanfibonacci(1,1,2,3,5,8,13,21,34,55,89,...).misalkanFnmenyatakansukuke-ndaribarisantersebut,perhatikanbahwan3,sukuke-ndaribarisantersebutadalahjumlahdariduasukusebelumnya,sehinggarelasirekursifuntukFnditulis:

F1=1,F2=1;Fn=Fn-1+Fn2,n=3

DalamrelasitersebutterdapatduakondisiawalyaituF1=1danF2=1.Jikakondisiawal

dirubah,makabarisanfibonacciyangdiperolehakanberbedadengandiatas

Berdasarkancontohdiatasterlihatbahwasuatufungsinumeric(a0,a1,a2,...,ar,...)dansembarangr,suatupersamaanyangmengaitkanardengansatuataulebihai,i


2/12


3/12

2.JENIS-JENISRELASIREKURSIFa.RelasiRekurensiLinierBerkoefisienKonstan

Bentukumumbagianrekursifdarisuaturelasirekursiflinierberderajatkdapatditulissebagaiberikut:

an+C1an-1+C2an-2++Ckan-k=f(n)

dimanaCi,untuki=1,2,3,,kadalahkonstantadanf(n)adalahsebuahfungsinumerikdenganvariabeln,danC00.Relasirekursifnyadisebutrelasirekursifdengankoefisienkonstanta

Jikaf(n)=0makarelasirekursifnyadisebuthomogen

Jikaf(n)0makarelasirekursifnyadisebutnonhomogen

Contoh1

1.2an+2an-1=3nadalahsebuahrelasirekurensilinierberderajat1

2.tn=7tn-1adalahsebuahrelasirekurensilinierberderajat13.anan-1an-2=0adalahsebuahrelasirekurensilinierberderajat24.bn-33bn=n+3adalahsebuahrelasirekurensilinierberderajat35.a0=a1=1;an=a0an-1+a1an-2+...+an-1a0,n1adalahrelasirekursifnonlinier6.D0=1;Dn=nDn-1+(-1)n,n1adalahrelasirekursifliniernonhomogendengankoefisiennonkonstanta

Suaturelasirekursifberderajatkterdiridarisebuahbaganrekursifdankkondisiawalberurutan.Relasirekursifdemikianmendefenisikantepatsatufungsi

Contoh1.

DiberikanRelasiRekursifan.an.1+an.2,

apakahtermasukbentuk

a)homogenb)linearc)berapakahderajatnya?d)tentukankoefisien

Penyelesaian:

an.an.1.an.2

..an.an.1.an.2.0

a)karenafn=0makatermasukhomogenb)karenatidakadaperkalianduavariablemakaRRtersebutlinear,


4/12

c)an-k=an-2makak=2,artinyaberderajat2d)karenah1(n)..1(koefisiendarian.1),danh2(n)..1(koefisiendarian.2),makamempunyaikoefisiennyakonstan,


5/12

contoh2

Tentukansifat-sifatdariRRan.nan.1.(.1)

Penyelesaian:

an.nan.1.(.1)n

an

b.RelasiRekursifLinearHomogenDenganKoefisienKonstanta

Bentukumumdarirelasirekursiflinierhomogendengankoefisienkonstantaadalahsebagaiberikut:

(2.2.1)

Dengankkondisiawal,untuk1=i=k,=konstanta.

Padabagianiniakandikembangkansuatuteknikuntukmenyelesaikanrelasirekursif.Untukmaksudtersebutdiperlukanteoremaberikut:

Teorema2.2.1:(prinsipsuperposisi).Jika()()berturut-turutadalahsolusidari:

(),(2.2.2)

dan

()(2.2.3)

Makauntuksebarangkonstanta^^,^()^()adalahsebuahsolusidari:

^()^()(2.2.4)

Bukti:

karena()()berturutturutadalahsolusidari(2.2.2)dan(2.2.3)maka

()()()()(),dan

()()()()(),

Misal:

^()^(),maka

^()^()^()^()^()^()^()^()

^()^()^()^()^()^()^()^()


6/12


7/12

^()^()

Iniberarti^()^()solusidari(2.4)terbukti

Sebagaiakibatdariteorema2.2.1diperolehteoremaberikut:

Teorema2.2.2:

jika()()(),adalahsolusisolusidari

,(2.2.5)

maka^()^()^()jugasolusidari(2.2.5)untuksebarangkonstanta^^^.

Untukmenyelesaikanrelasi(2.2.1),pertama-tamamisalkan,untukmenentukanx,substitusikandenganpada(2.2.1)dimanai.{n,n-1,n-2,...,n-k}.Diperoleh

Bagikeduaruaspersamaantersebutdengandiperoleh:

(2.2.6)

Persamaan(2.2.6)disebutpersamaankarakteristikdarirelasirekursifhomogendengankoefisienkonstanta.Padaumumnyapersamaan(2.2.6)mempunyaikakar,beberapadiantaranyamungkinbilangankompleks.

Jikaadalahkakar-akar(yangberbeda)daripersamaan(2.2.6),maka;1=i=kadalahpenyelesaiandariBerdasarteorema2.2.2jikag1(n),g2(n),...,gk(n)berturut-turutadalahsolusidarimaka^^^;^^

^adalahpenyelesaiandari.Dengandemikiansolusiumumdarirelasirekursif(2.2.1)adalah

=^^^(2.2.7)

Daripersamaan(2.2.7)dankkondisiawalakanterbentuksuatusistempersamaanyangterdiridarikpersamaandengankvariabel^^^.Jikapenyelesaiandarisistem

persamaaninikitasubstitusikankepersamaan(2.2.7),diperolehsolusidarirelasirekursif(2.2.1).

Contoh:

Selesaikanrelasirekursifberikutdenganakarkarakteristik

a0=0,a1=-1;an=7an-112an-2,


8/12

penyelesaian:


9/12

misalnyaan=xn:x0makabentukrekursifan=7an-112an-2menjadi

xn=7xn-112xn-2,ekuivalendenganxn7xn-112xn-2=0

bagikeduaruasdenganxn-2,sehinggadiperolehpersamaankarakteristik

x27x+12=0

denganakar-akarkarakteristiknyax1=4danx2=3

sehinggasolusihomogen(umum)darirelasirekkursiftersebutadalah

an(h)=+

an(h)=+............................(1)

karenakondisiawala0=0dana1=-1

makadaripersamaan(1)diperolehpersamaan

+......................................(2)

+......................................(3)

Daripersamaan(2)dan(3)diperoleh

c1=-1danc2=1

subtitusinilaic1danc2kepers(1)sehinggadiperolehsolusihomogen(khusus)darirelasirekursifberikut

an=-1.4n1.3n

an=-4n3n

Contoh2.2.1:

Selesaikanlahhubunganrekursifberikut:==,n=3

Penyelesaian:persamaankarakteristikdarirekursifiniadalah,yangakar-akarnyavdanv

,sehinggasolusiumumdarirelasirekursifadalah:(v)(v)

Karenakondisiawaldan,makadari(i)diperolehsistempersamaan


10/12

berikut:


11/12

1=(v)(v)

1=(v)(v)

Selanjutnyadaripersamaan(ii)dan(iii)didapat

dan

Substitusikannilaikepersamaan(i)diperolehpenyelesaiansebagaiberikut:()(v)()(v)

Perludicatatbahwauntuksetiapn=1,adalahbilanganbulatnonnegatif,walauformuladarimelibatkanirrasional


12/12

87191966-relasi-rekursif-oke

Documents