Root finding: bisection, Newton–Raphson, fixed point, order of convergence

The comparison table

Method	Order	Needs	Guaranteed?
Bisection	1 (linear, factor ½)	sign change	✓ always
Regula falsi	1	sign change	✓
Fixed point $x_{n}$₊$_{1} = g(x_{n})$	1 if 0 < |g′(r)| < 1; 2 if g′(r) = 0	|g′| < 1 near r	local
Secant	$(1+\sqrt{5})/2 \approx 1.618$	two starting points	local
**Newton$** x_{n}$₊$_{1} = x_{n} - f/f'$	2 at a simple root, 1 at a multiple root	f′ ≠ 0	local only
Modified Newton x − m f/f′	2 at a root of known multiplicity m		local

Newton's caveats

• Quadratic convergence is local: a poor start can diverge (f = $x^{1/3})$, cycle $(f = x^{3} - 2x + 2$ from $x_{0} = 0)$, or run away.
• At a root of multiplicity m ≥ 2 the convergence degrades to linear with factor (m−1)/m.
• Error recursion: $e_{n+1}$ $\approx (f''/2f') e_{n}^{2}$.

Fixed point iteration

Converges locally iff |g′(r)| < 1; the error satisfies $e_{n+1}$ $\approx g'(r)e_{n}$. Banach's contraction principle gives a global statement on an interval where |g′| ≤ k < 1 and g maps the interval into itself.

Bisection count

To reach tolerance $\varepsilon$ from an interval of length $L: n \ge log_{2}(L/\varepsilon)$ steps. Bisection never fails but never accelerates.

Key takeaways

• Newton is quadratic only at simple roots, and only locally.
• Secant beats bisection in order but loses the guarantee.
• Fixed point: the derivative at the root is the convergence factor.