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

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
f(α)=0,
ou, ce qui est équivalent, à résoudre une équation de type
g(x)=x.

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

Résolution numérique de l'équation f ( x ) = 0I 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 :
[p+a(NV) 2](VNb)=kNT
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 :
f(V)=[p+a(NV) 2](VNb)kNT.

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 (x n) n convergeant vers un réel alpha vérifiant f(α)=0.
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


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 f(x)=sin(2x)1+x=0, la fonction g peut être
g(x)=1sin(2x),x
ou
g(x)=12arcsin(1x),0x1.

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 α[0,1] et que les graphes des fonctions
y=x,y=1sin(2x), et y=1/2(arcsin(1x))
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

Définition

Un réel l[a,b] est dit point fixe d'une fonction g:[a,b] si
g(l)=l

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

Résolution numérique de l'équation f ( x ) = 0I IntroductionI-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
    f(α)=f (1)(α)=...=f (p1)(α)=0 et f (p)(α)0.
  2. Un zéro de multiplicité 1 (respectivement 2) est appelé un zéro simple (respectivement double ).

Définition

Soit k]0,1[. Une fonction g:[a,b] est dite fonction contractante de rapport k si
x,y[a,b],g(x)g(y)kxy

Remarque

  1. Soit g𝒞 1([a,b]). Si
    g(x)<1,x[a,b],
    alors g est contractante sur [a,b].
  2. Une fonction contractante est continue.

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


Théorème

Soit g:[a,b][a,b] une fonction contractante de rapport k. Alors g admet un unique point fixe l[a,b]. De plus, pour tout choix de x 0[a,b], la suite définie par x n+1=g(x n),n0 converge vers l quand n+.

Démonstration
Etape 1: Existence de l et convergence de la suite Remarquons d'abord que g([a,b])[a,b] ce qui implique que la suite (x n) est bien définie. Soit x 0 dans [a,b] et x n+1=g(x n),n0. Nous allons montrer:
  1. (x n) est de Cauchy (donc convergente, car [a,b] est complet)
  2. x nl quand n+,l est un point fixe de g.

Par hypothèse, on sait que
n1,x nx n+1=g(x n1)g(x n)kx n1x n.
Par récurrence sur n, on obtient:
x nx n+1k nx 0x 1,n0.
Soit n0 et p1, on a donc:
x n+px n x n+px n+p1++x n+1x n q=1 px n+qx n+q1 (*) q=1 pk n+q1x 1x 0 x 1x 0k n(1+k++k p1) x 1x 0k n1k0 quand n+ car k<1
La suite (x n) est donc de Cauchy dans [a,b] qui est complet et par conséquent (x n) converge vers une limite l quand n+. Comme la fonction g est contractante, elle est continue, et donc g(x n)g(l) quand n+. En passant à la limite dans l'égalité: x n+1=g(x n), on en déduit que l=g(l), c'est à dire que l est un point fixe de g.
Etape 2: Unicité
Soient l 1 et l 2 deux points fixes de g, donc l 1=g(l 1) et l 2=g(l 2), alors g(l 1)g(l 2)=l 1l 2kl 1l 2; comme k<1, ceci est impossible sauf si l 1=l 2.

Remarque

Si g est une application vérifiant
{g([a,b])[a,b] g(x)<1,x[a,b]
alors la suite définie par x n+1=g(x n),n0 converge vers l'unique point fixe l de g sur [a,b] pour tout choix de x 0[a,b]. De plus en faisant tendre p vers l'infini dans (*) et en gardant n, on obtient:
x nlx 1x 0k n1k,n avec k=max x[a,b]g(x)

I-3-4 Fonctions convexes

Définition [fonction convexe]

Soit I un intervalle de . Une fonction f:I est dite convexe sur I si
λ[0,1],x,yI,f(λx+(1λ)y)λf(x)+(1λ)f(y)
Si l'inégalité est stricte, f est dite strictement convexe .

Proposition

Si I=[a,b],α]a,b[ et f:I convexe, alors la fonction
Φ α:xΦ α(x)=f(x)f(α)xα
est croissante sur I{α}.

Proposition

Si f:I est deux fois dérivable, alors:
f (2)0fconvexe
f (2)>0f strictement convexe

Définition

On dit que f:I 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 ) = 0I IntroductionI-3 Rappels d'analyse → I-3-5 Vitesse de convergence d'une suite

Définition

Soit (x n) n une suite convergente vers alpha. On appelle ordre de convergence de la suite (x n) le réel fini ou infini r>0 défini par:
r=sup{s +tel quelim n+x n+1αx nα s<}
  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:
    lim n+x n+1αx nα=k1
    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
Soit a + *. Soit la suite récurrente (x n) n définie par
{x 0 = 3 x n+1 = g(x n)
avec
g(x)=12(x+ax).
La suite (x n) converge vers a et son ordre de convergence est égal à 2. En effet:
x n+1a(x na) 2=x n 2+a2ax n2(x na) 2x n12a quand n+
et
x n+1a(x na) 3+ quand n+

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 ) = 0I Introduction → I-4 Critère d'arrêt pour la résolution numérique de f(x) = 0

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 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 n 0 si on peut montrer théoriquement que:
    nn 0,x n+1x n<ε

Exemple
Soit f(x)=x 34x+1. On vérifie que f admet 3 racines réelles l 1[2.5,2] l 2[0,0.5] et l 3[1.5,2] en posant
g(x)=xx 34x+13x 24=2x 313x 24
Un simple calcul donne les valeurs suivantes:

x 0 
 -2  0  2

x 1 
 -2.125  0.25  1.875

x 2 
 -2.114975450  0.254098301  1.860978520

x 3 
 -2.114907545  0.254101688  1.860805877

x 4 
 -2.114907541  0.254101688   1.860805853

x 5 
 -2.114907541  0.254101688   1.860805853

x 6 
       

x 7 
       

x 8 
       

On constate que les valeurs numériques se stabilisent et on a alors les valeurs approchées de l 1, l 2 et l 3 à environ 10 9 près.

II Méthode de dichotomie

II-1 Principe

Considérons une fonction f continue sur un intervalle [a,b]. On suppose que f admet une et une seule racine alpha dans ]a,b[ et que f(a)f(b)<0. On note
c=a+b2
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 f(c)0, nous regardons le signe de f(a)f(c).
    1. Si f(a)f(c)<0, alors α]a,c[
    2. Si f(c)f(b)<0, alors α]c,b[

On recommence le processus en prenant l'intervalle [a,c] au lieu de [a,b] dans le premier cas, et l'intervalle [c,b] au lieu de [a,b] dans le second cas. De cette manière, on construit par récurrence sur n trois suites (a n), (b n) et (c n) telles que a 0=a,b 0=b et telles que pour tout n0,
  1. c n=a n+b n2
  2. Si f(c n)f(b n)<0 alors a n+1=c n et b n+1=b n.
  3. Si f(c n)f(a n)<0 alors a n+1=a n et b n+1=c n.
L'algorithme ci-dessus s'appelle l'algorithme de dichotomie .

II-2 Etude de la convergence

Théorème

Soit f une fonction continue sur [a,b], vérifiant f(a)f(b)<0 et soit α[a,b] l'unique solution de l'équation f(x)=0. Si l'algorithme de dichotomie arrive jusqu'à l'étape n alors on a l'estimation:
αc nba2 n+1.
Par conséquent, la suite (c n) converge vers alpha. C'est aussi vrai si (c n)=α.

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

II-3 Test d'arrêt


Pour que la valeur de c n de la suite à la n-ième itération soit une valeur approchée de alpha à ε>0 près, il suffit que n vérifie:
ba2 n+1ε
On a alors:
αc nba2 n+1ε
ce qui permet de calculer à l'avance le nombre maximal n 0 d'itérations assurant la précision varepsilon.
ba2 n+1εbaε2 n+1nlogbaεlog(2)1

Exemple
On considère la fonction f(x)=exp(x)+3x2 sur l'intervalle [0,1]. 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 α[0,1]. Si on veut utiliser la méthode de dichotomie pour estimer alpha à une tolérance ε=10 10 près, il nous faut au plus 33 itérations. En effet, la suite (x n) qui approche alpha vérifie
x nα12 n+1
et
12 n+110 10n10log(10)log(2)133.

Vérification numérique. Le code Matlab suivant permet de calculer la valeur de n nécessaire pour atteindre la précision ε=10 10 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
α=0.0910
f(α)=8.9593e12
n numerique=33
n theorique=10log(10)/log(2)1=32.2193

Exemple
Si nous reprenons l'exemple précédent avec la fonction f(x)=10x5, nous obtenons les résultats suivants:
α=0.5000
f(α)=0
n numerique=0
n theorique=10log(10)/log(2)1=32.2193
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

III-1 Principe


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 g(x)<1 sur ce voisinage. Dans ce cas, on construit une suite (x n) n définie par:
{x 0 dans un voisinage I de α n0,x n+1=g(x n)

Il ne reste plus qu'à appliquer localement le théorème de point fixe pour démontrer que
α=lim n+x n.

C'est l'objet du paragraphe suivant:
Exercice
Méthode de point fixe

III-2 Point attractif

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

Théorème

Soit g:I=[a,b][a,b] de classe 𝒞 1. On suppose que g admet un point fixe α[a,b] vérifiant g(α)<1. Alors il existe un voisinage V α de alpha dans I tel que la suite (x n) définie par :
{x 0V α x n+1= g(x n),n0

converge vers alpha.

Démonstration
Comme g(α)<1, il existe k0 tel que g(α)k<1. De plus, g est continue sur I donc il existe un voisinage V α=[αh,α+h]I(h>0) tel que
xV α,g(x)k<1.
Donc g est k-contractante sur V α. En particulier, g(x)V α. Le théorème de point fixe appliqué localement à g dans le voisinage V α implique que
x 0V α,lim n+x n=α

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 V α correspondant est dit intervalle de convergence de la méthode d'approximation.

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

Proposition

En pratique, un intervalle de convergence V α peut être calculé comme suit:
  1. Si 0g(α)<1, prendre comme intervalle de convergence
    V α=[β,γ]
    contenant alpha tel que
    0g(x)<1,x[β,γ].
  2. Si 1<g(α)<0, prendre comme intervalle de convergence
    V α=[β,g(β)]
    tel que
    1<g(x)<0,x[β,g(β)].

Démonstration
  1. Cas où 0g(α)<1. D'après la continuité de g, il existe [β,γ] contenant alpha tel que
    0g(x)<1,x[β,γ].
    On a alors
    g([β,γ])[β,γ].
    En effet, comme g est croissante sur [β,γ], on a:
    g([β,γ])=[g(β),g(γ)].
    D'autre part, on a
    αg(β)=g(α)g(β)=(αβ)g(ξ),ξ]β,γ[.
    Comme g(ξ)[0,1[,
    0αg(β)(αβ)
    ce qui donne g(β)β. Donc αβ0. De plus,
    g(γ)α=g(γ)g(α)=(γα)g(ν),ν]α,γ[.
    Comme g(ν)[0,1[,
    0g(γ)α(γα),
    ce qui donne g(γ)γ.
    D'où g([β,γ])[β,γ]. De plus:
    • si x 0<α, alors (x n) est croissante convergeant vers alpha ;
    • si x 0>α, alors (x n) est décroissante convergeant vers alpha

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

    On conclut donc que
    n,x n[β,γ].

    Remarquons finalement que alpha est toujours entre deux termes successifs de la suite (x n). On dit que (x n) encadre alpha. Par conséquent si x nx n1ε, x nαε.

III-3 Point répulsif

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

Théorème

Soit g:I=[a,b][a,b] de classe 𝒞 1. On suppose que g admet un point fixe α[a,b] vérifiant g(α)>1. Alors il existe un voisinage V α de alpha dans I tel que la suite (x n) définie par:
{x 0V α{α} x n+1=g(x n); n0

ne converge pas vers alpha.

Démonstration
Comme lim xαg(x)g(α)xα=g(α)>1, il existe un voisinage V α=[αh,α+h]I, avec h>0 tel que xV α{α},g(x)α>xα. Donc (x n) 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


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

Remarque

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

Exercice
Différents types de points fixes

III-4 Point douteux

III-4-1 Définition


Définition

Soit g:I=[a,b][a,b] de classe 𝒞 1 pour laquelle alpha est un unique point fixe vérifiant g(α)=1. 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


Exemple
Soit la fonction g définie par g(x)=sinx,x[0,π2]. On a x]0,π2],sinx<x et pour tout x 0]0,π2], la suite itérée (x n) définie par x n+1=g(x n) est strictement décroissante minorée par 0 donc convergeant vers une limite alpha. Comme g est continue et que α=g(α),α=0 est l'unique point fixe de g sur [0,π2].

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


Exemple
Soit la fonction g(x)=sinhx,x[0,+]. On a sinhx>x et pour tout x 0]0,+[, la suite itérée (x n) définie par x n+1=g(x n) est strictement croissante et non majorée donc divergente. Par conséquent, le point fixe α=0 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

Soit alpha un point fixe de g.

Remarque

Si g(α)=0, on sait que alpha est un point attractif. Si de plus g est de classe 𝒞 2 sur I et s'il existe M>0 tel que g (2)(x)M, pour tout x dans un voisinage V α de alpha alors d'après la formule de Taylor :
g(x) = g(α)+(xα)g(α)+(xα) 22g (2)(c) avec c]α,x[ = α+12g (2)(c)(xα) 2
d'où g(x)α12Mxα 2 avec M=sup xIg (2)(x). 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 g:I=[a,b][a,b] de classe 𝒞 m, avec m. On suppose que g admet un unique point fixe α[a,b] vérifiant g(α)<1. Il existe alors un voisinage V α de alpha dans I tel que la suite itérée (x n) définie par:
{x 0V α x n+1=g(x n) n0
converge vers alpha. De plus, si
g(α)==g (m1)(α)=0 et g (m)(α)0
alors l'ordre de convergence de (x n) est égal à m.

Démonstration
L'existence de V α 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 c n dans l'intervalle (x n,α) tel que :
x n+1=g(α)+g(α)(x nα)++g (m1)(α)(m1)!(x nα) m1+g (m)(c n)m!(x nα) m
Si on suppose de plus que g(α)==g (m1)(α)=0 et g (m)(α)0, alors
x n+1=α+g (m)(c n)m!(x nα) m.
Donc,
  • le rapport x n+1αx nα m=g (m)(c n)m! tend vers g (m)(α)m! qui est fini et non nul,
  • pour tout ε>0, le rapport x n+1αx nα m+ε=g (m)(c n)m!x nα ε tend vers +.

III-6 Test d'arrêt


Comme nous l'avons expliqué dans l'introduction, la suite (x n) converge vers un réel alpha vérifiant g(α)=α. En fixant la tolérance varepsilon on estime qu'on atteint la précision varepsilon dès qu'il existe n 0 tel que:
x n 0+1x n 0<ε

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

Proposition

Soit g:[a,b][a,b] de classe 𝒞 1. On suppose que g admet un unique point fixe α[a,b] vérifiant 1<g(x)<0 pour tout x dans un intervalle de convergence V α de alpha. Soit la suite (x n) définie par:
{x 0V α x n+1=g(x n); n0

Alors:
n,x n+1αx n+1x n

Par conséquent, soit n 0 tel que x n 0α<ε, alors x n 0 approche alpha à varepsilon près.

Démonstration
On applique le théorème des accroissements finis à g entre x n et alpha. Il existe alors c n entre x n et alpha telle que:
g(x n)g(α)=g(c n)(x nα)
ce qui donne:
x n+1α=g(c n)(x nα)
Comme g(c n)<0,(x n+1α) et (x nα) sont de signes contraires.
Finalement,
x n+1αx n+1x n

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 (x n) qui converge vers alpha d'une manière quadratique. Rappelons que d'après le théorème , si g est une application de [a,b] dans [a,b], on a les résultats suivants:
  1. Si g𝒞 1([a,b]),g(α)0,g(α)<1, et si n,x nα alors
    lim n+x n+1αx nα=g(α)]0,1[
    et la convergence est linéaire.
  2. Si g𝒞 2([a,b]),g(α)=0 et n,x nα, alors
    lim n+x n+1αx nα 2=12g (2)(α)
    et la convergence est au moins quadratique.

Poursuivons maintenant notre construction de la méthode de Newton. Considérons f𝒞 3([a,b]) et α[a,b] tel que f(α)=0. Posons
g(x)=x+h(x)f(x),
avec h𝒞 2([a,b]) tel que h(x)0,x[a,b]. Nous avons donc
g(x)=xf(x)=0.
Si on choisit h pour que g(α)=0, la méthode de point fixe appliquée g donne pour x 0V α une suite (x n) convergeant vers alpha d'une manière au moins quadratique (d'ordre supérieur ou égal à 2). Or
g(x)=1+h (x)f(x)+f(x)h(x)
et donc
g(α)=1+h(α)f(α).
Il suffit donc de choisir h telle que
h(α)=1f(α).
Ceci n'est possible que si
f(α)0.

En résumé, si f𝒞 3([a,b]) est telle que f(α)0 et f(α)=0, on prend h=1f pour x assez proche de α, et la fonction g𝒞 2([a,b]) définie par :
g(x)=xf(x)f(x)
vérifie g(α)=0. Grâce au théorème , il existe un voisinage V α de alpha dans [a,b] tel que la suite (x n) définie par
{x 0V α x n+1=g(x n)=x nf(x n)f(x n), n0
est convergente vers alpha de manière au moins quadratique.

Remarque

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

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 f:[a,b] une fonction de classe 𝒞 2 admettant un unique zéro α]a,b[ de multiplicité 1.
  1. Montrer qu'il existe η>0 tel que V α=[αη,α+η]]a,b[ vérifie xV α,f(x)0 et que la suite (x n) définie par : {x 0V α x n+1=x nf(x n)f(x n) n converge vers alpha.
  2. On pose e n=x nα. Montrer que lim n+e n+1e n 2=12f (2)(α)f(α). En déduire que n,e n+1e n 2M 22m 1, avec {m 1 = inf xV αf(x) M 2 = sup xV αf (2)(x)

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
f(α)=0 et f(α)0.
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é m2 ? 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
f(x)=(xα) mh(x) avec h(α)0.
Donc
g(x)=x(xα) mh(x)m(xα) m1h(x)+(xα) mh(x)=x(xα)h(x)mh(x)+(xα)h(x)

et lim xαg(x)g(α)xα=11m0, ce qui implique en terme de suite que x n+1αx nα tend vers 11m]0,+[. 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

On suppose ici que alpha est une racine de f de multiplicité m2, c'est-à-dire :
f(x)=(xα) mh(x) avec h(α)0.
On suppose que f𝒞 2([a,b]) et par conséquent h aussi. On définit alors la fonction g par :
g(x)=xmf(x)f(x).
Dans ce cas,
lim xαg(x)g(α)xα=0,
ce qui implique :
lim n+x n+1αx nα=0 et lim n+x n+1αx nα 2<+.

Exercice
Montrer que lim n+x n+1αx nα 2=h (α)mh(α).

IV-4 Théorème de convergence globale

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

Nous allons énoncer un résultat de convergence globale ( x 0 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 f:[a,b] de classe 𝒞 2 vérifiant :
  1. f(a)f(b)<0
  2. f(x)0,x[a,b]
  3. f (2)(x)0,x[a,b]

La suite (x n) définie par :
{x 0[a,b] tel que f(x 0)f (2)(x 0)>0 x n+1=x nf(x n)f(x n)
est convergente vers alpha.

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

IV-5 Test d'arrêt


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

V Méthode de Lagrange

V-1 Principe

La méthode de Lagrange est une variante de la méthode de Newton.
Soit f𝒞 1([a,b],) 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 (x n) définie par :
{x 0 proche de α f(x n)(x n+1x n)=f(x n),n0
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 :
{x 0,x 1 proche de α f(x n)f(x n1)x nx n1(x n+1x n)=f(x n), n1
Ici, x n+1 dépend de x n et de x n1: on dit que c'est une méthode à deux pas ; nous avons d'ailleurs besoin de deux itérés initiaux x 0 et x 1.
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 :
x n+1=g(x n)=x nf(x n)x nx n1f(x n)f(x n1).

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


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

Théorème

Soit f:[a,b] de classe 𝒞 2 telle que f et f (2) soient strictement positives sur [a,b]. On suppose que
f(a)<0,f(b)>0
et on appelle alpha l'unique solution de l'équation f(x)=0. Alors
  1. La suite (x n) telle que :
    {x 0=a x n+1=x nf(b)bf(x n)f(b)f(x n), n0
    est bien définie.
  2. La suite (x n) est croissante et converge vers alpha.
  3. La méthode de Lagrange est d'ordre au moins 1 :
    lim n+x n+1αx nα=1+(αa)f(α)f(a)

Démonstration

On pose x n+1=g(x n)
g(x)=xf(b)bf(x)f(b)f(x).
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 [a,b]. Comme f(a)<0 et f(b)>0, le réel x 1 est l'abscisse de l'intersection de la droite passant par (a,f(a)) et (b,f(b)) et vérifie f(x 1)<0 ; de même, f(x 2)<0 et par récurrence on a
f(x n)<0,n.
On vérifie que la suite (x n) est croissante majorée par b, donc convergente. Comme x n+1=g(x n) et que g est continue, la limite est l'unique point fixe de g. De plus,
x n+1αx nα=g(x n)g(α)x nαg(α)=1+(αb)f(α)f(a)
(la dernière égalité est obtenue en dérivant g au point alpha).

Exercice
Méthode de Lagrange

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


Exercice
On veut calculer les zéros de l'équation
f(x)=x2sin(x)+π632=0
dans l'intervalle [π2,π]. 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 ε=10 10, 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 x k+1=ϕ(x k), avec
    ϕ(x k)=sin(x k)+x k2(π632)
    pour calculer le zéro α>0. En observant que α[2π3,π], établir si cette méthode de point fixe est convergente.
  4. En considérant encore le zéro α[2π3,π] et la méthode de point fixe introduite à la question précédente, montrer qu'il existe une constante positive C>0 telle que
    x k+1αCx kα
    et estimer cette constante.

Exercice
On veut calculer le zéro alpha de la fonction f(x)=x 32 en utilisant la méthode de point fixe x k+1=ϕ(x k) suivante :
x k+1=x k(1w3)+(x k) 3(1w)+2w3(x k) 2+2(w1),k0,
w é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
f(x)=e xx 22x1=0
sur l'intervalle [1,1].
  1. Montrer que la fonction f admet un zéro alpha dans [1,1] 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 :
f(α)=f(α)=0 et f (2)(α)0.
  1. En tenant compte du fait qu'on peut écrire la fonction f comme
    f(x)=(xα) 2h(x)h(α)0,
    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 :
    x k+1=x k2f(x k)f(x k).
    Vérifier que cette méthode est d'ordre deux si l'on veut approcher alpha.

Exercice
On considère la fonction
f(x)=e x+3x2
sur l'intervalle [0,1].
  1. Montrer qu'il existe un zéro alpha pour la fonction f dans [0,1] 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 x=ϕ i(x),i=1,2, où les fonctions ϕ 1 et ϕ 2 sont définies comme :
    ϕ 1(x)=ln(23x) et ϕ 2(x)=(2e x) 29
    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 [0,1], estimer le nombre d'itérations nécessaires pour calculer le zéro alpha de la fonction f avec une tolérance ε=10 10.


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, wims, mathematics, mathematical, math, maths, interactive mathematics, interactive math, interactive maths, mathematic, online, calculator, graphing, exercise, exercice, puzzle, calculus, K-12, algebra, mathématique, interactive, interactive mathematics, interactive mathematical, interactive math, interactive maths, mathematical education, enseignement mathématique, mathematics teaching, teaching mathematics, algebra, geometry, calculus, function, curve, surface, graphing, virtual class, virtual classes, virtual classroom, virtual classrooms, interactive documents, interactive document


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.