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

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


Ce document, destiné à des étudiants de L3, explique quelques méthodes permettant de trouver numériquement les zéros de fonctions d'une variable réelle.

I Introduction

II Méthode de dichotomie

III Méthode de point fixe

IV Méthode de Newton

V Méthode de Lagrange

VI Bibliographie

VII Exercices

Vous trouverez ici le fichier pdf doczero.pdf

I Introduction

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

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

I-1 Préambule

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-1 Préambule
L'étude générale des fonctions à variables réelles nécessite de temps à autre la résolution d'équations de type f(x) = 0. Autrement dit, nous sommes amenés à trouver les zéros de fonctions non linéaires, c'est-à-dire les valeurs réelles alpha telles que
ou, ce qui est équivalent, à résoudre une équation de type

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

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-2 Exemple motivant: équation d'état d'un gaz
On veut déterminer le volume V occupé par un gaz de température T et de pression p. L'équation d'état (c'est-à-dire l'équation qui lie p, V et T) est :
où a et b sont deux coefficients dépendants de la nature du gaz, N le nombre de molécules contenues dans le volume V et k la constante de Boltzmann. Il faut donc résoudre une équation non linéaire d'inconnue V. Ceci revient à trouver les zéros de la fonction :

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, Octave, 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 alpha 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.

