Algorithme de dichotomie

Exercice 1

Soit \(f\) la fonction définie sur \(\mathbb{R}\) par \(f(x)=x^3-3x^2+5\).

  1. Etudier les variations de \(f\) sur \(\mathbb{R}\).
  2. Dresser le tableau de variation complet de \(f\) en justifiant les calculs de limites aux bornes.
  3. Justifier que l'équation \((\text{E}_{1}) \, : \, f(x)=0\) possède une unique solution \(\alpha\) dans \([-2;-1]\) et que c'est m^eme l'unique solution de l'équation \((\text{E}_{1})\) dans \(\mathbb{R}\).
  4. Appliquer à la main l'algorithme de dichotomie (voir Annexe 1) avec les valeurs initiales \(a=-2\) et \(b=-1\) pour déterminer un encadrement de \(\alpha\) d'amplitude \(0,1\). On complétera le tableau en Annexe 2.Combien d'étapes sont nécessaires ? Pouvait-on le prévoir ?
  5. Télécharger le fichier Dichotomie14Eleve.alg sur mon site et compléter l'algorithme de Dichotomie pour cette fonction avec Algobox.
  6. Tester cet algorithme en partant de \(a=-2\) et \(b=-1\) pour obtenir un encadrement de \(\alpha\) d'amplitude \(0,001\).
  7. Compléter l'algorithme pour qu'il affiche en sortie le nombre d'étapes nécessaires.
  8. Justifier que l'équation \((\text{E}_{2}) \, : \,f(x)=10\) possède une unique solution \(\beta\) sur \(]-\infty;+\infty[\) et déterminer le plus grand entier relatif \(n\) tel que \(n<\beta<n+1\). Modifier le programme Dichotomie14Eleve.alg pour qu'il détermine un encadrement de \(\beta\) d'amplitude saisie par l'utilisateur avec la méthode par dichotomie. Enregistrer le nouveau programme sous le nom Dichotomie14Eleve2.alg.

Question 1

In [3]:
from sympy import *
init_printing()
t = symbols('t')
In [32]:
import matplotlib.pyplot as plt
import numpy as np
In [5]:
%matplotlib inline
In [6]:
#expression de f(x)
expf = t**3 - 3*t**2 + 5
expf
Out[6]:
$$t^{3} - 3 t^{2} + 5$$
In [7]:
#expression de f'(x)
expfprim = diff(expf, t)
expfprim
Out[7]:
$$3 t^{2} - 6 t$$
In [8]:
f = lambdify(t, expf,"numpy")
fprim = lambdify(t, expfprim,"numpy")
In [9]:
#tracé des  courbes  de f et f'
xmin, xmax, ymin, ymax = -3, 1, -20, 20
plt.axis([xmin, xmax, ymin, ymax])
x = np.linspace(xmin, xmax, 1001)
y = f(x)
z = fprim(x)
plt.axhline(color='blue')
plt.axvline(color='blue')
plt.grid(True)
plt.plot(x, y, linestyle='-', linewidth=2, color='red', label=r'$y=f(x)')
plt.plot(x, z, linestyle='-', linewidth=1, color='green', label=r"$y=f'(x)")
plt.legend(loc='upper left')
         
Out[9]:
<matplotlib.legend.Legend at 0xae11470c>

Question 2

In [10]:
#limite de f en +oo
limit(expf, t, + oo)
Out[10]:
$$\infty$$
In [11]:
#limite de f en -oo
limit(expf, t, -oo)
Out[11]:
$$-\infty$$

Question 3

In [12]:
#f(-2)
expf.evalf(subs={t:-2})
Out[12]:
$$-15.0$$
In [13]:
#f(-1)
expf.evalf(subs={t:-1})
Out[13]:
$$1.0$$

D'après un corollaire du théorème des valeurs intermédiaires, l'équation \(f(x)=0\) possède donc une unique solution \(\alpha\) dans l'intervalle \([-2;-1]\)

Question 4

