Home > Mathematics > Numerical solution of nonlinear equations > Fixed point method

Fixed point method

Sunday 3 December 2006,

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

Existence.

If and , then g has a fixed point in [a, b].

Unicity.
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 :

thus:

Proof of the unicity.
We suppose now that there exists two fixed points with . We apply the mean value theorem : there exists with:

we get

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

Finally:

since est dans ]0,1[.

Corollary

Proof of the Corollary.
The first inequality is obvious. To prove the second inequality,we use
this one:

Let :

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 .

In Particular...

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 .

If

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

and

The rate of convergence and the convergence is quadratic(order 2). We can generalize this result with the following therorem.

Theorem.
if

then the order of convergence of the fixed point method is k.

Proof.
Taylor developement of order k around of gives:

with , d’où

and

since

pre-moderation

This forum is moderated before publication: your contribution will only appear after being validated by an administrator.

Who are you?