The Contraction Cobweb

The cobweb between

y = x

and

y = f(x)

gets sucked into one point. The error shrinks like

q^n

Examples & Exercises

Show $f(x) = \frac{x}{2} + 1$ is a contraction with $q = \frac12$ ; find the fixed point and the error bound.

x^* = 2, \quad |x_n - 2| \le \left(\tfrac12\right)^n |x_0 - 2|

x_0 = 0

n = 8

: the error

= 0.0078

matches the bound exactly.

Show proof

$|f(x) - f(y)| = \left|\frac{x-y}{2}\right| = \frac12|x - y|$ , so $f$ is a contraction with $q = \frac12$ .
Solving $x = \frac{x}{2} + 1$ gives $x^* = 2$ .
Since $|x_{n+1} - 2| = \frac12|x_n - 2|$ , induction gives $|x_n - 2| = \left(\frac12\right)^n|x_0 - 2|$ . For $x_0 = 0$ , $n = 8$ , the error is $\frac{2}{256} = 0.0078125$ .

Show $\cos x$ is a contraction on $[0,1]$ ; explain the existence and uniqueness of the Dottie number $x^* \approx 0.739$ .

|\cos x - \cos y| \le \sin(1)\,|x - y|, \quad \sin(1) \approx 0.8415 < 1

n = 20

: the iterates cling to the Dottie number

0.739085

Show proof

By the Mean Value Theorem, $|\cos x - \cos y| = |-\sin\xi|\cdot|x - y| \le \sin(1)\,|x - y|$ , and $\sin(1) \approx 0.8415 < 1$ , so $\cos$ is a contraction. Also $\cos$ is decreasing on $[0,1]$ (since $(\cos)' = -\sin < 0$ ), so $\cos([0,1]) = [\cos 1, \cos 0] = [\cos 1, 1] \subset [0,1]$ (with $\cos 1 \approx 0.5403 > 0$ ) — a contraction mapping $[0,1]$ into itself.
Banach's theorem gives a unique fixed point in $[0,1]$ — the Dottie number $x^* \approx 0.739085$ (the value is from iteration).

Prove in three lines that there is at most one fixed point.

|x^* - y^*| = |f(x^*) - f(y^*)| \le q|x^* - y^*|

Every start gets sucked into the same point

x^* = 2

Show proof