In [14]:
#fonctions dichotomies en Python
def dicho(f,a,b,e):
    """valeur approchée à e près de la solution de f(x)=0
    sur [a,b]. On admet que l'utilisateur saisit des paramètres
    où la dichotomie peut s'appliquer. Construit une figure 
    à chaque étape"""
    etape = 0 #nombre d'étapes
    if f(a) <= f(b):
        #croissant ou du moins passage de - à +
        croissant = True
    else:
        croissant = False
    while b-a > e:
        etape += 1
        #on calcule le milieu du segment [a,b]
        m = (a+b)/2
        #figure
        x = np.linspace(a,b,500)
        y = f(x)
        plt.xlim(a,b)
        if croissant:
            plt.ylim(max(f(a),-50),min(f(b),50))
        else:
            plt.ylim(max(f(b),-50),min(f(a),50))
        plt.plot(x,y,color='red')
        plt.grid(True)
        plt.axhline()
        plt.title('a=%.4f et m=%.4f et b=%.4f'%(a,m,b))
        plt.show()
        #fin de la figure
        s = f(m)*f(a)
        #si f(m) et f(a) sont de meme signe, f(x)=0 dans ]m,b[
        if s > 0:
            a = m
        #si f(m) et f(a) sont de signes opposés, f(x)=0 dans ]a,m[
        else:
            b = m       
    return a, b, etape

def dicho_tab(f,a,b,e):
    """valeur approchée à e près de la solution de f(x)=0
    sur [a,b]. On admet que l'utilisateur saisit des paramètres
    où la dichotomie peut s'appliquer. 
    Ne retourne rien mais remplit un tableau avec les valeurs
    de a, b et m aux differentes etapes"""
    count = 0 #nombre d'étapes
    if f(a) <= f(b):
        #croissant ou du moins passage de - à +
        croissant = True
    else:
        croissant = False
    #en-tete du tableau
    print('|{etape:^16}|{binf:^12}|{bsup:^12}|{median:^12}|{signe:^12}|'.format(etape='Etape',
                                                                     binf='a', bsup='b', median='m',
                                                                     signe='f(a)*f(m)'))
    while b-a > e:
        count += 1
        #on calcule le milieu du segment [a,b]
        m = (a+b)/2        
        #fin de la figure
        s = f(m)*f(a)
        #si f(m) et f(a) sont de meme signe, f(x)=0 dans ]m,b[
        #remplissage de la ligne du tableau
        print('|{etape:^16}|{binf:^12.6f}|{bsup:^12.6f}|{median:^12.6f}|{signe:^+12.6f}|'.format(etape=count,
                                                                     binf=a, bsup=b,
                                                                     median=m, signe=s))
        if s > 0:
            a = m
        #si f(m) et f(a) sont de signes opposés, f(x)=0 dans ]a,m[
        else:
            b = m
    print('|{etape:^16}|{binf:^12.6f}|{bsup:^12.6f}|{median:^12}|{signe:^12}|'.format(etape='Sortie de boucle',
                                                                     binf=a, bsup=b,
                                                                     median="", signe=""))
    

Ci-dessous, la correction du tableau de l'Annexe 2

In [15]:
dicho_tab(f, -2, -1, 0.1)
|     Etape      |     a      |     b      |     m      | f(a)*f(m)  |
|       1        | -2.000000  | -1.000000  | -1.500000  | +76.875000 |
|       2        | -1.500000  | -1.000000  | -1.250000  | +8.408203  |
|       3        | -1.250000  | -1.000000  | -1.125000  | +0.362091  |
|       4        | -1.125000  | -1.000000  | -1.062500  | -0.091331  |
|Sortie de boucle| -1.125000  | -1.062500  |            |            |

Ci-dessous la même chose mais avec les graphiques

In [16]:
#application de l'algorithme de dichotomie à f(x)=x**2-3*x**2+5
#avec a = -2 , b = -1 et precision = 0.1
dicho(f, -2, -1, 0.1)
Out[16]:
$$\begin{pmatrix}-1.125, & -1.0625, & 4\end{pmatrix}$$
In [17]:
1/2**3, 1/2**4
Out[17]:
$$\begin{pmatrix}0.125, & 0.0625\end{pmatrix}$$

