Méthode du point fixe

L’objectif ce méthode est la résolution d’équation du type :

$$f (x) = 0\quad (E)$$

Soit $x_*$ une solution de (E).
L’idée générale est de se ramener à une équation du type :

$$g(x)=x$$

o๠$x=x_*$ est un point fixe de l’application $g$.

On introduit alors une suite d’itérée $(x_n)_{n\geq 0}$ qui converge vers le point fixe $x_*$ de $g$, qui est en l’occurence la solution de l’équation (E).

Théorème du point fixe

Existence.

Si $g\in\mathcal{C}[a, b]$ et $ g(x) \in[a, b],\forall x\in[a, b]$, alors g a un point fixe $x_*$ en $[a, b]$.

Unicité.
Si $g\in\mathcal{C}^1[a, b]$ et s’il existe une constante $\tau$ dans ]0,1[ telle que

$$|g’ (x)|\leq \tau$$

sur $[a, b]$ alors :
 le point fixe $x_*$ est unique
 la suite définie par $x_{n+1} = g(x_n )$ converge vers $x_*$ le point fixe de $g$ $\forall x_0\in [a,b]$.

Preuve de l’existence.
On définit l’application $h$ sur [a,b], comme suit :

$$h(x)=x-g(x)$$

Clairement : $h(a)=a-g(a)\leq 0$ et $h(b)=b-g(b)\geq 0$ puisque par hypothèse $ g(x) \in[a, b],\forall x\in[a, b]$. On conclut donc en utilisant le théorème des valeurs intermédiaires :

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

c’est à dire :

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

Preuve de l’unicité.
Supposons qu’il existe deux point fixes $x_1,x_2$ pour l’application g avec $x_1\neq x_2$. En utilisant le théorème de la moyenne, on montre l’existence d’un élément $\xi\in]a,b[$ telle que :

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

donc

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

ce qui est contradictoire donc

$$x_1=x_2.$$

La suite définie par $x_{n+1} = g(x_n )$ est bien définie puisque
$g(x) \in[a, b],\forall x\in[a, b]$ et par voie de conséquence $g(x_n) \in[a, b], \forall x_n$ à condition évidemment que $x_0\in [a, b]$. Comme précédemment, en utilisant le théorème de la moyenne, on montre l’existence pour chaque $n$, d’un élément
$\xi_{n-1}\in ]x_{n-1},x_*[$
tel que

$$ \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} $$

Par passage à la limite on voit clairement que :

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

puisque $\tau$ est dans ]0,1[.

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

Preuve du corollaire.
La première inégalité est évidente. Pour démontrer la seconde inégalité, on utilise le fait que :

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

Soit deux entiers $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} $$

En faisant tendre $m$ vers l’infini :

$$|x_n-x_*|\leq \frac{\tau^n}{1-\tau}|x_1-x_0|$$

Vitesse de convergence-Ordre de convergence d’une suite

Supposons qu’une suite $(x_n)_{n\geq 0}$ converge vers un élélment
$x_*$ :

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

o๠$e_n=x_n-x_*$ représente l’erreur.

S’il existe deux constantes $C>0$et $p$ telles que :

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

on dit alors que la convergence de la suite $(x_n)_{n\geq 0}$ vers $x_*$
est d’ordre $p$ avec une constante d’erreur asymptotique $C$.

Cas particuliers.

Si p=1 et C<1 on dit que la convergence est linéaire.

Si p=2, la convergence est dite quadratique.

Si p=3, la convergence est dite cubique.

Ordre de convergence d’une méthode de point fixe

à‰videmment plusieurs cas peuvent se présenter, on peut construire plusieurs
fonctions $g$ et cela dépend aussi de la nature de $f$.

Si $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_*)|$$

donc puisque $g’(x_*)\neq 0$, la constante d’erreur asymptotique est $C=|g’(x_*)|$ et la convergence est linéaire, c’est à dire d’ordre 1 et $C<1$ puisque $|g’ (x)|\leq \tau<1$ sur $[a, b]$.

Si $g’(x_*)=0$, on doit faire une étude plus poussée en introduisant un développement de Taylor au voisinage de $x_*$ de de la fonction $g$, en utilisant le fait évidemment que $e_n$ tend vers 0. Par exemple à l’ordre 3 cela donne

$$ \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} $$

avec $\xi_n\in]x_*,e_n+x_*[=]x_*,x_n[$, d’oà¹

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

et

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

la constante d’erreur asymptotique est $C=\displaystyle|\frac{g’’(x_*)}{2}|$ et la convergence est quadratique, c’est à dire d’ordre 2. On peut alors citer le théorème suivant.

Théorème.
Si

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

alors la méthode du point fixe est d’ordre $k$.

Preuve.
On introduit un développement de Taylor au voisinage de $x_*$ de de la fonction $g$ à l’ordre $k$, en utilisant le fait évidemment que $e_n$ tend vers 0

$$ \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} $$

avec $\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)$$

et

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

puisque

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