# Metric Spaces, Contraction Maps and Fixed Point Iteration

## Contraction Maps and Fixed Point Iteration

A function f that takes one metric space into another is a contraction map
if it has a
lipschitz constant less than 1.
Such a map is automatically uniformly continuous.
Let f be a contraction map from a complete metric space into itself.
We will prove the existance of an s such that f(s) = s.
This is the fixed point.
Furthermore, repeated invokations of f, starting at any point x, move inexorably towards s.

For any starting point a_{0},
we will show that the sequence of points a_{i+1} = f(a_{i}) is cauchy.
Remember that the lipschitz constant k is less than 1.
Let d be the distance from a_{0} to a_{1}.
Hence the distance from a_{1} to a_{2} is at most dk.
The distance from a_{2} to a_{3} is at most dk^{2}, and so on.
The distance between a_{m} and a_{n}, for n > m,
is no larger (by the triangular inequality)
then the distance from a_{m} to a_{m+1},
plus the distance from a_{m+1} to a_{m+2},
plus the distance from a_{m+2} to a_{m+3},
and so on.
This is bounded by the tail of the geometric series
dk^{m} + dk^{m+1} + dk^{m+2} and so on.
This in turn is equal to dk^{m}/(1-k).
As m increases, terms of the sequence cluster together, and the sequence is cauchy.

Remember that the domain is complete,
hence the sequence approaches a point s.
In fact the approach is geometric.
The distance from a_{m+1} to s is bounded by k times the distance from a_{m} to s.

Finally the fixed point is unique.
If s and t are distinct fixed points,
then f(s) and f(t) are closer to each other than s an t,
which is impossible if s and t are fixed.

As we saw in the previous section, a lipschitz constant can often be inferred from the derivative of f.
If the derivative is bounded below 1, then f is a contraction map.
Start anywhere, repeatedly invoke f,
and you will approach the fixed point.
Furthermore, the algorithm is efficient,
since the approach is geometric.
Each step adds a certain number of digits to the precision.

For example, we can solve cos(x)-3x = 0 numerically by repeatedly evaluating cos(x)/3.
The derivative is bounded by 1/3, so the procedure is sure to work.