L'intervalle de départ a pour amplitude 1 (\(a_0=-2\) et \(b_0=-1\)) A chaque étape l'amplitude de l'intervalle de recherche est divisée par 2 Au bout de \(n\) étapes, l'amplitude de la zone de recherche est de \(\frac{b_{0}-a_{0}}{2^n}\) soit \(\frac{1}{2^n}\) ici. Avec la calculatrice (voir ci-dessu ou le logarithme népérien) on peut vérifier que le plus petit entier \(n\) tel que \(\frac{1}{2^n} \leqslant 0,1\) est \(n=4\)

Question 5

Pour voir (et tester) le corrigé de la version Algobox de Dichotomie14eleve.alg, cliquer sur ce lien qui renvoie vers mon site internet (tous les algorithmes et ce corrigé sont disponibles sur la page algorithme).

Question 6

Ci-dessous, le tableau puis les graphiques de l'algorithme de dichotomie pour \(a=-2\), \(b=-1\) et precision=\(0,001\)

In [18]:
dicho_tab(f, -2, -1, 0.001)
|     Etape      |     a      |     b      |     m      | f(a)*f(m)  |
|       1        | -2.000000  | -1.000000  | -1.500000  | +76.875000 |
|       2        | -1.500000  | -1.000000  | -1.250000  | +8.408203  |
|       3        | -1.250000  | -1.000000  | -1.125000  | +0.362091  |
|       4        | -1.125000  | -1.000000  | -1.062500  | -0.091331  |
|       5        | -1.125000  | -1.062500  | -1.093750  | -0.022664  |
|       6        | -1.125000  | -1.093750  | -1.109375  | +0.012682  |
|       7        | -1.109375  | -1.093750  | -1.101562  | -0.001322  |
|       8        | -1.109375  | -1.101562  | -1.105469  | +0.000985  |
|       9        | -1.105469  | -1.101562  | -1.103516  | -0.000051  |
|       10       | -1.105469  | -1.103516  | -1.104492  | +0.000121  |
|Sortie de boucle| -1.104492  | -1.103516  |            |            |

In [19]:
#application de l'algorithme de dichotomie à f(x)=x**2-3*x**2+5
#avec a = -2 , b = -1 et precision = 0.001
print(dicho(f, -2, -1, 0.001))
(-1.1044921875, -1.103515625, 10)

In [20]:
1/2**9, 1/2**10
Out[20]:
$$\begin{pmatrix}0.001953125, & 0.0009765625\end{pmatrix}$$

L'intervalle de départ a pour amplitude 1 (\(a_0=-2\) et \(b_0=-1\)) A chaque étape l'amplitude de l'intervalle de recherche est divisée par 2 Au bout de \(n\) étapes, l'amplitude de la zone de recherche est de \(\frac{b_{0}-a_{0}}{2^n}\) soit \(\frac{1}{2^n}\) ici. Avec la calculatrice (voir ci-dessu ou le logarithme népérien) on peut vérifier que le plus petit entier \(n\) tel que \(\frac{1}{2^n} \leqslant 0,001\) est \(n=10\)

Question 8

In [21]:
#tracé de la  courbe  de f et des droites d'équation y=10, et x=3 et x=4
xmin, xmax, ymin, ymax = 0, 10, -20, 20
plt.axis([xmin, xmax, ymin, ymax])
x = np.linspace(xmin, xmax, 1001)
y = f(x)
plt.axhline(color='blue')
plt.axvline(color='blue')
plt.axvline(3, linestyle='dashed', color='navy', label=r'$x=3$')
plt.axvline(4, linestyle='dashed', color='navy', label=r'$x=4$')
plt.axhline(10, linestyle='dashed',color='green',label=r'$y=10$')
plt.grid(True)
plt.plot(x, y, linestyle='-', linewidth=2, color='red', label=r'$y=f(x)$')
plt.legend(loc='lower right')
Out[21]:
<matplotlib.legend.Legend at 0xadf0f12c>

