RELASI REKURENSI

RELASI REKURENSI LINIER BERKOEFISIEN KONSTAN

            Sebuah relasi rekurensi linier berkoefisien konstan dari sebuah fungsi numerik  a, secara umum ditulis sebagai berikut

C₀ a_n + C₁ a_n-1 + C₂ a_n-2 + … + C_k a_n-k = f(n)

dimana  C_i , 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 C₀  dan C_k  keduanya tidak bernilai 0 (nol).

Contoh 1

2 a_n + 2 a_n-1 = 3ⁿ        adalah sebuah relasi rekurensi linier berderajat  1

t_n = 7 t_n-1                 adalah sebuah relasi rekurensi linier berderajat  1

a_n – a_n-1 – a_n-2 = 0       adalah sebuah relasi rekurensi linier berderajat  2

b_n-3 – 3b_n = n+3                  adalah sebuah relasi rekurensi linier berderajat  3

         Untuk sebuah relasi rekurensi dengan koefisien konstan derajat  k, jika diberikan  k  buah harga  a_j   yang berurutan   a_m-k , a_m-k+1 , … , a_m-1   untuk suatu nilai   m  tertentu, maka setiap nilai  a_m  yang lain dapat dicari dengan rumus

a_m =  -1/c0 ( C₁ a_m-1 + C₂ a_m-2 + … + C_k a_m-k -  f(m) )

dan selanjutnya, harga  a_m+1  juga dapat dicari dengan cara

a_m+1 = -1/c0  ( C₁ a_m + C₂ a_m-1 + … + C_k a_m-k+1 -  f(m+1) )

demikian pula untuk nilai  a_m+2 , a_m+3  dan seterusnya. Di lain pihak, harga  a_m-k-1  dapat pula dihitung dengan

a_m-k-1 = -1/Ck ( C₁ a_m-1 + C₂ a_m-2 + … + C_k-1 a_m-k -  f(m-1) )

dan  a_m-k-2   dapat dicari dengan

a_m-k-2 =  -1/Ck ( C₁ a_m-2 + C₂ a_m-3 + … + C_k-1 a_m-k-1 -  f(m-2) ).

Harga a_m-k-3 dan seterusnya dapat dicari dengan cara yang sama. Jadi, untuk sebuah relasi rekurensi linier berkoefisien konstan derajat  k  , bila harga k  buah  a_j yang berurutan diketahui, maka harga  a_j yang lainnya dapat ditentukan secara unik. Dengan kata lain, k  buah  harga a_j yang diberikan merupakan himpunan syarat batas (kondisi batas) yang harus dipenuhi oleh relasi rekurensi tersebut untuk dpat memperoleh harga yang unik.

Solusi dari Relasi Rekurensi

            Seperti telah disebutkan pada bagian sebelumnya, sebuah relasi rekurensi linier berkoefisien konstan dapat dinyatakan dalam bentuk  C₀ a_n + C₁ a_n-1 + … + C_k a_n-k = f(n). Bila nilai  f(n) = 0, maka diperoleh relasi rekurensi yang memenuhi

C₀ a_n + C₁ a_n-1 + C₂ a_n-2 + … + C_k a_n-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  a_n^(h) = (a₀^(h), a₁^(h), … )  adalah solusi homogen yang diperoleh dan   misalkan  a_n^(p) = (a₀^(p), a₁^(p), … ) adalah solusi partikuler yang diperoleh, maka solusi total dari relasi rekurensi yang dimaksud adalah

a_n = a^(h) + a^(p)

Solusi Homogen dari Relasi Rekurensi

            Solusi homogen dari sebuah relasi rekurensi linier dapat dicari dengan mengambil harga  f(n)=0. Solusi homogen dari sebuah persamaan diferensial linier dengan koefisien konstan dinyatakan dalam bentuk  Aaⁿ , dimana  a  adalah akar karakteristik  dan  A  adalah konstanta yang harganya akan ditentukan kemudian untuk memenuhi syarat batas yang diberikan. Dengan substitusi bentuk Aaⁿ  kepada  a_n   pada persamaan homogen    C₀ a_n + C₁ a_n-1 + C₂ a_n-2 + … + C_k a_n-k = 0 , maka diperoleh

C₀ Aaⁿ   + C₁ Aa^n-1 + C₂ Aa^n-2 + … + C_k Aa^n-k = 0.

Dengan penyederhanaan pada persamaan tersebut, maka diperoleh

C₀ aⁿ   + C₁ a^n-1 + C₂ a^n-2 + … + C_k a^n-k = 0

Persamaan ini merupakan persamaan karakteristik dari persamaan diferensial yang diberikan.  Jika,  bila   adalah akar karakteristik dari persamaan karakteristik ini, maka Aaⁿ akan memenuhi persamaan homogen. Jadi, solusi homogen yang dicari akan berbentuk Aaⁿ.

          Bila persamaan karakteristik memiliki sebanyak  k   akar karakteristik berbeda   (a₁ ¹ a₂ ¹ … ¹ a_k) , maka solusi homogen dari relasi rekurensi yang dimaksud dinyatakan dalam bentuk

 

a_n^(h) = A₁ a₁ⁿ + A₂ a₂ⁿ + … + A_k a_kⁿ

dimana  a_i adalah akar karakteristik dari persamaan karakeristik yang diperoleh, sedangkan  A_i  adalah konstanta yang akan dicari untuk memenuhi kondisi batas yang ditentukan.

 

Contoh 2

Tentukan solusi homogen dari relasi rekurensi b_n + b_n-1 – 6 b_n-2 = 0 dengan kondisi batas b₀ = 0 , b₁ = 1 .

