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
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 ) = 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 :
[p+a(NV) 2](V−Nb)=kNT
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 :
f(V)=[p+a(NV) 2](V−Nb)−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

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

Les instructions Matlab suivantes permettent de tracer les représentations graphiques de ces fonctions, y compris celle de la droite y=x: {code} 
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');
{code}

On voit bien que f admet un unique zéro α∈[0,1] et que les graphes des fonctions
y=x,y=1−sin(2x), et y=1/2(arcsin(1−x))
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 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 ) = 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
    f(α)=f (1)(α)=...=f (p−1)(α)=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)∣≤k∣x−y∣

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

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 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),∀n≥0 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),∀n≥0. Nous allons montrer:
  1. (x n) est de Cauchy (donc convergente, car [a,b] est complet)
  2. x n⟶l quand n⟶+∞, où l est un point fixe de g.

Par hypothèse, on sait que
∀n≥1,∣x n−x n+1∣=∣g(x n−1)−g(x n)∣≤k∣x n−1−x n∣.
Par récurrence sur n, on obtient:
∣x n−x n+1∣≤k n∣x 0−x 1∣,∀n≥0.
Soit n≥0 et p≥1, on a donc:
∣x n+p−x n∣ ≤ ∣x n+p−x n+p−1∣+⋯+∣x n+1−x n∣ ≤ ∑ q=1 p∣x n+q−x n+q−1∣ (*) ≤ ∑ q=1 pk n+q−1∣x 1−x 0∣ ≤ ∣x 1−x 0∣k n(1+k+⋯+k p−1) ≤ ∣x 1−x 0∣k n1−k⟶0 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 1−l 2∣≤k∣l 1−l 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),∀n≥0 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 n−l∣≤∣x 1−x 0∣k n1−k,∀n∈ℕ avec k=max x∈[a,b]∣g′(x)∣

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 f:I⟶ℝ est dite convexe sur I si
∀λ∈[0,1],∀x,y∈I,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)≥0⟹fconvexe
f (2)>0⟹f 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 ) = 0 → I Introduction → I-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−α∣=k≤1
    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+1−a(x n−a) 2=x n 2+a−2ax n2(x n−a) 2x n⟶12a quand n⟶+∞
et
x n+1−a(x n−a) 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 ) = 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 (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:
    ∀n≥n 0,∣x n+1−x n∣<ε

Exemple
Soit f(x)=x 3−4x+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)=x−x 3−4x+13x 2−4=2x 3−13x 2−4
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

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 [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 n≥0,
  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

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 [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 n∣≤b−a2 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

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 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:
b−a2 n+1≤ε
On a alors:
∣α−c n∣≤b−a2 n+1≤ε
ce qui permet de calculer à l'avance le nombre maximal n 0∈ℕ d'itérations assurant la précision varepsilon.
b−a2 n+1≤ε⟺b−aε≤2 n+1⟺n≥logb−aεlog(2)−1

Exemple
On considère la fonction f(x)=exp(x)+3x−2 sur l'intervalle [0,1]. Le code Matlab suivant trace le graphe de f. {code} 
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');
{code}



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