Fixed point method

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 0$because $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>0$and $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_*.$$