Aller au contenu principal
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »

Recherche numérique de zéros de fonctions

Dans ce document on introduit une méthode permettant d’évaluer numériquement une solution de l’équation f(x)=0f (x) = 0, avec ff une fonction de R\mathbb{R} dans R\mathbb{R} (lorsque la solution existe, bien sur) : la méthode de dichotomie.

  • La méthode de dichotomie est efficace et converge relativement vite. De plus, les conditions de son utilisation sont assez simples : la fonction ff doit seulement être continue et changer de signe sur l’intervalle choisi ;
  • La méthode de Newton converge étonnement vite ! Les conditions de son utilisation sont cependant plus contraignantes : la fonction ff doit être dérivable.

Méthode de la dichotomie

Le raisonnement à mettre en œuvre s’appuie sur le théorème des valeurs intermédiaires.

Théorème des valeurs intermédiaires

Soit f:[a,b]→Rf: [a,b] \to \mathbb{R} une fonction continue sur un segment. Si f(a)⋅f(b)⩽0f(a) \cdot f(b) \leqslant 0, alors il existe ℓ∈[a,b]\ell \in [a, b] tel que f(ℓ)=0f(\ell)=0.

Principe de résolution du problème

Info
  1. On choisit un intervalle [a,b][a, b] dans lequel on pense que la fonction ff s’annule une seule fois (il peut donc être nécessaire de limiter la largeur de cet intervalle).

  2. Étape 1. On détermine les coordonnées du point milieu de l’intervalle : a+b2\dfrac{a + b}{2}

    • Si f(a)⋅f(a+b2)⩽0f(a) \cdot f \left( \dfrac{a + b}{2} \right) \leqslant 0, le théorème des valeurs intermédiaires permet de conclure qu’il existe un point c∈[a,a+b2]c \in \left[a, \dfrac{a + b}{2} \right] tel que f(c)=0f(c) = 0.
    • Si f(a)⋅f(a+b2)⩾0f(a) \cdot f \left( \dfrac{a + b}{2} \right) \geqslant 0, le théorème des valeurs intermédiaires permet de conclure qu’il existe un point c∈[a+b2,b]c \in \left[ \dfrac{a + b}{2}, b \right] tel que f(c)=0f(c) = 0. On est donc parvenu, à l’issu de cette étape, à définir un intervalle dans lequel f(x)=0f(x) = 0, de longueur moitié par rapport à l’intervalle initial.
  3. Étape suivante. On répète le processus mis en œuvre dans l’Étape 1 pour l’intervalle [a,a+b2]\left[a, \dfrac{a + b}{2} \right] ou [a+b2,b]\left[ \dfrac{a + b}{2}, b \right].

  4. Étapes suivantes. On continue à répéter le processus jusqu’à ce que l’intervalle soit de longueur inférieure à une longueur choisie (arbitrairement).

