Is the scheme for generating $p_n=(1/3)^n$ stable or not?
$$p_n= \frac{5}{6} p_{n-1} - \frac{1}{6}p_{n-2}.$$
Is the following scheme for generating $p_n=(1/3)^n$ stable or not. $p_n=(5/6)p_{n-1}-(1/6)p_{n-2}$.
Asked
Active
Viewed 69 times
2
-
Write it as matrix recurrence and look at the eingenvalues. – lhf Feb 11 '14 at 19:50
-
how do i write the matrix recurrence? – user128024 Feb 11 '14 at 21:06
-
Write $u_n= [ p_n, p_{n-1}]$ and write $u_n= A u_{n-1}$ for some matrix $A$. – lhf Feb 11 '14 at 21:14
-
1should the term that multiplies $\frac 56$ be $p_{n-1}$? It appears so – Ross Millikan Feb 11 '14 at 22:57
-
yes it should have been n-1 sorry i mistyped it... – user128024 Feb 11 '14 at 23:35
-
Isn't important to derive the general term ?. – Felix Marin Feb 11 '14 at 23:55
1 Answers
2
From your recursion, we have $$ \left[\begin{array}{c}p_n\\p_{n-1}\end{array}\right] =\left[\begin{array}{c}5/6&-1/6\\1&0\end{array}\right] \left[\begin{array}{c}p_{n-1}\\p_{n-2}\end{array}\right] $$ The eigenvalues of the matrix are $$ \frac12\quad\text{for }\left[\begin{array}{c}1/2\\1\end{array}\right] $$ and $$ \frac13\quad\text{for }\left[\begin{array}{c}1/3\\1\end{array}\right] $$ Since $$ \left[\begin{array}{c}1/2&1/3\\1&1\end{array}\right]^{-1} \left[\begin{array}{c}p_1\\p_0\end{array}\right] =\left[\begin{array}{c}6p_1-2p_0\\-6p_1+3p_0\end{array}\right] $$ we get $$ \left[\begin{array}{c}p_n\\p_{n-1}\end{array}\right] =\dfrac1{2^{n-1}}\left[\begin{array}{c}1/2\\1\end{array}\right](6p_1-2p_0) +\dfrac1{3^{n-1}}\left[\begin{array}{c}1/3\\1\end{array}\right](-6p_1+3p_0) $$ Thus, unless you start with a multiple of $\left[\begin{array}{c}1/3\\1\end{array}\right]$, the system will tend to $$ \left[\begin{array}{c}p_n\\p_{n-1}\end{array}\right] \to\dfrac1{2^{n-1}}\left[\begin{array}{c}1/2\\1\end{array}\right](6p_1-2p_0) $$
Another approach:
Your recursion has the characteristic equation $$ 0=x^2-\frac56x+\frac16=\left(x-\frac12\right)\left(x-\frac13\right) $$ Thus, the solutions are of the form $$ \begin{align} p_n &=\frac{a}{2^n}+\frac{b}{3^n}\\ &=\frac{-2p_0+6p_1}{2^n}+\frac{3p_0-6p_1}{3^n} \end{align} $$ Note that if $p_0=3p_1$, then $p_n$ grows like $3^{-n}$; otherwise, it grows like $2^{-n}$.
robjohn
- 345,667
-
j need to do it by the error growth method? could you give me an idea about that method? – user128024 Feb 12 '14 at 01:28
-
@user128024: I am not quite sure what you mean by "error growth method". I have added a second approach. Perhaps that will help. – robjohn Feb 12 '14 at 04:01