§ 2.4 Méthodes itératives de type point fixe

Il n'existe pas de méthode efficace basée sur la bissection pour résoudre un système de plusieurs équations à plusieurs inconnues. C'est pourquoi nous continuons notre recherche de méthodes.

L'intérêt des méthodes de type point fixe est qu'elles peuvent aussi s'appliquer à des systèmes de plusieurs équations à plusieurs inconnues. De plus, certaines d'entre elles - la méthode de Newton - convergent rapidement, ce qui permet d'atteindre une grande précision à moindre coût.

Méthode de base

Activité d'introduction

Régler votre calculatrice en radian. A partir de la valeur initiale 1, calculez le cosinus, puis le cosinus du résultat, puis encore le cosinus du résultat et ainsi de suite. Vous obtenez une suite de nombres

1,  0.5403023058681,  0.8575532158464,  0.6542897904978,  0.7934803587426, 
 0.7013687736228,   0.7639596829007,  ...

qui tend vers  r = 0.7390851332152

Répétez l'expérience en partant d'une autre valeur initiale, par exemple 0.2  Vous obtiendrez ainsi une autre suite de nombres qui tend vers la même limite.

Par construction, la valeur de la limite est une solution de l'équation  x = cos(x). Nous constatons qu’en itérant une fonction, nous pouvons obtenir une solution d’une équations. La valeur valeur vers laquelle converge l’itération est un point fixe de la fonction :

Définitions

Soit x ↦ g(x) une fonction continue.

Tout nombre réel r tel que r = g(r) est appelé point fixe de g. Dans l'activité précédente,
r = 0.7390851332152  est un point fixe de la fonction g(x) = cos(x).

Pour une valeur de démarrage (Subscript[x, 0]) donnée, la méthode qui consiste à construire la suite de nombres

(Subscript[x, 1])=g((Subscript[x, 0])), (Subscript[x, 2])=g((Subscript[x, 1])), (Subscript[x, 3])=g((Subscript[x, 2])), (Subscript[x, 4])=g((Subscript[x, 3])), ...

est appelée méthode itérative de type point fixe. La fonction g est appelée fonction d'itération.

Si la suite (Subscript[((Subscript[x, n])), n∈ℕ]) converge vers un nombre r, cela a pour conséquence que g(r) = r (ceci est garanti uniquement si g est continue), autrement dit que r est une solution de l'équation  x=g(x).

Interprétation graphique

L'équation x = cos(x) possède une et une seule solution comme le montre la figure suivante. La solution est située dans l'intervalle [0; (π/2)].

Plot[{x,Cos[x]},{x,-2 π,2 π},Ticks->{Range[-2 π,2 π,(π/2)],Automatic}]

Pour illustrer la méthode itérative de type point fixe, effectuons un zoom qui représente la situation dans le carré [0.7; 0.8] × [0.7; 0.8]              (voir la figure ci-dessous).
On a choisi comme valeur de démarrage        (Subscript[x, 0])=0.78
La valeur suivante est                                      (Subscript[x, 1])=g((Subscript[x, 0]))=cos(0.78)=0.71
Graphiquement, pour passer de (Subscript[x, 0]) à (Subscript[x, 1]), on suit le chemin suivant:
	((Subscript[x, 0]), 0)  est un point sur l'axe des x;
	((Subscript[x, 0]), g((Subscript[x, 0]))) = ((Subscript[x, 0]), (Subscript[x, 1])) est situé sur la courbe de la fonction y = g(x);
	((Subscript[x, 1]), (Subscript[x, 1])) est situé sur la droite y = x;
	((Subscript[x, 1]), g((Subscript[x, 1]))) = ((Subscript[x, 1]), (Subscript[x, 2])) est situé sur la courbe y = g(x);
	((Subscript[x, 2]), (Subscript[x, 2])) est un point sur la droite y = x;
	etc.

On parcourt ainsi un chemin qui passe alternativement d'un point sur la courbe à un point sur la droite. En reliant ces points, on obtient la figure suivante.

La méthode converge vers le point fixe (r, r) qui est situé à l'intersection de la courbe et de la droite.

Si la méthode démarre d'une autre valeur initiale prise dans la même région, la suite tend vers le même point fixe. Par exemple, pour (Subscript[x, 0])=0.72,

La résolution de n’importe quelle équation peut se ramener à la recherche du point fixe d’une fonction. En effet, un nombre r est une solution de l’équation f(x)=0 si et seulement si r est un point fixe de la fonction h(x)=x+f(x) (preuve dans l’exercice 2-4-2). L’exemple suivant est une illustration de ce résultat.

Exemple 1

