21. Contraction Mapping Theorem

21. Contraction Mapping Theorem

Core Definitions

  1. Complete Metric Space: Let $(X, d)$ be a complete metric space
  1. Contraction Mapping: A mapping $T: X \to X$ is a contraction mapping if there exists a constant $c \in [0, 1)$ such that for all $x, y \in X$: $$d(T(x), T(y)) \le c \cdot d(x, y) \tag{1}$$

Theorem Statement

The **Contraction Mapping Theorem** (Banach Fixed-Point Theorem) states that if $(X, d)$ is a complete metric space and $T: X \to X$ is a contraction mapping, then $T$ has a unique fixed point $x^* \in X$.

Key Reasoning

  1. Constructing a sequence: Choose an arbitrary initial point $x_0 \in X$. Define a sequence $\{x_n\}$ iteratively by applying the mapping: $$x_{n+1} = T(x_n) \tag{2}$$
  1. Bounding distance between consecutive terms: By the contraction property, for any $n \ge 1$: $$d(x_{n+1}, x_n) = d(T(x_n), T(x_{n-1})) \le c \cdot d(x_n, x_{n-1}) \tag{3}$$
By induction, we can relate this to the initial step: $$d(x_{n+1}, x_n) \le c^n \cdot d(x_1, x_0) \tag{4}$$
  1. $\{x_n\}$ is a **Cauchy sequence** — its terms stop drifting apart, i.e. $d(x_m,x_n) \to 0$ as $m,n \to \infty$ (equivalently: $\forall\varepsilon>0,\ \exists N$ s.t. $m,n\ge N \Rightarrow d(x_m,x_n) < \varepsilon$; no advance knowledge of a limit is needed). For any $m > n$: $$\begin{aligned} d(x_m, x_n) &\le d(x_m, x_{m-1}) + \dots + d(x_{n+1}, x_n) \\ &\le (c^{m-1} + \dots + c^n) \cdot d(x_1, x_0) \\ &= c^n \frac{1 - c^{m-n}}{1 - c} \cdot d(x_1, x_0) \\ &\le \frac{c^n}{1 - c} \cdot d(x_1, x_0) \end{aligned} \tag{5}$$
Since $0 \le c < 1$, $c^n \to 0$, hence $d(x_m, x_n) \to 0$ — the Cauchy claim.
  1. Existence of a fixed point: Because $(X, d)$ is complete, every Cauchy sequence converges. Let $x^* = \lim_{n \to \infty} x_n$. Since $T$ is a contraction, it is uniformly continuous. Therefore: $$T(x^*) = T\left(\lim_{n \to \infty} x_n\right) = \lim_{n \to \infty} T(x_n) = \lim_{n \to \infty} x_{n+1} = x^* \tag{6}$$
Thus $x^*$ is a fixed point.
  1. Uniqueness: Suppose there is another fixed point $y^* \in X$ such that $T(y^*) = y^*$. Then: $$d(x^*, y^*) = d(T(x^*), T(y^*)) \le c \cdot d(x^*, y^*) \tag{7}$$
Since $0 \le c < 1$ and $d \ge 0$, this inequality holds if and only if $d(x^*, y^*) = 0$, meaning $x^* = y^*$.

Summary

The contraction mapping $T$ has a unique fixed point $x^* \in X$, and the sequence $x_{n+1} = T(x_n)$ converges to $x^*$ for any arbitrary initial point $x_0 \in X$. $${\exists! \ x^* \in X \ \text{ s.t. } T(x^*) = x^*} \tag{8}$$
Q.E.D.

Application: Why Does $x = \cos(x)$ Always Converge?

The Banach Fixed-Point Theorem provides the theoretical foundation for why iterative processes like repeatedly pressing the 'cos' button on a calculator always converge to a specific number.

1. Theoretical Background: The Strict Contraction Condition

The core of the Banach Fixed-Point Theorem relies on the space being complete (having no "holes", like the set of real numbers $\mathbb{R}$) and the mapping being a **strict contraction**.
Mathematically, for a function $f(x)$ mapping real numbers to real numbers, the contraction condition is: $$\vert{}f(x) - f(y)\vert{} \le q \cdot \vert{}x - y\vert{} \tag{9}$$
The crucial requirement is that $0 \le q < 1$.
If the function is differentiable, by the **Mean Value Theorem**, this condition is equivalent to requiring the absolute value of the derivative to be strictly bounded by a constant less than 1 across the domain: $$\vert{}f'(x)\vert{} \le q < 1 \tag{10}$$

2. Analyzing the Cosine Iteration

We want to find a fixed point for the function $T(x) = \cos(x)$, which means solving the equation $x = \cos(x)$. We do this by iterating $x_{n+1} = \cos(x_n)$.
  1. Finding the Derivative: The derivative of our mapping function is: $$T'(x) = -\sin(x) \tag{11}$$
According to the Mean Value Theorem, the contraction factor $q$ depends on the magnitude of this derivative: $$\vert{}T'(x)\vert{} = \vert{}-\sin(x)\vert{} = \vert{}\sin(x)\vert{} \tag{12}$$
  1. Establishing the Bound (**$q$**): globally $|\sin x| \le 1$ hits 1 near $x = \pi/2$, violating the strict $q < 1$. Restrict the domain: $\cos(\mathbb{R}) \subseteq [-1, 1]$, so after one iteration all $x_n \in [-1, 1]$ regardless of $x_0$. On $[-1, 1]$, $|\sin x|$ maxes at the endpoints: $$|T'(x)| = |\sin x| \le \sin 1 \approx 0.841 \equiv k < 1 \tag{13}$$

