Newton, Cauchy-Lipschitz and Others

Newton's method

To solve $g(x) = 0$, Newton's method iterates

$$f(x) = x - \frac{g(x)}{g'(x)}$$

A fixed point of $f$ is exactly a root of $g$. Near a simple root $c$, one shows that $f'(c) = 0$, so $f$ is a contraction there with a factor as small as desired: the convergence is in fact quadratic, the number of correct decimal places doubling at each step.

The canonical example is computing $\sqrt{2}$ with $g(x) = x^2 - 2$, which gives Heron's formula:

$$f(x) = \frac{1}{2}\left(x + \frac{2}{x}\right)$$

$n$	$u_n$	Correct decimals
$0$	$2$	$0$
$1$	$1.5$	$0$
$2$	$1.4166667$	$2$
$3$	$1.4142157$	$5$
$4$	$1.41421356237$	$11$

The Cauchy-Lipschitz theorem

The most spectacular application is the existence and uniqueness of solutions to a differential equation. The problem

$$y'(t) = F\left(t, y(t)\right), \qquad y(t_0) = y_0$$

can be written in integral form $y(t) = y_0 + \displaystyle\int_{t_0}^{t} F\left(s, y(s)\right)\,\mathrm{d}s$, that is, as the search for a fixed point of the mapping that sends a function $y$ to the right-hand side.

When $F$ is Lipschitz in its second variable, this mapping is a contraction on a well-chosen space of functions, complete for the norm of uniform convergence. Banach's theorem then provides the solution, and its uniqueness. The method of Picard iterates is nothing other than the sequence $u_{n+1} = f(u_n)$ in this setting.

An overview of applications

Field	What the theorem provides
Numerical analysis	convergence of Newton's method and of the secant method
Differential equations	Cauchy-Lipschitz theorem
Linear algebra	convergence of the Jacobi and Gauss-Seidel iterative methods
Fractal geometry	attractor of an iterated function system
Computer science	semantics of recursive definitions, least fixed point

Classic pitfall

Believing that every fixed-point theorem requires a contraction. That is not the case: Brouwer's fixed-point theorem states that every continuous map from a closed ball of $\mathbb{R}^d$ to itself has a fixed point, without any contraction hypothesis. In the case $d = 1$, it can be proved in two lines using the intermediate value theorem applied to $x \mapsto f(x) - x$.

The difference is decisive in practice: Brouwer gives existence, but neither uniqueness nor an algorithm. Banach gives all three.