Programming

Fixed-Point Iteration

Take any crumpled map and toss it onto the floor: exactly one point rests directly above the coordinate it represents. A contraction mapping folds an entire metric space inward, reeling every starting guess into an inescapable attractor at rate qⁿ.

At q=0.9999 one digit costs 23,025 steps; at q=0.6736 it takes 5.8: how the cobweb spiral converges to a fixed point.

Mission 22about 8 min

Reel erratic dynamical inputs into a guaranteed stable attractor by exploiting metric contraction mappings.

  1. Predict whether starting from x=0 or x=2 reaches the same equilibrium under repeated cosine iteration
  2. Step the IterationLab cobweb staircase to watch distances shrink geometrically by factor q
  3. Take the boss round bet on the derivative threshold where contraction shatters into chaos

After thisYou will harness contraction proofs for numerical solvers, PageRank equilibrium, and differential equations.

Short on timeStep the IterationLab panel to watch the cobweb staircase funnel any initial guess to 0.739085.

The Cobweb Spiral

3 minthe hook

At contraction factor , one correct digit costs 23,025 steps. At it costs 5.83. Type cos into a pocket calculator, press equals twice, and no matter what you entered the display drifts to 0.739085..., the Dottie number.

The picture is the cobweb: bounce between and ; a contraction shortens every bounce by , and a point with repels.

Before you press play, commit to a prediction below.

method
function

f(x) = cos x − x · f′(x) = −sin x − 1 · g(x) = cos x · true root x* = 0.7390851332151

1 / 41
Fixed point step 0 / 40
x_01
residual |f(x_0)|0.4596977
previous error e_0—
error e_0 = |x_0 − x*|0.2609149
e_{n+1} / e_n—
constant the theory predicts0.67361
-101-101xg
Fixed point iterates for f(x) = cos x − x
nx_nf(x_n)e_ne_{n+1} / e_n
01-0.45969770.2609149—

Order of convergence p = 1. The ratio column settles on a constant exactly when p is the right order; here that constant is 0.67361. A ratio that keeps drifting means the step is not yet in the asymptotic regime.

The Dottie number. cos is a global contraction, so fixed-point iteration converges from every start — it just converges linearly, at rate |sin x*| = 0.6736.

Vertical to the curve, horizontal to the diagonal: each corner of the staircase is one iterate. Step it and read the error column.

Watch the ratio column: it is the slope of at the fixed point, and the stopping rule is the only honest error bound. The factor is the same at every step, and everything on this page explains it.

NextWhy does an iteration loop wander endlessly if the function slope exceeds unity?

The Mirage of the Halting Loop

2 minthe trap

You want to solve , so you iterate and stop when the points stop moving. For this works from any start you drag the slider to.

The operational framing hides the real question. Some maps land and some run away, and the loop itself cannot tell you which kind you hold. The question is what property of makes iteration a proof instead of a hope.

NextHow does Banach's contraction mapping theorem guarantee a unique, inevitable attractor?

Complete Spaces and Metric Contractions

2 minthe invariant

The real object is a complete metric space with a contraction on it. A metric space is a set with a distance , and completeness means every Cauchy sequence has a limit in the space. The closed interval of the real line is complete; an open interval is not, since a sequence can converge to a missing endpoint.

A contraction is a map with one number below such that for every pair and . The constant is the whole story: it says all distances shrink by the same factor at every step. The panel’s ratio column is your window onto .

NextWhy does a contraction factor of 0.6736 converge in 5.8 steps while 0.9999 requires 23,025?

Banach’s Inevitable Attractor

2 minthe algebra

Banach’s contraction mapping theorem (Banach 1922, building on Picard’s 1890 successive approximations) states the payoff. If is a contraction with constant on a complete metric space, then has exactly one fixed point , and converges to it from any start.

The proof is short, and each hypothesis is used exactly once. First, successive distances shrink geometrically: , by applying the contraction times. This is where below does its work.

Next, the iterates form a Cauchy sequence, by the triangle inequality and the geometric sum:

Completeness is used here and only here: it promotes this Cauchy sequence to a limit in the space. Continuity of then gives .

Uniqueness needs no completeness at all. Two fixed points would satisfy , which forces the distance to zero since is below .

Letting grow without bound in the Cauchy estimate gives the a priori bound (Banach 1922):

It predicts the error before you iterate, from the first step alone. A one-step version gives the a posteriori bound, which prices the error you have already earned:

