Fixed Point Iteration: Concepts, Formulas and Examples

Fixed point iteration solves f(x) = 0 by rewriting it as x = g(x) and repeating x_new = g(x_old). If the sequence settles at x*, then x* = g(x*) — a fixed point of g — which is also a root of the original equation. It is the easiest iterative method to program: pick a starting guess and apply g again and again.

This idea is the skeleton behind many famous algorithms — Newton's method is secretly a special fixed point iteration — and it appears in economics, population models, and anywhere a quantity depends on itself. Knowing when the iteration converges and when it blows up is the central lesson of all iterative methods.

Key Concepts

• Fixed point: a number x* with g(x*) = x*. Graphically, where the curve y = g(x) crosses the line y = x.
• Contraction: g squeezes points together when |g′(x)| < 1 near the fixed point, so each step roughly multiplies the error by |g′(x*)|.
• Convergence condition: if |g′(x)| ≤ k < 1 on an interval holding x* and the starting point, the iteration converges to x*.
• Order of convergence: usually linear — the error shrinks by a roughly constant factor each step, unlike Newton's quadratic speedup.

Formulas

• Iteration: x_n+1 = g(x_n), for n = 0, 1, 2, …
• Error bound: |x_n − x*| ≤ k^n |x_1 − x_0| / (1 − k), where k is the maximum of |g′(x)| on the interval.
• Convergence rate: the error at step n+1 is approximately |g′(x*)| times the error at step n.
• Rearrangement: one equation gives many g choices — x² = 2 becomes x = 2/x, x = x + 2 − x², or x = (x + 2/x)/2 — but only some satisfy |g′| < 1.

Worked Example

Solve x² = 2 with g(x) = (x + 2/x)/2 from x₀ = 1. Since g′(x) = (1 − 2/x²)/2, g′(1) = −0.5 with |g′| < 1 near the root, so convergence is expected. Iteration 1: x₁ = (1 + 2)/2 = 1.5. Iteration 2: x₂ = (1.5 + 1.333333)/2 = 1.416667. Iteration 3: x₃ = (1.416667 + 1.411765)/2 = 1.414216. True √2 = 1.414214, so three steps give five correct decimals — errors roughly square each step here because this g has g′(√2) = 0, an extra-fast special case.

Common Misconceptions

• "Any rearrangement x = g(x) will converge." False. For x² = 2, the choice g(x) = x² + x − 2 has |g′| > 1 near the root and the iteration explodes. The rearrangement must satisfy the contraction condition.
• "It converges from any starting point." Only from starting points inside the interval where |g′(x)| < 1. A bad start can send the sequence wandering or diverging.
• "Fixed point iteration is just a slower Newton method." It is a different family: it needs no derivative, which is an advantage when f is complicated or only available as a black box, at the price of slower linear convergence.

Real-World Applications

• Solving transcendental equations like x = cos(x), which appear in electrical circuit analysis.
• Economics: finding equilibrium prices where supply equals demand expressed as price = g(price).
• Population biology: stable population sizes in models where next year's population is a function of this year's.
• Computer science: many algorithms, from PageRank to iterative solvers, are fixed point iterations in disguise.

Fixed point iteration rewrites f(x) = 0 as x = g(x) and repeats x_n+1 = g(x_n), converging when |g′(x)| < 1 near the solution. The rearrangement decides everything; the method's simplicity makes it both practical and the foundation of iterative mathematics.