Finding the fixed points of a contraction

Question

Banach's fixed point theorem gives us a sufficient condition for a function in a complete metric space to have a fixed point, namely it needs be a contraction.

I'm interested in how to calculate the limit of the sequence $x_0 = f(x), x_1 = f(x_0), \ldots, x_n = f(x_{n-1})$ for a fixed $x$. I couldn't figure out a way to do this limit with ordinary limits calculations.

The only thing I have at my disposal is the proof of the theorem, from which we see that the sequence $x_n$ is a Cauchy sequence; from this, I'm able to say, for example, that $\left|f(f(f(x))) - f(f(f(f(x))))\right| \leq \left|f(x_0)-f(x_1)\right| ( \frac{k^3}{1-k})$, where $k$ is the contraction constant, but I can't get any further in the calculations.

My question is: how should I procede to calculate this limit exactly? If there are non-numerical (read: analytical) way to do this.

Remark: I'm interested in functions $\mathbb{R} \rightarrow \mathbb{R}$ (as it can be seen from my use of the euclidean metric in $\mathbb{R}$)

Answer 1

@Andy (in reply to your comment/question "Could you provide some example that has a closed form and explain if (and how) it is possible to find the fixed point without solving x = f(x) but trying to calculate the limit of x_n?":

I believe that you would be hard-pressed to achieve this, since your function $f$ is a continuous function (being a contraction map in the first place); and if you then take limits of both sides of $x_n = f(x_{n-1})$, you will get:

$$\lim_{n \rightarrow \infty} x_n = \lim_{n \rightarrow \infty} f(x_{n-1})$$

which (by continuity) leads to:

$$\lim_{n \rightarrow \infty} x_n = f (\lim_{n \rightarrow \infty} x_{n-1})$$

or

$$l = f(l)$$

with $l = \lim_{n \rightarrow \infty} x_n$

This means that you will have to solve $l = f(l)$, which was what you wanted to avoid in the first place!

Answer 2

The limit is the fixpoint, so you "just" need to solve the equation $x=f(x)$. Whether this can be done in closed form or not depends on what $f$ looks like.

Answer 3

In addition to what Hans Lundmark has said about solving $x = f(x)$, you could also try writing a simple computer programme to read a number $n$ and a starting value $x_0$, and compute the result of applying f to $x_0$ $n$ times, thus delivering an approximation to the root that you are seeking. The value of $n$ may have to be fairly large in some cases.