Résolvons l'équation par une méthode itérative de type point fixe.

ln(x) = 4-x

Dans une première étape, mettons l'équation sous la forme x = g(x), c'est-à-dire

x =4 -ln(x)                  avec g(x) = 4-ln(x)

Par une méthode graphique, déterminons une valeur de démarrage :

Clear[g];g[x_]:=4-Log[x];
Plot[{x,g[x]},{x,1,5}]

Choisissons

x0=3.;

Appliquons la méthode d'itération             (Subscript[x, 1])=g((Subscript[x, 0])), (Subscript[x, 2])=g((Subscript[x, 1])), etc.

FixedPointList[g,x0,10]

On observe que la suite tend vers un point fixe r

N[FixedPoint[g,x0],16]

Représentons graphiquement la situation sur l'intervalle [2.89; 3.01]

Calcul avec Mathematica

Pour appliquer itérativement une fonction à une valeur initiale, on utilise la commande NestList. Pour l’exemple 1, cela donne

NestList[g,x0,12]

Pour que Mathematica fasse l’itération jusqu’à ce que le point fixe soit atteint, on utilise les fonctions FixedPointList et FixedPoint :

FixedPointList[g,x0]

NumberForm[FixedPoint[g,x0],16]

Exemple 2

Résolvons l'équation par une méthode itérative de type point fixe

(2^x)=5-x

Mettons-la d'abord sous la forme x = g(x)

x=5-(2^x)                           avec              g(x)=5-(2^x)

Déterminons une valeur de démarrage

Clear[g];g[x_]:=5-(2^x);
Plot[{x,g[x]},{x,0,3}]

Choisissons

x0=1.5;

Appliquons la méthode d'itération             (Subscript[x, 1])=g((Subscript[x, 0])), (Subscript[x, 2])=g((Subscript[x, 1])), etc.

NestList[g,x0,10]

On observe que la suite diverge. La méthode d'itération ne donne pas de résultat.
Représentons graphiquement la situation sur l'intervalle [-8; 6]

Par conséquent, la méthode du type point fixe n'est pas applicable à toutes les situations.

Remarquons cependant que, si dans un voisinage d’un point fixe (Subscript[x, 0]), la fonction g est continue et 
 - son graphe est plus proche de l'horizontale que de la verticale alors la méthode converge vers (Subscript[x, 0]);
 - son graphe est plus proche de la verticale que de l'horizontale alors la méthode ne converge pas vers (Subscript[x, 0]);
 - la pente de la tangente au graphe au point fixe vaut -1 ou 1, nous savons pas si la méthode converge.

Exercice 2-4-1

a)	On donne une fonction d'itération g et une valeur de démarrage (Subscript[x, 0]);

g(x)=(Sqrt[1+x]),                              (Subscript[x, 0])=2.

(i) 	Imprimez un graphique contenant les graphes des fonction y=x et g (utiliser l’option 
		GridLines→Automatic)  puis estimer graphiquement les dix premières itérations.

(ii)	Calculez  les dix premières itérations à l’aide de Mathematica.

(iii)	Si la suite converge vers un point fixe r, de quelle équation r est-il solution ?

b)	Idem pour les données suivantes avec 5 itérations :

g(x)=(x^2) ,                             (Subscript[x, 0])=(1/2).

c)	Idem pour les données suivantes avec 5 itérations

g(x)=(x^2),                              (Subscript[x, 0])=2.

d)	Idem pour les données suivantes avec 5 itérations

g(x)=(1/x)  ,                             (Subscript[x, 0])=(1/2).

Exercice 2-4-2

Soit f une fonction réelle et r un élément du domaine de définition de f. Démontrer que r est une solution de l’équation f(x)=0 si et seulement si r est un point fixe de la fonction h(x)=x+f(x)

Exercice 2-4-3

Soit l’équation 1-(1/2)(x^2)=0.

a)	Approximer au centième, sans Mathematica, la solution positive de cette équation avec la méthode de type
	point fixe de base.
b)	Déterminer avec Mathematica la solution positive de cette équation avec la méthode de type point fixe de base.
	Itérez jusqu’à ce que l’évaluation du membre de gauche de l’équation avec l’approximation fournie donne une 
	valeur absolue inférieure à (10^(-10)) (utiliser NestWhile).

Amélioration de la méthode (facultatif)

Exemple (facultatif)

Nous allons montrer que toute équation de la forme f(x) = 0 peut se mettre sous la forme x = g(x) de plusieurs manières différentes. Prenons l'exemple de l'équation

(x^3)=(Sqrt[x+2])

qu'on peut d'abord mettre sous la forme f(x) = 0

