Fixed point method
Sunday 3 December 2006, by
All the versions of this article: [English] [français]
Fixed point method allows us to solve non linear equations. We build an iterative method, using a sequence wich converges to a fixed point of g, this fixed point is the exact solution of f(x)=0.
The aim of this method is to solve equations of type:
Let be the solution of (E).
The idea is to bring back to equation of type:
where is a fixed point of .
We introduce a convergent sequence to the fixed point of , which is the solution of equation (E).
Fixed Point Theorem
If and , then g has a fixed point in [a, b].
If and if exists a constant in ]0,1[ such that
over [a, b] then:
the fixed point is unique
the iteration will converge to the unique fixed point of .
Proof of the existence.
We define over [a,b], like follows:
Clearly: and because . Now we apply the intermediate value theorem to :
Proof of the unicity.
We suppose now that there exists two fixed points with . We apply the mean value theorem : there exists with:
This is a contradiction! Finally
The sequence is well defined because
and consequently provided that . As previously , we apply the mean value theorem, we show the existence of
for all with
since est dans ]0,1[.
Proof of the Corollary.
The first inequality is obvious. To prove the second inequality,we use
when m goes to infinity:
Order and Rate of convergence of a sequence
We suppose that converges to :
where is the error between and .
If exists two constants and such that:
We say that the sequence converges with order p
with a rate of convergence .
If p=1 and C<1 we say that the sequence converges linearly .
If p=2, convergence is called quadratic convergence.
If p=3, convergence is called cubic convergence.
Order of convergence of the fixed point method
Obviously several cases are possible, we can build several functions and that also depends on the nature of .
since , the rate of convergence and the convergence is linear(order 1) and since on [a, b].
If , we must introduce a Taylor Developement of around . Don’t forget that converges to 0. For example,
a Taylor developement of order 3 gives:
with , thus
The rate of convergence and the convergence is quadratic(order 2). We can generalize this result with the following therorem.
then the order of convergence of the fixed point method is k.
Taylor developement of order k around of gives:
with , d’où