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

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

I Introduction picto

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

Ce document destiné à des étudiants de licence 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

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

I-1 Préambule

Résolution numérique de l'équation f ( x ) = 0  ---> I Introduction  ---> I-1 Préambule

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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
g(x) = x

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

I-3 Rappels d'analyse picto

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

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

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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 :
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 , 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.

Résolution numérique de l'équation f ( x ) = 0  ---> I Introduction  ---> I-2 Exemple motivant: équation d'état d'un gaz
I-1 Préambule

I-3 Rappels d'analyse picto

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

I-3 Rappels d'analyse

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

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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-1 Préambule

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

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

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

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

Définition

Un réel est dit point fixe d'une fonction si
g(l) = l

I-3-2 Multiplicité d'une racine

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

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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.

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
I-3-1 Point fixe

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

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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 .

Preuve

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-1 Point fixe

I-3-2 Multiplicité d'une racine

I-3-4 Fonctions convexes

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

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

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

Définition [fonction convexe]

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-1 Point fixe

I-3-2 Multiplicité d'une racine

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

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

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

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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écurente définie par
avec
La suite (xn) converge vers et son ordre de convergence est égal à 2. En effet:

et

I-3-1 Point fixe

I-3-2 Multiplicité d'une racine

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

I-3-4 Fonctions convexes

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

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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 nuériques se stabilisent et on a alors les valeurs approchées de l1, l2 et l3 à environ près.

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
I-1 Préambule

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

I-3 Rappels d'analyse picto

II Méthode de dichotomie

Résolution numérique de l'équation f ( x ) = 0  ---> II Méthode de dichotomie
I Introduction picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

II-1 Principe

Résolution numérique de l'équation f ( x ) = 0  ---> II Méthode de dichotomie  ---> II-1 Principe
I Introduction picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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écurence sur n trois suites (an), (bn) et (cn) telles que et telles que pour tout ,

  1. Si f(cn) f(bn)<0 alors et .
  2. Si f(cn) f(an)<0 alors et .
L'algorithme ci-dessus s'appelle l'algorithme de dichotomie .

II-2 Etude de la convergence

II-3 Test d'arrêt

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
I Introduction picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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 .

Preuve

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

II-1 Principe

II-3 Test d'arrêt

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
I Introduction picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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_{théorique} = 10*log(10)/log(2) - 1

Résultats

Exemple

Si nous reprenons l'exemple précedent 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
II-1 Principe

II-2 Etude de la convergence

III Méthode de point fixe

Résolution numérique de l'équation f ( x ) = 0  ---> III Méthode de point fixe
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

III-1 Principe

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

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

Le principe de cette méthode consiste à transformer l'équation f(x) = 0 en une équation équivalente g(x) = xg 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 picto

III-3 Point répulsif picto

III-4 Point douteux picto

III-5 Ordre de convergence

III-6 Test d'arrêt

III-2 Point attractif

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

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

III-1 Principe

III-3 Point répulsif picto

III-4 Point douteux picto

III-5 Ordre de convergence

III-6 Test d'arrêt

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

Théorème

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

converge vers alpha.

Preuve

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

III-2-3 Intervalle de convergence

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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-1 Théorème de convergence

III-2-3 Intervalle de convergence

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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

Preuve

  1. Cas de . 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 de . 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 l. Par conséquent si .

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

III-2-2 Illustration graphique

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

III-1 Principe

III-2 Point attractif picto

III-4 Point douteux picto

III-5 Ordre de convergence

III-6 Test d'arrêt

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

Théorème

Soit de classe . On suppose que g admet un unique 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.

Preuve

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

III-3-3 Remarque sur la convergence

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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-1 Théorème de non-convergence

III-3-3 Remarque sur la convergence

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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:

Exercice

Différents types de points fixes

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

III-3-2 Illustration graphique

III-4 Point douteux

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

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

III-1 Principe

III-2 Point attractif picto

III-3 Point répulsif picto

III-5 Ordre de convergence

III-6 Test d'arrêt

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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

III-4-3 Exemple2

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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-1 Définition

III-4-3 Exemple2

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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-4-1 Définition

III-4-2 Exemple1

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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

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

Preuve

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
En raison des hypothèses faites sur g, on obtient:
Enfin,
et
III-1 Principe

III-2 Point attractif picto

III-3 Point répulsif picto

III-4 Point douteux picto

III-6 Test d'arrêt

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
I Introduction picto

II Méthode de dichotomie picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

Comme nous 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.

Preuve

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,

III-1 Principe

III-2 Point attractif picto

III-3 Point répulsif picto

III-4 Point douteux picto

