Conditions to apply Banach fixed-point theorem

Question

Say that we have a recurrence of the form $u_{n+1}=f(u_{n})$, where $f:R \to R$, then, what is the conditions on $f$ to have a convergent series $u_{n}$.

I have the following questions:

• Is it enough for $f$ to be continuous? or it must be a map over $R$ too?
• Is it enough that $f$ is continuous/map over the interval $[u_0,p]$ where p satisfies $p=f(p)$
• A special example, If $f$ is a quadratic function of the form $f(x)=ax^2+bx+c$, then, what is the conditions on $a,b,c$ to guarantee the convergence of $u_n$?

Answer 1

The conditions to apply the Banach fixed point theorem are right there in the statement of the theorem. (Since you are restricting to real-valued functions of a real variable, I will give that version of the Banach fixed point theorem. The full theorem applies to maps from a complete metric space to itself.)

If $U \subset \Bbb R$ and $f$ is a real-valued function defined on $U$ such that

• $U$ is closed and non-empty,
• $f(U) \subseteq U$, ($f(U) = \{f(x) \mid x \in U\}$), and
• there is some $q \in [0,1)$ such that for every $x, y \in U, |f(x) - f(y)| \le q|x - y|$. (I.e., $f$ is a contraction.)

then $f$ has a unique point $t$ such that $f(t) = t$, and for every $u_0 \in U$, the sequence defined by $u_n = f(u_{n-1})$ for $n > 0$, converges to $t$.

The theorem is proved by choosing an arbitrary $u_0 \in U$, forming the sequence $(u_n)$, and noting that the contraction condition forces $(u_n)$ to be Cauchy, so it converges to some value $t$, and further, by continuity of the absolute value and subtraction, $|t - f(t)| \le q|t - f(t)|$. Since $q < 1$, this can only be true if $f(t) = t$. Finally, if $t'$ is another fixed point, then $|t - t'| = |f(t) - f(t')| \le q|t - t'|$, which again cannot be true except when $|t - t'| = 0$.

The requirements are all needed for the proof to work:

• If $U$ is empty, then it has no points, much less fixed points.
• If $U$ is not closed, then the Cauchy sequence can converge to a point outside of $U$. Since such a $t$ is not in the domain of $f$, it cannot be a fixed point of $f$.
• If the range $f(U)$ is not contained in the domain $U$, then it could be that for some $u_{k-1}, u_k = f(u_{k-1}) \notin U$. And therefore, $f(u_k)$ need not exist, making $u_{k+1}$ undefinable.
• If $f$ is not a contraction, then there is no guarantee that the sequence $(u_n)$ is Cauchy. It need not converge.

Note that there is no mention of continuity of $f$. It is not an explicit requirement of the theorem. However, it is easy to prove that all contractions are continuous.