Lompat ke konten Lompat ke sidebar Lompat ke footer

Solusi Korelasi Rekurensi Linier Homogen

Setelah paham perihal pengertian Relasi rekurensi Linear, non-linear, Homogen dan tak homogen. Berikut akan dibahas perihal solusi penyelesaian kekerabatan rekurensi Linear Homogen.

Solusi kekerabatan rekurensi Linear homogen 1
Solusi dari kekerabatan rekurensi $a_n=ca_{n−1}$, n≥0, c konstan, dan $a_0=A$ dirumuskan dengan $a_n=Ac^n$.
Pembuktian:
Penyelesaian permasalahan kekerabatan rekurensi linear dilakukan dengan pendekatan awal dimana solusi dari  $a_n=r^n$, dimana r konstan. Ingat kembali, $a_n=r^n$ ialah solusi dari kekerabatan rekurensi
$a_n = c_1a_{n_1} + c_2a_{n-2} + \ldots +c_ka_{n-k}$
kalau dan hanya jika
$r^n=c_1r^{n-1}+c_2r^{n-2}+ \ldots+c_kr^{n-k}$
Jika disamakan,
 $a_n=r^n$
$ c_1a_{n_1} + c_2a_{n-2} + \ldots +c_ka_{n-k}= r^n=c_1r^{n-1}+c_2r^{n-2}+ \ldots+c_kr^{n-k}$
Dibagi $r^{n-k}$ Diperoleh,
$\begin{align*}  r^k - c_1r^{k-1} - c_2r^{k-2} - \ldots - c_k = 0  \end{align*}$
Akibatnya:
Barisan ($a_n$) dengan $a_n=r^n$ merupakan solusi kalau dan hanya kalau r ialah solusi dari persamaan terakhir.

Contoh Soal dan Penyelesaian Rekurensi Linear Homogen 1
Soal 1:
Solusi kekerabatan rekurensi $a_n=7a_{n−1}$, dimana n≥0 dan $a_2=98$ !

Pembahasan:
Bentuk alternatif dari kekerabatan $a_n=7a_{n−1}$ untuk n≥0  dan $a_2=98$. Oleh lantaran itu solusi umumnya mempunyai bentuk $a_n=a_0(7^n)$. Karena $a_2=98=a_0(7^2), karenanya $a_0=2$, dan $a_n=2(7^n)$ untuk n≥0.

Soal 2:
Temukan $a_{12}$ kalau $a^2_n=5a^2_{n−1}$; dimana $a_n$>0 untuk n≥0, dan $a_0$=2

Pembahasan:
Walau kekerabatan rekurensi ini tak-linear, kalau dimisalkan $b_n=a^2_n$, maka diperoleh kekerabatan yang gres $b_n=5b_{n−1}$ untuk n≥0, dan $b_0=4$, yang merupakan kekerabatan rekurensi linear dengan solusi $b_n=4(5^n)$. Dengan demikian $a_n=2( \sqrt 5)^n$ untuk n≥0, dan $a_{12}=2( \sqrt 6)^{12}=31250$.

Solusi kekerabatan rekurensi Linear homogen 2
Misal $c_1$ dan $c_2$ ialah bilangan real. Misalkan pula $r^2−c_1^r−c_2=0$  mempunyai dua akar berbeda yaitu $r_1$ dan $r_2$. Maka barisan ($a_n$) ialah solusi dari kekerabatan rekurensi $a_n=c_1a_{n-1}+c_2a_{n-2}$  kalau dan hanya kalau $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ untuk n = 0,1,2,...., dimana α1 dan α2 konstan.
Pembuktian:
Akan dipakai 2 proposisi dalam pembuktian ini,
(i) kalau $r_1$ dan $r_2$ adalah akar-akar dari persamaan karakteristik, dan α1,α2 konstan, maka barisan (an) dengan $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ merupakan solusi dari kekerabatan rekurensi

