Metric Spaces, Contraction Maps and Fixed Point Iteration

Contraction Maps and Fixed Point Iteration

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₀, 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₀ to a₁. Hence the distance from a₁ to a₂ is at most dk. The distance from a₂ to a₃ is at most dk², 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.