Accueil > Mathématiques > Résolution numérique des équations non linéaires > Méthode du point fixe

Méthode du point fixe

samedi 2 décembre 2006, par Nadir SOUALEM

Toutes les versions de cet article : [English] [français]

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

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

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

S’il existe deux constantes C>0et 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_*.

Messages

Un message, un commentaire ?

modération a priori

Ce forum est modéré a priori : votre contribution n'apparaîtra qu'après avoir été validée par un administrateur du site.

Qui êtes-vous ?
Votre message
  • Pour créer des paragraphes, laissez simplement des lignes vides.

Si vous souhaitez aider financièrement le projet Math-Linux.com, vous pouvez aider notre équipe. Merci !!!

Links