The Bisection Method halves its error every step; the good rearrangement in Fixed-Point Iteration seemed to double its correct digits. "Order of convergence" makes this difference precise. With $e_n = |x_n - r|$, a method has order $p$ if $$e_{n+1} \approx Ce_n^{p}$$ for large $n$, with a constant $C > 0$ (and $C < 1$ when $p = 1$).
🔑 Key idea
Order 1 (linear): each step gains the same number of digits, $\log_{10}\frac{1}{C}$. Order 2 (quadratic): the number of correct digits roughly doubles each step. To estimate $p$ from three errors use logarithms: $$p \approx \frac{\ln(e_{n+1}/e_n)}{\ln(e_n/e_{n-1})}.$$
💡 Why it works
Take $-\log_{10}$ of $e_{n+1} \approx Ce_n^{p}$. With $d_n = -\log_{10}e_n$ (roughly the number of correct digits), $$d_{n+1} \approx p\,d_n - \log_{10}C.$$ For $p = 1$ the digits grow by a fixed amount; for $p = 2$ they double. For the estimate, divide $e_{n+1} \approx Ce_n^{p}$ by $e_n \approx Ce_{n-1}^{p}$: $\frac{e_{n+1}}{e_n} \approx \left(\frac{e_n}{e_{n-1}}\right)^{p}$, and the power rule for logarithms brings $p$ down.
Errors of a linear and a quadratic method from the same start.
step
linear, $C = 0.1$
quadratic, $C = 1$
0
$10^{-1}$
$10^{-1}$
1
$10^{-2}$
$10^{-2}$
2
$10^{-3}$
$10^{-4}$
3
$10^{-4}$
$10^{-8}$
4
$10^{-5}$
$10^{-16}$
✏️ Worked example: Bisection is linear
What are the order and rate of bisection?
The error bound halves each step: $e_{n+1} \approx \frac{1}{2}e_n$, so $p = 1$ and $C = \frac{1}{2}$.
Digits per step: $\log_{10}2 \approx 0.3$, so about 3.3 steps per digit.
The table lists the errors, the ratios e₍ₙ₊₁₎/eₙ and e₍ₙ₊₁₎/eₙ², and the estimated order. Correct digits are bold and green.
Between the two extremes is superlinear convergence: the ratio $\frac{e_{n+1}}{e_n}$ goes to $0$, so the method speeds up as it goes, but the order may be less than 2. The secant method, with order about $1.618$, is the standard example. Higher order is not everything, though: what matters in practice is the work per digit gained, which also depends on how much each step costs.
In real problems the root $r$ is unknown, so $e_n$ is too. Near convergence the change between iterates, $|x_{n+1} - x_n|$, is a good stand-in for $e_n$ when the method is faster than linear, and it is the usual stopping test: stop when it falls below the tolerance you need.
⚠️ Common mistake
Estimating the order from the ratio $\frac{e_{n+1}}{e_n}$ alone. For any order above 1 that ratio goes to $0$, so it cannot tell order 2 from order 3; it only separates linear from faster. The order comes from logarithms, as in the formula above, or from checking which ratio $\frac{e_{n+1}}{e_n^{p}}$ settles to a constant.
Practice
Pass with 3 right answers, the last 2 in a row. Each right answer earns 2 XP.
Tobin A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation (University of Delaware, free online edition): chapter "Roots of nonlinear equations", sections "Fixed-point iteration" and "Newton's method" (rates of convergence)
MIT OpenCourseWare 18.330, Introduction to Numerical Analysis: lecture notes on orders of convergence