(x^3)-(Sqrt[x+2])=0

Transformons l'équation pour la mettre sous la forme x = g(x)

(x^3)-(Sqrt[x+2])=0
⟺   0=- (x^3)+(Sqrt[x+2])
⟺   x = x - (x^3)+(Sqrt[x+2])
⟺   x = g(x)                        avec                        g(x) = x - (x^3)+(Sqrt[x+2])

Appliquons la méthode d'itération de type point fixe à partir de la valeur initiale (Subscript[x, 0])= 1.5

x0=1.5;
Clear[g]; g[x_]:=x-(x^3)+(Sqrt[x+2])

NestList[g,x0,5]

(Subscript[x, 5]) est situé hors du domaine de définition de la fonction g. La méthode itérative échoue.

Mais il existe d'autres manières de mettre l'équation donnée sous la forme x = g(x). On peut, par exemple, multiplier les deux membres de l'équation donnée par (1/4):

(x^3)-(Sqrt[x+2])=0
⟺   (1/4)((x^3)-(Sqrt[x+2])) = 0
⟺   0 =- (1/4)( (x^3)-(Sqrt[x+2]))
⟺   x = x -(1/4)( (x^3)-(Sqrt[x+2]))
⟺   x = g(x)                        avec                        g(x) = x -(1/4)( (x^3)-(Sqrt[x+2]))

Appliquons la méthode d'itération de type point fixe à partir de la valeur initiale (Subscript[x, 0])= 1.5

x0=1.5;
Clear[g]; g[x_]:=x-(1/4)((x^3)-(Sqrt[x+2]))

NestList[g,x0,5]

Cette fois, la méthode converge.

On peut généraliser le procédé pour mettre l'équation  f(x) = 0  sous la forme x = g(x) :

f(x)=0
⟺ λ f(x) = 0                      pour une constante non nulle   λ 
⟺ 0 = -λ f(x)
⟺ x = x - λ f(x)
⟺ x = g(x)                     où                g(x) = x - λ f(x).

Dans l'exemple précédent, nous avons vu que, pour λ = 1, la méthode ne converge pas tandis que pour 
λ = (1/4), la méthode converge. La question qui se pose est donc "Comment choisir λ  pour que la méthode converge ?", si possible rapidement.

Généralisation (facultatif)

La méthode d'itération du point fixe converge bien lorsque l'allure générale de la fonction g est proche de l'horizontale. L'idée est donc de choisir λ de telle sorte que le graphique de g soit le plus horizontal possible.
Plus précisément, soit [a, b] un encadrement de la solution r cherchée, c'est-à-dire a < r < b; nous allons choisir λ de telle sorte que g(a) = g(b)    (voir la figure ci-dessous).

