Iteration is a common approach widely used in various numerical methods.
It is the hope that an iteration in the general form of
will eventually converge to the true solution of the problem at
the limit when
. The concern is whether this iteration
will converge, and, if so, the rate of convergence. Specifically we use the
following to represent how quickly the error converges to zero:

Here is called the

This expression may be better understood when it is interpreted as when . Obviously, the larger and the smaller , the more quickly the sequence converges. Specially, we consider the following cases:

- If and ,
, then
- if , the convergence is
*sublinear* - if , the convergence is
*linear*with the*rate of convergence*of . - if , the convergence is
*superlinear*

- if , the convergence is
- If , , the convergence is quadratic.
- If , , the convergence is cubic.

The iteration
can be written in terms of the errors
and . Consider the Taylor expansion:

Subtracting from both sides, we get

At the limit , all higher order error terms become zero, we have

If , then the convergence is linear. However, if , then

and we have

the convergence is quadratic. We see that if the iteration function has zero derivative at the fixed point, the iteration may be accelerated.

**Examples:**

- , the sequence is

This is a sublinear convergence as only when will the limit be a constant . - , the sequence is

This is a linear convergence of order and rate . -
, the sequence is

This is superlinear, specifically quadratic, convergence of order and rate .

From these examples we see that there is a unique exponent , the
order of convergence, so that

In practice, the true solution is unknown and so is the error
. However, it can be estimated if the convergence is
superlinear, satisfying

Consider:

i.e., when ,

The order and rate of convergence can be estimated by