III-5 Ordre de convergence

IV Méthode de Newton

Résolution numérique de l'équation f ( x ) = 0  ---> IV Méthode de Newton
I Introduction picto

II Méthode de dichotomie picto

III Méthode de point fixe picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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
I Introduction picto

II Méthode de dichotomie picto

III Méthode de point fixe picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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 . Posons

g(x) = x + h(x) f(x),
avec tel que
Nous avons donc:
Nous allons choisir que avec ceci, 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:
y = f'(xn)(x - xn) + f(xn)
D'après l'équation , est le point où la droite d intersecte l'axe Ox.

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-2 Illustration graphique

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

II Méthode de dichotomie picto

III Méthode de point fixe picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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 vérifiant et la suite (xn) définie par: est convergente vers alpha.
  2. Si 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 sommes en train de chercher le zéro alpha vérifiant

autrement dit, 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é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 .
IV-1 Principe et convergence

IV-3 Méthode de Newton modifiée

IV-4 Théorème de convergence globale

IV-5 Test d'arrêt

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
I Introduction picto

II Méthode de dichotomie picto

III Méthode de point fixe picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

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 on a:
ce qui implique:

Exercice

Montrer que .

IV-1 Principe et convergence

IV-2 Illustration graphique

IV-4 Théorème de convergence globale

IV-5 Test d'arrêt

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
I Introduction picto

II Méthode de dichotomie picto

III Méthode de point fixe picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

Nous allons annoncer un résultat de convergence globale ( x0 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 :
  1. f(a) f(b)<0

alors la suite (xn) définie par:

est convergente vers alpha.

Preuve

Les hypothèses
implique qu'il existe un unique tel que . Comme f'' est de signe constant, on distingue deux cas:
  1. Si (donc f(x0)>0), alors,
    1. Si on a:
      Comme f(x0)>0, alors . Par conséquent,
      Donc g est croissante sur . D'où,
      De plus,
      Par récurrence, on obtient:
      Donc
      c'est-à-dire (xn) est décroissante minorée par alpha. Donc (xn) est convergente. Comme et que g est continue, (xn) converge vers l'unique point fixe alpha de g.
    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. Si (donc f(x0) < 0). Alors le raisonnement précédent, avec f remplacée par (-f), implique que la suite (xn) est convergente vers alpha.

IV-1 Principe et convergence

IV-2 Illustration graphique

IV-3 Méthode de Newton modifiée

IV-5 Test d'arrêt

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
I Introduction picto

II Méthode de dichotomie picto

III Méthode de point fixe picto

V Méthode de Lagrange picto

VI Bibliographie

VII Exercices

Index

Une fois construite la suite (xn) convergeant vers 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 et 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.
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

V Méthode de Lagrange

Résolution numérique de l'équation f ( x ) = 0  ---> V Méthode de Lagrange
I Introduction picto

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

VI Bibliographie

VII Exercices

Index

V-1 Principe

Résolution numérique de l'équation f ( x ) = 0  ---> V Méthode de Lagrange  ---> V-1 Principe
I Introduction picto

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

VI Bibliographie

VII Exercices

Index

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 quotient différentiel. Ce que nous obtenons est appelée la méthode de Lagrange :
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 nous perdons la convergence quadratique.

La fonction g correspondante vérifie:

V-2 Interprétation géométrique

V-3 Convergence

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
I Introduction picto

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

VI Bibliographie

VII Exercices

Index

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-1 Principe

V-3 Convergence

V-3 Convergence

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

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

VI Bibliographie

VII Exercices

Index

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 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, convergeant vers alpha.
  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 alpha dans l'intervalle . Comme f(a) < 0 et f(b) > 0, le réel x1 est l'absisse 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

V-1 Principe

V-2 Interprétation géométrique

VI Bibliographie

Résolution numérique de l'équation f ( x ) = 0  ---> VI Bibliographie
I Introduction picto

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VII Exercices

Index

  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
I Introduction picto

II Méthode de dichotomie picto

III Méthode de point fixe picto

IV Méthode de Newton picto

V Méthode de Lagrange picto

VI Bibliographie

Index

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(x) admet un zéro x 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.

: équation, lagrange,newton,zéros, 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 de web.

Pour accéder aux services de WIMS, vous avez besoin d'un navigateur qui connait les formes. 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 inutiles pour vous de les ramassez par un programme robot.

Description: document sur les méthodes de résolution d'équations numériques f(x) = 0. interactive exercises, online calculators and plotters, mathematical recreation and games

Keywords: interactive mathematics, interactive math, server side interactivity, analysis, équation, lagrange,newton,zéros, point fixe