Fixed Point Iteration

Fixed Points¶

The basic idea: reformulate a root-finding problem as a fixed-point problem.

\text{Root finding: } f(x) = 0 \quad \longrightarrow \quad \text{Fixed point: } x = g(x)

(1)

There are many ways to do this! Given $f(x) = 0$ , you could write:

$g(x) = x - f(x)$
$g(x) = x - cf(x)$ for any nonzero $c$
$g(x) = x - f(x)/f'(x)$ (this gives Newton’s method!)

The choice of $g$ matters enormously for convergence—as we’ll see.

The Algorithm¶

The fixed-point iteration is beautifully simple.

That’s it. But whether this converges—and how fast—depends entirely on properties of $g$ .

Why the Choice of $g$ Matters¶

Consider finding the root of $f(x) = x^2 - 3 = 0$ (i.e., finding $\sqrt{3}$ ).

Here are three valid reformulations:

G1: From $x^2 = 3$ , we get $g_1(x) = 3/x$
G2: Add $x$ to both sides: $g_2(x) = x - (x^2 - 3)/2$
G3: Divide by $2x$ : $g_3(x) = (x^2 + 3)/(2x)$

All three have $\sqrt{3}$ as a fixed point. But their behavior is dramatically different:

G1 cycles forever, never converging
G2 converges slowly (linearly)
G3 converges rapidly (quadratically—this is Newton’s method!)

Existence and Uniqueness¶

When does a fixed point exist? When is it unique?

Proof 1 (Existence)

Define $h(x) = x - g(x)$ .

If $g(a) = a$ or $g(b) = b$ , we’re done—we’ve found a fixed point.

Otherwise, since $g([a,b]) \subseteq [a,b]$ :

$g(a) > a$ , so $h(a) = a - g(a) < 0$
$g(b) < b$ , so $h(b) = b - g(b) > 0$

By the Intermediate Value Theorem, there exists $c \in (a,b)$ with $h(c) = 0$ , i.e., $g(c) = c$ .

Proof 2 (Uniqueness)

Suppose two fixed points $c_1 < c_2$ exist. By the Mean Value Theorem:

|c_1 - c_2| = |g(c_1) - g(c_2)| = |g'(\xi)||c_1 - c_2| \leq \rho|c_1 - c_2|

(2)

for some $\xi \in (c_1, c_2)$ .

This implies $(1-\rho)|c_1 - c_2| \leq 0$ . But $\rho < 1$ and $c_1 \neq c_2$ , so $(1-\rho)|c_1 - c_2| > 0$ —a contradiction.

Convergence¶

Proof 3

Since $c$ is a fixed point, $g(c) = c$ . Using the Mean Value Theorem:

|x_{n+1} - c| = |g(x_n) - g(c)| = |g'(\xi_n)||x_n - c| \leq \rho|x_n - c|

(4)

Applying this recursively:

|x_n - c| \leq \rho|x_{n-1} - c| \leq \rho^2|x_{n-2} - c| \leq \cdots \leq \rho^n|x_0 - c|

(5)

Since $\rho < 1$ , we have $\rho^n \to 0$ , so $x_n \to c$ .

The Derivative at the Fixed Point¶

The key insight: $|g'(c)|$ determines everything.

For our three reformulations of $x^2 - 3 = 0$ :

$g_1(x) = 3/x$ : We have $g_1'(x) = -3/x^2$ , so $|g_1'(\sqrt{3})| = 1$ . Right on the boundary—no convergence guaranteed (and indeed, it fails).
$g_2(x) = x - (x^2-3)/2$ : We have $g_2'(x) = 1 - x$ , so $|g_2'(\sqrt{3})| = |1 - \sqrt{3}| \approx 0.73$ . Linear convergence with rate $\rho \approx 0.73$ .
$g_3(x) = (x^2+3)/(2x)$ : We have $g_3'(x) = 1/2 - 3/(2x^2)$ , so $g_3'(\sqrt{3}) = 0$ . The derivative vanishes—this signals faster-than-linear convergence.

Order of Convergence¶

Proof 4

Taylor expand $g(x_n)$ around $c$ :

x_{n+1} = g(x_n) = g(c) + g'(c)(x_n - c) + \cdots + \frac{g^{(p)}(\xi)}{p!}(x_n - c)^p

(7)

Since $g(c) = c$ and the first $p-1$ derivatives vanish:

x_{n+1} - c = \frac{g^{(p)}(\xi)}{p!}(x_n - c)^p

(8)

Thus $|x_{n+1} - c| \approx C|x_n - c|^p$ with $C = |g^{(p)}(c)|/p!$ .

This explains why $g_3$ converges so fast: $g_3'(\sqrt{3}) = 0$ means at least quadratic convergence.

The Banach Fixed Point Theorem¶

The convergence results above are special cases of a fundamental principle that appears throughout mathematics.

Remark 2 (Why the Banach FPT Matters)

The Banach FPT is not just about scalar equations. The same principle governs:

Newton’s method for systems: The iteration is a contraction near the solution
Picard iteration for ODEs: Proves existence and uniqueness for $y' = f(t,y)$
Iterative linear solvers: Jacobi and Gauss-Seidel converge when the iteration matrix is a contraction

Whenever you see an iterative method that “works,” there’s often a contraction hiding underneath.

Advantages and Disadvantages¶

Advantages:

Simple — Just iterate $x_{n+1} = g(x_n)$
Unifying framework — Newton’s method is a fixed-point iteration in disguise
Flexible — Many choices for $g$ ; can design for fast convergence
Generalizes — Extends to systems, ODEs, infinite dimensions (Banach FPT)

Disadvantages:

Not guaranteed — Can diverge if $|g'(c)| \geq 1$
Sensitive — Different reformulations give wildly different behavior
Slow — Linear convergence when $|g'(c)|$ is close to 1

Design principle: Make $|g'(c)|$ small. If $g'(c) = 0$ , you get quadratic convergence—this is Newton’s method.

Fixed Points¶

The Algorithm¶

Why the Choice of ggg Matters¶

Existence and Uniqueness¶

Convergence¶

The Derivative at the Fixed Point¶

Order of Convergence¶

The Banach Fixed Point Theorem¶

Advantages and Disadvantages¶

Why the Choice of $g$ Matters¶