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

In one sentence

Bisection is slow and certain, Newton is fast and unguaranteed, and Newton's famous quadratic rate holds only at a simple root.

Why the exam asks it

Because "order of convergence" is a precise notion with a small number of standard answers, and because the multiple-root case is a clean way to test whether the quadratic claim was memorised or understood.

The idea

A method has order $p$ if the errors satisfy $|e_{n+1}| \approx C|e_n|^p$. Order $1$ with $C<1$ is linear; order $2$ means the number of correct digits roughly doubles each step.

Bisection

Needs $f$ continuous with $f(a)f(b)<0$. Then a root exists by the intermediate value theorem and the interval halves each step, so after $n$ steps the error is at most $(b-a)/2^n$.

Order $1$ with $C = 1/2$ — slow, and the only method here that cannot fail. Ten steps gain a factor of $1024$, so about $3$ decimal places.

Fixed point iteration

Rewrite $f(x)=0$ as $x = g(x)$ and iterate $x_{n+1}=g(x_n)$. If $|g'(r)|<1$ near the root, the iteration converges linearly with $C = |g'(r)|$; if $|g'(r)|>1$ it diverges however good the starting point.

The same equation admits many rearrangements with different $g$, and the choice decides convergence. That is why the question is usually "which of these iterations converges" rather than "does it".

When $g'(r)=0$ the convergence is faster than linear — and Newton is exactly that case.

Newton–Raphson

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.$$

At a simple root with $f''$ continuous, convergence is quadratic, with $C = |f''(r)/2f'(r)|$. Starting from $x_0=1$ for $x^2-2$: $3/2$, then $17/12$, whose square exceeds $2$ by only $1/144$ — the error squaring visibly.

At a root of multiplicity $m$ it is linear, with factor $(m-1)/m$. For $(x-1)^2$ from $x_0=2$ the iterates are $3/2$, $5/4$, $9/8$: the error halves rather than squares, and $1/2 = (2-1)/2$. Using $x_{n+1}=x_n - m f/f'$ restores the quadratic rate, and that modification is a standard question.

Newton has no convergence guarantee. It fails when $f'(x_n)=0$, when the iterates cycle — the classic being $x^3-2x+2$ from $x_0=0$, which alternates between $0$ and $1$ forever — and when a bad start sends it away entirely. Guaranteed convergence needs a hypothesis such as $f$ convex and monotone on an interval containing the root.

Secant

$$x_{n+1} = x_n - f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}.$$

Order $\varphi = \frac{1+\sqrt5}{2} \approx 1.618$, the golden ratio, which satisfies $t^2 = t+1$ — that equation coming directly from the error recurrence. Slower than Newton per step, but needs no derivative, so it is often faster in work done.

Where intuition breaks

"Newton always converges." It has no guarantee. Bisection is the one that cannot fail, and it is the slow one — the trade is the point.

"Newton is quadratic." At a simple root. At a double root it is linear with factor $1/2$, which is barely better than bisection.

"A faster order always means fewer steps in practice." Order describes behaviour near the root. A method may not get near it at all, and Newton's failures are all far from the root.

"Fixed point iteration converges if $|g'|<1$ somewhere." Near the root, and the iterates must stay in that neighbourhood. Options weaken this to a single point or to the whole line.

"Any rearrangement $x=g(x)$ will do." For $x^2=2$, $g(x)=2/x$ has $|g'(\sqrt2)|=1$ and the iteration cycles between two values forever. $g(x)=(x+2/x)/2$ is Newton and converges quadratically. Same equation, different behaviour.

"Bisection needs differentiability." Continuity and a sign change. It is the method with the weakest hypotheses.

"The secant method has order 2 since it approximates Newton." $1.618$. The approximation to $f'$ costs the difference.

The exam's angle

1. Check the multiplicity before claiming a rate. A repeated factor turns Newton linear, and that is the commonest trick in this topic.
2. For fixed point questions, differentiate $g$ at the root and compare $|g'|$ with $1$.
3. Count bisection steps with $(b-a)/2^n < \varepsilon$ — the answer is a logarithm and it is usually asked directly.
4. Remember the orders: bisection $1$, fixed point $1$, secant $1.618$, Newton $2$, Newton at a root of multiplicity $m$ back to $1$.
5. If asked when Newton fails, name a mechanism — vanishing derivative, cycling, or a bad start — rather than saying it always works.

The night before

• Order $p$: $|e_{n+1}| \approx C|e_n|^p$. Linear is $p=1$ with $C<1$.
• Bisection: needs continuity and a sign change, error $(b-a)/2^n$, order $1$, never fails.
• Fixed point: converges iff $|g'(r)|<1$ near the root, linearly with $C=|g'(r)|$.
• Newton: quadratic at a simple root, $C = |f''/2f'|$. Linear with factor $(m-1)/m$ at a root of multiplicity $m$; $x_{n+1}=x_n-mf/f'$ restores quadratic.
• Newton fails at $f'=0$, by cycling ($x^3-2x+2$ from $0$), or from a bad start.
• Secant: order $\frac{1+\sqrt5}{2}\approx1.618$, no derivative needed.
• $x^2=2$: $g=2/x$ cycles, $g=(x+2/x)/2$ is Newton.