Convergence order and efficiency

Convergence order and the error equation

Equivalently, writing the error as $e_k=x_k-\alpha$, the method has order $p$ if and only if it satisfies the error equation:

The error equation is obtained with Taylor expansions, as in the proof of Newton's order or in the fixed-point theorem.

Measuring the order in practice: COC and ACOC

Given the sequence of iterates, the theoretical order is estimated with the computational order of convergence (COC), which requires knowing $\alpha$:

Since in practice $\alpha$ is unknown, the error is replaced by the difference between consecutive iterates, giving the approximate computational order of convergence (ACOC):

It is the same philosophy as order estimation in ODE methods: compare how errors shrink under refinement. The Newton exercise shows the ACOC tending to 2.

Efficiency and optimal methods

High order is not free: each iteration may require several evaluations of $f$ and its derivatives. To compare methods one defines the efficiency index $I=p^{1/d}$, where $p$ is the order and $d$ the number of distinct functional evaluations per iteration, and the computational efficiency index $IC=p^{1/(d+op)}$, which also counts the $op$ products and quotients of each iteration.

Newton is optimal ($2=2^{2-1}$); third-order methods with three evaluations are not ($3<2^{3-1}=4$). Multipoint methods like Ostrowski or Jarratt reach order 4 with only three evaluations: they are optimal, which is why they stand out in the numerical comparison.