Fixed-point iteration

Put any number in your calculator and hit the cos key over and over. Start at 2: you get $-0.416$, then $0.914$, then $0.610$, then $0.820$ — the display keeps twitching, by a little less each time, and finally parks at $0.739085$. Hit cos once more and nothing moves: $\cos (0.739085)=0.739085$.

That parked value is a fixed point — an input the function hands back unchanged. Fixed-point iteration is nothing more than what your thumb just did: pick a function $g$, start anywhere, and feed each output back in as the next input, $x_{n+1}=g(x_n)$. Where the sequence stops moving is the answer, the $x^{\ast }$ with $g(x^{\ast })=x^{\ast }$.

Draw two things on the same axes: the curve $y=g(x)$ and the diagonal line $y=x$. A fixed point is wherever they cross — there the curve's height $g(x)$ equals $x$ itself.

The iteration has a picture too. Stand at $x_n$ on the diagonal, go straight up to the curve — that height is $g(x_n)=x_{n+1}$ — then straight across to the diagonal to deposit it as the new $x$. Up to the curve, over to the line, repeat. You trace a cobweb that either spirals into the crossing or is flung out of it. Which one depends on the slope of the curve where it cuts the diagonal:

Step through it. $\cos$ spirals in (the slope is negative, so the cobweb crosses the diagonal each step); $1+1/x$ winds down to the golden ratio; $x^2$ shows the other outcome — start just past the crossing and the staircase climbs away, because there the curve is steeper than the diagonal.

Some equations define their answer in terms of itself. Take $x=1+\frac{1}{x}$. The $x$ on the right is the same $x$ you are solving for — the equation refers back to its own answer. How do you solve a thing like that? Guess, and let the equation correct you: put $x=1$ into the right-hand side and it returns $2$; put $2$ in and it returns $1.5$; then $1.667$, $1.6$, $1.625$… closing in on the golden ratio $\phi =1.618$, the one value that already satisfies its own definition: $\phi =1+1/\phi$.

That is a fixed point — a solution of $x=g(x)$, the value $g$ hands back unchanged. The right-hand side is the update rule; you read the iteration straight off the equation. And it works in reverse for ordinary equations too: any $f(x)=0$ can be bent into this self-referential shape — write $x=x+f(x)$, or solve for one copy of $x$ — and then iterating hunts the value that makes the equation consistent with itself.

Follow the error, $e_n=x_n-x^{\ast }$, the gap between where you are and the fixed point. One step of the iteration moves it by, to first order,

So every step multiplies the error by the slope $g^{\prime }(x^{\ast })$. If $|g^{\prime }(x^{\ast })|<1$ the error shrinks by a fixed fraction each time — the map is a contraction, and you converge linearly. If $|g^{\prime }(x^{\ast })|>1$ the error grows and the iteration runs away, even though $x^{\ast }$ is a perfectly valid fixed point; it is simply unstable, and no starting guess short of landing on it exactly will reach it. For $\cos$, $g^{\prime }(x^{\ast })=-\sin (0.739)\approx -0.67$, comfortably inside the unit circle — which is why the calculator settled.

Once you see the skeleton — guess, push it through a map, feed the result back, repeat until it stops moving — you start seeing it everywhere.

Newton's method is fixed-point iteration with $g(x)=x-f(x)/f^{\prime }(x)$, rigged so that $g^{\prime }(x^{\ast })=0$ and the convergence jumps from linear to quadratic. The self-consistent field of quantum chemistry iterates an electron density through the Fock build until the density it produces matches the one it started from — a fixed point in the space of densities. PageRank iterates the link matrix to its dominant eigenvector; Picard iteration turns an ODE into a map on functions. Same skeleton every time: build a map whose fixed point is the thing you want, then iterate until it holds still.