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 x_* be the solution of (E).
The idea is to bring back to equation of type:

g(x)=x

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:

h(x)=x-g(x)

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

thus:

\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:

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

x_1=x_2.

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


\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 x_*:

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

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

If exists two constants C>0and p 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 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

\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 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:


\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 x_*of g 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}

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

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

and

\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_{n}|^k}=|\frac{g^{(k)}(x_*)}{k!}|

since

\lim_{n\to\infty}\xi_n=x_*.

Any message or comments?

pre-moderation

This forum is moderated before publication: your contribution will only appear after being validated by an administrator.

Who are you?
Your post
  • To create paragraphs, just leave blank lines.

If you want to help Math-Linux.com project , Send your contributions to our team. Thanks !!!

Links