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 .