a=(1/2);b=(3/2);Clear[g];g[x_]:=1-(1/2) (((x-1))^2);r=1;
Plot[{x,g[x]},{x,a,b},Axes->None,PlotRange->All,AspectRatio->Automatic,Epilog->{Text["(r, r)",{r,r},{1,-1}],Text["(a, g(a))",{a,g[a]},{1,0}],Text["(b, g(b))",{b,g[b]},{-1,0}],{Dashing[{0.01`,0.01`}],Line[{{a,a},{a,g[a]},{b,g[b]},{b,a}}],Line[{{1,a},{r,r}}]},{PointSize[0.02`],Point[{a,g[a]}],Point[{r,r}],Point[{b,g[b]}]}},ImageSize->{400,400}]

f(x)=0
⟺ λ f(x) = 0                
⟺ 0 = -λ f(x)
⟺ x = x - λ f(x)
⟺ x = g(x)                     où                g(x) = x - λ f(x)

On veut choisir λ de telle sorte que g(a) = g(b), c'est-à-dire

g(a) = g(b)
⟺	a- λ f(a) = b - λ f(b)
⟺ λ (f(b)-f(a)) = b - a
⟺   λ = ((b-a)/(f(b)- f(a)))

Exemple

(x^3)=(Sqrt[x+2])
⟺   f(x)=0                où            f(x)=(x^3)-(Sqrt[x+2])

Cherchons d'abord un premier encadrement  [a, b]  d'une solution

Clear[f];f[x_]:=(x^3)-(Sqrt[x+2]);Plot[f[x],{x,0,3}]

Choisissons a et b, puis calculons λ

a=1; b=1.5;λ=((b-a)/(f[b]- f[a]))

La fonction d'itération est

Clear[g];g[x_]:=x-λ*f[x]

x0=((a+b)/2)

FixedPointList[g,x0]

La convergence est rapide.

Méthode pseudo-Newton

Nous adoptons maintenant un autre point de vue.
Soit [a, b] un encadrement d'une solution de l'équation         f(x) = 0.
Une valeur de démarrage (Subscript[x, 0]) étant donnée (typiquement, (Subscript[x, 0])=((a+b)/2)), on fait passer par le point ((Subscript[x, 0]), f((Subscript[x, 0]))) une droite de pente m dont l'équation est

y=m x+p              où  p  est tel que la droite passe par le point ((Subscript[x, 0]), f((Subscript[x, 0])))

f((Subscript[x, 0]))= m (Subscript[x, 0])+p             ⟹                 p = f((Subscript[x, 0]))- m (Subscript[x, 0])

y = m x +(f((Subscript[x, 0]))- m (Subscript[x, 0]))  =  m (x - (Subscript[x, 0])) + f((Subscript[x, 0]))

Clear[f,x];f[x_]:=0.4`-(x^3);a=0.3`;b=0.9`;x0=((a+b)/2);m=((f[b]-f[a])/(b-a));x1=x0-((f[x0])/m);
r=x/.NSolve[f[x]==0,x][[3]];
Plot[{f[x],m (x-x0)+f[x0]},{x,a-0.1`,b+0.1`},AxesOrigin->{a-0.1`,0},PlotRange->{f[b]-0.05`,f[a]+0.05`},AspectRatio->1,Ticks->{{{a,"a"},{r,"r"},{x0,"\!\(\*SubscriptBox[\(x\), \(0\)]\)"}},None},Epilog->{Text["b",{b,0},{-1,-1}],Text["\!\(\*SubscriptBox[\(x\), \(1\)]\)",{x1,0},{-1,-1}],{Dashing[{0.01`,0.01`}],Line[{{x0,0},{x0,f[x0]}}],Line[{{a,0},{a,f[a]},{b,f[b]},{b,0}}]},{PointSize[0.01`],Point[{a,f[a]}],Point[{b,f[b]}],Point[{x0,0}],Point[{x0,f[x0]}],Point[{x1,0}]}},Ticks->None,ImageSize->{500,500}]

La méthode pseudo-Newton consiste à choisir comme valeur de m la pente de la droite qui passe par les points (a, f(a)), (b, f(b)). En d'autres termes, la droite qui passe par le point ((Subscript[x, 0]), f((Subscript[x, 0]))) est parallèle à la droite qui passe par les deux points (a, f(a)), (b, f(b)). On obtient

m=((f(b)-f(a))/(b-a))

La prochaine valeur approchée (Subscript[x, 1]) est l'intersection de la droite avec l'axe des x:

m (x - (Subscript[x, 0])) + f((Subscript[x, 0]))=0
⟺  m (x - (Subscript[x, 0])) =- f((Subscript[x, 0]))
⟺  x-(Subscript[x, 0]) = - (1/m)f((Subscript[x, 0]))
⟺ x = (Subscript[x, 1])=(Subscript[x, 0])-(1/m)f((Subscript[x, 0]))

Exemple

(x^3)=(Sqrt[x+2])
⟺   f(x)=0                où            f(x)=(x^3)-(Sqrt[x+2])

Cherchons d'abord un premier encadrement [a, b] d'une solution

Clear[f];f[x_]:=(x^3)-(Sqrt[x+2]);Plot[f[x],{x,0,3}]

Choisissons a et b puis calculons m

a=1; b=1.5;m=((f[b]-f[a])/(b-a)); x0=((a+b)/2);

La fonction d'itération est

Clear[g];g[x_]:=x-(1/m)f[x]

FixedPointList[g,x0]

La convergence est rapide!

Comparaison de la méthode itérative du point fixe améliorée et de la méthode pseudo-Newton (facultatif)

Soit a, b un encadrement d'une racine r de l'équation   f(x) = 0.
Comme valeur de démarrage, posons         (Subscript[x, 0])=((a+b)/2).

D'un premier point de vue, on définit

λ = ((b-a)/(f(b)- f(a)))                 et                    g(x) = x - λ f(x)

puis on calcule les itérés

(Subscript[x, 1])=g((Subscript[x, 0])),    (Subscript[x, 2])=g((Subscript[x, 1])),               ...

Globalement, on a

(Subscript[x, 1])=g((Subscript[x, 0]))=(Subscript[x, 0])-λ f((Subscript[x, 0])) = (Subscript[x, 0])- ((b-a)/(f(b)-f(a)))f((Subscript[x, 0]))

D'un deuxième point de vue, on calcule

m=((f(b)-f(a))/(b-a))

puis on calcule les itérés

(Subscript[x, 1])=(Subscript[x, 0])-(1/m)f((Subscript[x, 0])),    (Subscript[x, 2])=(Subscript[x, 1])-(1/m)f((Subscript[x, 1])),      ...

Globalement, on a

(Subscript[x, 1])=(Subscript[x, 0])-(1/m)f((Subscript[x, 0]))=(Subscript[x, 0])-(1/((f(b)-f(a))/(b-a)))f((Subscript[x, 0]))=(Subscript[x, 0])-((b-a)/(f(b)-f(a)))f((Subscript[x, 0]))

ce qui montre que les deux points de vue coïncident avec λ = (1/m).
Pour les applications et les exercices, retenons la formulation suivante.
D'abord, on définit

m=((f(b)-f(a))/(b-a)) ;
 g(x) = x - (1/m) f(x)

puis on calcule les itérés

(Subscript[x, 1])=g((Subscript[x, 0])),    (Subscript[x, 2])=g((Subscript[x, 1])),               ...

Dans les exemples, on constatera que, le plus souvent, cette méthode converge rapidement.
Il est ainsi peu coûteux d'atteindre une grande précision.

Méthode de Newton

Newton a proposé une méthode numérique dont nous nous sommes inspirés. Dans la méthode de Newton proprement dite, la pente varie à chaque pas

m=(Subscript[m, 0]) = pente de la tangente au graphe f en ((Subscript[x, 0]);f((Subscript[x, 0])))           puis
m=(Subscript[m, 1]) = pente de la tangente au graphe de f en ((Subscript[x, 1]);f((Subscript[x, 1]))) ,
...

La méthode de Newton ne nécessite pas un encadrement [a, b] d'une solution mais seulement une valeur de démarrage (Subscript[x, 0]).
L'étude de la méthode de Newton est reportée à plus tard, après l'étude de la notion de "dérivée d'une fonction" (la notation est m = f'((Subscript[x, 0])) ).

Exercice 2-4-4

On considère l'équation

(x^3)=3-x

a)	Déterminez le nombre de solutions.

b)	Déterminez graphiquement un encadrement des solutions.

c)	Au moyen de la méthode pseudo-Newton, déterminez une valeur numérique des solutions
	à 6 chiffres significatifs.

