# Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

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

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

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:

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

## Any message or comments?

comments powered by Disqus