3
$\begingroup$

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

  • 0
    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)|$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? – 2010-11-06
  • 0
    The problem I was encountering was calculating $\lim_{n \rightarrow \infty} x_n$. The question was about finding this limit without numerical approximations.2010-11-06

3 Answers 3

1

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.

  • 0
    Yes, that's what I wanted to avoid. But this is only because I don't like approximations much. :)2010-11-06
  • 1
    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.2010-11-06
6

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.

  • 0
    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).2010-11-06
  • 0
    @Andy: without knowing the true nature of $f$, your question cannot have a better answer than Hans's suggestion.2010-11-06
  • 0
    @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}$2010-11-06
  • 0
    @Andy: Roots of transcendental equations like [yours](http://mathworld.wolfram.com/DottieNumber.html) generally do not have neat closed form expressions.2010-11-06
  • 0
    @J.M.: My example was a bit too naive. 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?2010-11-06
  • 1
    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.2010-11-06
  • 0
    For the example of solving cos(x) = x, see Example 2.1, Corollary 2.3, and Example 2.4 of http://www.math.uconn.edu/~kconrad/blurbs/analysis/contractionshort.pdf2010-11-06
  • 0
    To add to KCd's comment @Andy, if indeed in practice you find a neat solution to a transcendental equation that is complicated enough, you should count yourself as incredibly lucky.2010-11-06
4

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