Take a calculator and enter any number. Then press the cosine key over and over. Eventually the numbers will stop changing. You will either see 0.99984774 or 0.73908513, depending on whether your calculator was in degree mode or radian mode. This is an example of a fixed point, a point that doesn’t change when you apply a function.
The example above is actually two examples, one for cosine of x degrees and one for cosine of x radians. These are two different functions, and they have different fixed points. Note that the two fixed points are not simply related to each other by converting between degrees and radians.
Contraction mapping theorem
The functions
f(x) = cos(x)
and
g(x) = cos(πx/180)
are both contraction mappings, the former corresponding to radians and the latter to degrees. A function h(x) is a contraction mapping if for any two points x and y,
|h(x) − h(y)| ≤ c|x − y|
for some constant c < 1. You can use the mean value theorem to show that c = sin(1) for the function f, and c = π sin(π/180) for the function g.
The contraction mapping theorem says that if a function h is a contraction mapping on a closed interval, then h has a unique fixed point. You can generalize this from working on closed interval to working in any complete metric space.
Weak contraction mappings
The constant c above is important. Without it, you don’t necessarily have a fixed point. For example, let
f(x) = x + 1/x
on the interval [1, ∞). Then you can show that
|f(x) − f(y)| < |x − y|
for x ≠ y but the function f has no fixed point. To see this, suppose f(x) = x, then 1/x = 0, but the reciprocal of a positive number is positive.
If you start with a point x ≥ 1 and repeatedly apply f, you’ll get a sequence of points that move closer to each other, but not closer to any particular number. The sequence of iterates diverges.
A function satisfying the inequality above is called weak contraction mapping. In general, a weak contraction mapping need not have a fixed point, as in the example above. But a weak contraction on a compact space will have a fixed point.
Commentary
As discussed in the link about Kepler’s equation below, something like the contraction mapping theorem was used in practice long before it was formalized in theory.
When I was in grad school, I studied nonlinear PDEs. After seeing a long list of existence theorems and getting lost in the proofs, I wondered what was at the heart of all these theorems. Under all the layers of operator and function space definitions, somewhere there had to be core theorems that said something exists, and I went back over my lecture notes to dig for what these theorems were. In every case it boiled down to a fixed point theorem, not the contraction mapping theorem per se but analogous theorems.
Just for fun, I wrote a Python program to see how it would respond. The value oscillates between 0.7390851332151605 and 0.7390851332151608:
New x: 0.7390851332151605
New x: 0.7390851332151608
New x: 0.7390851332151605
New x: 0.7390851332151608
New x: 0.7390851332151605
New x: 0.7390851332151608
Here’s the code:
#!/usr/bin/env python3
from math import cos
x = 1.0
print(“Starting value: “, x)
for i in range(100):
x = cos(x)
print(“New x: “, x)
The oscillation is interesting. Of course it’s a numerical artifact.