La méthode converge-t-elle réellement ?

  1. On construit deux suites (an)(a_n) et (bn)(b_n) qui évoluent comme les bornes de l’intervalle, et la suite (xn)(x_n), zéro de ff pour chaque intervalle.

    • Au rang 0. On pose a0=aa_0 = a, b0=bb_0 = b. Comme f(a)⋅f(b)⩽0f (a) \cdot f (b) \leqslant 0, il existe une solution, notée x0x_0, de l’équation f(x)=0f (x) = 0 dans l’intervalle [a0,b0][a_0, b_0].

    • Au rang 1. Si f(a0)⋅f(a0+b02)⩽0f (a_0) \cdot f \left( \dfrac{a_0 + b_0}{2} \right) \leqslant 0, alors on pose a1=a0a_1 = a_0 et b1=a0+b02b_1 = \dfrac{a_0 + b_0}{2}, sinon on pose a1=a0+b02a_1 = \dfrac{a_0 + b_0}{2} et b1=b0b_1 = b_0. Comme f(a1)⋅f(b1)⩽0f (a_1) \cdot f (b_1) \leqslant 0, il existe une solution, notée x1x_1, de l’équation f(x)=0f (x) = 0 dans l’intervalle [a1,b1][a_1, b_1].

    • Au rang nn. On suppose construit un intervalle [an,bn][a_n, b_n], de longueur bn−an2n\dfrac{b_n - a_n}{2^n}, contenant une solution xnx_n de l’équation f(x)=0f (x) = 0. Si f(an)⋅f(an+bn2)⩽0f (a_n) \cdot f \left( \dfrac{a_n + b_n}{2} \right) \leqslant 0, alors on pose an+1=ana_{n + 1} = a_n et bn+1=an+bn2b_{n + 1} = \dfrac{a_n + b_n}{2}, sinon on pose an+1=an+bn2a_{n + 1} = \dfrac{a_n + b_n}{2} et bn+1=bnb_{n + 1} = b_n. Comme f(an+1)⋅f(bn+1)⩽0f (a_{n + 1}) \cdot f (b_{n + 1}) \leqslant 0, il existe une solution, notée xn+1x_{n + 1}, de l’équation f(x)=0f (x) = 0 dans l’intervalle [an+1,bn+1][a_{n + 1}, b_{n + 1}].

  2. Étude des suites construites Par construction : - an⩽xn⩽bna_n \leqslant x_n \leqslant b_n - (an)(a_n) est une suite croissante, (bn)(b_n) une suite décroissante. La limite de (bn−an)(b_n - a_n) tend donc vers 0 lorsque nn tend vers +∞+ \infty :

    lim⁡(bn−an)→n→+∞0\lim (b_n - a_n) \xrightarrow [n \rightarrow + \infty]{} 0

    Les suites (an)(a_n) et (bn)(b_n) sont adjacentes. Elles admettent donc une même limite, ℓ\ell.

    Par application du théorème des gendarmes, on peut aussi en conclure que

    lim⁡(xn)→n→+∞ ℓ\lim (x_n) \xrightarrow[n \rightarrow + \infty] \ \ell

    et, comme ff est une fonction continue,

    f(ℓ)=lim⁡n→+∞f(xn)=lim⁡n→+∞0=0f (\ell) = \lim_{n \rightarrow + \infty} f (x_n) = \lim_{n \rightarrow + \infty} 0 = 0

    En conclusion, les suites (an)(a_n) et (bn)(b_n) tendent vers la valeur ℓ\ell, solution de f(x)=0f (x) = 0.

Remarque

En pratique, on arrête le processus dès que bn−an=b−a2nb_n - a_n = \dfrac{b - a}{2^n} est inférieur à la précision souhaitée.

Exemple : Approximation de 10\sqrt{10}

  • On définit la fonction ff définie par f(x)=x2−10f (x) = x^2 - 10. ff est une fonction continue sur R\mathbb{R} qui s’annule en 10\sqrt{10} et −10-\sqrt{10}.

  • On limite l’étude à l’intervalle [3;4][3 ; 4] puisque : f(3)=32−10=−1<0f (3) = 3^2 - 10 = - 1 < 0 et f(4)=42−10=6>0f (4) = 4^2 - 10 = 6 > 0 entraîne 10∈[3;4]\sqrt{10} \in [3 ; 4].

  • On écrit le processus itératif :

    • On pose a0=3a_0 = 3 et b0=4b_0 = 4. f(a0)⩽0f (a_0) \leqslant 0 et f(b0)⩾0f (b_0) \geqslant 0. a0+b02=3,5\dfrac{a_0 + b_0}{2} = \pu{3,5} donc f(a0+b02)=f(3,5)=3,52−10=2,25⩾0f \left( \dfrac{a_0 + b_0}{2} \right) = f (\pu{3,5}) = \pu{3,5}^2 - 10 = \pu{2,25} \geqslant 0. f(a0)⋅f(a0+b02)⩽0f (a_0) \cdot f \left( \dfrac{a_0 + b_0}{2} \right) \leqslant 0, on en déduit que 10\sqrt{10} est dans l’intervalle [3;3,5][3 ; \pu{3,5}].

    • On pose a1=3a_1 = 3 et b1=3,5b_1 = \text{3,5}. a1+b12=3,25\dfrac{a_1 + b_1}{2} = \pu{3,25} donc f(a1+b12)=f(3,25)=0,5625⩾0f \left( \dfrac{a_1 + b_1}{2} \right) = f (\pu{3,25}) = \pu{0,5625} \geqslant 0. f(a1)⋅f(a1+b12)⩽0f (a_1) \cdot f \left( \dfrac{a_1 + b_1}{2} \right) \leqslant 0, on en déduit que 10\sqrt{10} est dans l’intervalle [3;3,25][3 ; \pu{3,25}].

    • On pose a2=3a_2 = 3 et b2=3,25b_2 = \pu{3,25}. a2+b22=3,125\dfrac{a_2 + b_2}{2} = \pu{3,125} donc f(a2+b22)=f(3,125)=−0,23  ⋅  ⋅  ⋅ ⩽0f \left( \dfrac{a_2 + b_2}{2} \right) = f (\pu{3,125}) = - \pu{0,23...} \leqslant 0. f(b2)⩾0f (b_2) \geqslant 0, ff s’annule sur l’intervalle [3,125;3,25][\text{3,125} ; \pu{3,25}].

      À ce stade, on a donc démontré que : 3,125⩽10⩽3,25\pu{3,125} \leqslant \sqrt{10} \leqslant \pu{3,25}.

