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 a0, we will show that the sequence of points ai+1 = f(ai) is cauchy. Remember that the lipschitz constant k is less than 1. Let d be the distance from a0 to a1. Hence the distance from a1 to a2 is at most dk. The distance from a2 to a3 is at most dk2, and so on. The distance between am and an, for n > m, is no larger (by the triangular inequality) then the distance from am to am+1, plus the distance from am+1 to am+2, plus the distance from am+2 to am+3, and so on. This is bounded by the tail of the geometric series dkm + dkm+1 + dkm+2 and so on. This in turn is equal to dkm/(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 am+1 to s is bounded by k times the distance from am 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.