Résolution numérique de l'équation f ( x ) = 0

I-1 Préambule

I-2 Exemple motivant: équation d'état d'un gaz

I-3 Rappels d'analyse

I-4 Critère d'arrêt pour la résolution numérique de f(x) = 0

Dans le cas le plus général, il s'agit de résoudre une équation non linéaire dont on n'est pas capable de trouver une solution exacte. Dans ce cas, on dispose de quelques méthodes numériques exécutables sur des logiciels comme Matlab , Maple , Scilab pour approximer la solution exacte. Ces méthodes numériques sont toutes basées sur la construction d'une suite convergeant vers un réel vérifiant .

Dans ce document, nous allons traiter quatre méthodes: la méthode de dichotomie, de point fixe, de Newton, et de Lagrange. Pour le faire, nous avons besoin de quelques rappels d'analyse.

Une équation de type f(x) = 0 peut être écrite d'une manière équivalente sous la forme de g(x) = x. La fonction g est une fonction dépendante de f non unique comme le montre l'exemple suivant:

Exemple

Si la fonction g peut être

ou

Les instructions Matlab suivantes permettent de tracer les représentations graphiques de ces fonctions, y compris celle de la droite y = x:

Code Matlab

x = [0:0.001:1]; 
f = inline('sin(2*x)-1 + x');
g1 = inline('1-sin(2*x)'); 
g2 = inline('1/2*(asin(1-x))'); 
h = inline('x');
plot(x, f(x), '--.b',  x, g1(x), '-.b', x, g2(x), '--b', x, h(x),'b'); 
legend('f', 'y=1-(2x)', 'y=1/2*(Arcsin(1-x))', 'y=x'); 
grid on; 
ylabel('y(x)'); 
xlabel('x'); 

On voit bien que f admet un unique zéro et que les graphes des fonctions

se coupent en .

I-3-1 Point fixe

I-3-2 Multiplicité d'une racine, fonction contractante

I-3-3 Théorème de point fixe

I-3-4 Fonctions convexes

I-3-5 Vitesse de convergence d'une suite

Définition

Définition

Définition

Remarque

Théorème

Preuve

Définition [fonction convexe]

Proposition

Proposition

Définition

Définition

Soit une suite convergente vers . On appelle ordre de convergence de la suite (x_n) le réel fini ou infini r>0 défini par:

1. Si r = 2, on dit que la convergence de (x_n) est quadratique .
2. Si r = 3, on dit que la convergence de (x_n) est cubique .
3. Supposons que l'ordre de convergence de la suite (x_n) est r = 1 et que:
   1. Si 0 < k < 1 on dit que la suite (x_n) est à convergence linéaire .
   2. Si k = 0 on dit que la suite (x_n) est à convergence super-linéaire .
   3. Si k = 1 on dit que la suite (x_n) est à convergence logarithmique .

Exemple

Une fois construite la suite (x_n) convergeant vers l vérifiant g(l) = l, quand peut-on arrêter les itérations de l'algorithme numérique si l'on désire déterminer une valeur approchée de l avec une tolérance fixée à l'avance. Un bon critère d'arrêt est le contrôle de l'incrément :

1. On constate la convergence: les résultats numériques se stabilisent.
2. On s'arrète à l'itération n₀ si on peut montrer théoriquement que:

Exemple

II-1 Principe

II-2 Etude de la convergence

II-3 Test d'arrêt

1. Si f(c) = 0, c'est la racine de f et le problème est résolu.
2. Si nous regardons le signe de f(a) f(c)
   1. Si f(a) f(c)<0, alors
   2. Si f(c) f(b)<0, alors

On recommence le processus en prenant l'intervalle au lieu de dans le premier cas, et l'intervalle au lieu de dans le second cas. De cette manière, on construit par récurence sur n trois suites (a_n), (b_n) et (c_n) telles que et telles que pour tout ,

2. Si f(c_n) f(b_n)<0 alors et .
3. Si f(c_n) f(a_n)<0 alors et .

Théorème

