How to analyze convergence of non-linear difference equation (recurrrence relations)

Question

I've a couple of functions, such as:

• $Y(t+1)=2-\ln(Y(t))$
• $Y(t+1)=(Y(t))^{-2}$
• $Y(t+2)=e^{-Y(t)}$

and I need to analyze stability and convergence. No problem with stability, but I can't figure out convergence.

I read that if the absolute value of:

$$\frac{dY(t+1)}{dY(t) }$$ is less than 1, it's convergent, and if it's greater it's divergent. Is that correct?

Could you please use some of my examples to explain how/why it´s right or not?

Thanks!

Answer 1

If I understand correctly, you are iterating a function such as $f(y)=2-\ln y$, $f(y)=y^{-2}$, or $f(y)=e^{-y}$. If the result of iteration converges, its limit is a fixed point of $f$, that is a solution of $f(y)=y$. A fixed point $y_*$ is classified as

• attracting if $|f'(y_*)|<1$
• repelling if $|f'(y_*)|>1$
• neutral if $|f'(y_*)|=1$

Iteration can never converge to a repelling fixed point, unless it jumps directly onto it. It will converge to an attracting fixed point provided it gets into a neighborhood of the point where $|f'|<1$.

For example, $f(y)=2-\ln y$ has one fixed point, which is attracting. So, the iteration converges there provided it starts in the vicinity of the fixed point, or gets there in the process. But this depends on the initial value. If you start with $Y(0)=0.001$, then $Y(1)\approx 8.9$ and $Y(2)<0$, hence $Y(3)$ is undefined. If you start with $Y(0)=0.01$, the iteration converges to fixed point.

Answer 2

The exact result follows from the Banach fixed point theorem. What you are interested is this particular corollary: if $f$ is continuously differentiable and $\sup\left|f^{\prime}\right|<1$ on $\Omega$, $f$ admits a (unique) fixed point on $\Omega$. A fixed point of $f$ is a point $y$ such that $$ f\left(y\right)=y. $$

Let's rewrite your iterations to make this a little more clear. If we consider $$ y_{n+1}=2-\ln y_{n} $$ the relevant function is $$ f\left(y\right)=2-\ln y. $$ Note that $$ \left|f^{\prime}\left(y\right)\right|=\frac{1}{\left|y\right|}. $$ We will assume our iteration is defined only for real numbers ($\ln x$ for $x<0$ is undefined in this case), so that the requirement $1/\left|y\right|<1$ becomes $$ y>1. $$ Our set $\Omega$ is thus all the real numbers larger than 1. So if we choose a point $y_{0}>1$, we are certain our iteration converges to some point $y^\star$ in $\Omega$. Regardless of what $y_0$ in $\Omega$ we pick, we will always get the same point.

We can verify this numerically. If we pick $y_{0}=2$, we get $y_{1}\approx1.3069$, $y_{2}\approx1.7324$, $y_{3}\approx1.4504$, $y_{4}\approx1.6281$, etc. and if we look far enough in this sequence, we can see that $y^\star = \lim_{n\rightarrow\infty}y_{n}\approx1.5571$.