3. Final Conclusion

Because the absolute value of the derivative of $\cos(x)$ is strictly bounded by a constant $k \approx 0.841 < 1$ within the interval containing the fixed point, it is a true contraction mapping in that domain.
According to the Banach Fixed-Point Theorem, this guarantees that the sequence will invariably collapse to a single, unique fixed point, regardless of the initial starting value. This unique fixed point is known as the Dottie number: $$x^* \approx 0.739085\dots \tag{14}$$

Advanced: Newton's Method — From "Slow Crawl" to "Extreme Jump"

Newton's method exhibits **quadratic convergence**, reaching extreme precision in just a few iterations compared to ordinary fixed-point iteration.

1. Deriving Newton's Iteration Formula

To find the root of $f(x) = 0$, we seek the intersection of $y = f(x)$ and the $x$-axis. The core intuition is to approximate the complex curve with its tangent line.
  • Initial Guess: Start near the root at $x_n$. The point on the curve is $(x_n, f(x_n))$.
  • Tangent Line: The slope is $f'(x_n)$. The tangent line equation is: $$y - f(x_n) = f'(x_n) \cdot (x - x_n) \tag{15}$$
  • Intersection: Set $y = 0$ to find the new approximation $x_{n+1}$: $$0 - f(x_n) = f'(x_n) \cdot (x_{n+1} - x_n) \tag{16}$$
(Algebraic view: This is equivalent to setting the first-order Taylor expansion of $f(x)$ at $x_n$ to 0.)

2. Why is Newton's Method So Fast? (The "Super Contraction")

According to the Banach Fixed-Point Theorem, for $x_{n+1} = T(x_n)$, convergence speed depends on the magnitude of the derivative $|T'(x)|$ (the contraction factor $q$). Ordinary iterations (like $x = \cos(x)$) have $q \approx 0.841$, yielding linear convergence ("slow crawl").
Let's examine Newton's iteration function: $$T(x) = x - \frac{f(x)}{f'(x)} \tag{18}$$
Calculating the Derivative $T'(x)$:
Using the quotient rule: $$\begin{aligned} T'(x) &= 1 - \frac{f'(x) \cdot f'(x) - f(x) \cdot f''(x)}{[f'(x)]^2} \\ &= 1 - \left( 1 - \frac{f(x)f''(x)}{[f'(x)]^2} \right) \\ &= \frac{f(x)f''(x)}{[f'(x)]^2} \end{aligned} \tag{19}$$
At the Target Root $x^*$:
Since $x^*$ is the true root, $f(x^*) = 0$. Substituting this into $T'(x)$: $$T'(x^*) = \frac{f(x^*) \cdot f''(x^*)}{[f'(x^*)]^2} = 0 \tag{20}$$
Conclusion: At the target root $x^*$, the derivative of the iteration function is exactly 0!

3. The "Super Contraction" Effect

Ordinary contraction mapping requires $|T'(x)| \le q < 1$. But as Newton's method approaches the target, its contraction factor $q \to 0$.
When $q \to 0$, the first-order error term vanishes, making the new error proportional to the **square** of the previous error. This is the mathematical essence of **Quadratic Convergence**.
In practice, this means the number of correct decimal places doubles with each iteration! (e.g., 3 digits $\to$ 6 digits $\to$ 12 digits). This is why achieving $10^{-6}$ precision only takes 3-4 iterations—a true "extreme jump".

1. Mathematical Proof of Error Squaring

To see why the first-order error vanishes, let $x^*$ be the true root ($f(x^*) = 0$) and $e_n = x_n - x^*$ be the error at step $n$. We use the second-order Taylor expansion of $f(x)$ at the current guess $x_n$, evaluated at $x^*$: $$f(x^*) = f(x_n) + f'(x_n)(x^* - x_n) + \frac{1}{2}f''(\xi)(x^* - x_n)^2 \tag{21}$$
where $\xi$ is a point between $x_n$ and $x^*$ (Lagrange remainder). Since $f(x^*) = 0$: $$0 = f(x_n) + f'(x_n)(x^* - x_n) + \frac{1}{2}f''(\xi)(x^* - x_n)^2 \tag{22}$$
Dividing by $f'(x_n)$ and rearranging to isolate $x^*$: $$x^* = \underbrace{x_n - \frac{f(x_n)}{f'(x_n)}}_{\text{Newton's step } x_{n+1}} - \frac{f''(\xi)}{2f'(x_n)}(x^* - x_n)^2 \tag{23}$$
Notice that the first two terms perfectly match the definition of the next iteration $x_{n+1}$. By substituting $x_{n+1}$ and rearranging, we get: $$x_{n+1} - x^* = \frac{f''(\xi)}{2f'(x_n)}(x_n - x^*)^2 \tag{24}$$
Substituting the error definitions $e_n = x_n - x^*$ and $e_{n+1} = x_{n+1} - x^*$: $$e_{n+1} = \frac{f''(\xi)}{2f'(x_n)} \cdot e_n^2 \tag{25}$$
As $x_n \to x^*$, the point $\xi \to x^*$, and the fractional term converges to a constant $C = \frac{f''(x^*)}{2f'(x^*)}$. Thus: $$e_{n+1} \approx C \cdot e_n^2 \tag{26}$$
**Summary:** The first-order term didn't disappear into nowhere; Newton's iteration formula is perfectly designed to absorb it (along with the constant term), transforming them into the forward step $x_{n+1}$. The only remaining "residue" is the squared term, driving the extreme quadratic convergence speed.
Loading...