Soit f une fonction continue sur vérifiant f(a) f(b)<0 et soit l'unique solution de l'équation f(x) = 0. Si l'algorithme de dichotomie arrive jusqu'à l'étape n alors on a l'estimation:

Par conséquent, la suite (c_n) converge vers . C'est aussi vrai si .

Preuve

Pour que la valeur de c_n de la suite à la n-ième itération soit une valeur approchée de à près, il suffit que n vérifie:

Exemple

 
x = [0:0.001:1];
f = inline('exp(x)+3*sqrt(x)-2');
plot(x, f(x))
grid on;
ylabel('f(x)');
xlabel('x');
title('graphe de f');

g = inline('exp(t) + 3*sqrt(t)-2');
Nit = 0;
epsilon = 1e-10;
borneinf = 0;
bornesup = 1;
pmilieu = (borneinf + bornesup)/2;

while and(g(pmilieu) ~= 0, (bornesup-borneinf) >= epsilon )
    Nit = Nit+1;
    if g(pmilieu)*g(borneinf) < 0
        bornesup = pmilieu;
    else
       borneinf = pmilieu;
    end
    pmilieu = (borneinf + bornesup)/2;
end
pmilieu
g(pmilieu)
Nit - 1
n_{théorique} = 10*log(10)/log(2) - 1

Exemple

Exercice

III-1 Principe

III-2 Point attractif

III-3 Point répulsif

III-4 Point douteux

III-5 Ordre de convergence

III-6 Test d'arrêt

Le principe de cette méthode consiste à transformer l'équation f(x) = 0 en une équation équivalente g(x) = x où g est une fonction auxiliaire "bien" choisie. Le point est alors un point fixe de g. Approcher les zéros de f revient à approcher les points fixes de g. Le choix de la fonction g est motivé par les exigences du théorème de point fixe. En effet, elle doit être contractante dans un voisinage I de , ce qui revient à vérifier que sur ce voisinage. Dans ce cas, on construit une suite définie par:

Il ne reste plus qu'à appliquer localement le théorème de point fixe pour démontrer que

C'est l'objet du paragraphe suivant:

Exercice

III-2-1 Théorème de convergence

III-2-2 Illustration graphique

III-2-3 Intervalle de convergence

Théorème

Soit de classe . On suppose que g admet un unique point fixe vérifiant . Alors il existe un voisinage de dans I tel que la suite (x_n) définie par:

converge vers .

Preuve

Le réel vérifiant les hypothèses du théorème précédent est appelé point fixe attractif de g et le voisinage correspondant est dit intervalle de convergence de la méthode d'approximation.

Code Matlab

x = [1.3:0.001:2.3];
plot(x, log(x)+1.1, '-', x, x, '--')
grid on;
ylabel('y');
xlabel('x');
title('Cas d''un point fixe attractif');

Exercice

Proposition

Preuve

III-3-1 Théorème de non-convergence

III-3-2 Illustration graphique

III-3-3 Remarque sur la convergence

Théorème

Soit de classe . On suppose que g admet un unique point fixe vérifiant . Alors il existe un voisinage de dans I tel que la suite (x_n) définie par:

ne converge pas vers .

Preuve

Comme il existe un voisinage avec h>0 tel que . Donc (x_n) ne converge pas vers .

Le réel vérifiant les hypothèses du théorème précédent est appelé point fixe répulsif de g.

Code Matlab

x = [1: 0.0001:2];
plot(x, exp(x)-2, '-', x, x, '--')
grid on;
ylabel('y');
xlabel('x');
title('Cas d''un point fixe repulsif')

Remarque

Lorsque est un point répulsif de g, celle-ci devient bijective au voisinage de et . Par conséquent le point devient un point attractif pour . En effet:

Exercice

III-4-1 Définition

III-4-2 Exemple1

III-4-3 Exemple2

Définition

Soit de classe pour laquelle est un unique point fixe vérifiant . Alors est appelé point douteux de g, car il peut être attractif ou répulsif comme le montre les deux exemples suivants:

Exemple

Soit la fonction g définie par . On a et pour tout la suite itérée (x_n) définie par est strictement décroissante minorée par 0 donc convergeant vers une limite . Comme g est continue et que est l'unique point fixe de g sur .