Karena $r_1$ dan $r_2$ ialah akar - akar dari $r^2−c_1r−c2=0$, maka $r^2_1=c_1r_1+c_2$ dan $r^2_2=c_1r_2+c_2$
Bisa ditulis kesamaan:
$\begin{align*} c_1a_{n-1}+c_2a_{n-2}&=c_1(\alpha_1r_1^{n-1}+\alpha_2r_2^{n-1})+c_2(\alpha_1r_1^{n-2}+\alpha_2r_2^{n-2})\\ &= \alpha_1r_1^{n-2}(c_1r_1+c_2)+\alpha_2r_2^{n-2}(c_1r_2+c_2)\\ &= \alpha_1r_1^{n-2}r_1^2+\alpha_2r_2^{n-2}r_2^2\\ &= \alpha_1r_1^n+\alpha_2r_2^n\\ &=a_n \end{align*}$

Terbukti $a_n$ dengan $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ ialah solusi rekurensi.

(ii) kalau barisan ($a_n$) merupakan solusi, maka $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ untuk α1 dan α2 yang konstan.

misal bahwa ($a_n$) ialah solusi kekerabatan rekurensi, dengan syarat awal $a_0=C_0$ dan $a_1=C_1$. Akan ditunjukkan bahwa ada α1 dan α2 yang konstan sehingga barisan ($a_n$) dengan $a_n=\alpha_1r_1^n+\alpha_2r_2^n$ memenuhi syarat awal yang sama. Perhatikan,
 $a_0 = C_0 = \alpha_1 + \alpha_2\\ a_1 = C_1 = \alpha_1r_1 + \alpha_2r_2 $
