Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

The order of an iteration method measures how fast the error shrinks from one step to the next. Higher order means far fewer steps.

Definition

Let approximate , and write the error as with . A Taylor expansion of about gives

The power of in the first nonzero term after is the order of the method. Since is small, the first nonzero term dominates:

Fixed-point iteration

In general , so fixed-point iteration is first order: the error is multiplied by roughly each step. This also shows why we need .

Newton-Raphson

For :

At the root , so . The method is therefore at least second order. Also , which is usually nonzero, giving

In practice the number of correct decimals roughly doubles every step. In the Newton-Raphson Method example the error went from about to to .