Let

*X* be a

complete metric space, and let

*f: X->X* be a

contracting function (we shall be using the

definitions and

symbols of my

writeup in that

node, so you might want to read it). Our aim is to show that

*f* has a

*unique* fixed point. The

proof gives a taste of

constructive methods in complete metric spaces; non-constructive methods also abound, but have a vastly different character. In particular, we shall give a method which

converges to the fixed point of

*f*; this method is in fact used, e.g. to draw

fractals or solve

differential equations.

Uniqueness is easy: suppose *x,y* are 2 fixed points of *f*. Then

*d*(*x,y*) =
*d*(*f(x),f(y)*) <=
*c d*(*x,y*)

with

*c*<1, so

*d*(

*x,y*)=0 and

*x=y* --

*f* has at most one fixed point.

For existence, first note that any contracting function must be continuous. Pick *any* *x*_{0} in *X*, and define *x*_{n}=*f*(*x*_{n-1}).
If we can prove that this sequence converges, by applying *f* and using its continuity we see that

f(lim *x*_{n}) =
lim *f*(*x*_{n}) =
lim *x*_{n+1} =
lim *x*_{n},

so the limit is a (the) fixed point of

*f*
Write *d*=*d*(*x*_{0},*x*_{1}).
Then utilising the definition of a contracting function *n* times, *d*(*x*_{n+1},*x*_{n}) <= *d c*^{n}.
But this means that if *m*>*n* then
*d*(*x*_{m},x_{n}) < *d c*^{n} / (1-*c*), so our sequence is a Cauchy sequence. Thus it has a limit, which we saw is the fixed point of *f*.

Note that the above is a procedure for converging to the fixed point! Furthermore, we see that the rate of convergence is respectable -- a constant number of digits for each iteration.