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

Fixed point method

Sunday 3 December 2006, by Nadir SOUALEM

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 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 $(x_n)_{n\geq 0}$ to the fixed point of , 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 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 is unique
the iteration $x_{n+1} = g(x_n )$ will converge to the unique fixed point of $\forall x_0\in [a,b]$ .

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

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

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

thus:

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

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

$g(x_1)-g(x_2)=g'(\xi)(x_1-x_2)$

we get

$|g(x_1)-g(x_2)|=|x_1-x_2|=|g'(\xi)||x_1-x_2|<\tau|x_1-x_2|<|x_1-x_2|$

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 with

$\begin{array}{ccl} |x_n-x_*|&=&|g(x_{n-1})-g(x_*)|=|g'(\xi_{n-1})||x_{n-1}-x_*|\leq\tau|x_{n-1}-x_*|\\ |x_n-x_*|&\leq&\tau|x_{n-1}-x_*|\leq\tau^2|x_{n-2}-x_*|\leq\ldots\leq\tau^n|x_{0}-x_*| \end{array}$

Finally:

$\lim_{n\to\infty}|x_n-x_*|=\lim_{n\to\infty}\tau^n|x_{0}-x_*|=0$

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:

$|x_{n+1}-x_n|\leq\tau|x_n-x_{n-1}| \leq \ldots \leq \tau^n|x_1-x_0|$

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

$\begin{array}{ccl} |x_{n}-x_{n+m}|&\leq& |x_{n}-x_{n+1}|+|x_{n+1}-x_{n+2}|+\ldots+ |x_{n+m-1}-x_{n+m}|\\ &\leq& \tau^{n}|x_1-x_0|+\tau^{n+1}|x_1-x_0|\ldots+ \tau^{n+m-1}|x_1-x_0|\\ &\leq& (\tau^{n}+\tau^{n+1}+\ldots+\tau^{n+m-1})|x_1-x_0|\\ &\leq& \displaystyle\tau^n\frac{1-\tau^{m}}{1-\tau}|x_1-x_0|\\ &\leq& \displaystyle\frac{\tau^n}{1-\tau}|x_1-x_0|\\ \end{array}$

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 :

$\lim_{n\to\infty}|x_n-x_*|=\lim_{n\to\infty}|e_n|=0$

where is the error between and .

If exists two constants and such that:

$\lim_{n\to\infty}\frac{|x_{n+1}-x_*|}{|x_{n}-x_*|^p} =\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_{n}|^p}=C$

We say that the sequence $(x_n)_{n\geq 0}$ 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 $g'(x_*)\neq 0$

$\lim_{n\to\infty}\frac{|x_{n+1}-x_*|}{|x_{n}-x_*|}=\lim_{n\to\infty}|g'(\xi_{n-1})|=|g'(x_*)|$

since $g'(x_*)\neq 0$ , the rate of convergence and the convergence is linear(order 1) and since $|g' (x)|\leq \tau<1$ 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:

$\begin{array}{ccl} x_{n+1}&=&g(x_n)\\ &=&g(e_n+x_*)\\ &=&g(x_*)+e_ng'(x_*)+\displaystyle\frac{e_n^2}{2!}g''(x_*) +\displaystyle\frac{e_n^3}{3!}g^{(3)}(\xi_n)\\ &=&x_*+0+\displaystyle\frac{e_n^2}{2!}g''(x_*) +\displaystyle\frac{e_n^3}{3!}g^{(3)}(\xi_n)\\ &=&x_*+\displaystyle\frac{e_n^2}{2!}g''(x_*) +\displaystyle\frac{e_n^3}{3!}g^{(3)}(\xi_n)\\ \end{array}$

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

$e_{n+1}=x_{n+1}-x_*=\displaystyle\frac{e_n^2}{2!}g''(x_*) +\displaystyle\frac{e_n^3}{3!}g^{(3)}(\xi_n)$

and

$\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_{n}|^2}=|\frac{g''(x_*)}{2}|$

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

$\begin{array}{lcl} g'(x_*)&=&g''(x_*)=g^{(3)}(x_*)=\ldots=g^{(k-1)}(x_*)=0\\ g^{(k)}(x_*)&\neq& 0 \end{array}$

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

Proof.
Taylor developement of order k around of gives:

$\begin{array}{ccl} x_{n+1}&=&g(x_n)\\ &=&g(e_n+x_*)\\ &=&g(x_*)+e_ng'(x_*)+\displaystyle\frac{e_n^2}{2!}g''(x_*) +\ldots\displaystyle\frac{e_n^k}{k!}g^{(k)}(\xi_n)\\ &=&x_*+\displaystyle\frac{e_n^k}{k!}g^{(k)}(\xi_n)\ \end{array}$