Fixed-Point Theorem

The fixed-point theorem provides conditions under which iterative methods $x_{n+1} = g(x_n)$ converge, forming the theoretical foundation for analyzing root-finding algorithms including Newton's method.

TheoremContraction Mapping Fixed-Point Theorem

Let $g: [a,b] \to \mathbb{R}$ satisfy:

$g \in C[a,b]$ (continuity)
$g([a,b]) \subseteq [a,b]$ (maps interval to itself)
$\exists k \in (0,1): |g'(x)| \leq k$ for all $x \in (a,b)$ (Lipschitz with constant $k < 1$ )

Then:

$g$ has a unique fixed point $p \in [a,b]$ (i.e., $g(p) = p$ )
For any $x_0 \in [a,b]$ , the iteration $x_{n+1} = g(x_n)$ converges to $p$
The error satisfies: $|x_n - p| \leq \frac{k^n}{1-k}|x_1 - x_0|$ $|x_n - p| \leq \frac{k}{1-k}|x_n - x_{n-1}|$

The constant $k$ is called the contraction factor. Convergence is linear with asymptotic error constant $k$ . Smaller $k$ means faster convergence; $k$ near 1 implies slow convergence.

Remark

Relationship to Newton's Method: Newton's method $x_{n+1} = x_n - f(x_n)/f'(x_n)$ is a fixed-point iteration with: $g(x) = x - \frac{f(x)}{f'(x)}$

Computing $g'(x)$ : $g'(x) = 1 - \frac{f'(x)^2 - f(x)f''(x)}{f'(x)^2} = \frac{f(x)f''(x)}{f'(x)^2}$

At a simple root $r$ where $f(r) = 0$ and $f'(r) \neq 0$ , we have $g'(r) = 0$ , explaining Newton's quadratic (not just linear) convergence.

ExampleSolving $x = \cos(x)$

The equation $x = \cos(x)$ has a unique solution (since $\cos(x)$ crosses $y = x$ once). Using $g(x) = \cos(x)$ :

$g([0,1]) = [\cos(1), 1] \approx [0.540, 1] \subset [0,1]$
$|g'(x)| = |\sin(x)| \leq \sin(1) \approx 0.841 < 1$ on $[0,1]$

The iteration converges with rate $k \approx 0.841$ :

$x_0 = 1$
$x_1 = \cos(1) \approx 0.540$
$x_5 \approx 0.768$
$x_{20} \approx 0.739085133$

Convergence is relatively slow due to $k$ near 1. Accelerated methods like Aitken's $\Delta^2$ process can improve convergence rate.

The theorem extends to multidimensional systems: for $\mathbf{x}_{n+1} = \mathbf{g}(\mathbf{x}_n)$ with $\mathbf{g}: \mathbb{R}^n \to \mathbb{R}^n$ , if the Jacobian $\|\mathbf{J}_g\| \leq k < 1$ , convergence is guaranteed. This principle underpins Newton's method for systems of nonlinear equations.

Practical considerations include choosing $g$ to minimize $k$ . For $f(x) = 0$ , rewriting as $x = x + \alpha f(x)$ with optimal $\alpha$ can accelerate fixed-point iteration, though Newton's choice $\alpha = -1/f'(x)$ is typically best.