Point fixe - Méthode de relaxation
Point fixe
Définition:
Un point fixe pour une application Par exemple, pour
Si
Toute équation peut se ramener à la recherche d'un point fixe, par exemple
Pour les fonctions réelles, la propriété suivante est fondamentale: elle precise à la fois un cadre dans lequel une fonction admet un, et un seul, point fixe, ainsi que la construction d'une suite récurrente qui converge vers celui-ci.
Propriété
Soit avec
converge vers l'unique point fixe de
La fonction
définie par
vérifie:
![\[g(x)=0\iff f(x)=x\]](fich-IMG/28.png)
admet bien une unique solution
sur
.
De plus, d'après le théorème des accroissements finis
![\[\left|x_{n+1}-x_\infty\right|
=\left|f(x_n)-f(x_\infty)\right|
\leqslant k\left|x_n-x_\infty\right|\]](fich-IMG/31.png)
et alors, par récurrence,
![\[\left|x_n-x_\infty\right|\leqslant k^n\left|x_0-x_\infty\right|\]](fich-IMG/32.png)
puis, comme
,
![\[\lim_{n\to+\infty}\left|x_n-x_\infty\right|=0\]](fich-IMG/34.png)
c'est-à-dire
![\[\lim_{x\to+\infty}x_n=x_\infty\]](fich-IMG/35.png)
- elle est continue et dérivable sur
- elle est strictement décroissante car
-
puisque
-
puisque
admet bien une unique solution
De plus, d'après le théorème des accroissements finis
et alors, par récurrence,
puis, comme
c'est-à-dire
Relaxation
La convergence de la suite récurrente définie pardépend des variations de
En particulier, si cette dérivée est toujours strictement inférieure à 1, la convergence est assurée, et plus cette dérivée est petite (proche de 0), plus la convergence est rapide.
Pour tenter d'améliorer la convergence de cette méthode, on introduit un paramètre, dit de "relaxation", de la manière suivante: on souhaite trouver le point fixe
![\[\begin{array}{lrcl}&x_\infty&=&f\left( x_\infty\rp\\[.6em]
\iff&\alpha x_\infty+x_\infty&=&\alpha x_\infty+f\left( x_\infty\rp\enar\]](fich-IMG/38.png)
et on définit alors une suite récurrente par
![\[\begin{array}{ll}&\alpha x_{n+1}+x_{n+1}=\alpha x_n+f\left( x_n\rp\\[.8em]
\iff&
x_{n+1}=\dfrac{\alpha x_n+f\left( x_n\right)}{\alpha+1}=g\left( x_n\right)
\enar\]](fich-IMG/39.png)
En posant
,
la relation de récurrence précédente s'écrit comme un barycentre:
![\[\begin{array}{rlcl}
&x_{n+1}&=&\dfrac\alpha{\alpha+1}x_n+\dfrac1{\alpha+1}f\left( x_n\rp\\[1em]
\iff &x_{n+1}&=&(1-\omega)x_n+wf\left( x_n\rp\enar\]](fich-IMG/41.png)
Cette suite converge d'autant plus rapidement que
![\[\left|g'(x)\right|=\left|\dfrac{\alpha+f'(x)}{\alpha+1}\right|\]](fich-IMG/42.png)
est petit.
Comme on peut choisir librement le paramètre
Bien sûr, cette valeur n'est pas connue d'avance, car on cherche justement
Enfin, lorsque ce calcul doit être fait un nombre de fois important dans un algorithme, on peut chercher par tests numériques une valeur optimale qui sera ensuite utilisée systématiquement et accélerera les calculs successifs. On parle de méthode SOR: Successive Over Relaxation.
Un exemple et son traitement numérique
On considère l'équationPoint fixe
On se ramène tout d'abord à un problème de point fixe:![\[\begin{array}{rcrcl}e^x=2&\iff& 0&=&e^x-2\\
&\iff& x&=&x-\left( e^x-2\rp\\
& & &=&f(x)\enar\]](fich-IMG/48.png)
avec la fonction
et on définit alors une suite récurrente par
Par exemple, à partir de
tandis que pour
La convergence est lente…
Relaxation du point fixe
On introduit un paramètre de relaxation:Par exemple, avec
L'accélération de la convergence est ici une évidence…
Relaxation optimale
On ne peut pas toujours (et c'est même rare) connaître la valeur optimale du paramètre de relaxation, mais c'est le cas ici car on connaît effectivement la valeur limite recherchée:On a, avec relaxation,
avec
![\[g(x)=\dfrac{f(x)+\alpha x}{\alpha+1}\]](fich-IMG/57.png)
et donc
![\[g'(x)=\dfrac{f'(x)+\alpha}{\alpha+1}\]](fich-IMG/58.png)
La valeur optimale est donc pour
avec ici
et donc
ou encore
![\[\omega_{opt}=\dfrac1{\alpha_{opt}+1}=\dfrac12\]](fich-IMG/62.png)
La vitesse de convergence est donc optimale pour la suite récurrente
![\[\begin{array}{lrcccc}&x_{n+1}&=&\lp1-\omega_{opt}\right) x_n&+&\omega_{opt}f(x_n)\\[.8em]
\iff&x_{n+1}&=&\dfrac12\,x_n&+&\dfrac12\,f(x_n)\enar\]](fich-IMG/63.png)
Programmes python
Les programmes python suivants permettent d'obtenir les graphiques présentés dans l'exemple précédent. Les représentations graphiques utilisent Pylab.Méthode du point, et
from pylab import *
from math import log, exp
n=20
def g(x):
return x-(exp(x)-2)
x=[]
new=0
x.append(new)
for i in range(n):
new=g(new)
x.append(new)
plot(x,'-*b')
plot([-1,n],[log(2),log(2)],'-r')
xlim(-1,n)
ylim(0,1.2)
show()
Point fixe avec relaxation
from pylab import *
from math import log, exp
alpha=1
x=[]
new=0
x.append(new)
for i in range(n):
new=alpha/(alpha+1)*new+1/(alpha+1)*g(new)
x.append(new)
plot(x)
plot([-1,n],[log(2),log(2)],'-r')
xlim(-1,n)
ylim(0,1.2)
show()