Code Matlab

x = [-pi/2: 0.0001:pi/2]; 
g = inline('sin(x)'); 
plot(x, g(x), '--', x, x, '-') 
grid on; 
ylabel('g(x)'); 
xlabel('x'); 
axis on; 
title('graphe de g'); 

Exemple

Illustration graphique

Code Matlab

x = [-1: 0.0001:2]; 
g = inline('sinh(x)'); 
plot(x, g(x), '--', x, x, '-') 
grid on; 
ylabel('g(x)'); 
xlabel('x'); 
axis on; 
title('graphe de g'); 

Exercice

Remarque

Si on sait que est un point attractif. Si de plus g est de classe sur I et qu'il existe M>0 tel que pour tout x dans un voisinage de la formule de Taylor nous permet d'écrire:

d'où avec et la suite (x_n) est alors convergente à convergence au moins quadratique (voir introduction).

Nous allons maintenant présenter un résultat simplifié concernant l'ordre de la méthode de point fixe.

Théorème

Soit de classe avec . On suppose que g admet un unique point fixe vérifiant . Il existe alors un voisinage de dans I tel que la suite itérée (x_n) définie par:

est convergente vers . De plus, l'ordre de convergence de (x_n) est égal à m si et seulement si

Preuve

L'existence de de est assurée par le théorème de convergence pour un point attractif. La formule de Taylor appliquée à la fonction g au point à l'ordre m donne: il existe un réel c_n dans l'intervalle

En raison des hypothèses faites sur g, on obtient:

Enfin,

et

Comme nous avons expliqué dans l'introduction, la suite (x_n) converge vers un réel vérifiant . En fixant la tolérance on estime qu'on atteint la précision dès qu'il existe tel que:

Néanmoins, la situation devient plus concrète lorsque g' est négative au voisinage de . En effet:

Proposition

Soit de classe . On suppose que g admet un unique point fixe vérifiant -1 < g'(x)<0 pour tout x dans un intervalle de convergence de . Soit la suite définie par:

Alors:

Par conséquent, soit n₀ tel que alors approche à près.

Preuve

On applique le théorème des accroissements finis à g entre x_n et . Il existe alors c_n entre x_n et telle que:

ce qui donne:

Comme sont de signes contraires.

Finalement,

IV-1 Principe et convergence

IV-2 Illustration graphique

IV-3 Méthode de Newton modifiée

IV-4 Théorème de convergence globale

IV-5 Test d'arrêt

1. Si , et si alors
   et la convergence est linéaire.

2. Si et , alors
   et la convergence est au moins quadratique.

Poursuivons maintenant notre construction de la méthode de Newton. Considérons et . Posons

En résumé, si est telle que et , on prend pour x assez proche de et la fonction définie par:

Remarque

La suite de Newton vérifie

ou encore

Soit x₀ un point donné (proche de ). On considère la droite d qui passe par le point et qui a comme pente f'(x_n). Elle a comme équation:

y = f'(x_n)(x - x_n) + f(x_n)

D'après l'équation , est le point où la droite d intersecte l'axe Ox.

Code Matlab

x = [0.1: .001:3];
x0 = 2;
x1 = 2*(1 - log(2)); 
plot(x, x.^-1 - 1 , '-b', x, -(1/x0)^2*(x - x0) + (1/x0 -1), '--b')
grid on;
ylabel('y');
xlabel('x');
title('Illustration de la methode de Newton');

Exercice [ Convergence locale de la méthode de Newton ]

Exercice

Dans ce qui précède, nous avons supposé que la fonction f dont nous sommes en train de chercher le zéro vérifiant

autrement dit, est une racine simple de f. La question qu'on doit se poser maintenant est: que se passe t-il quand est une racine de f de multiplicité ? Si on garde la même fonction g que précédement, la méthode de Newton perd son caractère de convergence quadratique. En effet, on peut écrire

donc

ce qui implique en terme de suite:

Ceci se traduit par une convergence linéaire et pas du tout quadratique. Pour récupérer cette dernière, on fait appel à la méthode de Newton modifiée .

Exercice

