Many root-finding methods have the same shape: rewrite $f(x) = 0$ as $x = g(x)$, pick $x_0$, and repeat $$x_{n+1} = g(x_n).$$ If the iterates settle at a value $r$ and $g$ is continuous, then $r = g(r)$: a fixed point of $g$, and so a root of $f$. Whether they settle is decided by the The Mean Value Theorem and the derivative $g'$.
Key idea
Near a fixed point $r$, each step multiplies the error by about $g'(r)$. The iteration converges from nearby starting points when $|g'(r)| < 1$ (linearly, with ratio $|g'(r)|$) and moves away when $|g'(r)| > 1$.
Why it works
Subtract $r = g(r)$ from $x_{n+1} = g(x_n)$ and use the Mean Value Theorem: $$x_{n+1} - r = g(x_n) - g(r) = g'(\xi_n)(x_n - r)$$ for some $\xi_n$ between $x_n$ and $r$. If $|g'| \le L < 1$ on an interval around $r$ that holds $x_0$, every step keeps the iterate in that interval and shrinks the error by at least $L$: $|x_n - r| \le L^{n}|x_0 - r| \to 0$. If $|g'(r)| > 1$, the same equation shows errors growing.
Worked example: Two rearrangements of x² = 2
Compare $x_{n+1} = \frac{2}{x_n}$ and $x_{n+1} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right)$, both from $x_0 = 1$.
- $g(x) = \frac{2}{x}$: $x_1 = 2$, $x_2 = 1$, $x_3 = 2, \ldots$ It bounces forever. Here $g'(x) = -\frac{2}{x^{2}}$, so $g'(\sqrt{2}) = -1$: errors never shrink.
- $g(x) = \frac{1}{2}\left(x + \frac{2}{x}\right)$: $x_1 = 1.5$, $x_2 \approx 1.41667$, $x_3 \approx 1.414216$, already 6 digits of $\sqrt{2}$.
- Here $g'(x) = \frac{1}{2}\left(1 - \frac{2}{x^{2}}\right)$, so $g'(\sqrt{2}) = 0$: faster than any fixed ratio.
Answer: the second one converges; the first cycles
Worked example: Which rearrangement converges?
$x^{2} - x - 2 = 0$ has the root $r = 2$. Test $g_1(x) = x^{2} - 2$, $g_2(x) = \sqrt{x + 2}$ and $g_3(x) = 1 + \frac{2}{x}$.
- $g_1'(x) = 2x$, so $g_1'(2) = 4$: diverges. From $x_0 = 2.1$: $2.41$, $3.81$, $12.5, \ldots$
- $g_2'(x) = \frac{1}{2\sqrt{x + 2}}$, so $g_2'(2) = \frac{1}{4}$: converges, the error shrinking by about 4 each step (from $x_0 = 3$: $2.236$, $2.058$, $2.015$).
- $g_3'(x) = -\frac{2}{x^{2}}$, so $g_3'(2) = -\frac{1}{2}$: converges, with iterates alternating around $2$.
Answer: $g_2$ and $g_3$
Worked example: Counting steps
For $g(x) = \cos x$ the fixed point is $r \approx 0.739085$, with $|g'(r)| = \sin r \approx 0.674$. About how many steps gain 6 decimal digits?
- Each step multiplies the error by about $0.674$, gaining $\log_{10}\frac{1}{0.674} \approx 0.17$ digits.
- $6 \div 0.17 \approx 35$ steps. Linear convergence with a ratio near 1 is slow.
Answer: about 35
Common mistake
Expecting every rearrangement of $f(x) = 0$ to work. They all have the same fixed points, but they behave completely differently. Check before iterating: estimate $|g'(r)|$ (or $|g'|$ near your starting guess). Less than 1 converges, more than 1 diverges, and close to 1 is slow.