Fixed Point Iteration

A fundamental numerical method that transforms a root-finding problem f(x) = 0 into a fixed-point problem x = g(x). Starting from an initial guess, the sequence x_{n+1} = g(x_n) produces a cobweb plot that converges to the solution, provided the derivative |g'(x)| is less than 1 near the fixed point.

Historical Context

Fixed-point iteration is one of the most fundamental concepts in computational mathematics, forming the basis for many advanced numerical algorithms. Its theoretical foundation, the Banach Fixed-Point Theorem (also known as the Contraction Mapping Theorem), was formulated by Stefan Banach in 1922, though the core iterative concept has roots in ancient mathematical techniques.

The elegance of the method lies in its simplicity: a root-finding problem $f(x) = 0$ is algebraically manipulated into the form $x = g(x)$ . A value of $x$ that satisfies this equation is called a "fixed point" because applying the function $g$ to it leaves it unchanged. By repeatedly applying $g$ to an initial guess $x_0$ , the sequence $x_1 = g(x_0), x_2 = g(x_1), \dots$ can converge to this fixed point.

Visually, this process is often depicted using a "cobweb plot" or "staircase plot," where the iteration traces a path bouncing between the curve $y = g(x)$ and the identity line $y = x$ . While conceptually beautiful, its practical utility depends entirely on the contraction property: the method only converges if the absolute value of the derivative $|g'(x)| < 1$ near the root.

Geometric Foundation: The Rearrangement Problem

To use Fixed Point Iteration, we must rearrange our root-finding problem $f(x) = 0$ into the form $x = g(x)$ . Consider the equation $f(x) = x^2 - x - 2 = 0$ , which has a root at $x = 2$ .

There are multiple valid algebraic ways to isolate $x$ . Click through the arrangements below to see how the choice of $g(x)$ completely dictates whether the iteration converges to the root, or diverges wildly.

g'(2) = 4

Diverges

Diverging Staircase

Initial Guess (x₀)2.10

g(x) = \cos(x)

Geometric View

x_{n+1} = g(x_n)

Convergence Plot

Each step reduces the error. On a logarithmic scale, convergence patterns form straight lines.

Iteration Function g(x)

Initial Guess (x₀)

Tolerance (ε)

Speed

○ Iter 0. Ready.

Error Bound |x_n+1 - x_n|

Current State

No active state.

Algorithm

while |x_n+1 - x_n| > ε:x_next = g(x_n)x_n = x_nextreturn x_n

Why it works

Fixed-point iteration transforms a root-finding problem $f(x) = 0$ into the form $x = g(x)$ . Starting with an initial guess $x_0$ , we repeatedly apply the function: $x_{n+1} = g(x_n)$ . Visually, this creates a "cobweb" that bounces between the curve $y = g(x)$ and the line $y = x$ .

The method is guaranteed to converge to the root $x^*$ if and only if the absolute value of the derivative at the root is strictly less than one: $|g'(x^*)| < 1$ .

Furthermore, the sign of the derivative dictates the geometric path the iteration takes:

Positive Derivative ( $g'(x) > 0$ ): Produces a monotonic staircase pattern.
Negative Derivative ( $g'(x) < 0$ ): Produces an alternating spiral pattern around the root.

When the Method Fails

Fixed-point iteration is elegant but highly sensitive to the chosen function $g(x)$ .

Divergence: If $|g'(x)| > 1$ at the root, the fixed point is repelling. No matter how close your initial guess is, the iteration will spiral outward and diverge to infinity.
Cycles: If $g'(x) \approx -1$ , the sequence may become trapped in a 2-cycle, oscillating endlessly between two values around the root.
Zero Derivative: If $g'(x^*) = 0$ , the method achieves incredibly fast quadratic convergence, which is exactly why the Newton-Raphson method (which constructs a specific $g(x)$ with this property) is so powerful.

The same equation. Four arrangements. Only some converge. Find out why.

The rearrangement is everything. The same root, the same equation — but |g'(x*)| decides whether you spiral inward or escape to infinity.

Output

Output will appear here after running the code

Output

Output will appear here after running the code

Want to extend this idea to finding minimums in multiple dimensions? Welcome to the backbone of AI.Gradient Descent →