Avec quelques étapes de plus, on obtient :

a0=3a_0=3 b0=4b_0=4
a1=3a_1=3 b1=3,5b_1=\pu{3,5}
a2=3a_2=3 b2=3,25b_2=\pu{3,25}
a3=3,125a_3=\pu{3,125} b3=3,25b_3=\pu{3,25}
a4=3,125a_4=\pu{3,125} b4=3,1875b_4=\pu{3,1875}
a5=3,15625a_5=\pu{3,15625} b5=3,1875b_5=\pu{3,1875}
a6=3,15625a_6=\pu{3,15625} b6=3,171875b_6=\pu{3,171875}
a7=3,15625a_7=\pu{3,15625} b7=3,164062b_7=\pu{3,164062}
a8=3,16015a_8=\pu{3,16015} b8=3,164062b_8=\pu{3,164062}

En 8 étapes, on obtient donc l’encadrement :

3,160⩽10⩽3,165\pu{3,160} \leqslant \sqrt{10} \leqslant \pu{3,165}

ce qui donne les deux premières décimales du résultat.

Nombre d’itérations nécessaires pour atteindre un résultat

La longueur de l’intervalle [an,bn][a_n, b_n] est b−a2n\dfrac{b - a}{2^n} puisqu’il a été nécessaire de découper nn fois l’intervalle de départ en deux pour parvenir à cet intervalle.

On peut alors rechercher le nombre d’itérations nécessaires pour atteindre une précision choisie lors de la phase préliminaire de l’étude ; il suffit de rechercher le nombre nn tel que b−a2n⩽10−N\dfrac{b - a}{2^n} \leqslant 10^{- N} :

(b−a)10N⩽2n(b - a) 10^N \leqslant 2^nlog⁡(b−a)+log⁡(10N)⩽log⁡(2n)\log (b - a) + \log (10^N) \leqslant \log (2^n)log⁡(b−a)+N⩽nlog⁡(2)\log (b - a) + N \leqslant n \log (2)n⩾log⁡(b−a)+Nlog⁡(2)n \geqslant \dfrac{\log (b - a) + N}{\log (2)}

Exemple. log⁡(2)≃0,3  ⟺  1log⁡(2)=3,3\log (2) \simeq \pu{0,3} \iff \dfrac{1}{\log (2)} = \pu{3,3} donc si log⁡(b−a)⩽1\log (b - a) \leqslant 1, une précision de :

  • 10−1010^{- 10} (∼\thicksim 10 décimales) nécessite 34 itérations ;

  • 10−10010^{- 100} (∼\thicksim 100 décimales) nécessite 333 itérations ;

  • 10−100010^{- 1000} (∼\thicksim 1000 décimales) nécessite 3322 itérations.

Ajouter une décimale nécessite donc 3 ou 4 itérations supplémentaires.

Implémentation en Python de l’algorithme

L’objectif de cette partie pratique est de mettre en œuvre la méthode de dichotomie en Python pour rechercher la racine carré de 10.

Utiliser un algorithme itératif puis un algorithme récursif.

Corrigé