On peut conjecturer graphiquement que l'équation \(f(x)=10\) possède une unique solution \(\beta\) telle que \(3<\beta<3+1\)

Pour le justifier, il suffit de faire le tableau de variation de \(f\) sur \(\mathbb{R}\).

Sa fonction dérivée est \(f':x \mapsto 3x(x-2)\) donc on a :

Ainsi \(f\) admet deux extrema locaux en \(f(0)=5\) et \(f(2)=1\) et pour tout \(x \geqslant 2\) on a \(f(x)<10\) donc l'équation \(f(x)=10\) n'a pas de solution sur \(]-\infty;2[\).

On se place désormais sur \(]2;+\infty[\) :

D'après un corollaire du théorème des valeurs intermédiaires, l'équation \(f(x)=10\) possède donc une unique solution \(\beta\) dans l'intervalle \(]2;+\infty[\)

Enfin on a \(f(3)<10\) et \(f(4)>10\) donc \(\beta \in ]3;4[\).

Pour voir (et tester) le corrigé de la version Algobox de Dichotomie14eleve2.alg, cliquer sur ce lien qui renvoie vers mon site internet (tous les algorithmes et ce corrigé sont disponibles sur la page algorithme).

Exercice 2

In [22]:
#expression de g(x)
expg = Rational(1,2)*(t**2 - 6*t - 10/t)
expg
Out[22]:
$$\frac{t^{2}}{2} - 3 t - \frac{5}{t}$$
In [23]:
#expression de g'(x)
expgprim = diff(expg, t)
expgprim
Out[23]:
$$t - 3 + \frac{5}{t^{2}}$$
In [24]:
#on factorise
expgprim = expgprim.factor()
expgprim
Out[24]:
$$\frac{1}{t^{2}} \left(t^{3} - 3 t^{2} + 5\right)$$
In [25]:
t**2*expgprim
Out[25]:
$$t^{3} - 3 t^{2} + 5$$
In [26]:
expf
Out[26]:
$$t^{3} - 3 t^{2} + 5$$
In [27]:
t**2*expgprim == expf
Out[27]:
True

On a \(g'(x)=\frac{f(x)}{x^2}\), donc \(g'(x)\) est du signe de \(f(x)\) sur \(\mathbb{R}-\{0\}\).

Grace au tableau de variation de \(f\) étable précédemment, on peut écrire que :

In [28]:
g = lambdify(t, expg,"numpy")
In [29]:
#tracé de la  courbe  de g
xmin, xmax, ymin, ymax = -3, 10, -20, 20
plt.axis([xmin, xmax, ymin, ymax])
x = np.linspace(xmin, xmax, 1001)
y = g(x)
plt.axhline(color='blue')
plt.axvline(color='blue')
plt.grid(True)
plt.plot(x, y, linestyle='-', linewidth=2, color='red', label=r'$y=g(x)$')
plt.legend(loc='lower right')
Out[29]:
<matplotlib.legend.Legend at 0xadef506c>
In [30]:
import scipy.optimize
In [31]:
#valeur approchée de g(x)=0 avec la fonction bisect de la bibliothèque scipy.optimize
#qui en fait implémente l'algorithme de dichotomie
#pour la méthode par balayage voir les explications données en classe par le professeur
#en général on utilise le mode tableau de valeurs de sa calculatrice en reprérant les 2 valeurs
#encadrant le changement de signe puis en recommençant la tabulation entre ces 2 valeurs avec un pas
#plus petit (divisé par 10 par exemple)
scipy.optimize.bisect(g, 6, 7)
Out[31]:
$$6.255546254870751$$

Suites récurrentes

Exercice 3

Pour voir (et tester) le corrigé de l'algorithme de l'exercice 3, cliquer sur ce lien qui renvoie vers mon site internet (tous les algorithmes et ce corrigé sont disponibles sur la page algorithme).

Exercice 4

Pour voir (et tester) le corrigé de l'algorithme de l'exercice 4, cliquer sur ce lien qui renvoie vers mon site internet (tous les algorithmes et ce corrigé sont disponibles sur la page algorithme).