I-3 Rappels d'analyse

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 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-sin(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

I-3-1 Point fixe

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 Rappels d'analyse → I-3-1 Point fixe

Définition

Un réel est dit point fixe d'une fonction si

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

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 Rappels d'analyse → I-3-2 Multiplicité d'une racine, fonction contractante

Définition

Soit p un entier et f une fonction p fois dérivable.
  1. On dit que alpha est un zéro de f de multiplicité p si
  2. Un zéro de multiplicité 1 (respectivement 2) est appelé un zéro simple (respectivement double ).

Définition

Soit . Une fonction est dite fonction contractante de rapport k si

Remarque

  1. Soit . Si
    alors g est contractante sur .
  2. Une fonction contractante est continue.

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

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 Rappels d'analyse → I-3-3 Théorème de point fixe

Théorème

Soit une fonction contractante de rapport k. Alors g admet un unique point fixe . De plus, pour tout choix de la suite définie par converge vers l quand .

Démonstration
Etape 1: Existence de l et convergence de la suite Remarquons d'abord que ce qui implique que la suite (xn) est bien définie. Soit x0 dans et . Nous allons montrer:
  1. est de Cauchy (donc convergente, car est complet)
  2. quand où l est un point fixe de g.

Par hypothèse, on sait que
Par récurrence sur n, on obtient:
Soit et on a donc:
La suite (xn) est donc de Cauchy dans qui est complet et par conséquent (xn) converge vers une limite l quand . Comme la fonction g est contractante, elle est continue, et donc quand . En passant à la limite dans l'égalité: on en déduit que l = g(l), c'est à dire que l est un point fixe de g.
Etape 2: Unicité
Soient l1 et l2 deux points fixes de g, donc alors ; comme k<1, ceci est impossible sauf si l1 = l2.

Remarque

Si g est une application vérifiant
alors la suite définie par converge vers l'unique point fixe l de g sur pour tout choix de . De plus en faisant tendre p vers l'infini dans et en gardant n, on obtient:

I-3-4 Fonctions convexes

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 Rappels d'analyse → I-3-4 Fonctions convexes

Définition [fonction convexe]

Soit I un intervalle de . Une fonction est dite convexe sur I si
Si l'inégalité est stricte, f est dite strictement convexe .

Proposition

Si convexe, alors la fonction
est croissante sur .

Proposition

Si est deux fois dérivable, alors:

Définition

On dit que est concave sur I si (-f) est convexe sur I.

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

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 Rappels d'analyse → I-3-5 Vitesse de convergence d'une suite

Définition

Soit une suite convergente vers alpha. On appelle ordre de convergence de la suite (xn) le réel fini ou infini r>0 défini par:
  1. Si r = 2, on dit que la convergence de (xn) est quadratique .
  2. Si r = 3, on dit que la convergence de (xn) est cubique .
  3. Supposons que l'ordre de convergence de la suite (xn) est r = 1 et que:
    1. Si 0 < k < 1 on dit que la suite (xn) est à convergence linéaire .
    2. Si k = 0 on dit que la suite (xn) est à convergence super-linéaire .
    3. Si k = 1 on dit que la suite (xn) est à convergence logarithmique .

Exemple
Soit . Soit la suite récurrente définie par
avec
La suite (xn) converge vers et son ordre de convergence est égal à 2. En effet:
et

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

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

Une fois construite la suite (xn) 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 varepsilon 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 n0 si on peut montrer théoriquement que:

Exemple
Soit f(x) = x3-4x+1. On vérifie que f admet 3 racines réelles et en posant
Un simple calcul donne les valeurs suivantes:

x0 		 -2  0  2

x1 		 -2.125  0.25  1.875

x2 		 -2.114975450  0.254098301  1.860978520

x3 		 -2.114907545  0.254101688  1.860805877

x4 		 -2.114907541  0.254101688   1.860805853

x5 		 -2.114907541  0.254101688   1.860805853

x6 		       

x7 		       

x8 		       

On constate que les valeurs numériques se stabilisent et on a alors les valeurs approchées de l1, l2 et l3 à environ près.

II Méthode de dichotomie

Résolution numérique de l'équation f ( x ) = 0 → II Méthode de dichotomie

II-1 Principe

II-2 Etude de la convergence

II-3 Test d'arrêt

II-1 Principe

Résolution numérique de l'équation f ( x ) = 0 → II Méthode de dichotomie → II-1 Principe
Considérons une fonction f continue sur un intervalle . On suppose que f admet une et une seule racine alpha dans et que f(a) f(b) < 0. On note
le milieu de l'intervalle.
  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écurrence sur n trois suites (an), (bn) et (cn) telles que et telles que pour tout ,
  2. Si f(cn) f(bn)<0 alors et .
  3. Si f(cn) f(an)<0 alors et .
L'algorithme ci-dessus s'appelle l'algorithme de dichotomie .

II-2 Etude de la convergence

Résolution numérique de l'équation f ( x ) = 0 → II Méthode de dichotomie → II-2 Etude de la convergence

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 (cn) converge vers alpha. C'est aussi vrai si .

Démonstration
Il suffit de remarquer qu'à chaque itération, on divise l'intervalle par deux.

II-3 Test d'arrêt

Résolution numérique de l'équation f ( x ) = 0 → II Méthode de dichotomie → II-3 Test d'arrêt

Pour que la valeur de cn de la suite à la n-ième itération soit une valeur approchée de alpha à près, il suffit que n vérifie:
On a alors:
ce qui permet de calculer à l'avance le nombre maximal d'itérations assurant la précision varepsilon.

Exemple
On considère la fonction sur l'intervalle . Le code Matlab suivant trace le graphe de f.
Code Matlab 
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');

La figure montre que f admet un unique zéro . Si on veut utiliser la méthode de dichotomie pour estimer alpha à une tolérance près, il nous faut au plus 33 itérations. En effet, la suite qui approche alpha vérifie
et

Vérification numérique. Le code Matlab suivant permet de calculer la valeur de n nécessaire pour atteindre la précision en choisissant a = 0 et b = 1.
Code Matlab 
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_theorique = 10*log(10)/log(2) - 1

Résultats




Exemple
Si nous reprenons l'exemple précédent avec la fonction f(x) = 10x - 5, nous obtenons les résultats suivants:




On voit alors qu'on atteint la racine alpha sans aucune itération, ce qui montre contrairement à l'exemple précédent que la majoration du théorème ci-dessus est parfois assez large.

Exercice
Méthode de dichotomie

III Méthode de point fixe

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe

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

III-1 Principe

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-1 Principe

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 alpha 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 alpha, 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
Méthode de point fixe

III-2 Point attractif

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-2 Point attractif

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

III-2-2 Illustration graphique

III-2-3 Intervalle de convergence

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

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-2 Point attractif → III-2-1 Théorème de convergence

Théorème

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

converge vers alpha.

Démonstration
Comme il existe tel que . De plus, g' est continue sur I donc il existe un voisinage tel que
Donc g est k-contractante sur . En particulier, . Le théorème de point fixe appliqué localement à g dans le voisinage implique que

Définition

Le réel alpha 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.

III-2-2 Illustration graphique

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-2 Point attractif → III-2-2 Illustration graphique


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
Nature d'un point fixe

III-2-3 Intervalle de convergence

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-2 Point attractif → III-2-3 Intervalle de convergence

Proposition

En pratique, un intervalle de convergence peut être calculé comme suit:
  1. Si , prendre comme intervalle de convergence
    contenant alpha tel que
  2. Si , prendre comme intervalle de convergence
    tel que

Démonstration
  1. Cas où . D'après la continuité de g', il existe contenant alpha tel que
    On a alors
    En effet, comme g est croissante sur , on a:
    D'autre part, on a
    Comme ,
    ce qui donne . Donc . De plus,
    Comme ,
    ce qui donne .
    D'où . De plus:
    • si , alors (xn) est croissante convergeant vers alpha ;
    • si , alors (xn) est décroissante convergeant vers alpha

  2. Cas où . D'après la continuité de g', il existe un voisinage de alpha tel que
    et Les réels gamma et beta sont nécessairement de part et d'autre de alpha: ou . En effet, on a
    Comme , et sont de signes contraires, ce qui prouve le résultat.
    Montrons que si , alors
    On suppose que ; on a , ce qui implique que , puis que
    D'où . Soit en supposant que xn et appartiennent à , on montre de la même façon que

    On conclut donc que

    Remarquons finalement que alpha est toujours entre deux termes successifs de la suite (xn). On dit que (xn) encadre alpha. Par conséquent si .

III-3 Point répulsif

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-3 Point répulsif

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

III-3-2 Illustration graphique

III-3-3 Remarque sur la convergence

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

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-3 Point répulsif → III-3-1 Théorème de non-convergence

Théorème

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

ne converge pas vers alpha.

Démonstration
Comme il existe un voisinage avec h>0 tel que . Donc (xn) ne converge pas vers alpha.

Définition

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

III-3-2 Illustration graphique

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-3 Point répulsif → III-3-2 Illustration graphique

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

III-3-3 Remarque sur la convergence

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-3 Point répulsif → III-3-3 Remarque sur la convergence

Remarque

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

Exercice
Différents types de points fixes

III-4 Point douteux

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-4 Point douteux

III-4-1 Définition

III-4-2 Exemple1

III-4-3 Exemple2

III-4-1 Définition

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-4 Point douteux → III-4-1 Définition

Définition

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

III-4-2 Exemple1

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-4 Point douteux → III-4-2 Exemple1

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

Illustration graphique
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');

III-4-3 Exemple2

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-4 Point douteux → III-4-3 Exemple2

Exemple
Soit la fonction . On a et pour tout la suite itérée (xn) définie par est strictement croissante et non majorée donc divergente. Par conséquent, le point fixe de g est répulsif.

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

III-5 Ordre de convergence

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-5 Ordre de convergence
Soit alpha un point fixe de g.

Remarque

Si on sait que alpha est un point attractif. Si de plus g est de classe sur I et s'il existe M>0 tel que , pour tout x dans un voisinage de alpha alors d'après la formule de Taylor :
d'où avec . La suite (xn) 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 alpha dans I tel que la suite itérée (xn) définie par:
converge vers alpha. De plus, si
alors l'ordre de convergence de (xn) est égal à m.

Démonstration
L'existence de de alpha 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 alpha à l'ordre m donne: il existe un réel cn dans l'intervalle tel que :
Si on suppose de plus que , alors
Donc,
  • le rapport tend vers qui est fini et non nul,
  • pour tout , le rapport tend vers .

III-6 Test d'arrêt

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-6 Test d'arrêt

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

Néanmoins, la situation devient plus concrète lorsque g' est négative au voisinage de alpha. 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 alpha. Soit la suite définie par:

Alors:

Par conséquent, soit n0 tel que alors approche alpha à varepsilon près.

Démonstration
On applique le théorème des accroissements finis à g entre xn et alpha. Il existe alors cn entre xn et alpha telle que:
ce qui donne:
Comme sont de signes contraires.
Finalement,

IV Méthode de Newton

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton

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

IV-1 Principe et convergence

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton → IV-1 Principe et convergence
La méthode de Newton est une méthode particulière de point fixe. Elle est basée sur l'idée de construction d'une suite (xn) qui converge vers alpha d'une manière quadratique. Rappelons que d'après le théorème , si g est une application de dans , on a les résultats suivants:
  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 tel que . Posons
avec tel que Nous avons donc
Si on choisit h pour que , la méthode de point fixe appliquée g donne pour une suite (xn) convergeant vers alpha d'une manière au moins quadratique (d'ordre supérieur ou égal à 2). Or
et donc
Il suffit donc de choisir h telle que
Ceci n'est possible que si

