Point fixe - Méthode de relaxation

Point fixe

Définition:

Un point fixe pour une application

est un élément

tel que

, c'est-à-dire un invariant de

Par exemple, pour $f:\R\to\R$ définie par

, les nombres

sont des points fixes car

.

Si $f:\R^2\to\R^2$ est une rotation, son seul point fixe est le centre de la rotation, tandis que si

est une symétrie axiale, tout les points de l'axe de symétrie sont des points fixes.

Toute équation peut se ramener à la recherche d'un point fixe, par exemple

$E(x)=0\iff x=x-E(x)=f(x)$

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 $f:[a,b]\to[a,b]$ dérivable et telle que

$\forall x\in[a,b]\,,\ \left|f'(x)\right|<k$

avec $0\leqslant k<1$ alors, pour tout $x_0\in[a,b]$ , la suite définie par

$x_{n+1}=f\left( x_n\rp$

converge vers l'unique point fixe de

La fonction

définie par

vérifie:

elle est continue et dérivable sur
elle est strictement décroissante car
$g(a)=f(a)-a\geqslant0$ puisque $f(a)\in[a;b]$
$g(b)=f(b)-b\leqslant0$ puisque $f(b)\in[a;b]$

On en déduit que l'équation

$g(x)=0\iff f(x)=x$

admet bien une unique solution $x_\infty$ 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|$

et alors, par récurrence,

$\left|x_n-x_\infty\right|\leqslant k^n\left|x_0-x_\infty\right|$

puis, comme $0\leqslant k<1$ ,

$\lim_{n\to+\infty}\left|x_n-x_\infty\right|=0$

c'est-à-dire

$\lim_{x\to+\infty}x_n=x_\infty$

Relaxation

La convergence de la suite récurrente définie par

$x_{n+1}=f\left( x_n\rp$

dépend des variations de

, donc de sa dérivée (si elle est dérivable).
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$

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$

En posant $\omega=\dfrac1{\alpha+1}$ , 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$

Cette suite converge d'autant plus rapidement que

$\left|g'(x)\right|=\left|\dfrac{\alpha+f'(x)}{\alpha+1}\right|$

est petit.
Comme on peut choisir librement le paramètre $\alpha$ de relaxation, on voit qu'il est judicieux de prendre une valeur proche de

$\alpha\simeq-f'\left( x_\infty\rp$

Bien sûr, cette valeur n'est pas connue d'avance, car on cherche justement $x_\infty$ , mais on peut imaginer en avoir une estimation ou un encadrement. On peut aussi actualiser sa valeur au cours des itérations.

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'équation

, dont on connaît bien l'unique solution $x=\ln(2)\simeq0,693\dots$ .

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

avec la fonction

$f(x)=x-e^x+2$

et on définit alors une suite récurrente par

$x_{n+1}=f(x_n)$

Par exemple, à partir de

, on obtient les valeurs successives

tandis que pour

La convergence est lente…

Relaxation du point fixe

On introduit un paramètre de relaxation:

$x_{n+1}=(1-\omega)x_n+\omega f(x_n)$

Par exemple, avec $\alpha=1/2\iff\omega=2/3$ , on obtient

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: $x_\infty=\ln2$ .
On a, avec relaxation,

$x_{n+1}=g(x_n)$

avec

$g(x)=\dfrac{f(x)+\alpha x}{\alpha+1}$

et donc

$g'(x)=\dfrac{f'(x)+\alpha}{\alpha+1}$

La valeur optimale est donc pour

$g'(x_\infty)=0 \iff\alpha_{opt}=-f'(x_\infty)$

avec ici

$f'(x)=1-e^x$

et donc

$\alpha_{opt}=-\lp1-e^{\ln2}\rp=1$

ou encore

$\omega_{opt}=\dfrac1{\alpha_{opt}+1}=\dfrac12$

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$

5 première itérations avec relaxation optimale

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