Nous allons annoncer un résultat de convergence globale ( x₀ est quelconque dans le domaine de f) concernant la méthode de Newton pour des fonctions ayant une concavité déterminée (convexe ou concave).

Théorème

Soit de classe vérifiant :

alors la suite (x_n) définie par:

est convergente vers .

Preuve

Une fois construite la suite (x_n) convergeant vers vérifiant et une fois fixée la tolérance nous cherchons le premier entier n₀ vérifiant:

V-1 Principe

V-2 Interprétation géométrique

V-3 Convergence

L'avantage de cette méthode est qu'elle ne nécessite pas le calcul de la dérivée f'. L'inconvénient est que nous perdons la convergence quadratique.

La fonction g correspondante vérifie:

Code Matlab

x = [0: .001:2];
plot(x, x.^2 - 1 , '-b')
grid on;
ylabel('y');
xlabel('x');
title('Illustration de la methode de Lagrange');

Nous allons nous inspirer de l'exemple précédent pour présenter un théorème de convergence.

Théorème

Soit de classe telle que f' et f'' soient strictement positives sur . On suppose que

et on appelle l'unique solution de l'équation f(x) = 0. Alors:

1. La suite (x_n) telle que:
   est bien définie.
2. La suite (x_n) est croissante, convergeant vers .
3. La méthode de Lagrange est d'ordre au moins 1:

Preuve

On pose où

La fonction f est strictement convexe : sa courbe est en dessous de tout segment reliant deux points de cette courbe. Donc f admet son unique zéro dans l'intervalle . Comme f(a) < 0 et f(b) > 0, le réel x₁ est l'absisse de l'intersection de la droite passant par (a, f(a)) et (b, f(b)) et vérifie f(x₁) < 0 ; de même, f(x₂) < 0 et par récurrence on a

On vérifie que la suite (x_n) est croissante majorée par b, donc convergente. Comme et que g est continue, la limite est l'unique point fixe de g. De plus,

(la dernière égalité est obtenue en dérivant g au point ).

Exercice

1. Philipe G. Ciarlet. Introduction à l'analyse numérique et à l'optimisation . Dunod 1990.
2. Jean-Pierre Demailly. Analyse numérique et équations différentielles . Presses Universitaires de Grenoble, 1996.
3. Ernst Hairer. Introduction à l'analyse numérique . Université de Genève, section mathématiques, case postale 240. Octobre 2001.

Exercice

On veut calculer les zéros de l'équation

dans l'intervalle . Le graphe de la fonction f est montré dans la figure suivante :

1. Peut-on appliquer la méthode de la bissection pour calculer les deux racines? Pourquoi ? Dans le cas où c'est possible, estimer le nombre minimal d'itérations nécessaires pour calculer le(s) zéro(s) avec une tolérance aprés avoir choisi un intervalle convenable.
2. Ecrire la méthode de Newton pour la fonction f. A l'aide du graphe de la fonction f, déduire l'ordre de convergence de la méthode pour les deux zéros.
3. On considère maintenant la méthode de point fixe avec
   pour calculer le zéro . En observant que établir si cette méthode de point fixe est convergente.
4. En considérant encore le zéro et la méthode de point fixe introduite à la question précédente, montrer qu'il existe une constante positive C > 0 telle que
   et estimer cette constante.

Exercice

On veut calculer le zéro de la fonction en utilisant la méthode de point fixe suivante :

étant un paramètre réel.

1. Pour quelles valeurs du paramètre w le zéro de la fonction f est-il un point fixe de la méthode proposée ?
2. Pour quelles valeurs de w la méthode proposée est-elle d'ordre 2 ?
3. Existe-t-il une valeur de w telle que l'ordre de la méthode de point fixe est supérieur à 2 ?

Exercice

Exercice

Soit une racine double de la fonction f, :

1. En tenant compte du fait qu'on peut écrire la fonction f comme
   vérifier que la méthode de Newton pour l'approximation de la racine est seulement d'ordre 1.
2. On considère la méthode de Newton modifiée suivante :
   Vérifier que cette méthode est d'ordre deux si l'on veut approcher .

Exercice