To derive it, apply the contraction to to get , then split through by the triangle inequality and rearrange. Both bounds carry the same factor : the price of summing the whole tail of the staircase.

The check you actually run is calculus. If below on a closed interval, the mean value theorem (Lagrange 1797) gives . So is a contraction there, and the theorem applies.

For the derivative is , and at the fixed point its size is . That is the number the panel’s ratio column settles on, and the curve bends toward it one factor of per step.

Switch the panel to the √2 function in fixed-point mode and drag x₀ near −1.4. Does the iteration settle on a fixed point?

The cobweb is this proof drawn as geometry. Going vertical from to the curve reaches , and going horizontal to the diagonal carries that height to the next point .

When reaches the guarantee dies, and the same loop can misbehave completely. The logistic map is fixed-point iteration with a different , and as grows it doubles its period until the iterates turn chaotic (May 1976). Contraction is the boundary between this page and that chaos.

Newton’s method is the special case where the derivative vanishes at the answer. Its map satisfies at a simple root, so the linear factor collapses and the error squares instead of shrinking geometrically. That is why Newton converges quadratically while this page converges at rate ; the section’s Newton page proves the squaring.

Name the contrast that makes Banach 1922 worth its fame. Brouwer’s fixed-point theorem (Brouwer 1911) says a continuous map of a closed ball to itself has a fixed point: existence with no uniqueness, no rate, and no way to compute it. Banach trades the weak hypothesis for a strong one and returns existence, uniqueness, and a computable error bound in one stroke.

1 minboss round

For x = cos x from x₀ = 1, the first step moves d(x₀, x₁) = 0.4597 and q = 0.6736. What does the a priori bound guarantee after 5 steps?

NextHow does the cobweb staircase visualize convergence and divergence around fixed points?

Driving the Cobweb Staircase

2 minthe simulation

Return to the panel and change the function. On the cubic the ratio column settles on a smaller and the staircase falls faster; on the map it settles on near .

Drag the start across the slider range on each function. For the cosine map every start lands on the Dottie number, because the contraction is global. For the map a start near flees, exactly as the first prediction asked you to foresee.

The chart below plots the honest numbers for the cosine run from : the measured error against the a priori ceiling. Both fall geometrically with the same slope ; the ceiling stays above the truth at every step, which is what a bound must do.

Geometric error decay for x = cos x from x₀ = 1: measured error against the a priori bound (log scale)

1e-31e-21e-11e01e10246810nerror
a priori bound qⁿ/(1−q)·d(x₀,x₁)measured error eₙ

Read the two lines on the log scale as straight lines with the same slope. That shared slope is , and the gap between the lines is the slack the proof pays for not knowing the future.

NextHow do Google PageRank and differential equation solvers rely on contractive fixed points?

From Picard Iteration to PageRank

2 minsystems

Picard used this iteration to solve differential equations (Picard 1890): rewrite as an integral equation and iterate the integral, which contracts on a short time interval. Banach’s abstraction turned one existence proof into a method for equations everywhere.

Every solver with a “tolerance” and a “max iterations” field is spending this theorem. Value iteration in dynamic programming, power iteration for eigenvectors, and the inner loops of splitting methods all converge because some map contracts. When they stall, the first diagnostic is the same: estimate , and check whether it is really below .

Next missionKaratsuba MultiplicationAt 2^20 digits, 4^20=1.1×10^12 products drops to 3^20=3.49×10^9: how three multiplications beat four.

Escaping the Basin: When Contraction is Local

Skippable. The theorem needs to map a complete set into itself and contract there. Often neither holds globally, yet both hold on a small closed ball around the fixed point.

Then the same proof runs locally: start inside the ball and you converge with the same rate. Newton lives here, since only forces contraction near . The global cosine map of this page is the easy case, not the typical one.

Lineage & Attributions

  • Picard 1890 — successive approximations for ordinary differential equations, the iteration Banach later abstracted.
  • Brouwer 1911 — the topological fixed-point theorem: existence without uniqueness, rate, or construction; the foil to Banach.
  • Banach 1922 — the contraction mapping theorem with the a priori and a posteriori error bounds; the spine of this page.
  • Lagrange 1797 — the mean value theorem, which turns the derivative check into a contraction.
  • May 1976 — period doubling and chaos in the logistic map, showing what the same iteration does once .