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}}} {{Existence.}} 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]. {{Unicity.}} 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[. {{Corollary}} - |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. {{Theorem.}} if

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

then the order of convergence of the fixed point method is k. {{Proof.}} 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