Every way to find a root
Bracketing methods that never fail vs. open methods that are faster when they work -- and how to pick.
Start by asking whether you can bracket the root -- a sign change on [a,b]. If so, bisection and false position are slow but NEVER fail: reach for one of them when reliability matters more than speed, or when you have no derivative and no good starting guess. If you have a formula for f' and a starting guess already close to the root, Newton's method converges far faster (quadratically) -- use it when speed matters and you trust the starting point. No derivative available, but two starting points are? The secant method gets superlinear convergence without one. Chasing a COMPLEX or repeated root of a polynomial specifically is Muller's method's own job, not any of the above.
Bracketing methods -- guaranteed to converge, slower
Term
bracket
A sign change on [a,b] -- the starting assumption every method in this group needs.
Let f be continuous on [a,b] with f(a) and f(b) of opposite sign, and let \{c_n\} be the sequence of midpoints the bisection method produces from that starting bracket. Then a root p \in (a,b) exists, and |c_n - p| \le \frac{b-a}{2^{n}}, \qquad n = 1, 2, 3, \ldots so c_n \to p as n \to \infty.
The guaranteed error bound after n steps -- known before you run a single one.
Show proof
Existence of p is the Intermediate Value Theorem, applied once to the starting bracket. For the bound: each bisection step replaces the current bracket with a new one exactly half as wide, and the replacement is always the half that still contains a sign change — so it still contains p (since the endpoint that gets discarded shares c_n's sign, the discarded half cannot be the one holding a root by the same IVT argument that guaranteed one to begin with). By induction, the bracket containing p after n steps has width (b-a)/2^n. The midpoint c_n of that bracket is, at worst, half the bracket's own width away from either endpoint, and p lies inside the bracket — so |c_n - p| is at most half the bracket's width, which is already (b-a)/2^n for the bracket produced BEFORE computing c_n; tracking the indices carefully against the standard convention (where c_n is the midpoint used to produce the n-th bracket) gives exactly |c_n-p|\le (b-a)/2^n. Since (b-a)/2^n \to 0, the squeeze forces c_n \to p.
Same bracketing guarantee as bisection, but weights the new point toward whichever endpoint is closer to zero.
Open methods -- faster, not guaranteed
Term
fixed point
The general idea every open method specializes -- x = g(x), iterated.
Term
contraction
The condition (|g'(x)|<1 near the root) that decides whether a fixed-point iteration actually converges.
Let f \in C^2[a,b] (twice continuously differentiable). Let p \in (a,b) satisfy f(p) = 0, and suppose f'(p) \ne 0. Then there is some \delta > 0 with this property: for any starting guess x_0 within \delta of p, Newton's method x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} converges to p. The error satisfies x_{n+1} - p = -\frac{f''(\xi_n)}{2f'(x_n)}\,(x_n - p)^2 for some \xi_n between x_n and p. So once x_n is close enough to p, the error at each step is bounded by a constant times the SQUARE of the previous error. This is called order-2 (quadratic) convergence.
Quadratic convergence once you're close enough -- the payoff for needing f'.
Show proof
Since f'(p) \ne 0 and f' is continuous, f' stays bounded away from
zero on some interval around p. That interval is where \delta lives.
Shrink it further if needed, so that f'' (also continuous, by
hypothesis) is bounded there too. Expand f in a first-order Taylor
polynomial about x_n, evaluated at p, using the Lagrange remainder
(taylors-theorem-lagrange-remainder, ch.00):
f(p) = f(x_n) + f'(x_n)(p - x_n) + \frac{f''(\xi_n)}{2}(p-x_n)^2
for some \xi_n between x_n and p. The left side is 0, since
f(p) = 0. Divide through by f'(x_n). This is legal, since f'(x_n)
\ne 0 once x_n is in the interval where f' stays bounded away from
zero:
0 = \frac{f(x_n)}{f'(x_n)} + (p - x_n) + \frac{f''(\xi_n)}{2f'(x_n)}(p-x_n)^2.
Rearrange, using x_{n+1} = x_n - f(x_n)/f'(x_n) to replace the first
two terms:
x_{n+1} - p = -\frac{f''(\xi_n)}{2f'(x_n)}(x_n - p)^2.
This is the claimed error identity. f'' and 1/f' are both bounded
near p. So the coefficient -f''(\xi_n)/(2f'(x_n)) stays bounded by
some constant M as x_n \to p. This gives |x_{n+1}-p| \le
M|x_n-p|^2. Once |x_n - p| is small enough that M|x_n-p| < 1, each
step's error is a shrinking multiple of the SQUARE of the last one. That
forces x_n \to p, and makes the convergence quadratic.
Newton's method with the derivative replaced by a two-point slope estimate.
The secant method's own rate -- between bisection's linear and Newton's quadratic.
Polynomial-specific
A repeated root slows every method above down -- Newton's own quadratic rate degrades to linear.