Definition

Many numerical methods, like, e.g. Fixed Point Iteration or Newton-Raphson generate a sequence of successive approximations to the required solution. Often, each approximation requires a lot of time to calculate and one would like to know how fast this sequence of approximations is converging towards the solution.

>

Definition: Assume is a sequence of values which converges to for , and that for each . If positive constants and exists such that , or, , we say that converges to to order , with asymptotic error constant .

>

In line with this definition, we say that the iterative method generating the sequence is of order . In particular, a method is called linear when the generated sequence of approximations converges to order , or quadratic if the generated sequence converges to order .

>

Basically, the order of convergence tells us how quickly the error is decreasing, and therefore may give us an idea of how many iteration steps are needed to obtain a certain accuracy.

>

To illustrate this, consider a linear and a quadratic method with respective sequences of errors given by and with the same asymptotic error constant . This means that , approximately,

> eq1:=abs(e1[n+1])=0.75*abs(e1[n]);

> eq2:=abs(e2[n+1])=0.75*abs(e2[n])^2;

When we apply these equalities succesively, we find that under the present assumptions:

> for i from 1 to 5 do e1[i]:=0.75*abs(e1[i-1]); od;

> 0.75^2;0.75^3;0.75^4;0.75^5;

or in general . For the quadratic method, we obtain:

> for i from 1 to 5 do e2[i]:=0.75*abs(e2[i-1])^2; od;

> 0.75^3;0.75^7;0.75^15;0.75^31;

or in general, . It should be clear that the error in the quadratic method is getting smaller much more quickly. Can we predict how many steps we need to use to obtain an error less then with an initial error of, let's say, ?

> fsolve((0.75^n)*(0.6)=10^(-7),n);

> fsolve((0.75^(2^n-1))*(0.6^(2^n))=10^(-7),n);

So that the linear method needs more then 54 steps (55 or more) to obtain the required accuracy, while the quadratic method needs only 5 steps.