Penyelesaian :

Relasi rekurensi tersebut adalah relasi rekurensi homogen, karena f(n)=0.

Persamaan karakteristik dari relasi rekurensi b_n + b_n-1 – 6 b_n-2 = 0

adalah a² + a - 6 = 0 atau (a + 3) ( a - 2) = 0

hingga diperoleh akar-akar karakteristik a₁ = -3 dan a₂ = 2.

Oleh karena akar-akar karakteristiknya berbeda, maka solusi homogennya berbentuk b_n^(h) = A₁ a₁ⁿ + A₂ a₂ⁿ Þ b_n^(h) = A₁ (-3)ⁿ + A_{2 .} 2ⁿ.

Dengan kondisi batas b₀ = 0 dan b₁ = 1 , maka

b₀^(h) = A₁ (-3)⁰ + A_{2 .} 2⁰ Þ 0 = A₁ + A₂ .

b₁^(h) = A₁ (-3)¹ + A_{2 .} 2¹ Þ 1 = -3 A₁ + 2 A₂ .

bila diselesaikan maka akan diperoleh harga A₁ = (-1/5) dan A₂ = 1/5 , sehingga jawab homogen dari relasi rekurensi b_n + b_n-1 – 6 b_n-2 = 0 adalah

b_n^(h) = -1/5 (-3)ⁿ + 1/5 . 2ⁿ

            Jika akar karakteristik  a₁  dari persamaan karakteristik merupakan akar ganda yang berulang sebanyak  m  kali, maka bentuk solusi homogen yang sesuai untuk akar ganda tersebut adalah

(A₁ . n^m-1 + A₂ . n^m-2 + … + A_m-2 n² + A_m-1 . m + A_m ) a₁ⁿ

dimana   A_i  adalah konstanta yang nantinya akan ditentukan untuk memenuhi kondisi batas yang ditentukan.

Contoh 3

Tentukan solusi dari relasi rekurensi     a_n + 4 a_n-1 + 4 a_n-2 = 2ⁿ .

Penyelesaian :

Relasi rekurensi homogen :                    a_n + 4 a_n-1 + 4 a_n-2 =0.

Persamaan karakteristiknya adalah                 a²  +  4 a  + 4 = 0

                                                            (a + 2) ( a + 2) = 0

hingga diperoleh akar-akar karakteristik   a₁ =  a₂ = -2 ,  m = 2,

Oleh karena akar-akar karakteristiknya ganda,

maka solusi homogennya berbentuk        a_n^(h)  = (A₁ n^m-1 + A₂ n^m-2) a₁ⁿ  ,

a_n^(h)  = (A₁ n + A₂ ) (-2)ⁿ .

Contoh 4

Tentukan solusi homogen dari relasi rekurensi

4 a_n - 20 a_n-1 + 17 a_n-2 – 4 a_n-3 = 0.

Penyelesaian :

Persamaan karakteristiknya :      4 a³  - 20 a² + 17 a  - 4 = 0

akar-akar karakteristiknya         ½ , ½  dan   4

solusi homogennya berbentuk       a_n^(h)  = (A₁ n + A₂ ) (½)ⁿ + A₃ . 4ⁿ.

 

Solusi Khusus dari Relasi Rekurensi

            Pada dasarnya tidak ada satu metode yang dapat menentukan solusi khusus dari sebuah relasi rekurensi linier yang tidak homogen. Untuk menentukan solusi khusus dari sebuah relasi rekurensi linier dengan  f(n) ¹ 0, akan diberikan beberapa model solusi yang disesuaikan dengan bentuk  f(n). Model yang sering digunakan adalah model polinomial atau model eksponensial.

1.     Secara umum, jika  f(n)  berbentuk polinomial derajat  t  dalam  n  :

F₁ n^t + F₂ n^t-1  + … +  F_t n  + F_t+1   ,

maka bentuk dari solusi khusus yang sesuai adalah :

 P₁ n^t + P₂ n^t-1  + … +  P_t n  + P_t+1   

2.    Jika  f(n)  berbentuk  bⁿ  dan  b  bukan akar karakteristik dari persamaan homogen, maka jawab khusus berbentuk

 

P bⁿ

3.    Jika  f(n) berbentuk  (F₁.n^t + F₂.n^t-1 +…+ F_t.n + F_t+1 ).bⁿ  dan b bukan akar karakteristik dari persamaan homogen, maka bentuk dari solusi khusus yang sesuai adalah :

 (P₁ n^t + P₂ n^t-1  + … +  P_t n  + P_t+1  ) bⁿ

4.    Jika  f(n)  berbentuk  (F₁.n^t + F₂.n^t-1 +…+ F_t.n + F_t+1 ).bⁿ  dan b  akar karakteristik yang berulang sebanyak  (m-1)  kali, maka bentuk dari solusi khusus yang sesuai adalah :

n^m-1. (P₁ n^t + P₂ n^t-1  + … +  P_t n  + P_t+1  ) bⁿ

         

contoh 5

Diketahui a_r – 7 a_r-1 + 10 a_r-2 = 3^r . Tentukan solusi khusus dari a_r.

 

Penyelesaian :

Diketahui f(r) = 3^r .

Oleh karena bentuk dari f(r) tersebut adalah b^r dan b = 3 bukan akar karakteristik, maka solusi khusus dari relasi rekurensi tersebut berbentuk P3^r.

a_r = P 3^r.

Sumber : http://dc391.4shared.com/doc/ZhMl3NPZ/preview.html