Contraction Mapping Theory

The previous section showed that some forms of $g(x)$ converge while others diverge, and that the same $g(x)$ can converge to different roots from different starting points. Contraction mapping theory provides the precise mathematical criterion that predicts this behaviour, without having to run the iteration.

---

The Convergence Criterion

A fixed-point iteration $x_{k+1} = g(x_k)$ will converge to a root $x^*$ if and only if:

$\lambda = |g'(x^*)| < 1$

The value $\lambda$ is called the converging rate. To test whether a particular $g(x)$ converges to a particular root:

1. Compute $g'(x)$.
2. Evaluate $|g'(x^*)|$ at the root of interest.
3. If $|g'(x^*)| < 1$, the iteration converges to that root; otherwise it diverges from it.

Caution

The criterion $|g'(x^*)| < 1$ is a local condition: it guarantees convergence only if $x_0$ is sufficiently close to $x^*$. For Form 4 from the previous section, both roots satisfy the criterion, so the iteration converges to whichever root the initial guess is nearest to.

---

Testing the Four Forms

Returning to $f(x) = x^2 - 2x - 3 = 0$ with roots $x^* = -1$ and $x^* = 3$:

Form 1: $g(x) = \sqrt{2x+3} = (2x+3)^{1/2}$

$g'(x) = \frac{1}{\sqrt{2x+3}}$

Evaluating at each root:

$|g'(-1)| = \frac{1}{\sqrt{2(-1)+3}} = \frac{1}{\sqrt{1}} = 1 \qquad |g'(3)| = \frac{1}{\sqrt{2(3)+3}} = \frac{1}{\sqrt{9}} = \frac{1}{3}$

Root	$\lambda$	Converges?
$x^* = -1$	$1$	No (boundary case)
$x^* = 3$	$1/3$	Yes

Both starting points $x_0 = 0$ and $x_0 = 42$ converge to $x^* = 3$, which is the only root with $\lambda < 1$.

Form 2: $g(x) = x^2 - x - 3$

$g'(x) = 2x - 1$

Evaluating at each root:

$|g'(-1)| = |2(-1)-1| = |-3| = 3 \qquad |g'(3)| = |2(3)-1| = |5| = 5$

Root	$\lambda$	Converges?
$x^* = -1$	$3$	No
$x^* = 3$	$5$	No

Since $\lambda \ge 1$ at both roots, no initial guess will produce convergence. This explains the rapid divergence observed in the previous section.

Form 4: $g(x) = \dfrac{x^2 + 3}{2x - 2}$

Computing $g'(x)$ via the quotient rule:

$g'(x) = \frac{(2x)(2x-2) - (x^2+3)(2)}{(2x-2)^2} = \frac{4x(x-1) - 2(x^2+3)}{4(x-1)^2} = \frac{2x^2 - 4x - 6}{4(x-1)^2}$

Evaluating at each root (both substitute to give a numerator of zero):

$|g'(-1)| = 0 \qquad |g'(3)| = 0$

Root	$\lambda$	Converges?
$x^* = -1$	$0$	Yes (super-linear)
$x^* = 3$	$0$	Yes (super-linear)

Since $\lambda = 0$ at both roots, the iteration converges from any initial guess. Which root is reached depends only on which root $x_0$ is geometrically closest to. When we chose $x_0 = 0$, the iteration converges to $x^* = -1$, as it is closer; when we choose $x_0 = 42$, it converges to $x^* = 3$.

---

Order of Convergence

The converging rate $\lambda$ classifies how quickly an iteration reaches its root:

Converging rate	Classification	Behaviour
$\lambda = 0$	Super-linear convergence	Fastest convergence; fewest iterations required
$0 < \lambda < 1$	Linear convergence	Converges, but more slowly
$\lambda \ge 1$	Divergent	Does not converge; discard this $g(x)$

Note

Super-linear convergence ($\lambda = 0$) means the error shrinks far faster than a fixed fraction per step. Newton’s method, covered in the next section, always achieves $\lambda = 0$ at a simple root, which is why it typically converges in very few iterations.

---