The rate of convergence of a sequence describes how quickly its terms approach a limit. For a sequence whose errors
are eventually nonzero, a common definition of
order
is
where . This is called
-order to distinguish it from definitions based on bounds for
the errors. Order 1 with
gives linear convergence, while orders 2 and 3 give quadratic
and cubic convergence. Superlinear convergence means
, even when no order
exists in this definition.
For example,
converges linearly to 0 with
, while
converges quadratically to 0 with
. Near a simple root,
Newton's method applied to a twice continuously
differentiable function has an error bounded by a constant times the square of the preceding error. This
accounts for its characteristic quadratic convergence when the leading error coefficient
is nonzero.
For root-finding algorithms, the Kung-Traub conjecture gives the sharp universal local order for deterministic stationary methods without memory
using at most
scalar evaluations per iteration, with attainment for
(Kung and Traub 1974, Colbrook 2026).