# Finding the fixed points of a contraction

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}$)

-
Your question is confusing. First of all, apply $|f(x)-f(y)| < k |x-y|$ to $y=f(x)$ to get $|f(f(x))-f(x)|<k |f(x)-x|$, and, by induction, $f^{(m+1)}(x)-f^{(m)}(x)|< k^m |f(x)-x|$. The fixed point is the limit of $f^m(x)$. For any concrete computable $f$ you can get a good (exponentially fast) approximation to it just by repeatedly applying f. What exactly are you after? –  Max Nov 6 '10 at 13:58
The problem I was encountering was calculating $\lim_{n \rightarrow \infty} x_n$. The question was about finding this limit without numerical approximations. –  Andy Nov 6 '10 at 14:22

@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!

-
Thank you for pointing the whole thing out.. :) It's all clear now. –  Andy Nov 6 '10 at 18:36
You are welcome :-) –  knightofmathematics Nov 6 '10 at 20:54

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.

-
Alright, the solution of the equation is the fixed point, of course, but (I'm not sure I've been clear enough in the question) I wanted to know if there is a way to calculate $\lim_{n \rightarrow \infty} x_n$ in the "usual" way limits are calculated (like with big-O notation of asymptotics and such). –  Andy Nov 6 '10 at 14:25
@Andy: without knowing the true nature of $f$, your question cannot have a better answer than Hans's suggestion. –  Ｊ. Ｍ. Nov 6 '10 at 14:28
@J.M.: suppose $f(x) = \cos{x}$, then how could I do it the way I want to? i.e. not solving $x = \cos{x}$ –  Andy Nov 6 '10 at 14:31
@Andy: Roots of transcendental equations like yours generally do not have neat closed form expressions. –  Ｊ. Ｍ. Nov 6 '10 at 14:38
Andy, you are asking for something that is hopeless. In fact you've been misled by your experiences in calculus. Those are not the "usual" ways to find limits, because usually equations do not have closed form solutions. Anything that does is often a rigged example or a very elementary example. Heck, most infinite series like the power series for e^x or sin(x) can't be evaluated in closed form for generic choices of x. You have to settle for approximations with error estimate. That is real life, not a class. –  KCd Nov 6 '10 at 17:58

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.

-
Yes, that's what I wanted to avoid. But this is only because I don't like approximations much. :) –  Andy Nov 6 '10 at 14:23
Probably a better idea is to set up a Newton-Raphson iteration for $x=f(x)$; the convergence might be better than doing vanilla fixed-point iteration. –  Ｊ. Ｍ. Nov 6 '10 at 14:27