En résumé, si est telle que et , on prend pour x assez proche de et la fonction définie par :
vérifie . Grâce au théorème , il existe un voisinage de alpha dans tel que la suite (xn) définie par
est convergente vers alpha de manière au moins quadratique.

Remarque

La suite de Newton vérifie
ou encore
Soit x0 un point donné (proche de alpha). On considère la droite D qui passe par le point et qui a comme pente f'(xn). Elle a comme équation :
D'après l'équation , est le point où la droite D intersecte l'axe Ox.

IV-2 Illustration graphique

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton → IV-2 Illustration graphique

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 ]
Soit une fonction de classe admettant un unique zéro de multiplicité 1.
  1. Montrer qu'il existe tel que vérifie et que la suite (xn) définie par : converge vers alpha.
  2. On pose . Montrer que . En déduire que avec

Exercice
Méthode de Newton

Dans ce qui précède, nous avons supposé que la fonction f dont nous cherchons le zéro alpha vérifie
Autrement dit, nous avons supposé que alpha est une racine simple de f. La question qu'on doit se poser maintenant est : que se passe-t-il quand alpha est une racine de f de multiplicité  ? Si on garde la même fonction g que précédemment, 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 que tend vers . 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.

IV-3 Méthode de Newton modifiée

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton → IV-3 Méthode de Newton modifiée
On suppose ici que alpha est une racine de f de multiplicité c'est-à-dire :
On suppose que et par conséquent h aussi. On définit alors la fonction g par :
Dans ce cas,
ce qui implique :

