Knowledge base dedicated to Linux and applied mathematics.

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

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).

**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

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

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:

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.

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