Relasi Rekursif

FUNGSI NUMERIK

            Sebuah fungsi adalah sebuah relasi biner yang secara unik menugaskan kepada setiap anggota domain, satu dan hanya satu elemen kodomain. Fungsi diskrit numerik, atau singkatnya disebut fungsi numerik, adalah sebuah fungsi dengan himpunan bilangan cacah sebagai domain dan himpunan bilangan riil sebagai kodomainnya. Fungsi numerik ini menjadi pokok bahasan yang menarik karena sering digunakan dalam komputasi digital.

Relasi Rekursif

Relasi, dalam  ”MATEMATIKA” adalah hubungan antara dua buah elemen himpunan. Hubungan ini bersifat abstrak, dan tidak perlu memiliki arti apapun baik secara konkrit maupun secara matematis. Relasi biner R antara A dan B adalah himpunan bagian dari A x B. Himpunan A disebut daerah asal (domain) dari R dan himpunan B disebut daerah hasil (range) dari R. Relasi pada himpunan A adalah relasi dari A x A.

Relasi rekursif sering juga disebut relasi berulang . relasi ini mendefinisikan sebuah barisan dengan memberikan nilai ke-n yang dikaitkan dengan suku – suku sebelumnya . untuk mendefinisikan sebuah barisan, relasi berulang memerlukan nilai awal yang sudah ditentukan. Secara formal relasi berulang ini didefinisikan sebagai berikut:
Definisi sebuah relasi berulang untuk barisan a0, a1, a2, . . . merupakan sebuah persamaan yng mengkaitkan an dengan 0, a1, a2, . . . , an-1. Syarat awal untuk barisan a0, a1, a2, . . . adalah nilai nilai yang diberikan secara eksplisit pada beberapa suku dari barisan tersebut.

Contohnya:

Barisan 3, 7 , 11, 15, . . . didefinisikan dengan relasi berulang an = an-1 + 4 untuk n ≥ 1 dengan syarat awal a0 = 3.

Contoh 2

Carilah relasi berulang dengan syarat awal dari barisan 1, 1, 2, 4, 16, 128, 4096, . . .

Penyelesaian

Bentuk rumusan setiap suku dengan menggunakan suku sebelumnya

1 = 1

1 = 1 X 1

2 = 2 X 1 X 1

4 = 2 X 2 X 1

16 = 2 X 4 X 2

128 = 2 X 16 X 4

4096 = 2 X 128 X 16 X 4

Dengan demikian relasi yang berulang yang diperoleh adalah an = 2 X an-1 X 2 X an-2 untuk n≥2

Dengan syarat awal a0 = 1 dan a1 = 1

Relasi rekursif sering juga disebut relasi berulang . relasi ini mendefinisikan sebuah barisan dengan memberikan nilai

ke-n yang dikaitkan dengan suku – suku sebelumnya . untuk mendefinisikan sebuah barisan, relasi berulang memerlukan nilai awal yang sudah ditentukan.

Secara formal relasi berulang ini didefinisikan sebagai berikut:

Definisi sebuah relasi berulang untuk barisan a0, a1, a2, . . . merupakan sebuah persamaan yng mengkaitkan an dengan 0, a1, a2, . . . , an-1. Syarat awal untuk barisan a0, a1, a2, . . .

adalah nilai nilai yang diberikan secara eksplisit pada beberapa suku dari barisan tersebut.

@: 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 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.  Apabila 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.