Fixed Point Iteration (See ws1)

Fixed Point Iteration can be used when the equation can be rewritten as . This relationship then forms the basis for the iteration scheme , which, under certain conditions, generates a converging sequence. For example:

> f:=x->sin(x)-x-5;

> fsolve(f(x)=0,x);

> g:=x->sin(x)-5;

> epsilon:=10.^(-4);x[0]:=-5.;x[1]:=g(x[0]);

> for i from 2 to 20 while abs((x[i-1]-x[i-2])/x[i-1]) > epsilon do x[i]:=g(x[i-1]); od;

> g:='g';

This can be illustrated graphically in the picture below:

>

The algorithm for the Fixed Point Iteration is given below:

>

Step 1: Take first estimate for root, .

Step 2: Calculate next estimate as .

Step 3: When then is the root. Otherwise, if then is a sufficiently accurate approximation to the root. If not, repeat Step 2.

>

Fixed Point Iteration has a limited use as a method to find the root of an equation, but because the theory underlying the convergence of Fixed Point Iteration is pertinent to other methods as well, it is useful to study it.

>