Order of Convergence

The order of convergence quantifies how fast an iterative method's error shrinks, distinguishing linear, superlinear, and quadratic methods.

Measuring the speed of convergence

An iterative sequence converges with order p if the error e_{n+1} is asymptotically proportional to e_n^p. Order 1 is linear, order 2 is quadratic, and orders between are superlinear. The constant of proportionality is the asymptotic error constant; for linear convergence it must be below 1 for the sequence to converge at all.

What each order means in practice

• Linear (p=1): a fixed fraction of the error removed per step, adding a constant number of digits.
• Superlinear (1
• Quadratic (p=2): Newton's method roughly doubles the correct digits each step.
• Higher order methods exist but rarely pay for their extra evaluations.

Estimating order empirically

Given three successive errors, the order can be estimated from log(e_{n+1}/e_n) divided by log(e_n/e_{n-1}). When the true root is unknown, consecutive differences |x_{n+1} - x_n| serve as a proxy for the error. Watching digits of agreement grow reveals the order directly: doubling per step signals quadratic behavior.

import math
def order(errs):
    return [math.log(errs[k+1]/errs[k])/math.log(errs[k]/errs[k-1])
            for k in range(1, len(errs)-1)]

Order is not the whole story

A high order is worthless if the method diverges from the given start, or if each step is very expensive. The right comparison is work to reach a target accuracy: evaluations per iteration times iterations needed. This is why the secant method often beats Newton in wall-clock time when the derivative is costly, despite its lower order.

Choosing solvers for physics kernels balances order against robustness and cost per step, a trade managed carefully in the coupled nonlinear solvers used for breeder Hyperion design studies.