Knowledge base dedicated to Linux and applied mathematics.
Accueil > Mathématiques > Résolution numérique des équations non linéaires > Méthode du point fixe
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$$
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).
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|$$
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.
à‰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_*.$$