Exercice
Montrer que .

IV-4 Théorème de convergence globale

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton → IV-4 Théorème de convergence globale

Nous allons énoncer un résultat de convergence globale ( x0 est choisi n'importe où 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 :
  1. f(a) f(b)<0

La suite (xn) définie par :
est convergente vers alpha.

Démonstration
Les hypothèses
implique qu'il existe un unique tel que . Comme est de signe constant, on distingue deux cas :
  1. Premier cas : (donc f(x0)>0).
    1. Si on a :
      Comme f(x0)>0, alors . Rappelons que g est la fonction définie par . Comme
      g est croissante sur . D'où, puisque . On en déduit que . De plus,
      Donc, Par récurrence, on obtient :
      Donc la suite (xn) est décroissante et minorée par alpha, ce qui montre qu'elle est convergente. Comme et comme g est continue, (xn) converge vers l'unique point fixe alpha de g. On remarque de plus que
    2. Si un raisonnement semblable au précédent implique que (xn) est croissante majorée par alpha. Donc (xn) est convergente. Comme et que g est continue, on obtient que (xn) converge vers alpha l'unique point fixe de g.
  2. Second cas : (donc f(x0) < 0). Alors le raisonnement précédent, avec f remplacée par -f, implique que la suite (xn) converge vers alpha.

IV-5 Test d'arrêt

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton → IV-5 Test d'arrêt

Une fois construite la suite (xn) convergeant vers le réel alpha vérifiant et une fois fixée la tolérance nous cherchons le premier entier n0 vérifiant :
Si on note l'erreur à l'itération n, on a :
avec cn un réel entre xn et alpha donné par le théorème des accroissements finis. Par conséquent,
Or si n est suffisament grand,
et donc
L'erreur qu'on commet lorsque l'on adopte ce critère est donc plus petite que la tolérance varepsilon fixée.

V Méthode de Lagrange

Résolution numérique de l'équation f ( x ) = 0 → V Méthode de Lagrange

V-1 Principe

V-2 Interprétation géométrique

V-3 Convergence

V-1 Principe

Résolution numérique de l'équation f ( x ) = 0 → V Méthode de Lagrange → V-1 Principe
La méthode de Lagrange est une variante de la méthode de Newton.
Soit ayant une convexité déterminée. Rappelons que pour calculer un zéro alpha de f par la méthode de Newton, on considère la suite (xn) définie par :
Dans certaines situations, la dérivée de f est très compliquée voir même impossible à calculer. Dans ce cas, nous approchons la dérivée par un taux d'accroissement. Ce que nous obtenons est appelée la méthode de Lagrange ou méthode de la sécante :
Ici, dépend de xn et de : on dit que c'est une méthode à deux pas ; nous avons d'ailleurs besoin de deux itérés initiaux x0 et x1.
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 la convergence n'est plus quadratique.
La fonction g correspondante vérifie :

V-2 Interprétation géométrique

Résolution numérique de l'équation f ( x ) = 0 → V Méthode de Lagrange → V-2 Interprétation géométrique

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');

V-3 Convergence

Résolution numérique de l'équation f ( x ) = 0 → V Méthode de Lagrange → V-3 Convergence

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 soient strictement positives sur . On suppose que
et on appelle alpha l'unique solution de l'équation f(x) = 0. Alors
  1. La suite (xn) telle que :
    est bien définie.
  2. La suite (xn) est croissante et converge vers alpha.
  3. La méthode de Lagrange est d'ordre au moins 1 :

Démonstration

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 alpha dans l'intervalle . Comme f(a) < 0 et f(b) > 0, le réel x1 est l'abscisse de l'intersection de la droite passant par (a, f(a)) et (b, f(b)) et vérifie f(x1) < 0 ; de même, f(x2) < 0 et par récurrence on a
On vérifie que la suite (xn) 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 alpha).

