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 une solution de (E).
L’idée générale est de se ramener à une équation du type :

où est un point fixe de l’application .

On introduit alors une suite d’itérée $(x_n)_{n\geq 0}$ qui converge vers le point fixe de , 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 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 est unique
la suite définie par $x_{n+1} = g(x_n )$ converge vers le point fixe de $\forall x_0\in [a,b]$ .

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

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

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

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

où représente l’erreur.

S’il existe deux constantes et 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
est d’ordre avec une constante d’erreur asymptotique .

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 et cela dépend aussi de la nature de .

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 et la convergence est linéaire, c’est à dire d’ordre 1 et puisque $|g' (x)|\leq \tau<1$ sur [a, b].

Si , on doit faire une étude plus poussée en introduisant un développement de Taylor au voisinage de de de la fonction , en utilisant le fait évidemment que 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)$

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

Preuve.
On introduit un développement de Taylor au voisinage de de de la fonction à l’ordre , en utilisant le fait évidemment que 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}$