Theorem 3 (Fixed Point Theorem)

Theorem 3: Let be a function which is continuous on . Let be an element of for all in the interval. Let the derivative of exist on the open interval ( ) with and , for all in ( ). Then, if is any number in the interval , the sequence defined by , with , converges to the unique fixed point .

Proof:

By Theorem 2, a unique fixed point exits.

All elements in the sequence, , lie in the interval

Then

> expr:=abs(p[n]-p);

> expr=abs(g(p[n-1])-g(p));

> expr=abs(D(g)(zeta))*abs(p[n-1]-p);

> expr<=K*abs(p[n-1]-p);

with a value in the interval . Repeatedly applying this inequality yields

> expr<=K^n*abs(p[0]-p);

> lim(abs(p[n]-p),n=infinity)<=lim(K^n*abs(p[0]-p),n=infinity);

and thus

> lim(abs(p[n]-p),n=infinity)=0;

since .

>

As a consequence, an upper bound on the error of the sequence of approximations is given by or .

>

Alternatively, one can try to obtain an upper bound for the error which only uses calculated values. First notice that

> expr1:=abs(p[n+1]-p[n]);

> expr1=abs(g(p[n])-g(p[n-1]));

> expr1<=K*abs(p[n]-p[n-1]);

> expr1<=K^n*abs(p[1]-p[0]);

Then, for , we have

> expr2:=abs(p[m]-p[n]);

> expr2=abs(`p[m]-p[m-1]+p[m-1]-...-p[n]`);

> expr2<=abs(p[m]-p[m-1])+abs(p[m-1]-p[m-2])+`...`+abs(p[n+1]-p[n]);

> expr2<=K^(m-1)*abs(p[1]-p[0])+K^(m-2)*abs(p[1]-p[0])+`...`+K^n*abs(p[1]-p[0]);

> expr2<=K^n*(1+K+`...`+K^(m-n-1))*abs(p[1]-p[0]);

so that with the limit of going to for ,

> expr3:=abs(p-p[n]);

> expr3=lim(abs(p[m]-p[n]),m=infinity);

> expr3<=K^n*abs(p[1]-p[0])*Sum(K^i,i=0..infinity);

> expr3<=K^n*abs(p[1]-p[0])*sum(K^i,i=0..infinity);

The constant now is much smaller then previously and only uses values in the calculated sequence. This formula also shows that convergence will be very slow if is close to 1.