Exercice 2-4-5

On considère l'équation dans laquelle l'angle x est exprimé en radians

((sin(x))/x)=0.5

a)	Déterminez le nombre de solutions dans l'intervalle ]0; π[

b)	Déterminez graphiquement un encadrement des solutions.

c)	Au moyen de la méthode pseudo-Newton, déterminez une valeur numérique des solutions
	à 6 chiffres significatifs.

Exercice 2-4-6

On a déterminé le zéro de la fonction dessinée ci-dessous par la méthode pseudo-Newton
en partant de l'encadrement initial a=0.2,  b=1.4, et de la valeur initiale (Subscript[x, 0])=0.8

Clear[f];f[x_]:=(x^3)-1.7`;a=0.3`;b=1.3`;
Plot[f[x],{x,a-0.1`,b+0.1`},AxesOrigin->{0,0},ImageSize->{400,300},GridLines->Automatic]

On demande d'illustrer graphiquement la méthode pseudo-Newton en construisant (Subscript[x, 1]), (Subscript[x, 2]), (Subscript[x, 3]) dans le graphique donné (après avoir imprimé celui-ci).

Exercice 2-4-7

On considère l’équation

(3^x)=7-x.

a)	Mettez l'équation sous la forme f(x)=0
	Montrez que l'intervalle [1; 3] contient une solution.
b)	Imprimez le graphique de la fonction f sur l'intervalle [1; 3].
	En partant de la valeur de démarrage (Subscript[x, 0])= 2, construisez graphiquement (du point de vue
	de l'équation f(x) = 0) la première approximation (Subscript[x, 1]) donnée par la méthode pseudo-Newton. 
	Construisez aussi (Subscript[x, 2]).
c)	Ecrivez la fonction d'itération g de la méthode pseudo-Newton
	Imprimez le graphique de la fonction g sur l'intervalle [1; 3].
	En partant de la valeur de démarrage (Subscript[x, 0])= 2, construisez graphiquement (du point de vue
	de l'équation g(x) = x) la première approximation (Subscript[x, 1]) donnée par la méthode pseudo-Newton. 
	Construisez aussi (Subscript[x, 2]).

Exercice 2-4-8

Définissez un module pseudoNewton[f,{a,b},x0,n] retournant les n itérations de la méthode pseudo-Newton appliquée à la résolution de l’équation f(x)=0, où [a;b] est un encadrement d’une solution et x0 la valeur initiale de l’itération. Utilisez l’exemple de la théorie comme test.