be a complete metric space
, and let f: X->X
be a contracting function
(we shall be using the definition
s and symbol
s 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 converge
s to the fixed point of f
; this method is in fact used, e.g. to draw fractal
s or solve differential equation
Uniqueness is easy: suppose x,y are 2 fixed points of f. Then
<1, so d
)=0 and x=y
has at most one fixed point.
For existence, first note that any contracting function must be continuous. Pick any x0 in X, and define xn=f(xn-1).
If we can prove that this sequence converges, by applying f and using its continuity we see that
f(lim xn) =
lim f(xn) =
lim xn+1 =
so the limit is a (the) fixed point of f
Then utilising the definition of a contracting function n times, d(xn+1,xn) <= d cn.
But this means that if m>n then
d(xm,xn) < d cn / (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.