Iteration Is Pulled to a Fixed Point
Put any number into a calculator and keep pressing the cos button. The result stops changing near a single value, about 0.7391. This simple act of feeding a function its own output over and over is fixed-point iteration: x, then g(x), then g(g(x)). It halts when you reach a point where g(x)=x, a point that comes out exactly as it went in. That is the fixed point. The remarkable thing is that almost wherever you start, you are pulled to the same point. There is a catch: near the fixed point the slope |g'| must be less than 1, so that each step shrinks the distance, a contraction. This idea hides everywhere, from solving equations to computer graphics, economic equilibria, and Google's PageRank. And Newton's method is, underneath, just a very fast fixed-point iteration.
The blue curve is g(x)=cos x and the dashed line is y=x. The green dot where they meet is the fixed point. Press step and a cobweb is drawn: from the current x go vertically up to the curve to read the next value, then horizontally across to the line y=x to make it the new x. Move the start x0 anywhere and watch the cobweb spiral into the crossing. This single picture is the whole of fixed-point iteration.
Why do some iterations gather while others scatter? The answer is one number, the slope. Here g is a straight line with its fixed point at 1, and the slider a is exactly g'. Keep |a| below 1 and the cobweb, drawn green, files neatly into the fixed point. That is a contraction. Push |a| above 1 and it turns red, pushed away from the fixed point and diverging. What is more, the closer |a| is to 0, the fewer steps it takes. A small slope is fast convergence.
It is the same straight line g, but now watch the sign of a. The size of the slope decides whether it converges, while the sign decides the shape. A positive a makes a staircase that approaches the fixed point monotonically from one side. A negative a makes a spiral that flips above and below the fixed point, oscillating as the sign reverses each step. Drag the slider across 0 and you can see the staircase turn into a spiral and back.
Convergence may be guaranteed, but the speed varies wildly. The number of steps to reach a tolerance of 1e-6 is roughly n ≈ log(tol)/log|g'|, and the curve shows that count against |g'|. Set the slider near 0.5 and it finishes within about twenty steps; push it toward 0.95 and the count explodes into the hundreds. A contraction close to 1 does converge, but maddeningly slowly. That is exactly why a smarter method is worth wanting.
Here is that smarter method. Ordinary fixed-point iteration is linearly convergent, so the error shrinks only by a steady ratio (say a half) each step. The bars step down gently. Newton's method is quadratically convergent, so the error is squared each step. The correct digits double, and the bars drop like a cliff. Toggle between the two: to reach the same 1e-10 precision, linear needs dozens of steps while quadratic needs only four or five. That is why Newton, which cleverly designs g so that g'=0 at the root, is the fastest fixed-point iteration of all.