Fixed Point Iteration

Visualize fixed-point iteration and cobweb plots for finding roots of functions.

Fixed Point Iteration

Concept Overview

Fixed point iteration is a numerical method for finding roots of functions. Rather than solving f(x) = 0 directly, we rewrite the equation in the form x = g(x). A value x that satisfies this equation is called a fixed point of the function g, because applying g leaves the point unchanged. Starting from an initial guess x₀, we repeatedly apply the function to generate a sequence: x₁ = g(x₀), x₂ = g(x₁), and so on. Under the right conditions, this sequence converges to a fixed point.

Mathematical Definition

Given a continuous function g: [a, b] → [a, b], a fixed point is any number c in [a, b] such that:

g(c) = c

The iteration sequence is defined recursively by:

x_n+1 = g(x_n) for n ≥ 0

Graphically, finding a fixed point is equivalent to finding the intersection of the curve y = g(x) and the line y = x. The sequence is commonly visualized using a cobweb plot, tracing the path from (x_n, 0) to (x_n, g(x_n)), and then horizontally to (g(x_n), g(x_n)) on the line y = x, which becomes the new x_n+1.

Key Concepts

Existence: Brouwer's Fixed Point Theorem guarantees that if g is continuous and maps a closed interval [a, b] into itself, it must have at least one fixed point in that interval.
Convergence (Contraction Mapping Theorem): If g is differentiable and there exists a constant K < 1 such that |g'(x)| ≤ K for all x near the fixed point, the sequence will converge. The smaller the derivative, the faster the convergence.
Divergence: If |g'(x)| > 1 at the fixed point, the point is repelling. An initial guess near (but not exactly at) the fixed point will diverge away from it.
Cobweb Plot Geometry:If 0 < g'(c) < 1, the iterations approach the fixed point monotonically (a staircase pattern). If -1 < g'(c) < 0, the iterations alternate sides of the fixed point (a spiral pattern).

Historical Context

The concept of iteration dates back to ancient times, notably in the Babylonian method for computing square roots, which is equivalent to iterating g(x) = (x + S/x) / 2.

The formalization of fixed point theory began in the late 19th and early 20th centuries. The Polish mathematician Stefan Banach formalized the Contraction Mapping Theorem in 1922, establishing a rigorous framework for proving the existence and uniqueness of fixed points in complete metric spaces. This theorem remains a cornerstone in modern numerical analysis, differential equations, and dynamic systems.

Real-world Applications

Numerical Root Finding: Algorithms like Newton's method and the Secant method can be framed as specialized fixed-point iterations.
Differential Equations: Picard iteration relies on fixed-point principles to prove the existence and uniqueness of solutions to initial value problems.
Economic Equilibrium: Fixed point theorems are famously used (e.g., Nash equilibrium) to prove that markets or games have a stable state.
Dynamical Systems & Chaos: Models like the Logistic Map use iterations to study population dynamics, bifurcations, and chaos theory.
Google PageRank: The algorithm computes the stationary distribution of a random walk on the web graph, solving the fixed point equation P = M P.

Related Concepts

Logistic Map — A famous dynamic system that explores period-doubling and chaos through iteration.
Newton's Method — A highly efficient specialized fixed-point iteration for finding roots.
Gradient Descent — An optimization algorithm structurally similar to iterating toward a minimum.
Eigenvectors — Fixed points of matrix transformations (up to a scalar).

Fixed Point Iteration