Fixed Point Iteration

Fixed point iteration is a general-purpose root-finding strategy. Instead of working with $f(x) = 0$ directly, we rewrite the equation in a form where $x$ appears on both sides, then repeatedly substitute the previous output as the next input. If the process converges, the limit is a fixed point of the new function and a root of the original.

---

Core Idea

To solve $f(x) = 0$, rearrange the equation algebraically so that it takes the form:

$g(x) = x$

A fixed point of $g$ is any value $x^*$ where $g(x^*) = x^*$. If $x^*$ is a fixed point of $g$, it is also a root of $f$, because the rearrangement preserves the solution.

The iteration rule is simply:

$x_{k+1} = g(x_k)$

Starting from an initial guess $x_0$, each output feeds back in as the next input. If the sequence $x_0, x_1, x_2, \ldots$ settles to a limit, that limit is the root.

Note

The graphical interpretation: a fixed point is where the curve $y = g(x)$ crosses the diagonal line $y = x$. The iteration traces a “staircase” (or cobweb) path on this graph. It steps vertically from the x-axis to evaluate the curve $(x_k, g(x_k))$, and then moves horizontally to the diagonal line $(g(x_k), g(x_k))$ to set up the next input, stepping its way toward the crossing point.

---

Constructing $g(x)$ from $f(x)$

A single $f(x) = 0$ equation can be rearranged in many different ways to produce different $g(x)$ functions. Each choice leads to a different iterative process with potentially different convergence behaviour.

Example: Rearrange $f(x) = x^2 - 2x - 3 = 0$ (roots at $x = -1$ and $x = 3$) into four different fixed-point forms:

Form 1 — isolate by square root:

$x^2 = 2x + 3 \implies g(x) = \sqrt{2x + 3}$

Form 2 — expand and collect:

$x^2 - x - x - 3 = 0 \implies g(x) = x^2 - x - 3$

Form 3 — factor and divide:

$x(x - 2) = 3 \implies g(x) = \frac{3}{x - 2}$

Form 4 — multiply through and rearrange:

$2x^2 - 2x = x^2 + 3 \implies x(2x - 2) = x^2 + 3 \implies g(x) = \frac{x^2 + 3}{2x - 2}$

All four forms have exactly the same roots as $f(x) = 0$. However, as we will see, they do not all converge.

---

Evaluating the Forms

To see which forms converge, apply the iteration $x_{k+1} = g(x_k)$ from the same starting point $x_0 = 0$.

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

$g(0) = 1.7321$
$g(1.7321) = 2.5495$
$g(2.5495) = 2.8430$
$g(2.8430) = 2.9471$
$g(2.9471) = 2.9822$
$g(2.9822) = 2.9940$
$g(2.9940) = 2.9980$
$g(2.9980) = 3.0000$

The sequence converges to the root $x^* = 3$.

---

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

$g(0) = -3$
$g(-3) = 9$
$g(9) = 69$
$g(69) = 4.69 \times 10^3$

The sequence diverges rapidly. This form cannot be used.

---

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

$g(0) = -1.5$
$g(-1.5) = -1.05$
$g(-1.05) = -1.00$
$g(-1.00) = -1.00$

The sequence converges to the root $x^* = -1$.

Note

Notice that Form 1 and Form 4 both converge, but to different roots. Form 1 started at $x_0 = 0$ (closer to $x^* = -1$) yet still converged to $x^* = 3$. This illustrates that the choice of initial value $x_0$ alone does not determine which root is found. The structure of $g(x)$ itself plays a crucial role.

---

Effect of the Initial Guess

For a given $g(x)$, the root the iteration converges to can depend on $x_0$. Testing Form 1 and Form 4 with two very different starting points illustrates this:

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

• From $x_0 = 0$: $0 \to 1.73 \to 2.54 \to 2.84 \to 2.95 \to 2.98 \to 2.99 \to 3$
• From $x_0 = 42$: $42 \to 9.33 \to 4.65 \to 3.51 \to 3.17 \to 3.06 \to 3.02 \to 3.01 \to 3$

Both converge to $x^* = 3$, regardless of how far apart the starting points are.

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

• From $x_0 = 0$: $0 \to -3 \to 9 \to 69 \to 4690 \to \cdots$ (diverges)
• From $x_0 = 42$: $42 \to 1722 \to 2.95 \times 10^6 \to \cdots$ (diverges)

No starting point leads to convergence for Form 2.

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

• From $x_0 = 0$: $0 \to -1.5 \to -1.05 \to -1 \to -1$ (converges to $x^* = -1$)
• From $x_0 = 42$: $42 \to 21.6 \to 11.4 \to 6.39 \to 4.07 \to 3.19 \to 3.01 \to 3 \to 3$ (converges to $x^* = 3$)

Here the two starting points converge to two different roots. $x_0 = 0$ is geometrically closer to $-1$, so it converges there; $x_0 = 42$ is closer to $3$, so it goes there instead.

The theory behind which root a given $g(x)$ can reach, and why, is explained in the next section on Contraction Mapping Theory.