Dari persamaan pertama, diperoleh $\alpha_2=C_0 - \alpha_1$. Dengan mensubstitusikan nilai α2 ke persamaan kedua diperoleh
$\begin{align*}  C_1 = \alpha_1r_1 + (C_0 - \alpha_1)r_2 \end{align*}$
Akibatnya
$\begin{align*}  C_1 = \alpha_1(r_1 - r_2) + C_0r_2 \end{align*}$
Ini memperlihatkan
$\begin{align*} \alpha_1 = \frac{C_1 - C_0r_2}{r_1 - r_2} \end{align*}$
dan
$\begin{align*}  \alpha_2= C_0 - \alpha_1 = C_0 - \frac{C_1 - C_0r_2}{r_1 - r_2}=
\frac{C_0r_1 - C_1}{r_1 - r_2} \end{align*}$ (syarat $r_1 \neq r_2$
memenuhi dua syarat awal (sebagai solusi). Bisa disimpulkan,

Contoh Soal Penyelesaian Rekurensi Linear Homogen 2
Soal 1: Tentukan $(1+\sqrt{3}i)^{10}$

Pembahasan:
Misalkan $z=1+ \sqrt {3i}$, maka $x=1$, $y= \sqrt 3$, r=2, dan θ= \frac { \pi}{3}$.
$\begin{align*} (1+\sqrt{3}i)^{10} &= 2^{10}(cos \ \frac{10\pi}{3} + i \ sin \
\frac{10\pi}{3})\\ &= 2^{10}(cos \ \frac{4\pi}{3} + i \ sin \ \frac{4\pi}{3})\\
&= 2^{10}((-\frac{1}{2}) - (\frac{\sqrt{3}}{2})i)\\ &= (-2^9)(1+\sqrt{3}i) \end{align*}$

Soal 2: Selesaikan kekerabatan rekurensi $a_n=2(a_{n−1}−a_{n−2})$, dimana n≥2 dan $a_0=1$, $a_2=2$.

Pembahasan:
Persamaan karakteristik dari kekerabatan rekurensi tersebut ialah $r^2−2r+2=0$, dan akar-akarnya ialah $r_1=1+i$ dan $r_2=1−i$. Sehingga, barisan ($a_n$) ialah solusi kekerabatan rekurensi tersebut kalau dan hanya jika
$ \begin{align*} a_n = \alpha_1(1+i)^n + \alpha_2(1-i)^n, \end{align*}$

Berdasarkan teorema DeMoivre,
$\begin{align*} a_n &= \alpha_1(\sqrt{2})^n(cos \ \frac{n\pi}{4} + i \ sin \
\frac{n\pi}{4}) + \alpha_2(\sqrt{2})^n(cos \ \frac{-n\pi}{4} + i \sin \ \frac{-n\pi}{4})\\ &= \alpha_1(\sqrt{2})^n(cos \ \frac{n\pi}{4} + i \ sin \
\frac{n\pi}{4}) + \alpha_2(\sqrt{2})^n(cos \ \frac{n\pi}{4} - i \ sin \ \frac{n\pi}{4})\\ &= (\sqrt{2})^n(k_1 \ cos \ \frac{n\pi}{4} + k_2 \ \ sin \ \frac{n\pi}{4}) \end{align*}$

dimana $k_1 = \alpha_1+\alpha_2$ dan $k_2=(\alpha_1-\alpha_2)i$. Dengan memasukkan nilai dari syarat awal, akan diperoleh
$\begin{align*} a_0 &= 1 = (\sqrt{2})^0(k_1 \ cos \ 0 + k_2 \ sin \ 0) = k_1\\
a_1 &= 2 = (\sqrt{2})^1(k_1 \ cos \ \frac{\pi}{4} + k_2 \ \ sin \  \frac{\pi}{4}) = 1 + k_2, \end{align*}$
sehingga $k_1=1$ dan $k_2=1$. Jadi, solusi dari kekerabatan rekurensi $a_n=2(a_{n−1}−a_{n−2})$, dimana n≥2 dan $a_0=1$, $a_2=2$ adalah
$\begin{align*} a_n=(\sqrt{2})^n(\ cos \ \frac{n\pi}{4} + \ \ sin \  \frac{n\pi}{4}), n \geq 0. \end{align*}$


Solusi kekerabatan rekurensi Linear homogen 3
Misal $c_1$ dan $c_2$ ialah bilangan real dengan $c_2≠0$. Misalkan pula $r^2−c_1r−c_2=0$  mempunyai akar kembar yaitu $r_1=r_2=r$. Maka barisan ($a_n$) ialah solusi dari kekerabatan rekurensi $a_n=c_1a_{n−1}+c_2a_{n−2}$ kalau dan hanya kalau $a_n=\alpha_1r^n+\alpha_2nr^n $untuk n = 0,1,2,...., dimana α1 dan α2 konstan.

Contoh Soal
Carilah solusi dari kekerabatan rekurensi $a_n=6a_{n−1}−9a_{n−2}$ dengan syarat awal $a_0=1$ dan $a_1=6$

Pembahasan:
Akar dari persamaan $r_2−6r+9=0$ ialah r=3. Sehingga, solusi dari kekerabatan rekurensi ini adalah
$\begin{align*} a_n=\alpha_13^n + \alpha_2n3^n \end{align*}$
substitusikan nilai dari syarat awal $a_0=1$ dan $a_1=6$ diperoleh
$\begin{align*} a_0&= 1 =\alpha_1\\ a_1&=\alpha_1.3 + \alpha_2.3 \end{align*}$
dengan menuntaskan kedua persamaan di atas, diperoleh nilai α1=1 dan α2=1. Akibatnya, solusi dari kekerabatan rekurensi tersebut,
$\begin{align*} a_n=3^n + n3^n.\end{align*}$

solusi kekerabatan rekurensi linier homogen kalau ordenya lebih dari dua
Misalkan $c_1,c_2,…,c_k$ ialah bilangan real. Misalkan pula persamaan karakteristik 
$\begin{align*} r^k-c_1r^{k-1}-\ldots- c_k =0 \end{align*}$ mempunyai k akar yang berbeda yaitu $r_1,r_2,…,r_k$. Maka barisan ($a_n$) ialah solusi dari kekerabatan rekurensi $ \begin{align*} a_n=c_1a_{n-1}+c_2a_{n-2}+\ldots+c_ka_{n-k} \end{align*}$jika dan hanya kalau $\begin{align*} a_n=\alpha_1r_1^n+\alpha_2r_2^n+\ldots+\alpha_kr_k^n \end{align*}$ untuk n = 0,1,2,...., dimana α1,α2,…,αk konstan.
Contoh Soal:
Solusi dari kekerabatan rekurensi $a_n=6a_{n-1}-11a_{n-2}+6a_{n-3}$ dengan syarat awal $a_0=2, a_1=5,  a_2=15 $ adalah...

Pembahasan:
Persamaan karakteristik polinomial kekerabatan rekurensi ini ialah $r^3 - 6r^2 + 11r -6 = 0$ akar-akar karakteristiknya ialah $r_1=1,r_2=2,  r_3=3$, lantaran $r^3 - 6r^2 + 11r -6 = (r-1)(r-2)(r-3)$
solusi kekerabatan rekurensi ini berbentuk
$a_n=\alpha_1.1^n + \alpha_2.2^n + \alpha_3.3^n $
Untuk menemukan nilai α1,α2, dan α3, kita gunakan syarat awal yang telah ditentukan sebelumnya, yaitu  $a_0=2, a_1=5,  a_2=15 $.
$\begin{align*} a_0 &= 2 = \alpha_1 + \alpha_2 + \alpha_3\\ a_1 &= 5 = \alpha_1 + \alpha_2.2 + \alpha_3.3 \\ a_2 &= 15 = \alpha_1 + \alpha_2.4 + \alpha_3.9 \end{align*}$
Setelah diselesaikan (subtitusi-eliminasi) diperoleh nilai α1=1 , α2=−1, dan α3=2
sehingga solusinya dapat disebut, $a_n= 1 - 2^n + 2.3^n$

solusi rekurensi linier homogen orde lebih dari dua kalau persamaan karakteristiknya mempunyai beberapa akar yang kembar 
Misalkan $c_1,c_2,…,c_k $adalah bilangan real. Misalkan pula persamaan karakteristik $r^k-c_1r^{k-1}-\ldots- c_k =0 $
mempunyai t akar yang berbeda yaitu $r_1$ sebanyak $m_1$, $r_2$ sebanyak $m_2$ ,..., $r_t$ sebanyak $m_t$ sedemikian sampai $m_i$≥1 dengan i=1,2,…,t dan $m_1+m_2+…,m_t=k$. Maka
barisan ($a_n$) ialah solusi dari kekerabatan rekurensi
$a_n=c_1a_{n-1}+c_2a_{n-2}+\ldots+c_ka_{n-k}$
kalau dan hanya jika
$\begin{align*} a_n=&(\alpha_{1,0}+\alpha_{1,1}n+\ldots+\alpha_{1,m_1-1}n^{m_1-1})r_1^n\\ &+ (\alpha_{2,0}+\alpha_{2,1}n+\ldots+\alpha_{2,m_2-1}n^{m_2-1})r_2^n\\ &+\ldots+(\alpha_{t,0}+\alpha_{t,1}n+\ldots+\alpha_{t,m_t-1}n^{m_t-1})r_t^n  \end{align*}$
untuk n = 0,1,2,...., dimana α$_{i,j}$ konstan untuk 1≤i≤t dan 0≤j≤m$_i$−1

Contoh Soal:
Temukan solusi dari kekerabatan rekurensi $a_n=-3a_{n-1} - 3a_{n-2} - a_{n-3}$ dengan syarat awal $a_0=1,a_1=−2,  a_2=−1$.

Pembahasan:
Persamaan karakteristik dari kekerabatan rekurensi ini ialah $r^3 + 3r^2 + 3r + 1 = 0$ alasannya Karena $r^3 + 3r^2 + 3r + 1 =(r+1)^3$ , r=-1
solusi kekerabatan rekurensi ini berbentuk
$a_n=\alpha_{1,0}(-1)^n+\alpha_{1,1}n(-1)^n+\alpha_{1,2}n^2(-1)^n $
masukkan syarat awalnya.
$\begin{align*} a_0 &= 1 = \alpha_{1,0}\\ a_1 &= -2 = -\alpha_{1,0} - \alpha_{1,1} - \alpha_{1,2}\\ a_2 &= -1 = \alpha_{1,0} + 2\alpha_{1,1}+ 4\alpha_{1,2} \end{align*}$
Selesaikan tiga persamaan diatas dan diperoleh akan  α$_{1,0}$=1,α$_{1,1}$=3, dan α$_{1,2}$=−2
Dan solusinya dapat ditulis,
$a_n=(-1)^n+3n(-1)^n - 2n^2(-1)^n$

Posting Komentar untuk "Solusi Korelasi Rekurensi Linier Homogen"