. Fixed point method |
Fixed point method |
Fixed point method |

Fixed point method

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:

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)_$ to the fixed point $x_*$ of $g$, which is the solution of equation (E).

Fixed Point Theorem

Existence.

If $g\in\mathcal[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^1[a, b]$ and if exists a constant $\tau$ in ]0,1[ such that

  • the fixed point $x_*$ is unique
  • the iteration $x_ = 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 0$because $g(x) \in[a, b],\forall x\in[a, b]$. Now we apply the intermediate value theorem to $g$:

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:

This is a contradiction! Finally

The sequence $x_ = 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_\in ]x_,x_*[$ for all $n$ with

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\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_-x_n|\leq\tau|x_n-x_| \leq \ldots \leq \tau^n|x_1-x_0|\]

when m goes to infinity:

Order and Rate of convergence of a sequence

We suppose that $(x_n)_$ converges to $x_*$:

is the error between $x_n$ and $x_*$.

If exists two constants $C>0$and $p$ such that:

We say that the sequence $(x_n)_$ converges with order p with a rate of convergence $C$.

In Particular…

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

since $g’(x*)\neq 0$, the rate of convergence

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:

The rate of convergence

and the convergence is quadratic(order 2). We can generalize this result with the following therorem.

Theorem. if

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

Proof. Taylor developement of order k around $x_*$of $g$ gives:

If you found this post or this website helpful and would like to support our work, please consider making a donation. Thank you!

Articles in the same category
  • Newton's method
  • Fixed point method
  • Mathematics - Numerical solution of non-linear equations

2025 Math-linux.com. Knowledge base dedicated to Linux and applied mathematics.

📎📎📎📎📎📎📎📎📎📎