Two kinds of "getting better"
We have met two very different shapes of computation already. One is a fixed recipe that runs once and stops — Gaussian elimination does a known amount of work and hands you an answer. The other is an iterative method: it produces a sequence of guesses x_0, x_1, x_2, ... that, you hope, march toward the true answer x*. Iteration shows up everywhere — finding a root, solving a giant sparse system, training a model. The natural questions are: does the march actually arrive, and how quickly?
Convergence is the yes/no question: does the error e_n = x_n - x* shrink to zero as n grows? A method that converges for your problem is one whose later guesses you can trust. But convergence alone is a low bar. A method might converge yet need a million steps to reach four correct digits, while another reaches sixteen digits in five steps. To choose well, we need to measure the speed — and that is what the rate of convergence captures.
Linear convergence: chipping away
The cleanest way to measure speed is to compare each error to the one before it. Suppose the error roughly satisfies |e_{n+1}| ≈ C·|e_n| for some constant C with 0 < C < 1. Then each step multiplies the error by C — the error decays like a geometric sequence. This is linear convergence, and C is called the rate or contraction factor. If C = 0.1, you gain about one decimal digit per step; if C = 0.5, the error merely halves each time, so you crawl.
The word "linear" is unfortunate — the error curve is not a straight line, it is a decaying exponential. The name refers to the power of e_n on the right: it appears to the first power. Bisection, which halves a bracket around a root every step, is the textbook example: C = 1/2 exactly, completely reliable but slow. Many stationary iterations for linear systems (Jacobi, Gauss–Seidel) are also linear, with C governed by the spectral radius of the iteration matrix — converge only when that radius is below 1.
Faster than linear: the order p
Some methods do dramatically better. The general definition compares e_{n+1} to a power of e_n: |e_{n+1}| ≈ C·|e_n|^p. The exponent p is the order of convergence. When p = 1 we are back to linear (and there we additionally need C < 1). When p = 2 we have quadratic convergence, the prize: roughly speaking, the number of correct digits doubles every step. Two correct digits become four, then eight, then sixteen — you slam into double-precision's ceiling in a handful of steps.
Newton's method is the famous quadratic converger. Its update is the line below: from a guess x_n you slide along the tangent of f to where it crosses zero. Near a simple root, with a good starting point, the error squares each step — that doubling is why Newton feels almost magical when it works.
x_{n+1} = x_n - f(x_n)/f'(x_n)
n x_n |error|
0 1.0 ~5e-1 (good start)
1 1.5 ~8e-2
2 1.4167 ~2e-3
3 1.41422 ~6e-6
4 1.4142136 ~4e-11 digits roughly double each stepBetween linear and quadratic sits superlinear convergence, where the error ratio |e_{n+1}|/|e_n| itself tends to zero but the order is not a whole 2. The secant method is the classic case, with order about 1.618 (the golden ratio) — slower per step than Newton, but it needs no derivative, so each step is cheaper. "Fastest order" and "fastest in wall-clock time" are not the same thing.
The fine print: convergence is conditional
Order is a statement about behavior near the answer — it is asymptotic. It says nothing about whether you ever get close enough for the fast regime to kick in. Newton's quadratic rate is a local promise: from far away it can overshoot wildly, get stuck cycling between two points, or fly off to infinity. These are its failure modes, and they are real, not rare. The order also drops if the assumptions break: at a multiple root, where f'(x*) = 0, Newton degrades from quadratic all the way down to merely linear.
Even bog-standard linear methods need a condition to converge at all. Fixed-point iteration x_{n+1} = g(x_n) converges only when g is a contraction near the fixed point — concretely, when |g'(x*)| < 1, the contraction-mapping condition. If |g'(x*)| > 1 the iteration runs away from the answer. A cobweb diagram is the little picture that makes this visible: bounce between the curve y = g(x) and the line y = x, and watch whether the staircase spirals in or out.
Knowing when to stop — and measuring the rate yourself
There is a catch hiding in all of this: the error e_n = x_n - x* uses x*, the very answer you do not know. So in practice you cannot watch the true error directly. Instead you watch quantities you can see and use them as a stopping criterion — typically the step size |x_{n+1} - x_n| and the residual |f(x_n)| for a root. When both are below a tolerance, you stop. This is the a posteriori way of judging progress: estimate from the numbers you have produced, not from a formula known in advance.
You can also estimate the order p empirically from three successive iterates, without ever knowing x*. Form the ratio of consecutive differences and take a log; the steps below spell it out. This is the same spirit as the order-of-accuracy study for discretizations: don't just trust the theoretical O(h^p) claim — measure the exponent from your own runs and check that the numbers actually do what the theory promised.
- Run the iteration and keep three consecutive guesses x_{n-1}, x_n, x_{n+1} (plus the previous one x_{n-2}).
- Form the consecutive differences d_n = x_{n+1} - x_n, and likewise d_{n-1} and d_{n-2}.
- Estimate the order as p ≈ log(|d_n| / |d_{n-1}|) / log(|d_{n-1}| / |d_{n-2}|); these differences stand in for the unknown errors.
- Read the result: p near 1 means linear, near 2 means quadratic, around 1.6 hints at a secant-style superlinear method. If p comes out near 1 where you expected 2, suspect a multiple root or a bug.