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

  • $\lvert x_n-x_*\rvert\leq \tau^n \sup (x_0-a,x_0-b)$
  • $\lvert x_n-x_*\rvert\leq \dfrac{\tau^n}{1-\tau}\lvert x_1-x_0\rvert$

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=\lvert g'(x\_*) \rvert\]

and the convergence is linear(order 1) and $C<1$ since $\lvert g’ (x) \rvert \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[\]

thus

\[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_*.\]