Exercice
Méthode de Lagrange

VI Bibliographie

Résolution numérique de l'équation f ( x ) = 0 → VI Bibliographie
  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.

VII Exercices

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

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 alpha de la fonction f(x) = x3-2 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
On considère l'équation non linéaire
sur l'intervalle .
  1. Montrer que la fonction f admet un zéro alpha dans et qu'il est unique.
  2. Ecrire la méthode de Newton pour résoudre l'équation f(x) = 0. Quel est l'ordre de convergence de cette méthode ? Justifier la réponse.
  3. Proposer une méthode d'ordre 2 pour la résolution de l'équation donnée.

Exercice
Soit alpha 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 alpha 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 alpha.

Exercice
On considère la fonction
sur l'intervalle .
  1. Montrer qu'il existe un zéro alpha pour la fonction f dans et qu'il est unique.
  2. On veut calculer le zéro alpha de la fonction f par une méthode de point fixe convenable. En particulier on se donne deux méthodes de point fixe où les fonctions et sont définies comme :
    Laquelle de ces deux méthodes utiliseriez-vous pour calculer numériquement le zéro alpha de la fonction f ? Justifiez votre réponse.
  3. En utilisant la méthode de la bissection sur l'intervalle estimer le nombre d'itérations nécessaires pour calculer le zéro alpha de la fonction f avec une tolérance .


document sur les méthodes de résolution d'équations numériques f(x) = 0.
: equations, roots, méthode de dichotomie, méthode de Lagrange, méthode de Newton, point fixe, interactive mathematics, interactive math, server side interactivity

The most recent version
Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.