La méthode du point fixe appliquée à la résolutions d’équations non linéaires

consiste à élaborer un schéma itératif, en l’occurence une suite convergente vers un point fixe x d’une certaine application g, ce point fixe est en l’occurence

la solution de l’équation f(x)=0.

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

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

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

et la convergence est linéaire, c’est à  dire d’ordre 1 et $C<1$ puisque $\lvert g’ (x) \rvert \leq \tau<1$ on $[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_*.\]