I define a recurrence relation as follow:

$$ω_{n+1}=f(ω_{n})$$ for some function $f$.

Assume that $f:ℝ⁺→ℝ⁺$ is a derivable, strictly increasing (so it is bijective) and a contraction function. Then $(ω_{n})$ converges to the fixed point of $f$, i.e., $ω_{n}$→$x$ with $f(x)=x$ and this is the only type of solutions for the above recurrence equation. This is the Banach fixed point theorem.

My question is: Find sufficient and necessary conditions on which the sequence $(ω_{n})$ converges to the fixed point of $f$ via:

(a) finite number of iterations

(b) infinite number of iterations

I know that this is depends on the choice of initial conditions. However, I cannot find the good idea to start.


Let $C$ be a closed subset of $\mathbb R$ such that

  • $f$ is continuous at $C$

  • The unique fixed point $L\in C$

  • $\exists N\in\mathbb N\;\; \forall n\geq N\;\; \omega_n\in C$


if $(\omega_n)_n$ converges to $\omega,\;\;\;\omega \in C$ and




$$\implies \omega=f(\omega)$$

$$\implies \omega=L.$$

The number of iterations, depends on initial value $\omega_0$ and how $f$ is contractive.

we have $|f(\omega_n)-L|\leq K^n|\omega_1-\omega_0|<\epsilon$

this gives the number $n$ of iterations.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.