What Is Fixed-Point Iteration?
A fixed point of a function g is a value that g leaves unchanged: x* = g(x*), a point where the curve y = g(x) crosses the diagonal y = x. Fixed-point iteration hunts for it by feeding the function its own output:
xₙ₊₁ = g(xₙ), starting from any x₀
Press cos on a calculator repeatedly and the display settles at 0.739085…, fixed-point iteration converging to the Dottie number, the solution of cos(x) = x. Whether the orbit settles, and how fast, is governed by one number: the derivative of g at the fixed point. If |g′(x*)| < 1 the fixed point attracts nearby orbits; if |g′(x*)| > 1 it repels them. This calculator runs the orbit with a full iteration table, computes g′ symbolically and evaluates it at the limit to explain the observed behavior, and draws the classic cobweb diagram, the picture that turns the algebra into geometry.
How to Use the Fixed-Point Iteration Calculator
Enter the iteration function g(x), a starting value, and a number of steps. The table lists every iterate with its change from the previous one, so convergence (shrinking changes) or divergence (exploding ones) is visible at a glance. The verdict line evaluates |g′(x*)|: below 1 the point is attracting, monotone when g′ > 0 and alternating when g′ < 0; above 1 the tool explains why the orbit cannot settle. In the cobweb plot, staircases mean monotone convergence, inward spirals mean oscillating convergence, and outward spirals mean escape.
Worked Example
Iterate g(x) = cos(x) from x₀ = 0.5. The orbit runs 0.5 → 0.8776 → 0.6390 → 0.8027 → 0.6948 → …, overshooting alternately above and below before tightening to
x* = 0.739085…, where |g′(x*)| = |−sin(0.7391)| ≈ 0.674 < 1
The contraction factor 0.674 means each error is about two-thirds of the previous one, linear convergence needing roughly six iterations per digit, and the negative sign of g′ explains the alternation. Contrast the Babylonian chip g(x) = (x + 5/x)/2: its fixed point is √5, and since g′(√5) = 0, convergence is quadratic, digits double each step. That is no coincidence: the Babylonian rule is Newton's method for x² = 5 in fixed-point clothing.
The Contraction Principle and Convergence Speed
The theory is packaged in the Banach fixed-point theorem: if g maps an interval into itself and is a contraction there (|g′| ≤ k < 1), then a unique fixed point exists in the interval, every starting point converges to it, and the error obeys |xₙ − x*| ≤ kⁿ|x₀ − x*|. The derivative's size at the fixed point is the whole story of local speed: errors multiply by g′(x*) each step (linear convergence), unless g′(x*) = 0, in which case the error is squared each step (quadratic). This observation is the doorway to Newton's method, which is precisely the art of rewriting f(x) = 0 as x = g(x) with g = x − f/f′, engineered so that g′ vanishes at the root. Rearrangement matters enormously: x³ − x − 2 = 0 can be cast as x = (x + 2)1/3 (converges, |g′| ≈ 0.25) or as x = x³ − 2 (diverges violently, |g′| ≈ 6.9), the same equation, opposite fates.
Beyond Convergence: Cycles and Chaos
When |g′(x*)| > 1 at every fixed point, orbits cannot settle, but they need not flee to infinity: they may fall into periodic cycles or wander chaotically. The logistic map chip g(x) = 3.2x(1 − x) shows a stable 2-cycle, the orbit forever alternating between two values while the fixed point between them repels. Raising the coefficient toward 4 produces the famous period-doubling cascade into chaos. The cobweb diagram is the standard laboratory for these phenomena, and the study of iterated maps it opens, dynamical systems theory, underlies population models, weather predictability limits, and the Mandelbrot set (iteration of z² + c in the complex plane).
Common Mistakes to Avoid
- Iterating a rearrangement with |g′| > 1. Solving f(x) = 0 requires choosing among many forms x = g(x); only contractive ones work. If the orbit diverges, invert the rearrangement (solve for the other x) rather than iterating harder.
- Confusing a fixed point with a root. The fixed point of g solves x = g(x), not g(x) = 0. To find roots of f, first convert: x = x − c·f(x) for a suitable constant c is the simplest recipe.
- Judging by early iterates. Contraction with k close to 1 crawls: k = 0.99 needs about 230 iterations per digit. Slow-but-shrinking changes are convergence; be patient or accelerate (Aitken's Δ² squares the effective rate).
- Ignoring the basin of attraction. |g′(x*)| < 1 guarantees convergence only for starts near x*. Far-away starting points can escape, cycle, or find a different fixed point; the cobweb reveals which.
- Expecting the borderline case to behave. |g′(x*)| = 1 decides nothing: convergence, divergence, and infinitely slow drift are all possible, and higher derivatives arbitrate. Treat the boundary as a warning sign.
Real-World Applications
Fixed-point iteration is the quiet engine inside an enormous amount of computation. Implicit ODE solvers advance each time step by iterating to a fixed point; economics computes market equilibria as fixed points, with Nash equilibria the game-theoretic cousin; Google's original PageRank is fixed-point iteration of the link matrix until rankings stop changing. The value-iteration algorithm of reinforcement learning is a contraction mapping argument straight from Banach's theorem, the discount factor playing the contraction constant k. Even hardware square roots descend from the Babylonian iteration on this page. For the root-finding branch of the family, continue to the secant method and bisection calculators.
Frequently Asked Questions
How do I read the cobweb diagram?
Start on the diagonal at x₀. Move vertically to the curve, that evaluates g(xₙ), then horizontally back to the diagonal, that makes the output the next input. Staircases toward the crossing mean monotone convergence; rectangles spiraling inward mean alternating convergence; outward spirals mean the fixed point repels.
Why does |g′(x*)| < 1 decide everything?
Near the fixed point, the error obeys eₙ₊₁ ≈ g′(x*)·eₙ, by linearization. A multiplier smaller than 1 in magnitude shrinks errors geometrically; larger than 1 amplifies them. The sign adds the choreography: positive approaches from one side, negative alternates sides.
What exactly is a contraction mapping?
A function that uniformly shrinks distances: |g(a) − g(b)| ≤ k|a − b| with k < 1 on a region it maps into itself. Banach's theorem then guarantees a unique fixed point and global convergence on that region, with the explicit error bound kⁿ times the initial error, one of the most-used theorems in analysis.
How do I turn a root-finding problem into a fixed-point problem?
Rearrange f(x) = 0 into x = g(x): isolate an x, or add x to both sides, or use x = x − c·f(x) with c chosen so |1 − c·f′| < 1 near the root. Different rearrangements have wildly different g′, so check the derivative before iterating, that check is the method's entire skill.
Why does the Babylonian square-root iteration converge so much faster than cos?
Its derivative vanishes at the fixed point, so the linear error term disappears and the quadratic term takes over: digits double per step. Any iteration with g′(x*) = 0 enjoys this, and Newton's method is the systematic factory for building such iterations from arbitrary equations.
What is a basin of attraction?
The set of starting points whose orbits converge to a given fixed point. Basins can be intervals, unions of pieces, or, for complex iterations, fractal sets with infinitely detailed boundaries, Newton's method on z³ = 1 famously partitions the plane into three intertwined fractal basins.
What happens at exactly |g′(x*)| = 1?
The linear analysis is silent and higher-order terms decide. g(x) = sin(x) at x* = 0 has g′ = 1 yet converges (agonizingly slowly, like 1/√n); g(x) = x + x³ diverges. Such neutral fixed points are where bifurcations happen, new cycles being born as a parameter crosses the boundary.
Can fixed-point iteration find all solutions of x = g(x)?
Only the attracting ones. Repelling fixed points (|g′| > 1) exist but cannot be reached by forward iteration, though iterating the inverse function g⁻¹ flips their stability. Root-isolation methods or algebraic solving are needed to enumerate every crossing of the curve with the diagonal.
What is Aitken acceleration and when should I use it?
A sequence transformation, Δ²-extrapolation, that uses three consecutive iterates to cancel the leading geometric error, effectively squaring the convergence rate of a linearly convergent iteration. It rescues painfully slow contractions (k near 1) and underlies Steffensen's method, which reaches quadratic convergence without derivatives.
Is the logistic map's oscillation an error?
No, it is genuine dynamics: at coefficient 3.2 the fixed point is repelling and a stable period-2 cycle attracts almost every orbit, which is what the table's alternation and the cobweb's closed rectangle display. Push the coefficient higher and the cycle doubles again and again en route to chaos, mathematics, not malfunction.