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:

f (x) = 0\quad (E)

Let x_* be the solution of (E).
The idea is to bring back to equation of type:


where x=x_* is a fixed point of g.

We introduce a convergent sequence (x_n)_{n\geq 0} to the fixed point x_* of g, which is the solution of equation (E).

Fixed Point Theorem


If g\in\mathcal{C}[a, b] and  g(x) \in[a, b],\forall x\in[a, b], then g has a fixed point x_* in [a, b].

If g\in\mathcal{C}^1[a, b] and if exists a constant \tau in ]0,1[ such that

|g' (x)|\leq \tau

over [a, b] then:
- the fixed point x_* is unique
- the iteration x_{n+1} = g(x_n ) will converge to the unique fixed point x_* of g \forall x_0\in [a,b].

Proof of the existence.
We define h over [a,b], like follows:


Clearly: h(a)=a-g(a)\leq 0 and h(b)=b-g(b)\geq 0because g(x) \in[a, b],\forall x\in[a, b]. Now we apply the intermediate value theorem to g:

\exists x_*\in[a,b]|/h(x_*)=0


\exists x_*\in[a,b]|/g(x_*)=x_*.

Proof of the unicity.
We suppose now that there exists two fixed points x_1,x_2 with x_1\neq x_2. We apply the mean value theorem : there exists \xi\in]a,b[ with:


we get


This is a contradiction! Finally


The sequence x_{n+1} = g(x_n ) is well defined because
g(x) \in[a, b],\forall x\in[a, b] and consequently g(x_n) \in[a, b], \forall x_n provided that x_0\in [a, b]. As previously , we apply the mean value theorem, we show the existence of \xi_{n-1}\in ]x_{n-1},x_*[
for all n with




since \tau est dans ]0,1[.

- |x_n-x_*|\leq \tau^n \sup (x_0-a,x_0-b)
- |x_n-x_*|\leq \frac{\tau^n}{1-\tau}|x_1-x_0|

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

\leq \ldots \leq \tau^n|x_1-x_0|

Let n,m\in\mathbf{N}:


when m goes to infinity:

|x_n-x_*|\leq \frac{\tau^n}{1-\tau}|x_1-x_0|

Order and Rate of convergence of a sequence

We suppose that (x_n)_{n\geq 0} converges to x_*:


where e_n=x_n-x_* is the error between x_n and x_*.

If exists two constants C>0and p such that:


We say that the sequence (x_n)_{n\geq 0} converges with order p
with a rate of convergence C.

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 g and that also depends on the nature of f.

If g'(x_*)\neq 0


since g'(x_*)\neq 0, the rate of convergence C=|g'(x_*)| and the convergence is linear(order 1) and C<1 since |g' (x)|\leq \tau<1 on [a, b].

If g'(x_*)=0, we must introduce a Taylor Developement of g around x_*. Don’t forget that e_n converges to 0. For example,
a Taylor developement of order 3 gives:


with \xi_n\in]x_*,e_n+x_*[=]x_*,x_n[, thus




The rate of convergence C=\displaystyle|\frac{g''(x_*)}{2}| and the convergence is quadratic(order 2). We can generalize this result with the following therorem.


g^{(k)}(x_*)&\neq& 0

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

Taylor developement of order k around x_*of g gives:


with \xi_n\in]x_*,e_n+x_*[=]x_*,x_n[, d’oà¹






Any message or comments?

comments powered by Disqus